Dr. David Nordstrom
office: 5345 Nguyen Engineering Bldg.
phone (703) 993-1565
Office hours: Tuesday and Thursday 1:00 - 2:00, Wednesday 3:00 - 4:00, and by appointment.
The course website is at
Aho, Lam, Sethi, and Ullman, Compilers: Principles, Techniques, &
Tools, 2nd ed., 2007, Addison-Wesley, 1986.
Levine, Mason, and Brown, Lex &
Yacc, 2nd ed., O'Reilly & Associates, 1990.
This is a 3-credit course on programming language translation
concentrating on compilers. Prerequisites are grade of C or better in CS 310, CS 330
and CS 367. Students should know basic data structures, should have
seen finite automata (finite state machines) and context-free grammars
from CS 330, should be comfortable with assembly language programming,
and should be able to program in Java or C. Topics include:
There will be a significant programming project in which students
write a small interpreter and a compiler. Programming will be done in
Java or C (C is preferred) and will use the tools lex and yacc or their equivalents.
Regular expressions and finite automata
LL and LR parsing
lex and yacc
- be able to compare compiled and interpreted execution models, outlining the relative merits of each.
- be able to describe the phases of program translation from source code to executable code and the files produced by these phases.
- be able to write regular expressions and finite state automata for languages, be able to use tools to automatically generate scanners.
- understand the definition of grammars; be able to write grammar for context-free languages; be able to manually write recursive-descent parsers; be able to transform grammars and use automatic tools to generate bottom-up parsers.
- be able to construct and maintain symbol table; be able to process declarations and scopes; understand the type system and type checking.
- be able to describe the storage system and explain the implementation of high-level language features like function calls.
- be able to explain the major problems and solutions of code generation; be able to implement code generator from intermediate code.
- be able to explain important optimization schemes; be able to describe and apply data-flow analysis.
In addition to the programming project there will be a midterm and a
final exam. Makeups on exams will not be given except for very good
reason (as judged by me) and only when arranged in advance. The
course grade will be computed from:
- Programming: 35%
- Midterm: 30%
- Final: 35%