Unit 6: Syntax Directed Translation and Semantic Analysis
Semantic Analysis takes input from the parsing process and prepares the code for the code-generation step. In this unit, we will discuss this process in detail, learning about scope and type-checking, type expression, type equations, and type inference.
Completing this unit should take you approximately 33 hours.
Upon successful completion of this unit, you will be able to:
- Explain semantic analysis in the context of the compilation process.
- Describe scope checking and type checking.
- Specify the functions of semantic analysis.
- Solve type equations and make inferences in a type calculus.
6.1: Syntax-Directed Translation and Attribute Grammars
Read Chapter 5 on interpretation, where execution of a program takes place as the derivation is produced.
Study the definitions and examples. Syntax-directed translation and attribute grammars are techniques for using the parser to drive the translation directly. Attributes are properties of grammar symbols, and the attributes take on values. Rules associated with each grammar production specify how to compute the value of the attributes.
6.2: Intermediate Representation
Study the slides on intermediate representations. Data, as well as computations and flow of control, have intermediate representations.
Read Chapter 4 on scope of names and symbol tables.
6.3: Functions of Semantic Analysis
6.3.2: Static vs. Dynamic Scope Checking
Read these slides.
6.3.3: Type Checking
Read Chapter 6, which presents an overview of type checking, nicely organized: symbol table environment, type checking for expressions, functions, and then, for programs.
6.3.3.1: Type Expressions, Type Equivalence, Type Inference, and What to Check
Study the slides on type systems and what to check for when building intermediate representations for various language constructs.
Read slides 2 through 14 and use them as a review or supplement to the above readings. Slides 15 through 31 give examples of type inference for the languages Prolog, Java, and Python.
These lectures correspond to the notes and are optional. They may be helpful in understanding some of the notes.
6.3.3.2: Type Systems as Proof Systems-Type Checking as Proofs
Study the very interesting presentation on type checking by proofs.
Read slides 1 through 8. The slides are somewhat formal and present a "type calculus." Use these slides to add to your understanding of types.
This video corresponds to these notes and is optional. If it adds to the notes and helps you, watch it.
6.3.3.3: Applications of Type Proofs
Study the application of the type proof system (introduced above) to the detection of type errors.
6.3.3.4: Type Equations, Unification and Binding of Type Expressions
Study slides 8 through 19. The slides supplement the readings above with type examples. A binding is a substitution of a type expression for a type variable.
6.4: Verification and Validation of Semantic Analysis
Complete exercises 6.1 and 6.2 on pages 143 and 144.
These exercises will give you some practice with semantic analysis and are based on Chapter 6, which covers type checking. Then check your answers against the Answer Key.