COMS W4115
Programming Languages and Translators
Lecture 17: Intermediate Representations
March 31, 2008

Important Dates

• April 14: Homework #2 given out
• April 21: Homework #2 due in class
• April 23: Answers to HW#2 discussed in class
• April 28&30: 12-minute project presentations in class
• May 5: Final exam in class
• May 12&13: 30-minute project demos (11am-5:00pm) in CS conference room

Lecture Outline

1. Review
2. Intermediate representations
3. Three-address code
4. Semantic analysis
5. Types
6. Reading

1. Review

• Syntax-directed translation schemes
• Transforming an SDTS by left factoring
• SDTSs for translating infix to postfix
• Translation of while-statements

2. Intermediate Representations

• Compiler front end
• High-level IR
• Low-level IR
• Directed acyclic graphs
• Algorithm 6.3: Value-number method for constructing a DAG

3. Three-Address Code

• Three-address instructions
• Representations for three-address code
• Records
• Quadruples
• Triples
• Static single-assignment form

4. Semantic Analysis

• Uses made of semantic information for a variable x.
• What kind of value is stored in x?
• How big is x?
• Who is responsible for allocating space for x?
• Who is responsible for initializing x?
• How long must the value of x be kept?
• If x is a procedure, what arguments does it take and what kind of return value does it have?
• Storage layout for local names

5. Types

• Type expressions
• Rules for constructing type expressions
• Type equivalence
• Are the following two type declarations in C equivalent?

    struct TreeNode {                  struct Node {
     int value;                         int value;
     struct TreeNode *left;             struct Node *left;
     struct TreeNode *right;            struct Node * right;
    }                                  }
   

• Forms of type equivalence
• Name equivalence: two types are equivalent iff they have the same name.
• Structural equivalence: two types are equivalent iff they have the same structure.
• To test for structural equivalence, a compiler must encode the structure of a type in its representation. A tree (or type graph) is typically used.

6. Reading

• ALSU, Sections 6.1-6.3