Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Earley Parsing Explained

loup-vaillant.fr

Post reply on HN
Print view View original

11–16 of 16 posts

Re: Earley Parsing Explained

#11

Post by YorickPeterse »

thristian wrote: post #2

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.

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.

Re: Earley Parsing Explained

#12

Post by sklogic »

thristian wrote: post #2

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.

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.

Re: Earley Parsing Explained

#13

Post by sklogic »

YorickPeterse wrote: post #11
thristian wrote: post #2

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.

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.

LL(1) cannot recover that easily, which makes error reporting less useful.

Re: Earley Parsing Explained

#14

Post by YorickPeterse »

sklogic wrote: post #13
YorickPeterse wrote: post #11

Earlier quoted context omitted.

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.

LL(1) cannot recover that easily, which makes error reporting less useful.

This depends on the parser implementation. For example, 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/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.

Re: Earley Parsing Explained

#15

Post by sklogic »

YorickPeterse wrote: post #14
sklogic wrote: post #13

Earlier quoted context omitted.

LL(1) cannot recover that easily, which makes error reporting less useful.

This depends on the parser implementation. For example, 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/0fd6fd8645e57ea4b2... which changes messages from "unexpected T_FOO, expected T_BAR" to "unexpected end of input, expected element closing tag". Having said that…

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.

Re: Earley Parsing Explained

#16

Post by yxhuvud »

sklogic wrote: post #15
YorickPeterse wrote: post #14

Earlier quoted context omitted.

This depends on the parser implementation. For example, 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/0fd6fd8645e57ea4b2... which changes messages from "unexpected T_FOO, expected T_BAR" to "unexpected end of input, expected element closing tag". Having said that…

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.

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).
Post reply on HN