CS 440
Language Processors
Fall 2011
Dr. David Nordstrom
office: 5345 Nguyen Engineering Bldg.
email: dnordstr_AT_gmu_DOT_edu
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
http://cs.gmu.edu/~dnord/cs440
Texts
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.
Description
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:
Compiler organization
Regular expressions and finite automata
Lexical analysis
Symbol tables
Context-free grammars
LL and LR parsing
lex and yacc
Code generation
Attribute grammars
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.
Course Outcomes
Students will:
- 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.
Grading
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%