shift_reduce_parser_notes.txt

d -> [0-9]
n -> d d*
g -> '(' Alter(g, n) ')'
sum -> op '+' op
op -> Alter(n, g, sum)

op -> n;
   -> g -> (n)
        -> (g) -> ((n))
	       -> ((g)) -> ...
   -> sum -> op -> ...
             +
	     op -> ...

5+(10+5)

#d sum g d d sum d g

#d -> Alter(n, g, sum) -> Alter(n, Alter(g, n), Alter(op, op))

#n sum g n sum n g


---
tok       s
5+(10+5)  5     s
+(10+5)   d     r
+(10+5)   n     r
+(10+5)   op    r
(10+5)    op+   s
10+5)     op+(  s
...
          op+(10+5)
check:
  i=0: no handle
  i=1: +: op'+'op != op'+''('
  i=2: (: '('n')' != '(''1''0'
          '('g')' != '(''1''0'
  i=3: d: - ok
  continue or start over

reverse type tree:
d -> n
n -> g, sum, op

term -> get its type
nterm -> get type tree and iterate


Reduce:
op'+'op:
  op'+'[op] - no
  op['+'op]: <handle:sum><nterm:op> -> same types on the reverse tree -> only <sum>. Parse sum - fail
  [op'+'op]: check <sum> - ok, return sum

Implementing reduce operation:

n := stack.len()
// iterate over each window:
for i := n:
    window := stack.slice(n-i, n)
    // iterate over operators
    for j := window.len():
        // get the related type of each element
        types := [x.type() for x in window]
        // find the related rule definition for each type
        // [[def_a, def_b], [def_b, def_d, def_e], [def_b]]
        rule_defs := reverse_rule_tree.get(types)

        // find pairwise set intersections of the definitions
        common_defs := rule_defs[0]
        for k := range(1, rule_defs.len()):
            common_defs = intersection(common_defs, rule_defs[k])

        // iterate over common definitions
        for match := common_defs:
            if descend_batch(types, match):
                // replace the window with the matched NTerm
                stack.replace(window, match.nterm())
                return true
return false