9.7 RECOVERY FROM SEMANTIC ERRORS

9.6 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 9.4 and 9.5. The parsing table is constructed for the following grammar:

Table 9.4: LR Parsing Table

	id	+	*	$
E	E ’ TE 1
T	T ’ FT 1
F	F ’ id
E 1		E 1 ’ + TE 1		E 1 ’ ˆˆ
T 1		T 1 ’ ˆˆ	T 1 ’ * FT 1	T 1 ’ ˆˆ
id	pop
+		pop
*			pop
$				accept

The modified table is shown in Table 9.5. 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 9.5: Phrase Level Error-Recovery Implementation

	id	+	*	$
E	E ’ TE 1	e 1	e 1	e 1
T	T ’ FT 1	e 1	e 1	e 1
	F ’ id	e 1	e 1	e 1
E 1	E 1 ’ ˆˆ	E 1 ’ + TE 1	E 1 ’ ˆˆ	E 1 ’ ˆˆ
T 1	T 1 ’ ˆˆ	T 1 ’ ˆˆ	T 1 ’ * FT 1	T 1 ’ ˆˆ
id	pop
+		pop
*			pop
$	e 2	e 2	e 2	accept

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

Stack Contents	Unspent Input	Moves
$ E	id+*id$	derive using E ’ TE 1
$ E 1 T	id+*id$	derive using T ’ FT 1
$ E 1 T 1 F	id+*id$	derive using F ’ id
$ E 1 T 1 id	id+*id$	pop
$ E 1 T 1	+*id$	derive using T 1 ’ ˆˆ
$ E 1	+*id$	derive using E 1 ’ + TE 1
$ E 1 T +	+*id$	pop
$ E 1 T	*id$	call error routine e 1
$ E 1 T	id*id$	derive using T ’ FT 1
(imaginary id is pushed by e 1 )
$ E 1 T 1 F	id*id$	derive using F ’ id
$ E 1 T 1 id	id*id$	pop
$ E 1 T 1	*id$	derive using T 1 ’ * FT 1
$ E 1 T 1 F	id$	derive using F ’ id
$ E 1 T 1 id	id$	pop
$ E 1 T 1	$	derive using T 1 ’ ˆˆ
$ E 1	$	derive using E 1 ’ ˆˆ
$	$	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 ’ TE 1
$ E 1 T	id+*id$	derive using T ’ FT 1
$ E 1 T 1 F	id+*id$	derive using F ’ id
$ E 1 T 1 id	id+*id$	pop
$ E 1 T 1	id*id$	derive using T 1 ’ ˆˆ
$ E 1	id*id$	derive using E 1 ’ ˆˆ
$	id*id$	call error routine e 2
(id*id$ is removed by e 2 )
$	$	accept