LL Grammars
without
e
-rules
Definition:
Let
G
= (
N
,
T
,
P
,
S
) be a CFG
without
e
-rules
.
G
is
an
LL
grammar
if for every
a
Î
T
and every
A
Î
N
there is
no more than one
rule
A
®
X
1
X
2
...
X
n
Î
P
such that
a
Î
First
(
X
1
X
2
...
X
n
)
Illustration:
A
X
1
X
2
X
n
…
Rule
r
1
:
A
Y
1
Y
2
Y
m
…
Rule
r
2
:
a
x
1
a
x
2
Table:
...
a
...
...
...
A
a
(
A
,
a
)
a
a
Î
First
(
X
1
X
2
...
X
n
)
a
Î
First
(
Y
1
Y
2
...
Y
m
)
Ruled out in an LL grammar
Only rule
r
1
:
A
®
X
1
X
2
…
X
n
5/57