CSE 401/M501 24au 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.

The exam will be closed book, except that you may have one 5x8 (or smaller) index card with whatever notes you wish written on both sides for reference. The notes must be hand-written, i.e., no computer printouts, no scanned/reduced notes, and no electronic devices or other technology.

• 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, principle of longest match, etc.
• 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
• Compiler project phases that have been completed so far (scanner, parser, AST/visitor). Do not memorize code or similar details; reference information will be provided if needed to answer specific questions.
• Static semantics: There likely will be some basic overview questions on these concepts based on lectures, but the midterm will not include details that won't be encountered until implementing the next phase of the project.
  • Typical kinds of conditions that are tested/verified in the semantics pass and semantics check organization based on abstract grammar (i.e., ASTs)
  • General symbol table organization and representation of type information for languages like MiniJava