CSE411

CSE411: Introduction to Compilers

Parsing #3 (Parse Tree)

Jooyong Yi (UNIST)

2023 Spring
CSE411

Interface of Parser

                     |--------|           
a stream of tokens → | Parser | → parse tree
                     |--------|         
2023 Spring
CSE411

Parse Tree

Consider the following grammar :

2023 Spring
CSE411

Parse Tree

Consider the following grammar :

center

2023 Spring
CSE411

Why Parse Tree?

center

  • Is statement int x = 1+2 type-safe?
2023 Spring
CSE411

Why Parse Tree?

center

  • Code Generation Procedure
    • CodeGen(PLUS, CodeGen(), CodeGen())
2023 Spring
CSE411

Syntax checking is not enough.

  • The parse tree of 1 + 2 * 3?
2023 Spring
CSE411

Syntax checking is not enough.

  • The parse tree of 1 + 2 * 3?

center

2023 Spring
CSE411

Ambiguous Grammar

  • The parse tree of 1 + 2 * 3?

center

2023 Spring
CSE411

Ambiguous Grammar

  • Precedence
center center
2023 Spring
CSE411

Ambiguous Grammar

  • Associativity
center center
2023 Spring
CSE411

Resolving Ambiguity (Precedence)

-- resolves precedence -->

  • A higher precedence operator appears at a lower level of the parse tree.
center center
2023 Spring
CSE411

Resolving Ambiguity (Precedence)

  • Left (right) associativity: left (right) recursion
center center
2023 Spring
CSE411

Resolving Ambiguity

  • There is no general algorithm that can eliminate the ambiguity of any CFG without requiring additional information.
  • Why?
2023 Spring
CSE411

Resolving Ambiguity

  • Consider an ambiguous grammar .
  • Assume that is an unambiguous version of .
2023 Spring
CSE411

Resolving Ambiguity

  • Consider an ambiguous grammar .
  • Assume that is an unambiguous version of .
  • Which strings should be eliminated from ?
2023 Spring
CSE411

Another Example of Ambiguous Grammar

  • stands for any other statement.
2023 Spring
CSE411

Another Example of Ambiguous Grammar

  • Parse
center center center
2023 Spring
CSE411

Resolving Ambiguity

2023 Spring
CSE411

Resolving Ambiguity

  • Parse
center center center
2023 Spring
CSE411

Resolving Ambiguity

  • Consider an ambiguous grammar .
  • Assume that is an unambiguous version of .
  • Which strings should be eliminated from ?
    • An answer depends on the intention of the language designer.
2023 Spring