Parsing & Error Recovery
vaibhav kumar
03711502716
Error Recovery
• What should happen when your parser finds an
error in the user’s input?
– stop immediately and signal an error
– record the error but try to continue
• In the first case, the user must recompile from
scratch after possibly a trivial fix
• In the second case, the user might be
overwhelmed by a whole series of error
messages, all caused by essentially the same
problem
• We will talk about how to do error recovery in a
principled way
Error Recovery
• Error recovery:
– process of adjusting input stream so that the parser can continue
after unexpected input
• Possible adjustments:
– delete tokens
– insert tokens
– substitute tokens
• Classes of recovery:
– local recovery: adjust input at the point where error was
detected (and also possibly immediately after)
– global recovery: adjust input before point where error was
detected.
• Error recovery is possible in both top-down and
bottom-up parsers
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| LPAR exp RPAR ()
• general strategy for both bottom-up and top-down:
• look for a synchronizing token
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| LPAR exp RPAR ()
• general strategy for both bottom-up and top-down:
• look for a synchronizing token
• accomplished in bottom-up parsers by adding error rules to grammar:
exp : LPAR error RPAR ()
exps : exp ()
| error ; exp ()
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| LPAR exp RPAR ()
• general strategy for both bottom-up and top-down:
• look for a synchronizing token
• accomplished in bottom-up parsers by adding error rules to grammar:
exp : LPAR error RPAR ()
exps : exp ()
| error ; exp ()
• in general, follow error with a synchronizing token. Recovery steps:
• Pop stack (if necessary) until a state is reached in which the
action for the error token is shift
• Shift the error token
• Discard input symbols (if necessary) until a state is reached that has
a non-error action
• Resume normal parsing
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| ( exp ) ()
exp : ( error ) ()
exps : exp ()
| error ; exp ()
yet to read
input: NUM PLUS ( NUM PLUS @#$ PLUS NUM ) PLUS NUM
stack: exp PLUS ( exp PLUS
@#$ is an unexpected token!
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| ( exp ) ()
exp : ( error ) ()
exps : exp ()
| error ; exp ()
yet to read
input: NUM PLUS ( NUM PLUS @#$ PLUS NUM ) PLUS NUM
stack: exp PLUS (
pop stack until shifting “error” can result in correct parse
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| ( exp ) ()
exp : ( error ) ()
exps : exp ()
| error ; exp ()
yet to read
input: NUM PLUS ( NUM PLUS @#$ PLUS NUM ) PLUS NUM
stack: exp PLUS ( error
shift “error”
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| ( exp ) ()
exp : ( error ) ()
exps : exp ()
| error ; exp ()
yet to read
input: NUM PLUS ( NUM PLUS @#$ PLUS NUM ) PLUS NUM
stack: exp PLUS ( error
discard input until we can legally
shift or reduce
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| ( exp ) ()
exp : ( error ) ()
exps : exp ()
| error ; exp ()
yet to read
input: NUM PLUS ( NUM PLUS @#$ PLUS NUM ) PLUS NUM
stack: exp PLUS ( error )
SHIFT )
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| ( exp ) ()
exp : ( error ) ()
exps : exp ()
| error ; exp ()
yet to read
input: NUM PLUS ( NUM PLUS @#$ PLUS NUM ) PLUS NUM
stack: exp PLUS exp
REDUCE using exp ::= ( error )
Local Bottom-up Error Recovery
exp : NUM () exps : exp ()
| exp PLUS exp () | exps ; exp ()
| ( exp ) ()
exp : ( error ) ()
exps : exp ()
| error ; exp ()
yet to read
input: NUM PLUS ( NUM PLUS @#$ PLUS NUM ) PLUS NUM
stack: exp PLUS exp
continue parsing...
