Java Reference
In-Depth Information
Algorithm 3.5 Construct an LL(1) Parse Table for a Grammar G = (N;T;S;P)
Input: a context-free grammar G = (N;T;S;P)
Output: LL(1) Parse Table for G
for each non-terminal Y 2 G do
for each rule Y ::= X
1
X
2
:::X
n
2 P with number i do
for each terminal a 2 rst(X
1
X
2
:::X
n
) fg do
table[Y;a] i
if rst(X
1
X
2
:::X
n
) contains then
for each terminal a (or
#
) in follow(Y ) do
table[Y;a] i
end for
end if
end for
end for
end for
Example. Let as construct the parse table for (3.21). For the non-terminal E, we consider
rule 1: E ::= TE
0
. rst(TE
0
) = f
(
,
id
g. So,
table[E,
(
] = 1
table[E,
id
] = 1
Because rst(TE
0
) does not contain , we need not consider follow(E).
For the non-terminal E
0
, we first consider rule 2: E
0
::=
+
TE
0
; rst(
+
T E
0
) = f
+
g so
table[E
0
,
+
] = 2
Rule 3: E
0
::= is applicable for symbols in follow(E
0
) = f
)
,
#
g, so
table[E
0
,
)
] = 3
table[E
0
,
#
] = 3
For the non-terminal T, we consider rule 4: T ::= FT
0
. rst(F T
0
) = f
(
,
id
g, so
table[T,
(
] = 4
table[T,
id
] = 4
Because rst(F T
0
) does not contain , we need not consider follow(T).
For non-terminal T
0
, we first consider rule: 5: T
0
::=
*
FT
0
; rst(
*
F T
0
), so
table[T
0
,
*
] = 5
Rule 6: T
0
::= is applicable for symbols in follow(T
0
) = f
+
,
)
,
#
g, so
table[T
0
,
+
] = 6
table[T
0
,
)
] = 6
table[T
0
,
#
] = 6
Search WWH ::
Custom Search