[ACCEPTED]-What advantages do LL parsers have over LR parsers?-lr

Accepted answer
Score: 35

GLR is great if you want a parse tree/forest 52 and don't mind black boxes. It lets you 51 type in whatever CFG you want at the cost of 50 checking for ambiguities at parse time via 49 exhaustive testing, instead of resolving 48 LR/LALR conflicts statically. Some say 47 that's a good trade-off. Ira Baxter's DMS 46 tool or Elkhound, which has a free C++ grammar, are 45 useful for this class of problem. ANTLR is useful 44 for a large class of language applications 43 too, but uses a top-down approach, generating 42 recursive descent parsers called LL(*) that 41 allow semantic predicates. I will state 40 without proof here that predicates allow 39 you to parse context-sensitive languages 38 beyond CFGs. Programmers like to insert 37 actions into grammars, like good error handling, and 36 like to single-step debug. LL is good at 35 all three. LL is what we do by hand so 34 it's easier to understand. Don't believe 33 the wikipedia nonsense about LR being better at handling errors. That said, if you backtrack a lot 32 with ANTLR, errors are indeed worse with 31 LL(*) (PEGs have this problem).

Re backtracking. GLR 30 speculates (i.e. backtracks) too, just like 29 PEGs, ANTLR, and any other non-deterministic 28 strategy. At any non-deterministic LR state, GLR 27 "forks" sub-parsers to try out 26 any viable path. Anyway, LL has good context 25 for error handling. Where LR knows it's 24 matching an expression, LL knows it's an 23 expression in an assignment or IF-conditional; LR 22 knows it could be in either but isn't sure 21 - and that uncertainty is where it gets 20 its power.

GLR is O(n^3) worst case. packrat/PEG 19 is O(n) worst case. ANTLR's are O(n^2) due to cyclic 18 lookahead DFA but O(n) in practice. Doesn't 17 matter really. GLR is fast enough.

ANTLR is ANother 16 Tool for Lang Recognition not anti-LR, but 15 I like that one too ;)

Frankly, like a lot 14 of young coders in 80s, I didn't understand 13 LALR and didn't like black boxes (now I 12 dig the beauty of the GLR engine but still 11 prefer LL). I built a commercial LL(k) based 10 compiler and decided to build a tool to 9 generate what I had built by hand. ANTLR 8 isn't for everyone and edge cases like C++ might 7 be better handled with GLR but a lot of 6 people find ANTLR fits into their comfort 5 zone. Since Jan 2008, there have been 134,000 4 downloads of ANTLR's binary jar, within 3 ANTLRWorks, and source zips total (according 2 to Google Analytics). See our paper on LL(*) with 1 lots of empirical data.

Score: 12

If you have to hand code one, recursive 17 descent (LL) is something you can do realistically; people 16 cannot hand-build L(AL)R parsers practically 15 by hand.

Given that modern parser generators 14 will handle all the parser construction 13 for you, and that space is not much of an 12 issue, I prefer LR parsers because you don't 11 have to fight with the grammars as much 10 to make them valid for your particular parser 9 generator (no "remove all the left 8 recursion" silliness).

In fact, I prefer 7 GLR parsers, which will pretty much parse anything 6 with a context free grammar. No left-recursion 5 worries. No shift/reduce conflict worries. No 4 lookahead limits.

If you want to see the 3 range of languages that one GLR parsing engine 2 can handle (including the famously hard-to-parse-using-LL/LALR 1 language, C++), you can look here.

Score: 3

From my personal experience (I used both 13 for various situations), the most practical 12 difference is that, with a LL(k), you can 11 define the grammar in an easier way (since 10 it's top-down) without caring about many 9 possible reduce-reduce or shift-reduce conflicts 8 which often occur with LR parsers. The only 7 thing you have to care about is left-recursion 6 which must be transformed into right one.

Another 5 thing is that the top-down approach usually 4 implies a higher complexity (regarding either 3 space or time), because it has to store 2 the whole tree while parsing and it can 1 grow a lot until ambiguities are solved.

Score: 1

The only advantage I've ever been familiar 3 with is that you can easily code LL parsers 2 by hand. LR parsers are MUCH harder to code 1 by hand (you usually use a parser generator).

Score: 1

LL Parsings worst case complexity is O(n^4), whereas 2 LR parsing's worst case complexity is better, O(n^3).

(But 1 no one would ever write O(n^4) grammar.)

https://en.wikipedia.org/wiki/Top-down_parsing

Score: 1

According to Laurence Tratt, LL parsers 16 have a small but important niche, which 15 is if you need:

the highest possible performance 14 and/or the best possible error messages.

And 13 hand code a recursive descent parser to 12 accomplish that.

For a realistic programming 11 language grammar, it will typically take 10 many person months of effort to beat an 9 automatically generated parser.

However:

LL 8 parsers are largely unappealing, because 7 the lack of left recursion makes expressing 6 many standard programming language constructs 5 awkward.

and thus his conclusion is that 4 LR parsing, which handles left recursion 3 just fine, is the way to go.

For a more thorough 2 review of this I recommend Laurence Tratt's 1 excellent essay Which Parsing Approach?

Score: 0

One reason that comes to mind is, it's much 2 easier to do a language that needs arbitrary 1 backtracking (cough C++) in an LL paradigm.

More Related questions