ITEC 460 - Chapter 5 Notes

Top Down vs Bottom Up Parsing

• Top Down Parsing creates a parse tree from the root (the start symbol) to the leaves (the terminals)
• LL - Leftmost scan of input, follow steps of leftmost parse
• LL parsers choose a production to expand by matching the input symbol with the first character on RHS of that production


• Bottom Up Parsing creates a parse tree from the leaves to the root.
• It creates a forest of trees and merges the trees to form larger trees
• LR - Leftmost scan of input, follow steps of rightmost parse (in reverse)
• A LR parser must match the entire RHS of a production before it will reduce the RHS to a LHS


• Reduce: Replace RHS w/ LHS (ie join a set of nodes by adding their parent)


• Example: parse 2 + 3 * 5 with E → E + T|T; T → T * num | num
• Example: page 83

Comparison of Stacks in Top Down and Bottom Up

• Top Down: Stack holds variables that are waiting to be expanded
• TOS is leftmost nonterminal in a derivation


• Bottom Up: Stack holds a string of vars and terms that are waiting to be reduced
• TOS is rightmost symbol of shifted terminals and reduced variables
• Actions:
• Shift: move terminals from input to top of stack
• Reduce: pop RHS and replace with LHS


• Later we see that stack also holds states


• Example: Page 83
• Example: Page 84

LR Parse Tables Specify when to Shift and Reduce

• Stack holds actions (Shift or Reduce) and states


• Example: Page 86 - 87


• Example: Pages 87 - 88

Creating LR parsing Tables

• Example: LR(0) table: example page 88

Topic

Topic

Topic

Topic

Topic

Topic

Topic

Topic

Topic

Topic