Error Recovery in Predictive Parsing
An error occurs in predictive parsing when,
The terminal on the top of the stack does not match the
current input symbol or
A non terminal A is on the top of the stack with a as the
current input symbol and the entry M[A, a] is empty
We discuss the error recovery in predictive parsing using the
following two methods:
Panic Mode
Recovery
Phrase Level
Recovery
Panic Mode Recovery
This involves careful selection of synchronizing tokens for each non terminal.
Some points to follow are,
- Place all symbols in FOLLOW(A) into the synchronizing set of A. In this case parser skips symbols until a symbol from FOLLOW(A) is seen. Then A is popped off the stack and parsing continues
- The symbols that begin the higher constructs must be added to the synchronizing set of the lower constructs
- Add FIRST(A) to the synchronizing set of A, so that parsing can continue when a symbol in FIRST(A) is encountered during skipping of symbols
- If some non-terminal derives ε then using it can be used as default
- If a symbol on the top of the stack can't be matched, one method is pop the symbol and issue message saying that the symbol is inserted.
Phrase Level Recovery
This involves, defining the blank entries in the table with pointers to some error routines which may
- Change, delete or insert symbols in the input or
- May also pop symbols from the stack
Whatever may be the action, care should be taken that it should not lead the parser into infinite loop.
Example:
The Grammar:
E → TE'
E' → +TE' |
T → FT'
T' → *FT' |
F → (E)
F → id
FIRST(E) =
FIRST(T) = FIRST(F) = {{, id}
FIRST(E') =
{+, ε}
FIRST(T') =
{*, ε}
FOLLOW(E) =
FOLLOW(E') = {$, )}
FOLLOW(T) =
FOLLOW(T') ={+, $, )}
FOLLOW(F) =
{*, +, $, )}
Predictive Parser table
for given grammar is
Non-Terminal
|
INPUT
SYMBOLS
|
|||||
id
|
+
|
*
|
(
|
)
|
$
|
|
E
|
E→TE’
|
E→TE’
|
||||
E’
|
E’→+TE’
|
E’→ε
|
E’→ε
|
|||
T
|
T→FT’
|
T→FT’
|
||||
T’
|
T’→ε
|
T’→*FT’
|
T’→ε
|
T’→ε
|
||
F
|
F→id
|
F→(E)
|
||||
Parsing and Error Recovery moves made by Predictive Parser
STACK
|
INPUT
|
REMARK
|
$E
$E
$E’T
$E’T’F
$E’T’id
$E’T’
$E’T’F*
$E’T’F
$E’T’
$E’
$E’T+
$E’T
$E’T’F
$E’T’id
$E’T’
$E’
$
|
)id* +id$
id* +id$
id* +id$
id* +id$
id* +id$
*+id$
*+id$
+id$
+id$
+id$
+id$
id$
id$
id$
$
$
$
|
Error, skip )
id is in FIRST(E)
Error,M[F, +] = synch
F has been popped
|
