9.5 AUTOMATIC ERROR RECOVERY IN YACC


9.4 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 9.1.

Table 9.1: Parsing Table for E E + E E * E id
 

id

+

*

$

E

I

S 2

     

1

I 1

 

S 3

S 4

Accept

 

I 2

 

R 3

R 3

R 3

 

I 3

S 2

     

5

I 4

S 2

     

6

I 5

 

S 3 / R 1

S 4 / R 1

R 1

 

I 6

 

S 3 / R 2

S 4 / R 2

R 2

 

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

Table 9.2: Higher Precedent * and Left-Associativity
 

id

+

*

$

E

I

S 2

     

1

I 1

 

S 3

S 4

Accept

 

I 2

 

R 3

R 3

R 3

 

I 3

S 2

     

5

I 4

S 2

     

6

I 5

 

R 1

S 4

R 1

 

I 6

 

R 2

R 2

R 2

 

The parsing table with error routines is shown in Table 9.3, where routine e 1 is called from states I , I 3 , and I 4 , which pushes an imaginary id onto the stack and covers it with state I 2 . The routine e 2 is called from state I 1 , which pushes + onto stack and covers it with state I 3 .

Table 9.3: Parsing Table with Error Routines
 

id

+

*

$

E

I

S 2

e 1

e 1

e 1

1

I 1

E 2

S 3

S 4

Accept

 

I 2

R 3

R 3

R 3

R 3

 

I 3

S 2

e 1

E 1

E 1

5

I 4

S 2

E 1

E 1

E 1

6

I 5

R 1

R 1

S 4

R 1

 

I 6

R 2

R 2

R 2

R 2

 

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

Stack Contents

Unspent Input

Moves

$ I

id+*id$

shift and enter into state 2

$ I id I 2

+*id$

reduce by production number 3

$ I EI 1

+*id$

shift and enter into state 3

$ I EI 1 + I 3

*id$

call error routine e 1

$ I EI 1 + I 3 id I 2

*id$

reduce by production number 3

(id I 2 pushed by e 1)

   

$ I EI 1 + I 3 EI 5

*id$

shift and enter into state 4

$ I EI 1 + I 3 E I 5 * I 4

id$

shift and enter into state 2

$ I EI 1 + I 3 E I 5 * I 4 id I 2

$

reduce by production number 3

$ I EI 1 + I 3 E I 5 * I 4 EI 6

$

reduce by production number 2

$ I EI 1 + I 3 EI 5

$

reduce by production number 1

$ I EI 1

$

accept

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

Stack Contents

Unspent Input

Moves

$ I

id id*id$

shift and enter into state 2

$ I id I 2

id*id$

reduce by production number 3

$ I EI 1

id*id$

call error routine e 2

$ I EI 1 + I 3

id*id$

shift and enter into state 2

( I 3 pushed by e 2)

   

$ I EI 1 + I 3 id I 2

*id$

reduce by production number 3

$ I EI 1 + I 3 EI 5

*id$

shift and enter into state 4

$ I EI 1 + I 3 EI 5 * I 4

id$

shift and enter into state 2

$ I EI 1 + I 3 EI 5 * I 4 id I 2

$

reduce by production number 3

$ I EI 1 + I 3 EI 5 * I 4 EI 6

$

reduce by production number 2

$ I EI 1 + I 3 EI 5

$

reduce by production number 1

$ I EI 1

$

accept




Algorithms for Compiler Design
Algorithms for Compiler Design (Electrical and Computer Engineering Series)
ISBN: 1584501006
EAN: 2147483647
Year: 2005
Pages: 108
Authors: O G Kakde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net