# 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
4. Semantic analysis
5. Types

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

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