Section notes: Week 14

CS 164, Fall 2005

General

• Last week! Final: Dec 15
• Office hours as usual through Monday (or by appointment)

The big picture

Compilers are usually divided into modules. The different modules pass different intermediate representations to each other: from the raw program text to a sequence of lexemes to an abstract syntax tree to assembly language to binary machine code. The usual division is lexical analysis, parsing, static analysis, code generation, and optimization; but the boundaries between these modules are not set in stone.

• Lexical analysis
  • Regular languages and regular expressions
  • NFAs and DFAs
  • Recursive descent applied to tokenizing
• Parsing
  • Recursive-descent and LL(1) grammars
  • Factoring grammars (e.g. removing left recursion)
  • First, follow, and nullable; writing parse tables
  • Bottom-up parsing and LR(1) / LALR(1) grammars
  • Establishing precedence and associativity among operators
  • The LR state machine
  • Abstract syntax
• Static analysis and type-checking
  • Computing types of simple expressions
  • Static versus dynamic typing
  • Representing inheritance
  • Representing nested name spaces
• Code generation
  • Stack machine idea
  • Code for branches (including short-circuit)
  • Code for method calls
• Optimization
  • Peephole optimization
  • Data flow ideas
  • Profiling
• Run time support
  • Stack machine at run time
  • Memory management and garbage collection
  • Run-time support for dynamic typing

Questions

• What would it take to add Java-style interfaces to MJ?
• Write a regular expressions for expressions involving sums, differences, and products of positive integers. What is the alphabet?
• Write an LL(1) grammar and parse table for this expression language.
• Write an LR(1) grammar with correct precedence and associativity.
• Define call by value, by reference, and by name. Give an example which prints a different result for each.
• Write down a factorial program in MJ. What does the machine state look like before returning from the base case in a call to compute 3!?
• Write stack machine assembly for the factorial program, and describe the basic blocks and the control flow graph for the routine that does the actual computation.