- 9/26/05: Structure of a language-processing system. Phases
of a compiler: front end and back end. The role of formal languages in
parsing. Knuth's theorem on Deterministic Languages and LR(k)
Grammars. Top-Down Parsing. An example: the Calculator.
Reading assignment: Chapters 1,3.
- 9/28/05-10/3/05: Lexical Analysis. Regular expressions and
regular definitions. From Regular expressions to Nondeterministic FSA
with epsilon transitions. The membership problem for regular
languages. Designing a Lexical Analyzer generator. Lex
specifications. Synthesized attributes and tokens.
Reading assignment: Chapter 3 (all).
- 10/5/05: Context Free grammars. Parse Trees. Leftmost and
rightmost derivations. Ambiguity. Nonrecursive Top-down
parsing. Parsing arithmetic expressions. LL(k) grammars.
Reading assignment: Chapter 4.1-4.4.
- 10/10/05: Elimination of Left Recursion. FIRST and
FOLLOW. LL(1) grammars. Nonrecursive predictive parsing.
Reading assignment: Chapter 4.1-4.4 (all).
- 10/12/05: Review on Top-Down Parsing. Building Top-down
parsing tables using FIRST and FOLLOW. Bottom-up parsing. Stack-based
Shift/Reduce Parsing.
Reading assignment: Chapter 4.5.
- 10/17/05: Viable Prefixes. LR Parsers. LR(0) items. SLR
Parsing Tables.
Reading assignment: Chapter 4.7.
- 10/19/05: LR(1) items. Canonical LR Tables. LALR Tables.
Reading assignment: Chapter 4.7.
- 10/24/05: Yacc and Lex specifications for a
calculator. Evaluation of synthesized attributes using a stack.
- 10/26/05: L-attributed Definitions.
- 10/31/05: Yacc and Lex specifications for Little-C.
- 11/2/05: Shift/Reduce and Reduce/Reduce conflicts. Coping
with ambiguous grammars. Conflict analysis and
resolution. Implementation of L-attributed definitions. Topological
sorts.
- 11/7/05: Introduction to Type Checking. A compiler for
Little-C. Translation of control statements, assignments and
arithmetic expressions. Intermediate code.
- 11/9/05: Front-end revisited: keeping track of the scope in
Symbol Tables, efficient implementation of Symbol Tables, DAGs and
Syntax Trees for expressions, supporting recursion: activation records
and offsets.
- 11/14/05: Introduction to Process Query Systems.
- 11/16/05: Process Query Systems: theory and
applications.
- 11/21/05: Code Generation: overview. Register machines:
address modes. Block graphs. Next-use information. Address descriptors
and register descriptors.
- 11/23/05: A language for PQS. PQML and P++.
- 11/30/05: Physical Type
Checking, Register Allocation and Coloring, Block Graph and Code
optimization. CLR, JVM and
Reflection.
- 12/5/05: Decompilers. Linkers and Loaders. WCET Analysis. Garbage Collectors.