4 ms·

Traditional shift/reduce parsers are impractical to write without a specialised tool and often difficult to debug, PEG parsers and parser-combinators are great

Traditional shift/reduce parsers are impractical to write without a specialised tool and often difficult to debug, PEG parsers and parser-combinators are great to work with but are often inefficient and produce unhelpful syntax errors. If there's some other parsing scheme that could be a best-of-both-worlds, I would love to learn more.

amelius 11y ago
This one uses the shift/reduce approach but can be applied to any context free grammer, efficiently: [1] [1] http://scottmcpeak.com/elkhound/ http://scottmcpeak.com/elkhound/
spacebat 11y ago
I believe that the Marpa parser may be what you're looking for. A C library with the most refined API in Perl5, improvements are in the works to make it easier to produce interfaces to the library in other languages. https://jeffreykegler.github.io/Marpa-web-site/ https://jeffreykegler.github.io/Marpa-web-site/ http://savage.net.au/Marpa.html http://savage.net.au/Marpa.html
kazinator 11y ago
Unfortunately, there is a catch: http://loup-vaillant.fr/tutorials/earley-parsing/parser http://loup-vaillant.fr/tutorials/earley-parsing/parser Once you have a successful parse, extracting the tree from it is a little bit like pulling teeth. You have to perform searches on the Early set data, and deal with ambiguities at that point. None of the mainstream method have any major difficulty with popping out abstract syntax trees in a straightforward syntax-directed manner.
- yxhuvud 11y ago
  There are efficient ways to do it though (the article link to Scott), even if they are not always very easy to understand.
joe_the_user 11y ago
I've always loved traditional recursive descent parsers. You have to learn a bit about transforming the target language into the required form. But they are nice because they require no tools at all. Being hand-created, they can be among the most efficient available. This link seems to have good info on language operations required to put language in the required form. http://www.cs.engr.uky.edu/~lewis/essays/compilers/rec-des.html http://www.cs.engr.uky.edu/~lewis/essays/compilers/rec-des.h...
Others 11y ago
I quite like anltr4's ALL(*) parsing. It always seems to hit the spot between reasonable speed and user friendliness. http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf
YorickPeterse 11y ago
A good LL(1) parser generator will be able to provide helpful error messages and good performance, at the cost of not being able to parse all grammars you might come up with.
- sklogic 11y ago
  LL(1) cannot recover that easily, which makes error reporting less useful.
  - YorickPeterse 11y ago
    This depends on the parser implementation. For example, https://github.com/yorickpeterse/ruby-ll https://github.com/yorickpeterse/ruby-ll lets you customize the error messages as the default ones can be a little bit confusing at times. An example of this is https://github.com/YorickPeterse/oga/blob/0fd6fd8645e57ea4b2c29264d498b9bccbb43a04/lib/oga/xml/parser.rll#L268-L284 https://github.com/YorickPeterse/oga/blob/0fd6fd8645e57ea4b2... which changes messages from "unexpected T_FOO, expected T_BAR" to "unexpected end of input, expected element closing tag". Having said that, a hand written parser _will_ beat LL(1) (or any parser generator for that matter) when it comes to error reporting, though this depends on the amount of effort a programmer put in to the error reporting.
    - sklogic 11y ago
      I'm talking about the recovery, not the messages - things like "skip to the next ';' and continue parsing a statement". > or any parser generator for that matter PEG-based generators can be just as good as handcrafted ones.
      - yxhuvud 11y ago
        As can Earley based ones, since the full parsing state is available (and, for that matter - possible to modify. It is quite possible to make up rules as you go).
sklogic 11y ago
An optimised Packrat is very efficient (especially when combined with Pratt), and the error handling can be on the same level as the best handcrafted professional parsers (like Clang or gcc) - it is easy to mix the recovery rules and arbitrarily complex messages into a PEG. I do not uderstand why PEG is so persistently misunderstood and unjustly criticised.

amelius 11y ago

This one uses the shift/reduce approach but can be applied to any context free grammer, efficiently: [1] [1] http://scottmcpeak.com/elkhound/ http://scottmcpeak.com/elkhound/

spacebat 11y ago

I believe that the Marpa parser may be what you're looking for. A C library with the most refined API in Perl5, improvements are in the works to make it easier to produce interfaces to the library in other languages. https://jeffreykegler.github.io/Marpa-web-site/ https://jeffreykegler.github.io/Marpa-web-site/ http://savage.net.au/Marpa.html http://savage.net.au/Marpa.html

kazinator 11y ago

Unfortunately, there is a catch: http://loup-vaillant.fr/tutorials/earley-parsing/parser http://loup-vaillant.fr/tutorials/earley-parsing/parser Once you have a successful parse, extracting the tree from it is a little bit like pulling teeth. You have to perform searches on the Early set data, and deal with ambiguities at that point. None of the mainstream method have any major difficulty with popping out abstract syntax trees in a straightforward syntax-directed manner.

yxhuvud 11y ago
There are efficient ways to do it though (the article link to Scott), even if they are not always very easy to understand.

joe_the_user 11y ago

I've always loved traditional recursive descent parsers. You have to learn a bit about transforming the target language into the required form. But they are nice because they require no tools at all. Being hand-created, they can be among the most efficient available. This link seems to have good info on language operations required to put language in the required form. http://www.cs.engr.uky.edu/~lewis/essays/compilers/rec-des.html http://www.cs.engr.uky.edu/~lewis/essays/compilers/rec-des.h...

Others 11y ago

I quite like anltr4's ALL(*) parsing. It always seems to hit the spot between reasonable speed and user friendliness. http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf

YorickPeterse 11y ago

A good LL(1) parser generator will be able to provide helpful error messages and good performance, at the cost of not being able to parse all grammars you might come up with.

sklogic 11y ago
LL(1) cannot recover that easily, which makes error reporting less useful.
- YorickPeterse 11y ago
  This depends on the parser implementation. For example, https://github.com/yorickpeterse/ruby-ll https://github.com/yorickpeterse/ruby-ll lets you customize the error messages as the default ones can be a little bit confusing at times. An example of this is https://github.com/YorickPeterse/oga/blob/0fd6fd8645e57ea4b2c29264d498b9bccbb43a04/lib/oga/xml/parser.rll#L268-L284 https://github.com/YorickPeterse/oga/blob/0fd6fd8645e57ea4b2... which changes messages from "unexpected T_FOO, expected T_BAR" to "unexpected end of input, expected element closing tag". Having said that, a hand written parser _will_ beat LL(1) (or any parser generator for that matter) when it comes to error reporting, though this depends on the amount of effort a programmer put in to the error reporting.
  - sklogic 11y ago
    I'm talking about the recovery, not the messages - things like "skip to the next ';' and continue parsing a statement". > or any parser generator for that matter PEG-based generators can be just as good as handcrafted ones.
    - yxhuvud 11y ago
      As can Earley based ones, since the full parsing state is available (and, for that matter - possible to modify. It is quite possible to make up rules as you go).

sklogic 11y ago

An optimised Packrat is very efficient (especially when combined with Pratt), and the error handling can be on the same level as the best handcrafted professional parsers (like Clang or gcc) - it is easy to mix the recovery rules and arbitrarily complex messages into a PEG. I do not uderstand why PEG is so persistently misunderstood and unjustly criticised.