Java Reference
In-Depth Information
Example. Consider the following grammar.
S ::= A
a
j
b
A ::= S
c
j
d
In step 1, we can enumerate the non-terminals using subscripts to record the numbering:
S
1
and A
2
. This gives us a new set of rules:
S
1
::= A
2
a
j
b
A
2
::= S
1
c
j
d
In the rst iteration of step 2 (i = 1), no rules apply. In the second iteration (i = 1;j = 2),
the rule
A
2
::= S
1
c
applies. We replace it with two rules, expanding S
1
, to yield
S
1
::= A
2
a
j
b
A
2
::= A
2
ac
j
bc
j
d
We then use the transformation (3.26) to produce the grammar
S
1
::= A
2
a
j
b
A
2
::=
bc
A'
2
j
d
A'
2
A'
2
::=
ac
A'
2
A'
2
::=
Or, removing the subscripts,
S ::= A
a
j
b
A ::=
bc
A
0
j
d
A
0
A
0
::=
ac
A
0
A
0
::=
Leftfactoring
Another common property of grammars that violates the LL(1) property is when two
or more rules defining a non-terminal share a common prefix:
Y ::=
Y ::=
The common violates the LL(1) property. But, as long as rst() and rst() are
disjoint, this is easily solved by introducing a new non-terminal:
Search WWH ::
Custom Search