A.3 Grammars

A correct specification of a programming language requires:

  1. Specification of a set of symbols, called Terminals;
  2. The set of all syntactically correct programs;
  3. The “meaning” of such programs.

Possible methods in which we can specify a language:

  1. Exhaustive listing of each and every sentence in that language.
  2. Use a Generative method: give rules by which correct sentences can be formed. The set of such rules, which must be finite, is called a Grammar.

    For certain restricted class of languages, known as Regular Languages, a simpler generative method, known as Regular Expression, which is a kind of formula, is generally used (see Section A.4).

  3. Use a machine or Acceptor which, when fed with any string sV*, will tell us “Accepted” ...

Get Compilers: Principles and Practice now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.