LL Grammars with e-rules: Definition
Definition: Let G = (N, T, P, S) be a CFG. G is an LL grammar if for every a Î T and every A Î N there is no more than one A-rule A ® X1X2...Xn Î P such that a Î Predict(A ® X1X2...Xn)
Illustration:
a Î Predict(A ® X1X2...Xn)
Ruled out in an LL grammar
a Î Predict(A ® Y1Y2...Ym)
Rule r1:
A ® X1X2...Xn
X1
X2
Xn
…
Rule r2:
A ® Y1Y2...Ym
Y1
Y2
Ym
…
a
A
 x
S
 y
a
A
 x
S
 y
40/57