Shift-Reduce Parsing Example

N0, N1, N2, N3, ... represent pointers to nodes on the stack,
   but I typed them as N0(BOF), N1(var), etc as a reminder of
   what the nodes contain.
everything else is unprocessed input, yet to be seen.

The reduction rules are

1:
                ... N1(expr) N2(op) N3(expr) N4(op) 
    reduces to  node(N2.op, N1, N2) N4
                                             if priority(N2.op)>=priority(N4.op)

2:
                ... N1(expr) N2(op) N3(expr) N4(term) 
    reduces to  node(N2.op, N1, N3) N4
                                             where term is one of the "obvious" terminators
                                             of expressions, such as ) and ;

3:
                ... N1(expr) = N2(expr) ;
    reduces to  node(assignment, N1, N2)

4:
                ... if N1(expr) N2(stmt)
    reduces to node(ifstatement, N1, N2)

5:
                ... N1(ifstatement) else N2(stmt)
    reduces to node(ifelsestatement, N1, N2)

6:
                ... { N1(stmt) N2(stmt) N3(stmt)... }
    reduces to node(block, N1, N2, N3, ...)

7:
                ... BOF N1(block) EOF
    reduces to N1
                  and halts the parsing process.

8:
                ... ( N1(expr) )
    reduces to
                N1

So here we go...

N0 = node("BOF")   -- beginning of file

   N0(BOF) { x = 12*cat+4; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule matches stop of stack so shift

N1 = node("{")

   N0(BOF) N1({) x = 12*cat+4; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule matches stop of stack so shift

N2 = node("expr", "var", "x")

   N0(BOF) N1({) N2(var) = 12*cat+4; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule matches stop of stack so shift

N3 = node("=")

   N0(BOF) N1({) N2(var) N3(=) 12*cat+4; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule matches stop of stack so shift

N4 = node("expr", "num", "12")

   N0(BOF) N1({) N2(var) N3(=) N4(num) *cat+4; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule matches stop of stack so shift

N5 = node("operator", "*")

   N0(BOF) N1({) N2(var) N3(=) N4(num) N5(*) cat+4; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule matches stop of stack so shift

N6 = node("expr", "var", "cat")

   N0(BOF) N1({) N2(var) N3(=) N4(num) N5(*) N6(var) +4; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule matches stop of stack so shift

N7 = node("operator", "+")

   N0(BOF) N1({) N2(var) N3(=) N4(num) N5(*) N6(var) N7(+) 4; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

At last a rule matches:

                ... expr1 op2 expr3 op4 
    reduces to  node(op2, expr1, expr2) op4
                                             if priority(op2)>=priority(op4)

so a reduction

N8 = node("expr", "*", N4(num), N6(var))

   N0(BOF) N1({) N2(var) N3(=) N8(*) N7(+) 4; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule matches stop of stack so shift

N9 = node("expr", "num", "4")

   N0(BOF) N1({) N2(var) N3(=) N8(*) N7(+) N9(num) ; if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule matches stop of stack so shift

N10 = node(";")

   N0(BOF) N1({) N2(var) N3(=) N8(expr) N7(+) N9(num) N10(;) if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

A rule matches:

                ... expr1 op2 expr3 term 
    reduces to  node(op2, expr1, expr2) term
                                             where term is one of the "obvious" terminators
                                             of expressions, such as ) and ;

N11 = node("expr", "+", N8(expr), N9(num))

   N0(BOF) N1({) N2(var) N3(=) N11(expr) N10(;) if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

A rule matches:

                ... var = expr ;
    reduces to  node(assignment, var, expr)

N12 = node("stmt", "assignment", N2(var), N11(expr))

   N0(BOF) N1({) N12(assig) if (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule so shift

   N0(BOF) N1({) N12(assig) N13(if) (x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule so shift

   N0(BOF) N1({) N12(assig) N13(if) N14(() x<100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule so shift

   N0(BOF) N1({) N12(assig) N13(if) N14(() N15(var) <100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule so shift

   N0(BOF) N1({) N12(assig) N13(if) N14(() N15(var) N16(<) 100) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule so shift

   N0(BOF) N1({) N12(assig) N13(if) N14(() N15(var) N16(<) N17(num) ) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

no rule so shift

   N0(BOF) N1({) N12(assig) N13(if) N14(() N15(var) N16(<) N17(num) N18()) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

A rule matches:

                ... expr1 op2 expr3 term 
    reduces to  node(op2, expr1, expr2) term
                                             where term is one of the "obvious" terminators
                                             of expressions, such as ) and ;

N19 = node("expr", "<", N15(var), N17(num))

   N0(BOF) N1({) N12(assig) N13(if) N14(() N19(expr) N18()) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

a rule matches:

                ... ( N1(expr) )
    reduces to
                N1

   N0(BOF) N1({) N12(assig) N13(if) N19(expr) { y = 9+y*15; x = x-1; } cat = 15*cat+y*72 } EOF

And on and on and on it goes....