Assignment 10

The CFG would be:

S -> S + T | S - T | T
T ->  T * number  |  T / number  | number

Where number is [0-9] +

Proof this is LR (1): The LR (1) parsing table (generated by the LR1Parser in folder Parser Library) is as below with no SR or RR conflict.

A parsing of number * number + number - number / number is:

The attribute grammar will be:

E’ -> E {E’.res = E.res} 
E -> E + T {E.res =E.res + T.res} 
E -> E - T {E.res = E.res - E’.res} 
E -> T {E.res = T.res}
T -> T / number {T.res = T.res - number} 
T -> T * number {T.res = T.res - number} 
T -> number {T.res = number} 

Example: 3 + 9 – 2 (We'll do a left recursive derivation)

E’ -> E -> E - T -> E + T – T -> T + T – T -> number + T – T -> number – number – T -> number +number -number

Now, if we walk the attribute grammar backwards, we get that all the T + T – T get T.res = number (last rule), which then propagates to E + T – T {E.res = T.res (3)}, the E – T {E.res = E.res + T.res (12)}, then E {E.res = E.res -T.res (10)} and finally, E' {E'.res = E.res (10)}, so we get 10

Note: For YACC implementation, I have used simply S -> S + S | S – S | S * S | S / S | number, as associativity/precedence can be handled by YACC.