CSE 401, Wi10:  Midterm Topics

CSE Home

About Us

Search

Contact Info

The midterm is Friday Feb 19 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. The exam is closed book, closed notes, etc., except that you may bring one sheet of paper with any handwritten notes you wish.

I. Overall Compiler Organization

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

II.  Lexical Analysis

• Terminology

  • tokens
  • principle of longest match

• 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

• Grammars and LL(1) parsing

  • LL(k) property - disjoint FIRST sets
  • ambiguity & fixes
    • 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.
• FIRST, FOLLOW, and NULLABLE
• SLR(1) vs LR(0)
• Using ambiguous grammars and precedence rules in parser generators

IV.  Semantic Analysis

• Type checking basics

  • examples
  • attribute framework for describing static semantics

• Symbol tables

  • typical information recorded for names
  • scopes: when created, how used, why have them
  • general organization for MiniJava (global, per-class, and per-method information)

• Strong, weak, static, dynamic typing

• Type equivalence

  • structural vs name

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