Java Reference
In-Depth Information
These are defined as one would expect. Method mustBe() , defined as follows, makes use
of a boolean flag, isRecovered , which is true if either no error has been detected or if the
parser has recovered from a previous syntax error. It takes on the value false when it is in
a state in which it has not yet recovered from a syntax error.
booleanisRecovered=true;
privatevoidmustBe(TokenKindsought){
if(scanner.token().kind()==sought){
scanner.next();
isRecovered=true;
}elseif(isRecovered){
isRecovered=false;
reportParserError("%sfoundwhere%ssought",scanner
.token().image(),sought.image());
}else{
//Donotreportthe(possiblyspurious)error,
//butratherattempttorecoverbyforcingamatch.
while(!see(sought)&&!see(EOF)){
scanner.next();
}
if(see(sought)){
scanner.next();
isRecovered=true;
}
}
}
When mustBe() first comes across an input token that it is not looking for (it is in the
recovered state), it reports an error and goes into an unrecovered state. If, in a subsequent
use of mustBe() , it finds another syntax error, it does not report the error, but rather it
attempts to get back into a recovered state by repeatedly scanning tokens until it comes
across the one it is seeking. If it succeeds in finding that token, it goes back into a recovered
state. It may not succeed but instead scan to the end of the file; in this case, parsing stops.
Admittedly, this is a very na ve error recovery scheme, but it works amazingly well for its
simplicity 5 .
3.3.2 LL(1) Parsing
The recursive invocation of methods in the recursive descent parsing technique depends on
the underlying program stack for keeping track of the recursive calls. The LL(1) parsing
technique makes this stack explicit. The first L in its name indicates a left-to-right scan
of the input token stream; the second L signifies that it produces a left parse, which is a
left-most derivation. The (1) indicates we just look ahead at the next 1 symbol in the input
to make a decision.
Like recursive descent, the LL(1) technique is top-down, goal oriented, and predictive.
LL(1) Parsing Algorithm
An LL(1) parser works in typical top-down fashion. At the start, the start symbol is pushed
onto the stack, as the initial goal. Depending on the first token in the input stream of
tokens to be parsed, the start symbol is replaced on the stack by a sequence of symbols
from the right-hand side of a rule defining the start symbol. Parsing continues by parsing
each symbol as it is removed from the top of the stack:
5 It reminds us of the story of the dancing dog: one does not ask how well the dog dances but is amazed
that he dances at all.
 
Search WWH ::




Custom Search