A correct specification of a programming language requires:
- Specification of a set of symbols, called Terminals;
- The set of all syntactically correct programs;
- The “meaning” of such programs.
Possible methods in which we can specify a language:
- Exhaustive listing of each and every sentence in that language.
- 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).
- Use a machine or Acceptor which, when fed with any string s ∈ V*, will tell us “Accepted” ...