Know the phases of a compiler (scanner, parser, semantic analyzer, code generator, optimizer); know what each phase takes for input and produces as output (from lecture notes and book chapter 1).
Know what a scanner generator and parser generator take as input and produce as output
Know historical background about compiler development (from the lecture)
Be prepared to (formally and informally) define: language, derivation, ambiguity, regular expression, regular grammar, context-free grammars, Finite State Automaton, NFA, DFA
Know the four classes of grammars, and how they are used in compiler development
Be able to perform derivations and draw parse trees for a sentence, given a CFG
Given a regular expression, be able to discuss the language it defines, and create a FA that recognizes strings matched by the regular expression; given a description of a language, be able to write a regular expression that defines it
Know the process by which a set of regular expressions can be automatically converted to a scanner
Know practical issues involved in using scanner generators (keyword handling; ambiguity in reg exp’s, etc.)
Be able to compute the FIRST and FOLLOW sets for nonterminals, given a CFG
Be able to rewrite a grammar to remove left recursion
Know the different common parsing techniques available (Recursive Descent, LL, LR, ALL)
Be able to sketch a recursive descent parser for a grammar containing epsilon productions
Be able to create an LL(1) Parse Table
Be able to determine whether a grammar is compatible with LL(1) and recursive descent parsing techniques
Be able to perform an LL(1) parse