When building a parser to a programming language what I earn and what I lost choosing one or the other?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
I'll contrast LL and LR parsing for a number of criteria:
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.
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 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.
Here is a link to a site also contrasting LL and LR. Look for the section near the bottom.
protected by gnat Dec 7 '14 at 15:27
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?