| No. I was pretty naive in my initial attempts. I tried for many months to make Laurence Tratt's Algorithm 2 (see https://tratt.net/laurie/research/pubs/html/tratt__direct_le... ) work, but ultimately I failed. I recall running into some problem with my implementation of Tratt's idea that led me to conclude that his Algorithm 2 doesn't work as stated. My reasoning is buried in a git commit message from many months ago - I'd have to go look it up. My takeaway from Tratt's explanation was that the general technique of growing the seed bottom-up style when in left-recursion - I think I've also seen that idea termed "recursive ascent" somewhere else but I can't place it offhand - seemed reasonable, so that's what I kept working on until I figured out something that seemed to work. Later on, I ran across https://github.com/PhilippeSigaud/Pegged/wiki/Left-Recursion, which describes Sergio Medeiros' technique at a high level. One of the nice things I used from the Pegged project was the unit test suite. I re-implemented some of the unit tests from Pegged in my own PEG implementation and discovered that it failed at those unit tests. It took me another number of months to figure out why my implementation failed the unit tests. I re-jiggered my implementation to make it handle the scenarios captured by those unit tests, and then naively thought "hey, it works!"... All was well until I ran across another set of unit tests in the Autumn PEG parser (see https://github.com/norswap/autumn). My implementation failed some of those as well. After another number of months, I had a fix for those too. Long long long story short, this process continued until I couldn't find any more unit tests that my implementation would fail, so once again I'm at the point where I think "well, I think it works". There have been a number of occasions where I've thought "if this doesn't work, I'm just going to re-implement Pegged in Crystal!". Perhaps that's what I should've done. Ha ha! In a few months, when I find another test case that breaks my implementation, I may just do that. We'll see. I hope it doesn't come to that. Fingers crossed. :-) |