CSE411: Introduction to Compilers

A Walkthrough of Compilation

Jooyong Yi (UNIST)

Compilation

Source Program →  ································· → Target Code

Intermediate Representation

Source Program →  ·········· → IR → ············ → Target Code

Frontend and Backend

    |-------- Frontend --------||-------- Backend --------|
    
Source Program →  ·········· → IR → ············ → Target Code

Frontend

         |-------|            |--------|           |----------|        |-----------|
Source → | Lexer | → tokens → | Parser | → parse → | Semantic |→ AST → |   IR      | → IR
Program  |       |            |        |   tree    | Analyzer |        | Generator |
         |-------|            |--------|           |----------|        |-----------|

Lexer (Lexical Analyzer)

• Given a source program, the lexer extracts the sequence of tokens.

        position  =  initial  +  rate   *   60
                           ↓
        |------------------------------------|
        |      Lexical Analyzer (Lexer)      |
        |------------------------------------|
                           ↓
        <ID, 1> <=> <ID, 2> <+> <ID, 3> <*> <INT, 60>                     

Parser (Syntax Analyzer)

• Given a sequence of tokens, the parser extracts the parse tree.

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

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

Back End

• Typically, multiple code optimization takes place.

     |-------------|         |-------------|          |-------------|
IR → |    Code     | → IR' → |    Code     | → IR'' → |    Code     | → Target
     | Optimizer 1 |         | Optimizer 2 |          |  Generator  |   Program
     |-------------|         |-------------|          |-------------| 

Code Optimization

                       t1 = 60
                       t2 = id3 * t1
                       t3 = id2 + t2
                       id1 = t3
                           ↓                            
        |------------------------------------|
        |        Code Optimization           |
        |------------------------------------|
                           ↓   
                      t2 = id3 * 60
                      id1 = id2 + t2                         

Code Generation

                      t2 = id3 * 60
                      id1 = id2 + t2                         
                           ↓                            
        |----------------------------------|
        |        Code Generation           |
        |----------------------------------|
                           ↓   
                     LD  R2, id3
                     MUL R2, R2, 60
                     LD  R1, id2
                     ADD R1, R1, R2
                     ST  id1, R1