CSCI 310 - Topics for Midterm - Spring 2008

• Regular expressions
• DFAs
• Constructing NFAs from regular expressions
• Converting NFA -> DFA
• Basic structure of scanner
• CFGs
• Issues of ambiguity, precedence, associativity in CFG
• Recursive descent/predictive parsing
• LL(1) grammars - characteristics
• Constructing First/Follow/Lookahead sets
• Eliminating left recursion, left factoring
• LR parsing – LR(0) mainly but also what makes a grammar not LR(0)
• Abstract Syntax Trees
• Arithmetic precedence and associativity in syntax trees (not how to create during parsing, but how it is reflected in tree)
• Overview of compiler processing - purpose of each stage, input/output
• Be able to tell the difference between errors caught by scanner and parser