5 ms·
It does not make any sense to reimplement yacc in the 21st century. There are far more powerful and yet simple parsing techniques, rendering all that automata s
by sklogic 11y ago
It does not make any sense to reimplement yacc in the 21st century. There are far more powerful and yet simple parsing techniques, rendering all that automata stuff useless and outdated. Take a look at PEG, Pratt parsing and GLR.
- sparkie 11y agoPfft. Who wants to parse in 2015? We all know that constructing your language as a JSON schema is the way forward. Your JSON parser is the only parser you'll ever need.
- ORioN63 11y agoOr a lisp.
- wtetzner 11y agoOr even better, GLL. http://dotat.at/tmp/gll.pdf http://dotat.at/tmp/gll.pdf
- nickpsecurity 11y agoBest features of both types of parsers? Hell yeah! Never even heard of this one despite all the research updates I did a few years ago. Thanks for the link.
- sklogic 11y agoIt's an interesting one, I'll add it to my collection. Although, to be fair, PEG (Packrat) do support left recursion [1], and it can also be combined with Pratt for the binary expressions very efficiently, at O(n). [1] http://www.vpri.org/pdf/tr2007002_packrat.pdf http://www.vpri.org/pdf/tr2007002_packrat.pdf
- wtetzner 11y ago> Although, to be fair, PEG (Packrat) do support left recursion [1] Unfortunately it sometimes generates the wrong parse: http://tratt.net/laurie/research/pubs/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf http://tratt.net/laurie/research/pubs/papers/tratt__direct_l...
- sklogic 11y agoAnd all the edge cases are related to the binary expressions - and you should be using Pratt for them instead. Left recursive PEG must be reserved for things like method, structure field and array access, which are ok with that algorithm.
- wtetzner 11y agoAh, gotcha. I struggled with PEG and left recursion for a while before finding GLL. Do you have any resources on how to combine PEG and Pratt?
- sklogic 11y agoThere must have been some papers on it, but I lost a track. Will try to dig out something. Meanwhile, you can take a look a my implementation of such a mix: https://github.com/combinatorylogic/mbase/tree/master/src/l/lib/parsing https://github.com/combinatorylogic/mbase/tree/master/src/l/... An example of a grammar built on top of it: https://github.com/combinatorylogic/clike/blob/master/clike/clike-parser.hl https://github.com/combinatorylogic/clike/blob/master/clike/... - see the `binary` nodes there, they're translated into Pratt while all the others are Packrat.