image University of Washington Computer Science & Engineering
 CSE 401, Wi09:  Midterm Review
  CSE Home   About Us    Search    Contact Info 

The midterm is Friday Feb 13th during class.

All topics from the beginning of the course up through semantic analysis are fair game, although not the minijava code for typechecking. The following is a list of the main things we've covered.

I.  Overall Compiler Organization

  • what's in the front/back end
  • what the job of each phase is

II.  Lexical Analysis

  • Terminology

    • token, pattern

  • Regular expressions

    • the notation
    • how you build them, concrete examples
    • advantages
    • limitations
    • naming them

  • Scanners

    • Regular expressions and DFAs. You are not responsible for the details of the RE -> NFA -> DFA construction.

III.  Syntactic Analysis

  • Context-free grammar

    • BNF: terminals, nonterminals, productions
    • how you build them, concrete examples
    • advantages
    • limitations

  • Derivations

    • abstract vs. concrete (parse) syntax trees

  • Parsing algorithms

    • top-down vs. bottom-up
    • predictive parsing
    • table-driven & recursive descent implementations
  • LL(1) grammars

    • LL(k) property - disjoint FIRST sets
    • ambiguity & fixes
      • meta-rules (code/precedence tables)
      • rewrite grammar
      • change language
    • common prefixes (left factoring)
    • left recursion
  • Bottom Up LR(0) Parsing

    • Building a LR(0) DFA
    • Building a LR(0) parse table
    • Shift-reduce parsing using an LR(0) parse table
    • Dealing with shift-redue and reduce-reduce conflicts.
    • SLR(1) vs LR(0)
    • Using ambiguous grammars and precedence rules in parser generators

IV.  Semantic Analysis

  • Type checking basics

    • examples
    • type checking algorithm

  • Symbol table

    • typical information recorded for names
    • scopes: when created, how used, why have them
    • handling procedures
    • handling records

  • Strong, weak, static, dynamic typing

  • Type equivalence

    • structural vs name


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to rea at]