Look Step Parse Stack Unscanned Parser Action Ahead 0 = id + id*int $ Just the start id 1 id + id*int $ B Shift, Parser wants as big of a match as possible id = 2 + id * int $ B Parser wants as big of a match as possible id = id 3 id * int $ A Reduce to id = id + “id” “Value” 4 id * int $ A Reduce to id = + “Value” “Products” 5 id * int $ A Reduce to id = Products + “Products” “Sums” 6 id * int $ C Shift, since more to go (lookahead) id = Sums + 7 * int $ B Shift, since Sums + is a partial match, parser wants to see more id = Sums + id 8 int $ A Reduce to id = Sums + id * “id” “Value” 9 int $ A Reduce to id = Sums + Value * “Value” “Products” 10 int $ C Shift, still have more to do id = Sums + Products * 11 $ B Shift, since Products * is a partial match, parser wants to see more id = Sums + Products * int 12 A Reduce to id = Sums + Products * int $ “int” “Value” 13 D Reduce * Value” to id = Sums + Products * Value $ “Products “Products” 14 D Reduce + Products” to id = Sums + Products $ “Sums “Sums” 15 D Reduce = Sums” to id = Sums $ “id “Sums” 16 D Reduce to Sums $ “Sums” “Assign” 17 E Assign $ Now DRAW how this happens!!! (Hint: The parser builds up the incrementally, bottom up, and left to right. Start with the input at the very bottom) Expr→Expr Op Expr Expr→(Expr) Expr→-Expr Expr→num Op→+ | - | * A no production match in ENTIRE stack to ANY production reduce rightmost non-terminal B partial rightmost stack match Shift, parser wants to see more before deciding C whole production matches in stack and lookahead $ Shift, still have more reading to do rightmost != D rightmost whole production matches in stack and lookahead is $ reduce rightmost production E rightmost production matches START and lookahead is $ ACCEPT!! Look Step Parse Stack Unscanned Parser Action Ahead
Step Parse Stack Look Ahead Unscanned Parser Action 0 id = id + id*int $ Just the start 1 id = id + id*int $ B Shift, Parser wants as big of a match as possible 2 id = id + id * int $ B Parser wants as big of a match as possible 3 id = id + id * int $ A Reduce “id” to “Value” 4 id = + id * int $ A Reduce “Value” to “Products” 5 id = Products + id * int $ A Reduce “Products” to “Sums” 6 id = Sums + id * int $ C Shift, since more to go (lookahead) 7 id = Sums + id * int $ B Shift, since Sums + is a partial match, parser wants to see more 8 id = Sums + id * int $ A Reduce “id” to “Value” 9 id = Sums + Value * int $ A Reduce “Value” to “Products” 10 id = Sums + Products * int $ C Shift, still have more to do 11 id = Sums + Products * int $ B Shift, since Products * is a partial match, parser wants to see more 12 id = Sums + Products * int $ A Reduce “int” to “Value” 13 id = Sums + Products * Value $ D Reduce “Products * Value” to “Products” 14 id = Sums + Products $ D Reduce “Sums + Products” to “Sums” 15 id = Sums $ D Reduce “id = Sums” to “Sums” 16 Sums $ D Reduce “Sums” to “Assign” 17 Assign $ E Now DRAW how this happens!!! (Hint: The parser builds up the incrementally, bottom up, and left to right. Start with the input at the very bottom) Expr→Expr Op Expr Expr→(Expr) Expr→-Expr Expr→num Op→+ | - | * A no production match in ENTIRE stack to ANY production reduce rightmost non-terminal B partial rightmost stack match Shift, parser wants to see more before deciding C whole rightmost production matches in stack and lookahead != $ Shift, still have more reading to do D rightmost whole production matches in stack and lookahead is $ reduce rightmost production E rightmost production matches START and lookahead is $ ACCEPT!! Step Parse Stack Look Ahead Unscanned Parser Action
Shift%20Reduce%20parsing.docx