back to cs488-syllabus

CS488 - Teaching Material - Spring 2007

Lectures

  1. 3/26/07: Course overview. Compiler, Assembler and Linker. Frontend and backend of a Compiler. Lexical, syntax and semantic analysis, intermediate code generation, quadruples and intermediate code optimization. Code generation.

  2. 3/28/07: Regular expressions and regular definitions and corresponding JFlex syntax. Examples: specifying numbers and identifiers.

  3. 4/2/07: Lexical Analyzer generation. From regular expressions to DFAs. Use of JFlex. Design of a Tokenizer.

  4. 4/5/07: Syntax Specification: the role of the parser. Error types. Context Free Grammars. Leftmost derivations. Parse trees. Ambiguity.

  5. 4/9/07: Top-down parsing. Recursive top-down parsing. The problem of backtracking. Syntactic charts. A predictive parser for arithmetic expressions.

  6. 4/11/07: LL(1) grammars. First and Follow. Building the operators tree of an arithmetic expression during top-down parsing. Evaluation of operators trees using postorder traversals.

  7. 4/16/07: Characterization of LL(1) grammars using First and Follow. Parsing tables. Nonrecursive predictive parsers.

  8. 4/18/07: Elimination of left recursion. Regular languages vs CF languages. Non context free languages.

  9. 4/23/07: Preparation to the Midterm.

  10. 4/25/07: MT.

  11. 4/30/07: Bottom-up parsers. Handles. Shift/reduce and reduce/reduce conflicts. LR-parsing. LR(0) items. Recognizing viable prefixes with a DFA.

  12. 5/2/07: SLR-Parsing Tables. LR(1) items. Canonical LR(1) Parsing Tables.

  13. 5/7/07: LALR-Parsing Tables. Using ambiguous grammars.

  14. 5/11/07: Use of CUP. CUP-JFlex interoperability. Coping with ambiguity. Precedence and associativity. Actions and attributes.

  15. 5/14/07: Syntax Directed Translation. Syntax Directed Definitions (SDDs). Synthesized attributes and inherited attributes. Annotated Parse trees. Order of evaluation. Dependency graphs and topological sorts.

  16. 5/16/07: S-attributed SDDs and L-attributed SDDs. Syntax Directed Translation-Schemes (SDTs). SDT implementation of L-attributed SDDs. SDT evaluation during parsing. SDDs for Syntax Trees.

  17. 5/21/07: Types and Symbol Tables.

  18. 5/23/07: Static Semantics. Implementation issues. Intermediate Code generation.

  19. 5/30/07: Review of pj3. Preparation to the final exam: IMPORTANT see announcements.

Announcements

  1. 4/25/2007: MT
  2. The final exam is replaced with the Final project due next Tuesday at noon (posted Thursday, May 31st at 1:00pm).

Projects

  1. pj1. Due Monday, April 30th, 2007 at the beginning of class.
  2. pj2. Due Monday, May 14th, 2007 at the beginning of class. Extended to Wed.
  3. pj3. Due Monday, May 21th, 2007 at the beginning of class.
  4. Final. Due Tuesday, June 5th, 2007 at noon. Posted Thursday, May 31st at 1:00pm.

Downloads

  1. Tokenizer
  2. Calculator2006
  3. CalculatorCUP

Important Links

  1. Scanner Generator for Java: JFlex
  2. LALR Parser Generator for Java: CUP

CSNS - Computer Science Network Services

Assignments and exams should be uploaded by the due date through the CSNS - Computer Science Network Services website. If you have never used this system before then follow the instructions for students.