CS 445: 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, Fall 2015, Spring 2016, Fall 2016)
http://www2.cs.uidaho.edu/~jeffery/courses/445/ (Fall 2012, Fall 2014)
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; or "Compiler Construction: Principles and Practice", 2001, Kenneth Louden, Cengage Learning;
Textbook URL: http://www.pearsonhighered.com/educator/product/Compilers-Principles-Techniques-and-Tools/9780321486813.page (Fall 2012, Fall 2014), http://www.cengage.com/search/productOverview.do?N=16+4294962468+4294962467 (Fall 2013, Fall 2015, Spring 2016, Fall 2016)
Prerequisites by Topic:
- Skill at programming in C or C++, including scope and recursion, and understand the process of edit/compile/debug cycle.
- Understand pointers for the recursive construction and traversal of trees
- Understand debugging of pointer and memory allocation errors
- 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, differences 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
- Language standards
- The role of a compiler in the world of software
- Organization of a compiler
- Bison & Flex
- Formal language theory incl. RE, BNF, EBNF, grammars and their organization
- How to control derivation of sentences
- Finite State Automata
- Some UNIX tools (make, tar, etc)
- LL and LR parsers including LALR and SLR parsers and how they work
- First and follow sets
- Syntax trees
- Tree annotation
- Nice error reporting in a lookahead parser
- Attribute grammars
- Ambiguity and how to avoid it
- Controlling precedence
- Dangling else
- Shift reduce conflicts
- Reduce reduce conflicts
- Error handling via the error token mechanics
- Memory allocation for variables and procedures
- Scoping of variables
- Procedure call implementation and frames
- Global variables
- Type checking
- Expression compilation
- Code generation
- Code optimizations including intermediate representation optimization, and backend optimizations such as instruction selection and scheduling and register allocation, peephole optimization, variable length data allocation
Note: the primary Student Outcomes for this course are (b), (c), (i), and (k), all Emphasized.
- 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 (j).
- 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).
- Understand 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).