restricted forms of context-free grammars. For example, the while statement in C
can be defined as
Here the keyword while is a terminal symbol. All other terms are variables,
which still have to be defined. If we check this against Definition 5.4, we see
that this looks like an s-grammar production. The variable
on the left is always associated with the terminal
while on the right. For this reason such a statement is easily and efficiently
parsed. We see here a reason why we use keywords in programming languages.
Keywords not only provide some visual structure that can guide the reader of a
program, but also make the work of a compiler much easier.
Unfortunately, not all features of a typical programming language can be
expressed by an s-grammar. The rules for
above are not of this
type, so that parsing becomes less obvious. The question then arises what
grammatical rules we can permit and still parse efficiently. In compilers,
extensive use has been made of what are called LL and LR grammars. These
grammars have the ability to express the less obvious features of a programming
language, yet allow us to parse in linear time. This is not a simple matter, and
much of it is beyond the scope of our discussion. We will briefly touch on this
topic in Chapter 6, but for our purposes it suffices to realize that such grammars
exist and have been widely studied.
In connection with this, the issue of ambiguity takes on added significance.
The specification of a programming language must be unambiguous, otherwise a
program may yield very different results when processed by different compilers
or run on different systems. As Example 5.11 shows, a naive approach can easily
introduce ambiguity in the grammar. To avoid such mistakes we must be able to
recognize and remove ambiguities. A related question is whether a language is or
is not inherently ambiguous. What we need for this purpose are algorithms for
detecting and removing ambiguities in context-free grammars and for deciding
whether or not a context-free language is inherently ambiguous. Unfortunately,
these are very difficult tasks, impossible in the most general sense, as we will see
later.
Those aspects of a programming language that can be modeled by a contextfree grammar are usually referred to as its syntax. However, it is normally the
case that not all programs that are syntactically correct in this sense are in fact
can be defined as
Here the keyword while is a terminal symbol. All other terms are variables,
which still have to be defined. If we check this against Definition 5.4, we see
that this looks like an s-grammar production. The variable
on the left is always associated with the terminal
while on the right. For this reason such a statement is easily and efficiently
parsed. We see here a reason why we use keywords in programming languages.
Keywords not only provide some visual structure that can guide the reader of a
program, but also make the work of a compiler much easier.
Unfortunately, not all features of a typical programming language can be
expressed by an s-grammar. The rules for
above are not of this
type, so that parsing becomes less obvious. The question then arises what
grammatical rules we can permit and still parse efficiently. In compilers,
extensive use has been made of what are called LL and LR grammars. These
grammars have the ability to express the less obvious features of a programming
language, yet allow us to parse in linear time. This is not a simple matter, and
much of it is beyond the scope of our discussion. We will briefly touch on this
topic in Chapter 6, but for our purposes it suffices to realize that such grammars
exist and have been widely studied.
In connection with this, the issue of ambiguity takes on added significance.
The specification of a programming language must be unambiguous, otherwise a
program may yield very different results when processed by different compilers
or run on different systems. As Example 5.11 shows, a naive approach can easily
introduce ambiguity in the grammar. To avoid such mistakes we must be able to
recognize and remove ambiguities. A related question is whether a language is or
is not inherently ambiguous. What we need for this purpose are algorithms for
detecting and removing ambiguities in context-free grammars and for deciding
whether or not a context-free language is inherently ambiguous. Unfortunately,
these are very difficult tasks, impossible in the most general sense, as we will see
later.
Those aspects of a programming language that can be modeled by a contextfree grammar are usually referred to as its syntax. However, it is normally the
case that not all programs that are syntactically correct in this sense are in fact