CSC362 2011F, Class 21: Shift-Reduce Parsing (1)
Overview:
* Introduction to shift-reduce parsing.
* A shift-reduce parser for a non-predictive language.
* A shift-reduce parser for a simple expression language.
* LR(0) parsers: Basic shift-reduce parsers. [Unlikely.]
Admin:
* EC for tomorrow's Thursday extra.
* EC for panel on the future of the book, Thursday at 4:15 in the Gallery.
Intro to Shift-Reduce Parsing
* Parsing technique that keeps track of two things
* Remaining input
* A stack of things - partial right-hand sides
* Based on what's on the stack and the next input
* Shift the next input onto the stack
* Reduce what's on the stack (RHS->LHS)
* This is a bottom-up parsing technique
A sample language
A^n(B^n|C^n)
s : b
| c
b : A b B
| epsilon
c : A c C
| epsilon
Assuming that we're not doing empty strings,
Can we parse this predictively as is?
Factor out the common A, step 1
s : A b B
| A c C
| epsilon
Factor out the common A, step 2
s : A s'
| epsilon
s' : b B
| c C
first(b B) = { A, B }
first(c C) = { A, C }
---
top of stack symbol action
empty A shift
A A shift
A B reduce 'b : epsilon'
b B shift
A b B B reduce 'b : A b B'
A b B EOI reduce 'b : A b B'
A C reduce 'c : epsilon'
c C shift
A c C C reduce 'c : A c C'
b EOI reduce 's : b'
c EOI reduce 's : c'
(input: NUM, stack: anything) -> shift
(input: ADDOP, stack: NUM) -> reduce NUM to factor
(input: ADDOP, stack: term MULOP factor) -> reduce term MULOP factor to expression
(input: ADDOP, stack: factor) -> reduce factor to term
(input: ADDOP, stack: expression ADDOP term) -> reduce expression ADDOP term to term
(input: ADDOP, stack: term) -> reduce term to expression
(input: ADDOP, stack: expression) -> shift
(input: MULOP, stack: NUM) -> reduce NUM to factor
(input: MULOP, stack: term MULOP factor) -> reduce term mulop factor to term
(input: MULOP, stack: factor) -> reduce factor to term
(input: MULOP, stack: term) -> shift
(input: EOI, stack: term MULOP factor) -> reduce term mulop factor to term
(input: EOI, stack: term) -> reduce term to expression
(input: EOI, stack: term MULOP factor) -> reduce term MULOP factor to term
(input: EOI, stack: factor) -> reduce factor to term
(input: EOI, stack: expression ADDOP term) -> reduce expression ADDOP term to expression
So, how does one build the table?
* Script kiddie solution: Just use Yacc/Bison
* Real hacker solution: Learn how to build Yacc/Bison, then build your own
and submit it to FSF.
* CS solution: Learn enough about the theory
Building LR(0) parsers, the simplest shift-reduce parsers
* Build a deterministic finite automaton. (Yay)
* States represent states of knowledge about parsing