CSE411: Introduction to Compilers

Abstract Syntax Tree

Jooyong Yi (UNIST)

Where We Are

         |-------|            |--------|        
Source → | Lexer | → tokens → | Parser | → parse
Program  |       |            |        |   tree 
         |-------|            |--------|        
                                                        

Semantic Analyzer

• Given a parse tree, the semantic analyzer detects semantic errors such as type errors.

                       =
                      / \
                <ID,1>   +
                        / \
                   <ID,2>  *
                          / \
                    <ID,3>   <INT,60>           
                           ↓                    
        |------------------------------------|
        |  Semantic Analyzer (Type Checking) |
        |------------------------------------|
                           ↓                            
                       =
                      / \
                <ID,1>   +
                  INT   INT
                        / \
                   <ID,2>  *
                     INT   INT
                          / \
                    <ID,3>   <INT,60>
                     INT       INT

IR (Intermediate Representation) Generator

• At this phase, we do not restrict ourselves to a specific hardware architecture.

                       =
                      / \
                <ID,1>   +
                  INT   INT
                        / \
                   <ID,2>  *
                     INT   INT
                          / \
                    <ID,3>   <INT,60>
                     INT       INT
                           ↓                            
        |------------------------------------|
        |            IR Generator            |
        |------------------------------------|
                           ↓                            
                       t1 = 60
                       t2 = ID3 * t1
                       t3 = ID2 + t2
                       ID1 = t3

E → E + T | T
T → T * F | F
F → (E) | ID | INT

                                    E
x + y * 60    --------->        /   |   \
                               E    +    T
                               |       / | \  
                               T      T  *  F
                               |      |     |
                               F      F     INT
                               |      |
                               ID    ID

E → E + T | T
T → T * F | F
F → (E) | ID | INT

                                    E                                  BinExp(Op: +)
x + y * 60    --------->        /   |   \        --------->            /           \
                               E    +    T                           ID(x)      BinExp(Op: *)
                               |       / | \                                     /       \
                               T      T  *  F                                  ID(y)     INT(60)
                               |      |     |
                               F      F     INT
                               |      |
                               ID    ID

E → E + T | T
T → T * F | F
F → (E) | ID | INT

                               Parse Tree                          
                        Concrete Syntax Tree (CST)               Abstract Syntax Tree (AST)

                                    E                                  BinExp(Op: +)
x + y * 60    --------->        /   |   \        --------->            /           \
                               E    +    T                           ID(x)      BinExp(Op: *)
                               |       / | \                                     /       \
                               T      T  *  F                                  ID(y)     INT(60)
                               |      |     |
                               F      F     INT
                               |      |
                               ID    ID

How do we convert a parse tree to an AST?

Rule-based conversion from a parse tree to an AST

Rule-based conversion from a parse tree to an AST

                                                  Parse Tree                          
                                           Concrete Syntax Tree (CST)               Abstract Syntax Tree (AST)
E: E '+' T { $$ = BinExp('+', $1, $3); }
 | T       { $$ = $1; }                                E                                  BinExp(Op: +)
 ;                                                 /   |   \        --------->            /           \
T: T '*' F { $$ = BinExp('*', $1, $3); }          E    +    T                           ID(x)      BinExp(Op: *)
 | F       { $$ = $1; }                           |       / | \                                     /       \
 ;                                                T      T  *  F                                  ID(y)     INT(60)
F: '('E')' { $$ = $2; }                           |      |     |
 | id      { $$ = ID($1); }                       F      F     INT  
 | int     { $$ = INT($1); }                      |      |
 ;                                                ID     ID

Applications of ASTs

• Type checking
• IR generation

Applications of ASTs

• Program analysis, including type checking
• Program transformation, including IR generation

• Code interpretation

Code Interpretation Using ASTs

            BinExp(Op: +)
            /           \
         ID(x)      BinExp(Op: *)
                     /       \
                  ID(y)     INT(60)

Code Interpretation Using ASTs

                   If
               /       \
      BinExp(Op: <)     Assign
          /    \        /   \
       ID(x)  INT(0)  ID(y) INT(1)

Program Analysis Using ASTs

• Example: MISRA C
  • A set of coding guidelines designed to improve code safety and reliability in embedded systems

• Example rules
  • Do not use goto
  • Every switch statement must have a default case.
  • Do not ignore the return value of a non-void function.
    • e.g., In f(); x = f();, the first call for f should not be allowed.

Program Transformation Using ASTs

• Code generation (AST -> IR)

• Source code instrumentation (AST -> AST')
• Transpilation (source-to-source compilation)