Algorithms for Compiler Design: ERROR RECOVERY IN LR PARSING

A systematic method for error recovery in LR parsing is to scan down the stack until a state S with a goto on a particular nonterminal A is found, and then discard zero or more input symbols until a symbol a is found that can legitimately follow A. The parser then shifts the state goto [S, A] on the stack and resumes normal parsing.

There might be more than one choice for the nonterminal A. Normally, these would be nonterminals representing major program pieces, such as statements.

Another method of error recovery that can be implemented is called "phrase level recovery". Each error entry in the LR parsing table is examined, and, based on language usage, an appropriate error-recovery procedure is constructed. For example, to recover from an construct error that starts with an operator, the error-recovery routine will push an imaginary id onto the stack and cover it with the appropriate state. While doing this, the error entries in a particular state that call for a particular reduction on some input symbols are replaced by that reduction. This has the effect of postponing the error detection until one or more reductions are made; but the error will still be caught before a shift.

A phrase level error-recovery implementation for an LR parser is shown below. The parsing table's grammar is:

The SLR parsing table for the above grammar is shown in Table 1.

Table 1: Parsing Table for E → E + E | E * E | id

�	id	+	*	$	E
I0	S2	�	�	�	1
I1	�	S3	S4	Accept	�
I2	�	R3	R3	R3	�
I3	S2	�	�	�	5
I4	S2	�	�	�	6
I5	�	S3/R1	S4/R1	R1	�
I6	�	S3/R2	S4/R2	R2	�

The conflict is resolved by giving higher precedence to * and using leftassociativity, as shown in Table 2.

Table 2: Higher Precedent * and Left-Associativity

�	id	+	*	$	E
I0	S2	�	�	�	1
I1	�	S3	S4	Accept	�
I2	�	R3	R3	R3	�
I3	S2	�	�	�	5
I4	S2	�	�	�	6
I5	�	R1	S4	R1	�
I6	�	R2	R2	R2	�

The parsing table with error routines is shown in Table 3, where routine e₁ is called from states I₀, I₃, and I₄, which pushes an imaginary id onto the stack and covers it with state I₂. The routine e₂ is called from state I₁, which pushes + onto stack and covers it with state I₃.

Table 3: Parsing Table with Error Routines

�	id	+	*	$	E
I0	S2	e1	e1	e1	1
I1	E2	S3	S4	Accept	�
I2	R3	R3	R3	R3	�
I3	S2	e1	E1	E1	5
I4	S2	E1	E1	E1	6
I5	R1	R1	S4	R1	�
I6	R2	R2	R2	R2	�

For example, if we trace the behavior of the parser described above for the input id + *id $:

Stack Contents	Unspent Input	Moves
$I0	id+*id$	shift and enter into state 2
$I0idI2	+*id$	reduce by production number 3
$I0EI1	+*id$	shift and enter into state 3
$I0EI1+I3	*id$	call error routine e1
$I0EI1+I3id I2	*id$	reduce by production number 3
(id I2 pushed by e1)	�	�
$I0EI1+I3EI5	*id$	shift and enter into state 4
$I0EI1+I3E I5*I4	id$	shift and enter into state 2
$I0EI1+I3E I5*I4idI2	$	reduce by production number 3
$I0EI1+I3E I5*I4EI6	$	reduce by production number 2
$I0EI1+I3EI5	$	reduce by production number 1
$I0EI1	$	accept

Similarly, if we trace the behavior of the parser for the input id id*id $:

Stack Contents	Unspent Input	Moves
$I0	id id*id$	shift and enter into state 2
$I0idI2	id*id$	reduce by production number 3
$I0EI1	id*id$	call error routine e2
$I0EI1+ I3	id*id$	shift and enter into state 2
(I3 pushed by e2)	�	�
$I0EI1+I3id I2	*id$	reduce by production number 3
$I0EI1+I3EI5	*id$	shift and enter into state 4
$I0EI1+I3EI5*I4	id$	shift and enter into state 2
$I0EI1+I3EI5*I4idI2	$	reduce by production number 3
$I0EI1+I3EI5*I4EI6	$	reduce by production number 2
$I0EI1+I3EI5	$	reduce by production number 1
$I0EI1	$	accept