Each student will be able to:

• Given a regular expression, build an equivalent non-deterministic finite-state automata (NDFA)
• Given an NDFA, build an equivalent deterministic finite-state automata (DFA)
• Given a DFA, build an equivalent minimal DFA
• Given a context-free grammar (CFG), build the recursive-descent parser for that grammar.
• Given a context-free grammar (CFG), build the LR(0) itemsets for that grammar.
• Given a context-free grammar (CFG), build the LR(1) itemsets for that grammar.
• Given the the LR(1) itemsets for a context-free grammar, build the LALR(1) itemsets for the same grammar.
• Given a context-free grammar (CFG) and the LR(0) itemsets for that grammar, build the LR(0) parse table for that grammar.
• Given a context-free grammar (CFG) and the LR(0) itemsets for that grammar, build the SLR parse table for that grammar.
• Given a context-free grammar (CFG) and the LR(1) itemsets for that grammar, build the LR(1) parse table for that grammar.
• Given a context-free grammar (CFG) and the LALR(1) itemsets for that grammar, build the LALR(1) parse table for that grammar.
• Given a context-free grammar (CFG) language that supports:
  • Input and output
  • Integer data and variables
  • Arrays
  • Assignment statments
  • IF statments
  • Loops
  • Function calls
  write a functioning compiler using lex and yacc (or flex and bison) for that imperative programming language. This compiler will generate correct executable assembly code on the department CSP machine(s).
• Given naive intermediate code for a C loop, hand-optimize the code, reducing by at least 20% the number of intermediate code instructions needed while maintaining semantic correctness of the program.
• Define "register assignment" in the context of a compiler. Explain why register assignment is an important compiler optimization.
• Given a basic block, represented by both the live-out set for the block and the list of three-address statements, in order, determine the set of variables live at each statement of the block.
• Consider graph-coloring register assignment. Given a list of statements for a function, with each statement annotated with the set of those symbolic registers live at that statement, build the register interference graph for that function.
• Consider graph-coloring register assignment. Given a matrix representation of the register inteference graph for the function, and the number of "physical" registers available, color the interference graph such that each interference graph node has a different "color" than any of its neighbors in the graph.