CS 445

From CS Wiki
Jump to: navigation, search

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)

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)

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

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

Course Outcomes

  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 (k).
  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. Undersand 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).