CSE 401 15wi Midterm Exam Topic List

This list is a summary of the topics we've covered in class so far that could potentially be on the midterm. Generally, if you've kept up with everything that's been covered in lecture, sections, homework assignments, and the compiler project you should be well prepared.

  • Interpreters and compilers - key differences
  • Gross structure of compilers - tasks of front/middle/back ends
  • Basic notions of grammars - productions, terminals, non-terminals
  • Regular expressions and DFAs
    • Standard regular expression operators
    • Writing regular expressions to generate specific languages
    • Constructing DFAs to recognize regular languages (but you are not responsible for the detailed RE -> NFA -> DFA construction algorithms)
  • Scanners - transforming character streams to token streams
  • Context-free grammars
    • Derivations, leftmost, rightmost, etc.
    • Constructing grammars to generate languages
    • Ambiguity
    • First, follow, and nullable
  • LR parsing
    • Shift-reduce parsing
    • Construction of LR(0) and SLR parsers and tables
    • Items, item sets, and parser states
    • Shift-reduce and reduce-reduce conflicts and how to deal with them
    • Differences between LR(0) and SLR parsers
  • LL and recursive-descent parsers
    • Predictive parser operation and grammar requirements (disjoint first sets)
    • Constructing hand-written recursive-descent parsers
    • Grammar problems and fixes for LL parsing - left recursion, left-factoring common prefixes, etc.
  • Abstract Syntax Trees (ASTs) and the visitor pattern
  • Static semantics - know the basic issues from lecture, but you will not be tested on details that you will encounter in the next phase of the compiler project
    • Typical kinds of conditions that are tested/verified in the semantics pass
    • Attribute grammar general concepts
    • General symbol table organization for languages like MiniJava