Logo University of Washington Computer Science & Engineering
 CSE 401, Sp '03: Midterm Review
  CSE Home  About Us    Search    Contact Info 

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
    • why use an NFA? a DFA?
    • 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

  • Building a table-driven predictive parser

    • *PREDICT(nonterminal, input symbol)
    • *FIRST(RHS)
    • *FOLLOW(nonterminal)

IV.  Semantic Analysis

  • Type checking basics

    • examples
    • type checking algorithm: bottom up

  • 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

    * = less important

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