โ† Compiler Design learning path
Compiler Design ยท Module 4 of 10

Bottom-up parsing

Shift-reduce, LR, SLR and LALR.

๐Ÿ“– Key ideas

  1. Bottom-up parsers start from tokens and reduce them to the start symbol, finding a rightmost derivation in reverse.
  2. Shift-reduce actions: shift, reduce, accept and error.
  3. A handle is the substring that matches a production and is reduced next.
  4. LR parsers (SLR, LALR, canonical LR) handle most programming language grammars.
  5. Yacc and Bison generate LALR(1) parsers.
๐Ÿ’ก Real-life example: Bottom-up parsing is like assembling furniture: join small pieces into parts, then parts into the finished chair.
Shift-reduce parserBottom-up parser using a stack
HandleSubstring reduced in the next step
LALRLook-ahead LR, used by Yacc and Bison
Reduce-reduce conflictTwo productions could reduce at the same point