Current thoughts on the exam

General comments:

1. The exam is not yet finished, but I have included below an outline of the kinds of questions I would like to ask. This is just a guideline. Do not expect the exam to be exactly what I have shown here.
2. I do not know yet if the exam as planned is too long or not.

Current question possibilities:

1. Regular expressions and finite automata.
   • Come up with a regular expression for ...
   • Use Thompson's construction to ...
   • Come up with and NFA for ...
   • Use subset construction to convert an NFA to a DFA.
   • Come up with an equivalent DFA that has a minimum number of states.
   • Which of the following regular expressions is equivalent to ...
2. Context free grammars.
   • Given a grammar, which set of strings does it generate?
   • Give a CFG for a language.
   • Given a grammar and string generated from the grammar, draw a parse tree and answer some questions about precedence and associativity.
3. Parsing.
   • Given a grammar, make it LL(1).
   • Augment a grammar for LR parsing.
   • Compute the First and Follow sets.
   • Compute the LR(0) item sets for an LR parser.
   • Construct the DFA from the item sets by computing the GoTo function.
   • Construct an LR(0) and/or SLR(1) parse table.
   • Trace an LR(0) and/or SLR(1) parse for a given input string.
4. Semantic processing.
   • Come up with an attribute grammar for ...
   • Answer some questions about type checking and symbol tables.
5. Code generation and runtime environment.
   • Given a program, show the runtime environment at a certain point during its execution. Include access and control links. Show the layout for your generic activation record.
   • What is the output of a program if parameters are passed by value, by name, or by reference?
   • show three-address code and/or P-code to a given program fragment
   • interpret a program in three-address code and/or P-code

Old Exams: