The LL parser (left-to-right, leftmost derivation) and LR parser (left-to-right, rightmost derivation) are parsers for restrictive context-free grammar.

Difference between LL and LR Parsing

If we think parsing as outputting a traversal of the parse tree, then the LL parsers output a pre-order traversal and LR parsers a post-order traversal. 1

Example

For example, for a parse tree like the following: JSON Parse Tree.png

We will have the following results: JSON LL and LR parsing output.png

This also explain why LL is top-down parsing while LR is bottom-up parsing. 1

We can view LL and LR parser as taking a token stream, and then inserts interior nodes of the tree at appropriate places to achieve pre-order (LL) and post traversal (LR) of the parse tree.

Lookahead

Sometimes we need to look ahead of tokens in stream position to make decision. When we see designations like LL(1), LR(0), etc. the number in parentheses is the number of tokens of lookahead. 1

Note that the lookahead is relative to where the rule should be inserted, which is before that rule’s tokens for LL parsers or after that rule’s tokens for LR parsers. This is why we can have an LR(0) parser, whereas an LL(0) parser would be impossible.

Pros and Cons

LR Parsers Can Handle More Grammar

Since LR lookahead starts from the end of a rule, a LR(1) parser has strictly more information available to it when making a decision than an LL(1) parser. LR parsers can also handle left recursion, which LL parsers can’t. 1

LL Parsers Can Support Regex-like Operators in Grammars

With top-down parsers like LL, we can form a DFA for each rule.

pairs → (pair (',' pair)*)?

This is not possible with LR. 1

LL Parsers Support Inherited Attributes

Understanding the context enables LL parsers to pass attributes or metadata down the tree as it is being built, a concept known as “inherited attributes.” Both LL and LR parsers can also support “synthesized attributes,” which are passed up the tree. 1

Footnotes

  1. LL and LR Parsing Demystified 2 3 4 5 6