Error Recovery in Parsing

Error detection abilities of LR parsers:

• LR parsers announce an error as soon as there is no valid continuation for the input scanned so far
• A CLR parser never attempts a single reduction before announcing an error
• An SLR or LALR may take several reductions before announcing an error, but they will never shift an erroneous input symbol on to the stack
• In LR parsing, an error is detected when the parser consults the table and finds that the corresponding action entry is empty
• Errors are never detected by consulting goto entries

Error Recovery

An LR parser can use any one of the following two techniques for error recovery:

                Panic mode

                Phrase level

Panic mode recovery:

It involves the following steps

• Scan down the stack until a state ’a’ with goto on a particular non terminal ‘B’ is found (by removing states from the stack)
• Zero or more input symbols are discarded until a symbol ‘b’ is found that can follow ‘B’
• Then the parser stacks the stage goto(s, B) and resumes parsing

Note:

• Generally there can be more choices for ‘B’. Normally non terminals representing major program pieces like expressions or statements or blocks are considered for ‘B’
• This method attempts to isolate the phrase containing syntactic error. This is done by skipping the remaining input of the phrase derivable from ‘B’ after detecting an error in it.

Phrase Level Recovery:

It involves the following steps

• Deciding on programmer errors, basing on the language, that call error routines in the parser table
• Designing appropriate error routines carefully that can modify the top of the stack and/or some symbols on input in a way suitable for error entries in the table

Note:
The modifications done by error routines should not take parser into an infinite loop

Consider the parsing table for the grammar E → E + E | E * E | ( E ) | id

State	Action						Goto
	id	+	*	(	)	$	E
0	s3	e1	e1	s2	e2	e1	1
1	e3	s4	s5	e3	e4	ACC
2	s3	e1	e1	s2	e2	e1	6
3	r4	r4	r4	r4	r4	r4
4	s3	e1	e1	s2	e2	e1	7
5	s3	e1	e1	s2	e2	e1	8
6	e3	s4	s5	e3	s9	E4
7	r1	r1	s5	r1	r1	r1
8	r2	r2	r2	r2	r2	r2
9	r3	r3	r3	r3	r3	r3

Where

e1: /* This routine is called from states 0, 2, 4 and 5 all of which expect the beginning of an operand, either and id or a left parenthesis. Instead an operator, ‘+’, or ‘*’ or the end of the input was found. */ push an imaginary id onto the stack and cover it with state 3 (the goto of states 0, 2, 4 and 5 on id)5

issue diagnostic “missing operand”

e2: /* this routine is called from states 0,1,2, 4 and 5 on finding a right parenthesis. */

remove the right parenthesis from the input

issue diagnostic “unbalanced right parenthesis”

e3: /* this routine is called from states 1 or 6 when expecting an operator, and an id or ritht parenthesis is found. */

push + onto the stack and cover it with state 4

issue diagnostic “missing operator”

e4: /* this routine is called form state 6 when the end of the input is found. State 6 expects an operator or a right parenthesis */

push a right parenthesis onto the stack and cover it with state9

issue diagnostic “missing right parenthesis”

 Now working of parser on id+)$ is as shown

Stack	Input	Error message and Action
0	id + ) $	Action(4, )) = error i.e., “unbalanced right parenthesis” c2 removes right parenthesis “missing operand” e2 pushes id3 on stack
0id3	+ ) $
0E1	+ ) $
0E1 + 4	) $
0E1 +4	$
0E2 + 4id3	$
0E1 +4E7	$
0E1	$

Handling Ambiguous Grammar2

Home

YACC Automatic Parser Generator