Error Recovery in Predictive Parsing

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

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.