Java Reference
In-Depth Information
1 S
→
[E]
2
|
(E)
3 E
→
a
procedure
S(
ts
,
termset
)
switch
()
case
ts
.
peek()∈{[}
call
match
([)
call
E(
ts
,
termset
∪{
]
}
)
18
(])
case
ts
.
peek()∈{(}
call
call
match
match
(()
call
E(
ts
,
termset
∪{
)
}
)
19
call
match
())
end
procedure
E(
ts
,
termset
)
if
ts
.
peek()= a
then call
match
(
ts
,
a)
else
call
(Expectedana)
while
ts
.
peek()
termset
do call
ts
.
advance()
error
end
Figure 5.26: A grammar and its Wirth-style, error-recovering parser.
found. Because end-of-input can follow S,every
termset
includes $. In the
worst case, the input program is advanced until $, at which point all pending
parsing procedures can exit.
Summary
This concludes our study of LL parsers. Given an LL(1) gram-
mar, we have studied how to construct recursive-descent or table-driven LL(1)
parsers. Grammars that are not LL(1) can often be converted to LL(1) form
by eliminating left recursion and by factoring common prefixes. Some pro-
gramming language constructs are inherently non-LL(1). Intervention by the
compiler writer can often resolve the conflicts that arise in such cases. Al-
ternatively, more powerful parsing methods can be considered, such as those
presented in Chapter 6.
