- Major phases of a compiler; what the phases do; data flow between phases.
- Formal definition of a grammar; chart about grammar classes.
- Regular languages: grammar definitions, uses; local ambiguity: examples, ways to handle. Relationship of finite automata and regular grammars; linear nature of a derivation from a regular grammar.
- Regular expressions: definition; be able to construct a regular
expression for a language, or to describe the language denoted by
a regular expression. Regular expressions and finite automata can also
describe regular languages.
`lex`constructs a table-driven finite automaton from regular expressions. - Lexical analyzer: what constructs are parsed;
`lex`. - Context-free languages: grammar definition; stack needed for parsing. Notations for defining the syntax of a language: BNF, Yacc, Pascal-style transition diagrams. Ambiguous grammars vs. unambiguous grammars. Augmented transition network; Yacc. Context-free language features include recursion, balanced parentheses, counting.
- Derivation from a context-free grammar: relationship to parse tree, notations for a derivation, definition of a language in terms of derivations.
- Operator precedence grammar and parser: definitions; precedence numbers, associativity. How operator precedence parser works (be able to work an example).
- Top-down parsing: definition; why backup may be required; for what kinds of languages does it work well; recursive descent parser; problems with left recursion; left factoring; implementation of top-down parser by a recursive program: be able to write a procedure for a construct such as an IF statement.
- Shift-reduce parser: use of stack; four actions of shift-reduce parser.
- Symbol tables: methods of organization; speed, advantages, disadvantages of each; comparisons; be able to select a method for a particular application. Search is more frequent than insertion. Symbol tables for lexical scoping in block-structured languages. What things are put in symbol tables? Kinds of symbols in a compiler. Methods of storing identifier names.
- Data area and base-offset addressing; storage allocation algorithm; allocation of data in records; word alignment and padding; variant records.
- Address calculations for array references (know the formulas). Address calculations for access to fields of a record; determining types of accesses to parts of a structure. Be able to calculate the size of an array of records; be able to calculate the address offsets for access to an array element and record field.

abstract syntax tree (AST) | accepting state | address alignment |

alphabet | ambiguity | ambiguous grammar |

arity | associativity | augmented transition network (ATN) |

AVL tree | base address | basic type |

BNF | bottom-up parsing | cascading errors |

cast | character class | Chomsky hierarchy |

CKY chart parser | code generation | collision |

compile-time | concatenation | context-free grammar |

controllability | data area | declaration |

derivation | deterministic finite automaton | disambiguating rules |

dynamic | enumerated type | equivalent grammars |

error production | finite automaton | fix |

fixed-point | float | floating-point |

grammar | hash function | hash table |

hash with buckets | infix | insertion |

intermediate language | Kleene closure | language denoted by a grammar |

left-associative | left recursion | left factoring |

leftmost derivation | lexeme | lexer |

lexical analysis | mnemonic | NaN |

nondeterministic finite automaton | nonterminal | object language |

observability | offset | operand |

operator | optimization | padding |

parse tree | parsing | pass |

postfix | precedence | prefix |

preorder | production | recognizer |

record | recursive descent | reduce |

reduce-reduce conflict | reduction step | regular expression |

regular grammar | regular language | rehash |

reserved word | right-associative | scalar type |

scope | semantics | shift |

shift-reduce parser | shift-reduce conflict | significand |

SNaN | sound | sound type system |

start symbol S | static | storage allocation |

string | subrange | substring |

suffix | symbol table | syntax |

syntax-directed translation | synthesized translation | table lookup |

terminal | token | top-down parsing |

top-down filtering | type | type constructor |

type lattice | unary | variable |

variable declaration | variant record | white space |

yacc |