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

LL and LR Parsing Demystified (2013)

blog.reverberate.org

Post reply on HN
Print view View original

11–20 of 37 posts

Re: LL and LR Parsing Demystified (2013)

#11

Post by AceJohnny2 »

What about Earley's algorithm?

Unfortunately, given the extremely limited hardware of 1960s computers (not helped by the lack of an efficient algorithm), the parsing of an arbitrary CFG was too slow to be practical. Parsing algorithms such as LL, LR, and LALR identified subsets of the full class of CFGs that could be efficiently parsed. Later, relatively practical algorithms for parsing any CFG appeared, most notably Earley's 1973 parsing algorithm. It is easy to overlook the relative difference in performance between then and now: the fastest computer in the world from 1964-1969 was the CDC6600 which executed at around 10 MIPS; my 2010 mobile phone has a processor which runs at over 2000 MIPS. By the time computers had become fast enough for Earley's algorithm, LL, LR, and friends had established a cultural dominance which is only now being seriously challenged - many of the most widely used tools still use those algorithms (or variants) for parsing. Nevertheless in tools such as ACCENT / ENTIRE and recent versions of bison, one has access to performant parsers which can parse any CFG, if that is needed.

from: http://tratt.net/laurie/blog/entries/parsing_the_solved_prob...

Featured here 6 years ago: https://news.ycombinator.com/item?id=2327313

Re: LL and LR Parsing Demystified (2013)

#12

Post by CalChris »

tl;dr use ANTLR

But actually, I did read this excellent article for the second time. However, unless you are skilled in the art, you should be using ANTLR4, Honey Badger. Terence Parr deserves a Turing award.

For parsing, most upper div compiler classes start off with CFGs, dip briefly into LL recursive descent and then conclude with LALR. If people remember anything, it's SHIFT/REDUCE. Unfortunately, there doesn't seem to be any standard tools for the LL(1) equivalent, FIRST/FOLLOW tables. And as the article shows, they aren't equivalent. Each has strengths but LALR has tools.

Except for ANTLR. Which started out as recursive descent ...

Parsing Techniques doesn't really have any competition. The compiler books, like the compiler classes, can only give a little attention to parsing. Given how strong the available tools are and how hard the remaining subjects are (SSA, code generation, ...) maybe they have a point.

Re: LL and LR Parsing Demystified (2013)

#13

Post by fernly »

AceJohnny2 wrote: post #11

What about Earley's algorithm? Unfortunately, given the extremely limited hardware of 1960s computers (not helped by the lack of an efficient algorithm), the parsing of an arbitrary CFG was too slow to be practical. Parsing algorithms such as LL, LR, and LALR identified subsets of the full class of CFGs that could be efficiently parsed. Later, relatively practical algorithms for parsing any CFG appeared, most notably…

Thanks for the reference. For those like me who'd not heard of it, see [1] for a description and links to many implementations.

[1] https://en.wikipedia.org/wiki/Earley_parser

Re: LL and LR Parsing Demystified (2013)

#16

Post by cbHXBY1D »

haberman wrote: post #7
devty wrote: post #6

Earlier quoted context omitted.

Out of curiosity, where would one find an explanation (potentially dry, long, and complicated) of the algos you mention here? In other words - how did you get to know them?

By far my favorite survey book on the subject is "Parsing Techniques: A Practical Guide" by Grune and Jacobs. Here is my Amazon review of the book: https://www.amazon.com/gp/customer-reviews/R17E19PSPM2UO9

How does it compare to the Dragon Book?

Re: LL and LR Parsing Demystified (2013)

#17

Post by nickpsecurity »

wfunction wrote: post #15
nickpsecurity wrote: post #14

People interested in these things should look up GLR and GLL. Pretty powerful when I studied them.

Funny, I knew GLR but I had never heard of GLL. Thanks for writing this!

Welcome. :) Here's the link to first paper I saw I think:

http://dotat.at/tmp/gll.pdf

Re: LL and LR Parsing Demystified (2013)

#18

Post by exDM69 »

CalChris wrote: post #12

tl;dr use ANTLR But actually, I did read this excellent article for the second time. However, unless you are skilled in the art, you should be using ANTLR4, Honey Badger. Terence Parr deserves a Turing award. For parsing, most upper div compiler classes start off with CFGs, dip briefly into LL recursive descent and then conclude with LALR. If people remember anything, it's SHIFT/REDUCE. Unfortunately, there doesn't s…

There are plenty of other parser generators than ANTLR and interesting parsing techniques that fit the bill. Not that there's anything wrong with ANTLR.

The last few time when I've been working on programming language prototypes, I've written the parser using Parsec parser combinators in Haskell. It's super fast and easy to use, however it's more like syntactic sugar for recursive descent parsers than a rigorous parser generator that works for a certain grammar class.

Re: LL and LR Parsing Demystified (2013)

#19

Post by barrkel »

haberman wrote: post #9
barrkel wrote: post #8

Earlier quoted context omitted.

If you implement a top-down recursive descent parser, you'll quickly learn how it maps to LL. This is best done by following tutorials and reading and rewriting simple expression parsers. There's no substitute to doing and experimentation. No short paragraph is going to give you the insight. Build a parse tree in a recursive descent parser, and you'll notice that you build it from the top down - even if you actually…

> If you implement a top-down recursive descent parser, you'll quickly learn how it maps to LL. This will indeed tell you how top-down parsers work. But this doesn't tell you very much about LL specifically. The trickiest part of parsing is deciding what path to take. When you hand-write a recursive descent parser, your code for deciding between alternatives is ad hoc. For example if you are parsing JSON you'll have…

The first and follow sets for LL are the first hurdle you'll hit when you try to parse something where the next production (the next path) doesn't consume the token straight away. The theory becomes instantly accessible for practical reasons. So I respectfully disagree.

You'll quickly learn there's a mechanical transformation from LL(1) grammars to recursive descent. And if you write a recursive descent parser with one token of lookahead, no backtracking, and straightforward syntax actions, it has a mechanical translation into LL(1).

Anyway, I described the journey I went through learning compiler theory before I went to college. I covered undergrad compiler course content long before I left secondary school, and understood it at a much deeper level. I got a job at Borland working on the Delphi compiler (6 years I put in) on the back of the same knowledge. It worked for me.

Post reply on HN