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-LR(1)" in what sense "minimal"? #46

Closed modulovalue closed 1 year ago

modulovalue commented 1 year ago

Hey @kjosib,

the readme says:

The "minimal-LR(1)" algorithm used here is -- I believe -- provably minimal,

When you refer to "minimal", can you clarify what kind of minimal you are referring to? That is, do you conjecture your algorithm to be minimal in the #45 sense, where you conjecture that no table compression will be needed once the LR(1) table is constructed, or some other form of minimal?

kjosib commented 1 year ago

Yes, I see your point... It's a bit glib to talk of minimal before I fix correctness which is presently lacking. But to your point: The goal was the smallest number of states such that the resulting parse table does the right thing. So for the grammar in #45 I think 18 states makes sense. while 16 is clearly too few. But I don't know whether the ideas behind the algorithm would achieve 18 rather than 20 even once the present flaw is corrected (which be non-trivial). I'll have to try it and see.

Meanwhile, I'll update the comment in the readme.

modulovalue commented 1 year ago

Thank you for the clarification.