Compilers: Principles and Practice

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 s ∈ V*, will tell us “Accepted” ...