CSE 401/M501 19au 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)
  • Analyzing regular expressions and DFAs to determine which languages (sets of strings) they accept
• 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: There may be some basic overview questions on these concepts based on lectures, but the midterm will not include details that won't be encountered until the next phase of the 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