CS 445

From CS Wiki
Jump to: navigation, search

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

  1. Types of language translation
  2. Language standards
  3. The role of a compiler in the world of software
  4. Organization of a compiler
  5. Bison & Flex
  6. Formal language theory incl. RE, BNF, EBNF, grammars and their organization
  7. How to control derivation of sentences
  8. Finite State Automata
  9. Some UNIX tools (make, tar, etc)
  10. Tokens
  11. LL and LR parsers including LALR and SLR parsers and how they work
  12. First and follow sets
  13. Syntax trees
  14. Tree annotation
  15. Nice error reporting in a lookahead parser
  16. Attribute grammars
  17. Ambiguity and how to avoid it
  18. Controlling precedence
  19. Dangling else
  20. Shift reduce conflicts
  21. Reduce reduce conflicts
  22. Error handling via the error token mechanics
  23. Memory allocation for variables and procedures
  24. Scoping of variables
  25. Procedure call implementation and frames
  26. Global variables
  27. Type checking
  28. Expression compilation
  29. Code generation
  30. Code optimizations including intermediate representation optimization, and backend optimizations such as instruction selection and scheduling and register allocation, peephole optimization, variable length data allocation

Course Outcomes

Note: the primary Student Outcomes for this course are (b), (c), (i), and (k), all Emphasized.

  1. Apply knowledge of context free grammars to language translation and file parsing problems (a).
  2. Write and integrate a scanner, parser, semantic analyzer, and code generator into a simple working compiler (j).
  3. Use a lexical analyzer and parser generator to write and compile a front-end for a compiler (k).
  4. Understand scanners and how they are defined (b).
  5. Demonstrate proficiency with regular expressions and lexical analysis techniques (a).
  6. Understand parsers and how they are defined ( b).
  7. Understand recursive descent and related LL parsing algorithms (b).
  8. Know and use LR parsing theory and methods (j).
  9. Understand semantic analysis principles (i).
  10. Use synthesized and inherited grammar attributes (a).
  11. Employ symbol tables and implement type checking algorithms (i).
  12. Demonstrate knowledge of principles of intermediate and final code generation (i).
  13. Understand instruction selection and register allocation (j).
  14. Understand common optimizations (j).