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

The midterm is Friday Feb 8th during class.

All topics from the beginning of the course up through semantic analysis are fair game. 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

    • lexeme, token, pattern

  • Regular expressions

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

  • Scanners

    • 4 steps: RE -> NFA -> DFA -> code/tables
    • constructing an NFA
    • constructing a DFA

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

    • 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

IV.  Semantic Analysis

  • Type checking basics

    • examples
    • type checking algorithm

  • Symbol table

    • attributes for each type of symbol
    • 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 cs.washington.edu]