252 J;! Theory of Computer Science
7.4.1 TOP-DOWN PARSING
In this section we present certain techniques for top-down parsing which can
be applied to a certain subclass of context-free languages. We illustrate them
by means of some examples. We discuss LL(l) parsing, LL(k) parsing, left
factOling and the technique to remove left recursion.
EXAMPLE 7.10
Let G = ({S, A, B}, {a, b}, P, S) where P consists of S ~ aAB, S ~ bBA,
A ~ bS, A ~ a, B ~ as, B ~ b. w = abbbab is in L(G) . Let us try to
get a leftmost derivation of w. When we start with S we have two choices:
S ~ aAB and S ~ bBA. By looking at the first symbol of w, we see that
S ~ bBA will not yield w. So we choose S ~ aAB as the production to be
applied in step 1 and we get S => aAB. Now consider the leftmost variable
A in the sentential form aAB. We have to apply an A-production among the
productions A ~ bS and A ~ a. A ~ a will not yield IV subsequently since
the second symbol in IV is b. So, we choose A ~ bS and get S => aAB =>
abSB. Also, the substring ab of w is a substring of the sentential form abSB.
By looking ahead for one symbol, namely the symbol b, we decide to apply
S ~ bBA in the third step. This leads to S => aAB =>abSB => abbBAB. The
leftmost variable in the sentential form abbBAB is B. By looking ahead for
one symbol which is b. we apply the B-production B ~ b in the fourth step.
On similar considerations, we apply A ~ a and B ~ b in the last two steps
to get the leftmost derivation.
S => aAB => abSB => abbBAB => abbbAB => abbbaB => abbbab
Thus in the case of the given grammar. we are able to construct a leftmost
derivation of IV by looking ahead for one symbol in the input string. In order
to do top-down parsing for a general string in L(G). we prepare a table called
the parsing table. The table provides the production to be applied for a given
variable with a particular look ahead for one symbol.
For convenience, we denote the productions S ~ aAB, S ~ bBA, A ~
bS, A ~ a, B ~ as and B ~ b by PI' P~ . .. " P 6 . Let E denote an error.
It indicates that the given input string is not in L(G). The table for the given
grammar is given in Table 7.1.
TABLE 7.1 Parsing Table for Example 7.10
S
A
B
A
E
E
E
a
b
For example. if A. is the leftmost variable in a sentential form and the first
symbol in unprocessed substring of the given input string is b, then we have to
apply P3'
7.4.1 TOP-DOWN PARSING
In this section we present certain techniques for top-down parsing which can
be applied to a certain subclass of context-free languages. We illustrate them
by means of some examples. We discuss LL(l) parsing, LL(k) parsing, left
factOling and the technique to remove left recursion.
EXAMPLE 7.10
Let G = ({S, A, B}, {a, b}, P, S) where P consists of S ~ aAB, S ~ bBA,
A ~ bS, A ~ a, B ~ as, B ~ b. w = abbbab is in L(G) . Let us try to
get a leftmost derivation of w. When we start with S we have two choices:
S ~ aAB and S ~ bBA. By looking at the first symbol of w, we see that
S ~ bBA will not yield w. So we choose S ~ aAB as the production to be
applied in step 1 and we get S => aAB. Now consider the leftmost variable
A in the sentential form aAB. We have to apply an A-production among the
productions A ~ bS and A ~ a. A ~ a will not yield IV subsequently since
the second symbol in IV is b. So, we choose A ~ bS and get S => aAB =>
abSB. Also, the substring ab of w is a substring of the sentential form abSB.
By looking ahead for one symbol, namely the symbol b, we decide to apply
S ~ bBA in the third step. This leads to S => aAB =>abSB => abbBAB. The
leftmost variable in the sentential form abbBAB is B. By looking ahead for
one symbol which is b. we apply the B-production B ~ b in the fourth step.
On similar considerations, we apply A ~ a and B ~ b in the last two steps
to get the leftmost derivation.
S => aAB => abSB => abbBAB => abbbAB => abbbaB => abbbab
Thus in the case of the given grammar. we are able to construct a leftmost
derivation of IV by looking ahead for one symbol in the input string. In order
to do top-down parsing for a general string in L(G). we prepare a table called
the parsing table. The table provides the production to be applied for a given
variable with a particular look ahead for one symbol.
For convenience, we denote the productions S ~ aAB, S ~ bBA, A ~
bS, A ~ a, B ~ as and B ~ b by PI' P~ . .. " P 6 . Let E denote an error.
It indicates that the given input string is not in L(G). The table for the given
grammar is given in Table 7.1.
TABLE 7.1 Parsing Table for Example 7.10
S
A
B
A
E
E
E
a
b
For example. if A. is the leftmost variable in a sentential form and the first
symbol in unprocessed substring of the given input string is b, then we have to
apply P3'