What are the main advantages and disadvantages of LL and LR parsing?

Question

When building a parser to a programming language what I earn and what I lost choosing one or the other?

Answer 1

I'll contrast LL and LR parsing for a number of criteria:

Complexity

LL wins here, hands down. You can easily hand-write an LL parser. In fact, this is commonly done: the Microsoft C# compiler is a hand-written recursive descent parser (source here, look for a comment made by Patrick Kristiansen - the blog post is very interesting as well).

LR parsing uses a rather counter-intuitive method to parse a text. It works, but it took me some time to wrap my head around how it works exactly. Writing such a parser by hand is therefore hard: you'd be more or less implementing an LR parser-generator.

Generality

LR wins here: all LL languages are LR languages, but there are more LR languages than LL languages (a language is an LL language if it can be parsed with an LL parser, and a language is an LR language if it can be parsed with an LR parser).

LL has quite a few nuisances that will bother you when implementing just about any programming language. See here for an overview.

There are unambiguous languages that are not LR languages, but those are pretty rare. You almost never encounter such languages. However, LALR does have a few issues.

LALR is more or less a hack for LR parsers to make the tables smaller. The tables for an LR parser can typically grow enormous. LALR parsers give up the ability to parse all LR languages in exchange for smaller tables. Most LR parsers actually use LALR (not secretively though, you can usually find exactly what it implements).

LALR can complain about shift-reduce and reduce-reduce conflicts. This is caused by the table hack: it 'folds' similar entries together, which works because most entries are empty, but when they are not empty it generates a conflict. These kinds of errors are not natural, hard to understand and the fixes are usually fairly weird.

Compiler errors and error recovery

LL wins here. In an LL parse, it's usually pretty easy to emit useful compiler errors, in particular in hand-written parsers. You know what you're expecting next, so if it doesn't turn up, you usually know what went wrong and what the most sensible error would be.

Also, in LL parsing, error recovery is a lot easier. If an input doesn't parse correctly, you can try to skip ahead a bit and figure out if the rest of the input does parse correctly. If for instance some programming statement is malformed, you can skip ahead and parse the next statement, so you can catch more than one error.

Using an LR parser this is a lot more difficult. You can try to augment your grammar so that it accepts erroneous input and prints errors in the areas where things went wrong, but this is usually pretty hard to do. The chance you end up with a non-LR (or non-LALR) grammar also goes up.

Speed

Speed is not really an issue with the manner in which you parse your input (LL or LR), but rather the quality of the resulting code and the use of tables (you can use tables for both LL and LR). LL and LR are therefore comparable in this respect.

Links

Here is a link to a site also contrasting LL and LR. Look for the section near the bottom.

Here you can find a conversation regarding the differences. It's not a bad idea to critically look at the opinions voiced there though, there is a bit of a holy war going on there.

For more info, here and here are two of my own posts about parsers, though they are not strictly about the contrast between LL and LR.