โ Compiler Design learning pathCompiler Design ยท Module 4 of 10
Bottom-up parsing
Shift-reduce, LR, SLR and LALR.
๐ Key ideas
- Bottom-up parsers start from tokens and reduce them to the start symbol, finding a rightmost derivation in reverse.
- Shift-reduce actions: shift, reduce, accept and error.
- A handle is the substring that matches a production and is reduced next.
- LR parsers (SLR, LALR, canonical LR) handle most programming language grammars.
- 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