CSE 401, Au10:  Midterm Topics

CSE Home

About Us

Search

Contact Info

The midterm is Friday Nov. 5 during class.

All topics from the beginning of the course up to, but not including, semantic analysis are fair game. Lectures, homework, and the MiniJava project are all potential sources for exam questions. 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 parsing

  • LL(k) property - disjoint FIRST sets
  • ambiguity & fixes
    • rewrite grammar
    • change language
  • common prefixes (left factoring)
  • left recursion

• Bottom Up LR 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

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