Algorithms for Compiler Design: PREDICTIVE PARSING ERROR RECOVERY

An error is detected during predictive parsing when the terminal on the top of the stack does not match the next input symbol, or when nonterminal A is on top of the stack and a is the next input symbol. M[A,a] is the error entry used to for recovery. Panic mode recovery can be used to recover from an error detected by the LL parser. The effectiveness of panic mode recovery depends on the choice of the synchronizing token. Several heuristics can be used when selecting the synchronizing token in order to ensure quick recovery from common errors:

1. All the symbols in the FOLLOW(A) must be kept in the set of synchronizing tokens, because if we skip until an a symbol in FOLLOW(A) is read, and we pop A from the stack, it is likely that the parsing can continue.

2. Since the syntactic structure of a language is very often hierarchical, we add the symbols that begin higher constructs to the synchronizing set of lower constructs. For example, we add keywords to the synchronizing sets of nonterminals that generate expressions.

3. We also add the symbols in FIRST(A) to the synchronizing set of nonterminal A. This provides for a resumption of parsing according to A if a symbol in FIRST(A) appears in the input.

4. A derivation by an ∈-production can be used as a default. Error detection will be postponed, but the error will still be captured. This method reduces the number of nonterminals that must be considered during error recovery.

Note�

Another method of error recovery that can be implemented is called "phrase level recovery". In phrase level recovery, each error entry in the LL parsing table is examined, and based on language usage, an appropriate error-recovery procedure is constructed. For example, to recover from a construct error that starts with an operator, the error-recovery routine will insert an imaginary id into the input. Then, if some state terminal symbols are derived using an ∈-production, the error entries in that state are replaced by the derivation using the imaginary-id ∈-production. This has the effect of postponing error detection.

A phrase level error-recovery implementation for an LR parser is shown in Tables 1 and 2. The parsing table is constructed for the following grammar:

Table 1: LR Parsing Table

�	id	+	*	$
E	E → TE1	�	�	�
T	T → FT1	�	�	�
F	F → id	�	�	�
E1	�	E1→ +TE1	�	E1→ ∈
T1	�	T1 → ∈	T1 → * FT1	T1 → ∈
id	pop	�	�	�
+	�	pop	�	�
*	�	�	pop	�
$	�	�	�	accept

The modified table is shown in Table 2. Routine e₁, when called, pushes an imaginary id into the input; and routine e₂, when called, removes all the remaining symbols from the input.

Table 2: Phrase Level Error-Recovery Implementation

�	id	+	*	$
E	E → TE1	e1	e1	e1
T	T → FT1	e1	e1	e1
�	F → id	e1	e1	e1
E1	E1→ ∈	E1→ +TE1	E1→ ∈	E1→ ∈
T1	T1→ ∈	T1→ ∈	T1 → *FT1	T1→ ∈
id	pop	�	�	�
+	�	pop	�	�
*	�	�	pop	�
$	e2	e2	e2	accept

For example, if we trace the behavior of the parser shown in Table 2 for the input id + *id $:

Stack Contents	Unspent Input	Moves
$E	id+*id$	derive using E →TE1
$E1T	id+*id$	derive using T →FT1
$E1T1F	id+*id$	derive using F → id
$E1T1id	id+*id$	pop
$E1T1	+*id$	derive using T1→ ∈
$E1	+*id$	derive using E1→ +TE1
$E1T+	+*id$	pop
$E1T	*id$	call error routine e1
$E1T	id*id$	derive using T → FT1
(imaginary id is pushed by e1)
$E1T1F	id*id$	derive using F → id
$E1T1id	id*id$	pop
$E1T1	*id$	derive using T1 → *FT1
$E1T1F	id$	derive using F → id
$E1T1id	id$	pop
$E1T1	$	derive using T1 → ∈
$E1	$	derive using E1 → ∈
$	$	accept

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

Stack Contents	Unspent Input	Moves
$E	id id*id$	derive using E → TE1
$E1T	id+*id$	derive using T → FT1
$E1T1F	id+*id$	derive using F → id
$E1T1id	id+*id$	pop
$E1T1	id*id$	derive using T1→ ∈
$E1	id*id$	derive using E1→ ∈
$	id*id$	call error routine e2
(id*id$ is removed by e2)
$	$	accept