search

kjosib / booze-tools

Booze Tools will become the complete programming-language development workbench, all written in Python 3.9 (for now).
MIT License
14 stars 1 forks source link

Minimal-LR1 bug with certain non-LR(k) grammars (hidden left recursion) #30

Closed kjosib closed 4 years ago

kjosib commented 4 years ago

Consider the grammar:

S -> a | eps S b
eps -> :nothing

This language is actually regular (ab*) but the grammar is not LR(k) for any k. (To see why, ask how many epsilon-productions to recognize before shifting the a.)

This should pose no problem to a generalized parse engine, and indeed it works just fine with the LALR and Canonical-LR1 table generators, but for some reason the tables coming out of minimal-LR1 mode are deficient in this particular scenario: The initial state has the shift on a but that action should really be a shift/reduce conflict.

kjosib commented 4 years ago

This seems to be fixed by a subtle change in how the algorithm behaves around epsilon rules.