20. Prove the following result. Let G = (V, T, S, P) be a context-free grammar in
which every A ∈ V occurs on the left side of at most one production. Then G
is unambiguous.
21. Find a grammar equivalent to that in Example 5.5 that satisfies the
conditions of Theorem 5.2.
5.3 Context-Free Grammars and Programming
Languages
One of the most important uses of the theory of formal languages is in the
definition of programming languages and in the construction of interpreters and
compilers for them. The basic problem here is to define a programming language
precisely and to use this definition as the starting point for the writing of
efficient and reliable translation programs. Both regular and context-free
languages are important in achieving this. As we have seen, regular languages
are used in the recognition of certain simple patterns that occur in programming
languages, but as we argue in the introduction to this chapter, we need contextfree languages to model more complicated aspects.
As with most other languages, we can define a programming language by a
grammar. It is traditional in writing on programming languages to use a
convention for specifying grammars called the Backus-Naur form or BNF. This
form is in essence the same as the notation we have used here, but the
appearance is different. In BNF, variables are enclosed in triangular brackets.
Terminal symbols are written without any special marking. BNF also uses
subsidiary symbols such as |, much in the way we have done. Thus, the grammar
in Example 5.12 might appear in BNF as
and so on. The symbols + and * are terminals. The symbol | is used as an
alternator as in our notation, but ::= is used instead of →. BNF descriptions of
programming languages tend to use more explicit variable identifiers to make
the intent of the production explicit. But otherwise there are no significant
differences between the two notations.
Many parts of C-like programming languages are susceptible to definition by
which every A ∈ V occurs on the left side of at most one production. Then G
is unambiguous.
21. Find a grammar equivalent to that in Example 5.5 that satisfies the
conditions of Theorem 5.2.
5.3 Context-Free Grammars and Programming
Languages
One of the most important uses of the theory of formal languages is in the
definition of programming languages and in the construction of interpreters and
compilers for them. The basic problem here is to define a programming language
precisely and to use this definition as the starting point for the writing of
efficient and reliable translation programs. Both regular and context-free
languages are important in achieving this. As we have seen, regular languages
are used in the recognition of certain simple patterns that occur in programming
languages, but as we argue in the introduction to this chapter, we need contextfree languages to model more complicated aspects.
As with most other languages, we can define a programming language by a
grammar. It is traditional in writing on programming languages to use a
convention for specifying grammars called the Backus-Naur form or BNF. This
form is in essence the same as the notation we have used here, but the
appearance is different. In BNF, variables are enclosed in triangular brackets.
Terminal symbols are written without any special marking. BNF also uses
subsidiary symbols such as |, much in the way we have done. Thus, the grammar
in Example 5.12 might appear in BNF as
and so on. The symbols + and * are terminals. The symbol | is used as an
alternator as in our notation, but ::= is used instead of →. BNF descriptions of
programming languages tend to use more explicit variable identifiers to make
the intent of the production explicit. But otherwise there are no significant
differences between the two notations.
Many parts of C-like programming languages are susceptible to definition by