CSE411: Introduction to Compilers

Semantic Analysis

Jooyong Yi (UNIST)

Announcements

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

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 |
         |-------|            |--------|           |----------|        |-----------|
                                                        

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.

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.

Type Checking Using a Parse Tree

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

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.

Abstract Syntax Tree (AST)

Parse Tree (a.k.a., Concrete Syntax Tree)	Abstract Syntax Tree

• 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.

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

Elimination of Immediate Left Recursion

-- transform -->

Transformed LL(1) Grammar

E : T E'
E' : + T E'
E' : - T E'
E' : ε
T : ( E )
T : id
T : num

Top-Down Parse Tree

• Inconvenient to work with the following parse tree.

How to Obtain an AST?

• Short answer: use a syntax-directed definition.

Syntax-Directed Definition (SDD)

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

SDD Example 1

• Subscripts are used to distinguish between non-terminals with the same name.
• id.entry refers to an entry of the symbol table.

Transforming a Parse Tree into an AST

• Perform a post-order traversal of the parse tree.

Parse Tree	SDD	AST

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

How about Top-Down Parsing?

Parse Tree	SDD	AST

SDD Example 2

Constructing an AST from a Top-Down Parse Tree

Parse Tree	SDD	AST Construction Flow