You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
It would be useful to be able to validate that a grammar is LR-regular and thus can be parsed in linear time. It would be useful to diagnose the causes of non-LR-regularity.
The text was updated successfully, but these errors were encountered:
Detecting LR-regularity appears not to be a simple question: https://www.sciencedirect.com/science/article/pii/0022000083900260 . Note in the abstract of this article: "The original test for the LR-regular property is not quite correct." So this is something the pros screw up.
Also, Leo proved in his paper that question of linearity for his algorithm is, in the general case, undecidable.
LR(k) is a subclass of LR-regular. There is no test for LR(k) for any k, but there is an algorithm for a specific k. Off the top of my head the test of LR(k)-ness is expensive as k grows large.
It would be useful to be able to validate that a grammar is LR-regular and thus can be parsed in linear time. It would be useful to diagnose the causes of non-LR-regularity.
The text was updated successfully, but these errors were encountered: