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

Tainting doesn't need to consider shift reduce conflicts? #49

Closed modulovalue closed 7 months ago

modulovalue commented 10 months ago

Quote from: https://github.com/mdaines/grammophone/issues/26#issuecomment-1776780227

In his dissertation on LR parsing (page 94, first bullet, third paragraph), Xin Chen claims that it is widely known that only reduce/reduce conflicts can be resolved by state splitting and not shift/reduce conflicts. [...]

If that is true, then it seems like there might be a source of inefficiency in the "tainting" LR(1) implementation:

Consider:

https://github.com/kjosib/booze-tools/blob/987cd90d040cc6eba2d46cebd85db0c091cc8692/boozetools/parsing/lr1.py#L210-L217

Shouldn't it then suffice to only consider states that have reduce/reduce conflicts? That is, if state.has_reduce_reduce_conflict(): instead of if state.has_conflict():?

modulovalue commented 7 months ago

I'm closing this as stale.

kjosib commented 7 months ago

It sounds like a good point. A shift-reduce conflict would not seem to be resolvable by the act of splitting states. However, if I make that change, then various tests fail. Have a look at this example and the tests that use it.