search

hylo-lang / Lotsawa

A Swift implementation of the MARPA algorithms
Apache License 2.0
18 stars 2 forks source link

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

Open dabrahams opened 2 years ago

dabrahams commented 2 years ago

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 commented 2 years ago

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.