CSE411

CSE411: Introduction to Compilers

Semantic Analysis

Jooyong Yi (UNIST)

2023 Spring
CSE411

Announcements

  • No class in the next week.
  • Deadline for the 1st assignment: April 25 (Tuesday)
2023 Spring
CSE411

Where We Are

                 |-----------|        |----------|
Source Program → | Front End | → IR → | Back End | → Target Program
                 |-----------|        |----------|
                      👆
         |-------|            |--------|           |----------|        |-----------|
Source → | Lexer | → tokens → | Parser | → parse → | Semantic |→ AST → |   IR      | → IR
Program  |       |            |        |   tree    | Analyzer |        | Generator |
         |-------|            |--------|           |----------|        |-----------|
                                                        👆
2023 Spring
CSE411

Semantic Analysis

  • Given a grammatically correct program, we want to check whether the program satisfies desired semantic properties such as:

    1. Type checking
    2. A variable is defined before it is used.
2023 Spring
CSE411

Type Checking Example

Consider the following grammar

E : E + T 
E : E - T 
E : T
T : ( E )
T : id
T : num
  • Check whether the following program is well-typed: a - 4 + c

    • Assume that the programming language supports only two types: int and string.
    • Also assume that + and - are defined only for int.
2023 Spring
CSE411

Type Checking Using a Parse Tree

  • The following shows the parse tree for a - 4 + c.

center

2023 Spring
CSE411

Type Checking Using an Attributed Parse Tree

  • In the following parse tree, each node is annotated with Type.
  • We will see later how type checking is performed.

center

2023 Spring
CSE411

Abstract Syntax Tree (AST)

Parse Tree (a.k.a., Concrete Syntax Tree) Abstract Syntax Tree
center center
  • In a parse tree, many interior nodes are for "helper" non-terminals.
  • In an AST, all nodes directly correspond to program constructs.
  • An AST is more suitable for semantic analysis than a parse tree.
2023 Spring
CSE411

How about Top-Down Parsing?

  • The grammar used in our example is not an LL(1) grammar.
E : E + T 
E : E - T 
E : T
T : ( E )
T : id
T : num
2023 Spring
CSE411

Elimination of Immediate Left Recursion

-- transform -->

2023 Spring
CSE411

Transformed LL(1) Grammar

E : T E'
E' : + T E'
E' : - T E'
E' : ε
T : ( E )
T : id
T : num
2023 Spring
CSE411

Top-Down Parse Tree

  • Inconvenient to work with the following parse tree.

center

2023 Spring
CSE411

How to Obtain an AST?

  • Short answer: use a syntax-directed definition.
2023 Spring
CSE411

Syntax-Directed Definition (SDD)

  • CFG (Context-Free Grammar) + extension
  • Extension:
    • Attributes
    • Semantic rules
2023 Spring
CSE411

SDD Example 1

Production Semantic Rules
E E + T E.node = new Node('+', E.node, T.node)
E E - T E.node = new Node('-', E.node, T.node)
E T E.node = T.node
T ( E ) T.node = E.node
T id T.node = new Leaf(id, id.entry)
T num T.node = new Leaf(num, num.val)
  • Subscripts are used to distinguish between non-terminals with the same name.
  • id.entry refers to an entry of the symbol table.
2023 Spring
CSE411

Transforming a Parse Tree into an AST

  • Perform a post-order traversal of the parse tree.
Parse Tree SDD AST
center center center
2023 Spring
CSE411

Transforming a Parse Tree into an AST

  • The AST can also be directly constructed while parsing.
    • Apply the semantic rule when a production is used to reduce a non-terminal.
Parse Tree SDD AST
center center center
2023 Spring
CSE411

How about Top-Down Parsing?

Parse Tree SDD AST
center
2023 Spring
CSE411

SDD Example 2

Production Semantic Rules
E T E (1) E.node = E.syn (2) E.inh = T.node
E T E (1) E.inh = new Node('+', E.inh, T.node) (2) E.syn = E.syn
E T E (1) E.inh = new Node('-', E.inh, T.node) (2) E.syn = E.syn
E E.syn = E.inh
T (E) T.node = E.node
T id T.node = new Leaf(id, id.entry)
T num T.node = new Leaf(num, num.val)
2023 Spring
CSE411

Constructing an AST from a Top-Down Parse Tree

Parse Tree SDD AST Construction Flow
center center center
2023 Spring

\Tree [.E [.E [.E [.T id ] ] $-$ [.T num ] ] $+$ [.T id ] ]

\Tree [.E(int:Type) [.E(int:Type) [.E(int:Type) [.T(int:Type) id(int:Type) ] ] $-$ [.T(int:Type) num(int:Type) ] ] $+$ [.T(int:Type) id(int:Type) ] ]

\Tree [.E($+$:Op) [.E($-$:Op) id(a:Name) num(4:Val) ] id(c:Name) ]

\Tree [.E [.T id ] [.E' $-$ [.T num ] [.E' $+$ [.T id ] [.E' $\epsilon$ ] ] ] ]