issue290.md

Issue 290

What happens in both these grammars is that all of the terminals are removed due to conflict resolution, leaving the non-terminal in a state where it will never actually reduce.

Bison at least recognizes these as useless due to conflict resolution.

Recursive yacc rule

%%
Start: Bar;
Foo: 'a' | ;
Bar: Foo | Foo Bar;

The above image of the bison state graph is actually quite helpful. https://www.gnu.org/software/bison/manual/html_node/Graphviz.html

Interesting:

1. Red diamond's indicating reductions discarded due to conflicts, have discarded all of the non-terminals.
2. Dotted arrows being the arrows of the goto table, containing a loop.

Yacc output:

yacc: 1 rule never reduced
yacc: 2 shift/reduce conflicts, 1 reduce/reduce conflict.

Bison output:

recursive.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
recursive.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
recursive.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
recursive.y:4.6-8: warning: rule useless in parser due to conflicts [-Wother]
    4 | Bar: Foo | Foo Bar;
      |      ^~~

Mutually recursive yacc rule

%%
Start: Bar;
Foo: 'a' | ;
Bar: Foo | Foo Baz;
Baz: Foo | Foo Bar;

Yacc Output:

yacc: 2 rules never reduced <br>
yacc: 3 shift/reduce conflicts, 2 reduce/reduce conflicts.

mutually_recursive.y: warning: 3 shift/reduce conflicts [-Wconflicts-sr]
mutually_recursive.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
mutually_recursive.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
mutually_recursive.y:4.6-8: warning: rule useless in parser due to conflicts [-Wother]
    4 | Bar: Foo | Foo Baz;
      |      ^~~
mutually_recursive.y:5.6-8: warning: rule useless in parser due to conflicts [-Wother]
    5 | Baz: Foo | Foo Bar;
      |      ^~~

Differences of behavior between grmtools & yacc

• Error reporting, currently we don't recognize these rules as being useless merely reporting the conflicts.

  I suppose this means StateGraph should just gain some fields something to the effect of useless: Vec<RIdx>, and useless_rules().

  Doing a recursive walk of the state graph looking for rules without non-terminals, and accounting non-terminals removed by conflicts.

• In addition to reporting the useless rules, bison/yacc appear to omit them from the goto table.

  While bison/yacc appear to omit them, grmtools will keep them in the state table. Upon entering the loop, going into an Accept loop, which never results in a Reduce.

  In StateGraph<StIdx> and StateTable<StIdx>, we currently have a correspondence between the StIdx where the StIdx for a state graph == state table StIdx - 1. Due to the addition of a zero start rule not represented in the state graph.

  Omitting these recursively useless rules from the StateTable's goto table, introduces a data dependency between StateTable StIdx and the subset of useful StGraph StIdx. As such a constant stidx - 1 no longer suffices.

  The relation between state graph and state table index now effectively becomes:
  stidx - 1 + state_graph.useless_rules().filter(less_than(stidx)).len()
  Such it is better to have a precomputed (stidx, sgidx) pair.

  At that point it seems like we would want to introduce different Idx types SgIdx for StateGraph, and StIdx for StateTable.

There are potentially other options for fixing this in ways that wouldn't impact the relation between the StIdxs

1. In addition to a start rule, add a special goto at the end of the goto table, this would serve as a goto for pruned useless functions.
2. Have a mechanism to return from a StateGraph a pruned StateGraph with useless rules discarded.

mutually_recursive.png

recursive.png