Java Reference
In-Depth Information
1 S
→
V
2
|
W
3 V
→
vAb
4 W
→
wAc
5 A
→ λ
Figure 5.25: An LL(1) grammar.
program. The compiler does not presume to knowor to suggest an appropriate
revision of the faulty program. The purpose of error repair is to analyze the
o
ff
ending input more carefully so that better diagnostics can be issued.
Algorithms for error recovery and error repair can exploit the fact that
LL(1) parsers have the
correct-prefix
property: For each state entered by such
parsers, there is a string of tokens that could result in a successful parse.
Consider the input string
,wheretokenx causes an LL(1) parser to detect
a syntax error. The correct-prefix property means that there is at least one
string
α
x
β
αγ α
x
β
that can be accepted by the parser.
What can a parser do to repair the faulty input? The following options are
possible:
•
Modification of
α
•
Insertion of text
δ
to obtain
αδ
x
β
•
Deletion of x to obtain
αβ
These options are not equally attractive. The correct-prefix property implies
that
is at least a portion of a syntactically correct program. Thus, most error
recovery methods do not modify
α
except in special situations. One notable
case is
scope repair
, where nesting brackets may be inserted or deleted to
match the corresponding brackets in x
α
β
.
Insertion of text must also be done carefully. In particular, error repair
based on insertion must ensure that the repaired string will not continually
grow so that parsing can never be completed. Some languages are
insert
correctable
. For such languages, it is always possible to repair syntactic faults
by insertion. Deletion is a drastic alternative to insertion, but it does have the
advantage of making progress through the input.
