3 ms·
The main contrast is with LL. LL(1) is trivially parsed with recursive descent; you start with the root production in the grammar, and you never need more than
by barrkel 11y ago
The main contrast is with LL. LL(1) is trivially parsed with recursive descent; you start with the root production in the grammar, and you never need more than one token of lookahead to figure out which alternate to parse next. This maps naturally to turning productions into functions and alternation choices into switches on the next token. The parse tree is built from the top down, like a pre-order traversal, because the current production is chosen before the constituent productions and terminals are parsed.
LR parsers build the tree from the bottom up. Productions / terminals get pushed onto a stack (shift) until there's enough information to decide what parent production to use, and children are popped off and replaced with the parent (reduce). The tree gets built post-order; the parents are built after the children are already built. The hard bit is figuring out whether the productions on the stack are enough to compose a parent rule or not.
LR parser generators figure out a state machine for making shift / reduce decisions quickly.