Shift Reduce Example (shown in class)

Parsing:

id:alpha op:= id:beta op:+ id:gamma op:* int:4

Using production rules:

 Assign -> id = Sum
    Sum -> Sum + Product
    Sum -> Product
Product -> Product * Value
Product -> Value
  Value -> int
  Value -> id
Step Parser State Parser Action
0 | id:alpha op:= id:beta op:+ id:gamma op:* int:4 END Shift
1 id:alpha | op:= id:beta op:+ id:gamma op:* int:4 END Shift
2 id:alpha op:= | id:beta op:+ id:gamma op:* int:4 END Shift
3 id:alpha op:= id:beta | op:+ id:gamma op:* int:4 END Reduce by Value -> id
4 id:alpha op:= Value | op:+ id:gamma op:* int:4 END Reduce by Product -> Value
5 id:alpha op:= Product | op:+ id:gamma op:* int:4 END Reduce by Product -> Sum
6 id:alpha op:= Sum | op:+ id:gamma op:* int:4 END Shift
7 id:alpha op:= Sum op:+ | id:gamma op:* int:4 END Shift
8 id:alpha op:= Sum op:+ id:gamma | op:* int:4 END Reduce by Value -> id
9 id:alpha op:= Sum op:+ Value | op:* int:4 END Reduce by Product -> Value
10 id:alpha op:= Sum op:+ Product | op:* int:4 END Shift
11 id:alpha op:= Sum op:+ Product op:* | int:4 END Shift
12 id:alpha op:= Sum op:+ Product op:* int:4 | END Reduce by Value -> id
13 id:alpha op:= Sum op:+ Product op:* Value | END Reduce by Product -> Product * Value
14 id:alpha op:= Sum op:+ Product | END Reduce by Sum -> Sum + Product
15 id:alpha op:= Sum | END Reduce by Assign -> id = Sum
16 Assign | END Finished, yield Assign