Earley Parsing Explained
loup-vaillant.fr
Earley Parsing Explained
1–10 of 16 posts
Re: Earley Parsing Explained
#2Traditional 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.
Re: Earley Parsing Explained
#3Slight tangent, but interesting: Earley became a therapist and has been practicing since 1973. From his bio:
> Jay also has a Ph.D. in computer science from Carnegie-Mellon University and was formerly on the U.C. Berkeley faculty, where he published 12 computer science papers, one of which was voted one of the best 25 papers of the quarter century by the Communications of the A.C.M.
https://selftherapyjourney.com/Pattern/Beginning/Who_We_Are....
Re: Earley Parsing Explained
#4Traditional 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.
This one uses the shift/reduce approach but can be applied to any context free grammer, efficiently: [1]
Re: Earley Parsing Explained
#5Traditional 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.
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/ http://savage.net.au/Marpa.html
Re: Earley Parsing Explained
#6I'm looking at this, and the Earley items with the "fat dot" look a heck of a lot like LR(0) kernel items in LALR(1) parser generation.
Then it hits me: it looks like Earley parsing is to LALR(1) (vaguely ) like NFA simulation is to DFA table.
If we look at it at a very high level: Earley is making these items dynamically while scanning the input, and grouping them into sets representing states. Whereas a LALR parser generator will generate the items and group them into subsets statically, while processing the grammar, generating a push-down table driven by lookahead which is then applied to the input.
Analogously, NFA computes sets of states dynamically according to the input, by performing closures on the NFA graph, whereas DFA does it statically in the absence of input.
Re: Earley Parsing Explained
#7Traditional 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.
Unfortunately, there is a catch:
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.
Re: Earley Parsing Explained
#8Traditional 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.
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.h...
Re: Earley Parsing Explained
#9Traditional 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.
Unfortunately, there is a catch: 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.
There are efficient ways to do it though (the article link to Scott), even if they are not always very easy to understand.
Re: Earley Parsing Explained
#10Traditional 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.
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