Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add a function to test a claim of LR-Regularity #5

Open
dabrahams opened this issue Jun 17, 2022 · 1 comment
Open

Add a function to test a claim of LR-Regularity #5

dabrahams opened this issue Jun 17, 2022 · 1 comment

Comments

@dabrahams
Copy link
Collaborator

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.

@jeffreykegler
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants