Compiler and Translator Design
Catalog Description: Algorithms used by the following system software: assemblers, macro-processors, interpreters, and compilers; compiler design options and code optimization; all concepts implemented in major programming assignments.
Type: Required for all Computer Science majors.
Total Credits: 4
Contact Hours: 4 lecture hours per week.
Course Coordinator: Robert Heckendorn
URL: http://marvin.cs.uidaho.edu/Teaching/CS445/index.html (Fall 2013)
http://www2.cs.uidaho.edu/~jeffery/courses/445/ (Fall 2012)
Prereq: Have passed all required CS 2XX level courses with C or better and CS 385: Theory of Computation with a C or better.
Textbook: "Compilers: Principles, Techniques and Tools," 2007, Aho, Lam, Sethi, and Ullman, Prentice Hall
Prerequisites by Topic:
- Skill at programming in C or C++, including scope and recursion, and understand the process of edit/compile/debug cycle.
- Understand the use, design and implementation of many common data structures.
- Understand principles of good program design and be able to apply that to a large incremental programming project.
- Understand the basics of computer architecture including machine organization, assembly language, instruction sets, and memory organization.
- Understand operating systems concepts including details of program loading, system calls, libraries, memory allocation and initializing for execution.
- Understand systems concepts such as dependency driven build, linking, tarring, d ifferences in operating systems and system tools.
- Understand the basics of formal grammar and language theory including Finite State Automata (FSA), Control Flow Graphs (CFGs), Regular Expressions (REs).
Major Topics Covered
- Types of language translation (1 hour)
- Language standards (1 hour)
- The role of a compiler in the world of software (1 hour)
- Organization of a compiler
- Bison & Flex (4 hours)
- Formal language theory incl. RE, BNF, EBNF, grammars and their organization (3 hours)
- How to control derivation of sentences (1 hour)
- Finite State Automata (1 hours)
- Some UNIX tools (make, tar, etc) (1 hours)
- Tokens (1 hours)
- LL and LR parsers including LALR and SLR parsers and how they work (6 hours)
- First and follow sets (2 hours)
- Syntax trees (2 hours)
- Tree annotation (4 hours)
- Nice error reporting in a lookahead parser, (1 hour)
- Attribute grammars (1 hour)
- Ambiguity and how to avoid it (2 hour)
- Controlling precedence (1 hour)
- Dangling else (2 hours)
- Shift reduce conflicts (1 hour)
- Reduce reduce conficts (2 hours)
- Error handling via the error token mechanism (2 hours)
- Memory allocation for variables and procedures (4 hours)
- Scoping of variables (2 hours)
- Procedure call implementation and frames (2 hours)
- Global variables (1 hour)
- Type checking (2 hours)
- Expression compilation (1 hour)
- Code generation (4 hours)
- Code optimizations including intermediate representation optimization, and backend optimizations such as instruction selection and scheduling and register allocation, peephole optimization, variable length data allocation (6 hours)
- Apply knowledge of context free grammars to language translation and file parsing problems (a).
- Write and integrate a scanner, parser, semantic analyzer, and code generator into a simple working compiler (k).
- Use a lexical analyzer and parser generator to write and compile a front-end for a compiler (k).
- Understand scanners and how they are defined (b).
- Demonstrate proficiency with regular expressions and lexical analysis techniques (a).
- Understand parsers and how they are defined ( b).
- Understand recursive descent and related LL parsing algorithms (b).
- Know and use LR parsing theory and methods (j).
- Undersand semantic analysis principles (i).
- Use synthesized and inherited grammar attributes (a).
- Employ symbol tables and implement type checking algorithms (i).
- Demonstrate knowledge of principles of intermediate and final code generation (i).
- Understand instruction selection and register allocation (j).
- Understand common optimizations (j).