Notes on Bottom-Up Parsing

4.5 Bottom-Up Parsing

Overview of Bottom-Up Parsing

  • Bottom-Up Parsing defines the construction of a parse tree starting from the leaves (input symbols) and proceeding to the root (start symbol).
  • It is presented through the process of building parse trees, although direct translations without explicit tree construction can occur.
  • The prominent style of Bottom-Up Parsing is Shift-Reduce Parsing, which applies primarily to LR grammars.

Key Operations of Bottom-Up Parsing

  • Reductions: This process replaces substrings of the parsed input that match the body of a production with the corresponding nonterminal.
  • Handle: A substring that meets the body of a production wherein its reduction represents a step towards forming a rightmost derivation.
  • In executing the parse, two decisions are key:
  • When to reduce.
  • Which production to apply for reduction.
Example of Reductions
  • Consider the input sequence id * id using expression grammar:
  • Initial: id * id
  • 1st Reduction: Reduce id to F, giving F * id
  • 2nd Reduction: Reduce F to T, giving T * id
  • Continue reducing until reaching the start symbol E.

Shift-Reduce Parsing

  • Involves using a stack to manage grammar symbols with an input buffer for remaining tokens.
  • The steps follow:
  1. Shift: Move input symbols onto the stack.
  2. Reduce: Replace a string on the top of the stack with the corresponding nonterminal.
  3. Accept: If the start symbol is on the stack and input is empty, parsing is successful.
  4. Error: If a syntax error is detected, invoke error recovery.
Handling Conflicts
  • Shift-Reduce Parsing may face conflicts:
  • Shift/Reduce Conflict: Unable to decide if an action should be a shift or a reduction.
  • Reduce/Reduce Conflict: More than one production can be reduced at the same point.
  • Non-LR grammars cannot be parsed effectively leading to such conflicts.
Example Cases Leading to Conflicts
  • Example: Dangling-else problem can cause confusion during parsing.
  • Procedures vs. Arrays ambiguity where array references and procedure calls share syntax but differ in semantic interpretation.

Exercises

  • Modify algorithms for parse trees and error recovery.
  • Create error-correcting predictive parsing tables and demonstrate parser behavior on given inputs.

Conclusion

  • Bottom-Up Parsing is fundamental in syntax analysis, providing tools to parse and understand programming languages by resolving derivations and handling grammar constraints efficiently. The topic sets a premise for more advanced parsing methods discussed in sections following:
  • LR Parsing
  • Canonical-LR
  • LALR

Important Concepts in Upcoming Sections

  • Understanding LR Parsing (Lookahead mechanism)
  • Shift-Reduce advantages and limitations
  • Recognizing parses through states and items in an LR automaton.