News for hackers. Stuff that matters.
Re:Want to Write a Compiler? Read These Two Papers (2008) by sklogic on Thursday December 24, 2015 @03:48AM (#10787594)
PEG (Packrat) is hot now.
Re:Want to Write a Compiler? Read These Two Papers (2008) by fanf2 on Friday December 25, 2015 @11:33AM (#10791573)
It is important to distinguish between PEG and packrat.

PEG is a model for recognizers, distinct from traditional grammers whose theoretical model is usually based on generating strings rather than recognising them. (Yes this is a bit backwards.) The most distinctive feature of PEGs is the ordered choice operator - traditional context-free grammars and regexes use unordered choice, but ordered choice is a closer model of how recursive descent parsers work in practice. Ordered choice naturally leads to implementations that have less backtracking than common regex matchers, e.g. Lpeg.

Packrat parsers are based on a clever non-backtracking PEG matching algorithm. They spend O(n) memory to get O(n) parsing time, so they are reliably fast but not good for long inputs. They are also effective in a pure, lazy setting like Haskell.

Lpeg is a PEG parser but not a packrat parser.

Re:Want to Write a Compiler? Read These Two Papers (2008) by nly on Thursday December 24, 2015 @02:22PM (#10789298)
Interesting paper on left-recursion in recursive descent parsers like PEGs and Packrats

http://web.cs.ucla.edu/~todd/research/pub.php?id=pepm08

Re:Want to Write a Compiler? Read These Two Papers (2008) by ltratt on Thursday December 24, 2015 @06:35PM (#10789927)
If you're interested in left-recursion in PEGS then, at the risk of gross immodesty, you may be interested in http://tratt.net/laurie/research/pubs/html/tratt__direct_lef...

With less risk of immodesty you may also find http://arxiv.org/pdf/1207.0443.pdf?ref=driverlayer.com/web interesting.

There's probably more recent work than these two papers, but I'm a little out of date when it comes to the PEG world.

Re:Want to Write a Compiler? Read These Two Papers (2008) by nly on Thursday December 24, 2015 @08:26PM (#10790114)
Thanks, looks like you've put a lot of work in to it and I'll enjoy reading it.
Re:Want to Write a Compiler? Read These Two Papers (2008) by sklogic on Thursday December 24, 2015 @02:35PM (#10789342)
Yes, I implemented exactly this approach. But for the binary expressions I am using Pratt, it is faster and easier to construct left-associative nodes.