important in the study of compilers, but somewhat peripheral to our interests. We
will provide only a brief introduction to some important results, referring the
reader to books on compilers for a more thorough treatment.
Suppose we are parsing top-down, attempting to find the leftmost derivation
of a particular sentence. For the sake of discussion, we use the approach
illustrated in Figure 7.5. We scan the input w from left to right, while developing
a sentential form whose terminal prefix matches the prefix of ω up to the
currently scanned symbol. To proceed in matching consecutive symbols, we
would like to know exactly which production rule is to be applied at each step.
This would avoid backtracking and give us an efficient parser. The question then
is whether there are grammars that allow us to do this. For a general context-free
grammar, this is not the case, but if the form of the grammar is restricted, we can
achieve our goal.
As first case, take the s-grammars introduced in Definition 5.4. From the
discussion there, it is clear that at every stage in the parsing we know exactly
which production has to be applied. Suppose that w = w 1 w 2 and that we have
developed the sentential form w 1 A x . Toget the next symbol of the sentential form
matched against the next symbol in w, we simply look at the leftmost symbol of
w 2 , say a. If there is no rule A → ay in the grammar, the string w does not belong
to the language. If there is such a rule, the parsing can proceed. But in this case
there is only one such rule, so there is no choice to be made.
Although s-grammars are useful, they are too restrictive to capture all aspects
of the syntax of programming languages. We need to generalize the idea so that
it becomes more powerful without losing its essential property for parsing. One
type of grammar is called an LL grammar. In an LL grammar we still have the
property that we can, by looking at a limited part of the input (consisting of the
scanned symbol plus a finite number of symbols following it), predict exactly
which production rule must be used. The term LL is standard usage in books on
compilers; the first L stands for the fact that the input is scanned from left to
right; the second L indicates that leftmost derivations are constructed. Every sgrammar is an LL grammar, but the concept is more general.
Figure 7.5
will provide only a brief introduction to some important results, referring the
reader to books on compilers for a more thorough treatment.
Suppose we are parsing top-down, attempting to find the leftmost derivation
of a particular sentence. For the sake of discussion, we use the approach
illustrated in Figure 7.5. We scan the input w from left to right, while developing
a sentential form whose terminal prefix matches the prefix of ω up to the
currently scanned symbol. To proceed in matching consecutive symbols, we
would like to know exactly which production rule is to be applied at each step.
This would avoid backtracking and give us an efficient parser. The question then
is whether there are grammars that allow us to do this. For a general context-free
grammar, this is not the case, but if the form of the grammar is restricted, we can
achieve our goal.
As first case, take the s-grammars introduced in Definition 5.4. From the
discussion there, it is clear that at every stage in the parsing we know exactly
which production has to be applied. Suppose that w = w 1 w 2 and that we have
developed the sentential form w 1 A x . Toget the next symbol of the sentential form
matched against the next symbol in w, we simply look at the leftmost symbol of
w 2 , say a. If there is no rule A → ay in the grammar, the string w does not belong
to the language. If there is such a rule, the parsing can proceed. But in this case
there is only one such rule, so there is no choice to be made.
Although s-grammars are useful, they are too restrictive to capture all aspects
of the syntax of programming languages. We need to generalize the idea so that
it becomes more powerful without losing its essential property for parsing. One
type of grammar is called an LL grammar. In an LL grammar we still have the
property that we can, by looking at a limited part of the input (consisting of the
scanned symbol plus a finite number of symbols following it), predict exactly
which production rule must be used. The term LL is standard usage in books on
compilers; the first L stands for the fact that the input is scanned from left to
right; the second L indicates that leftmost derivations are constructed. Every sgrammar is an LL grammar, but the concept is more general.
Figure 7.5