CS 3723 Programming Languages  Fall 2013
Mid-Term Exam     Topics and Review

Note: Review changed on 2013-10-14, at 7 pm.

---

1. Introductory material: Contrasts and Compiler Phases. (Probably no questions.)

   ---

2. Languages: (A number of later questions will cover languages.)

   ---

3. DFAs and Subset Algorithm:
   Favorite Question: Given an NFA, use the subset algorithm to construct a DFA accepting the same language. (You would have to actually use the subset algorithm, and not just guess the DFA.)

   ---

4. Epsilon Closure:
   Favorite Question: Given an NFA with epsilon moves, determine the epsilon closure of a given set of states. (You will not have to follow the steps of the epsilon closure algorithm, but can determine the closure intuitively.)

   ---

5. Regular Expressions & NFAs:
   Type of Question: Given a regular expression, Use our algorithm from class to construct an NFA with epsilon moves that accepts the language described by the regular expression. (If I ask a question like this, it would have to be a small part of the general topic.)

   ---

6. RPN:
   Type of Question: Translate a given ordinary arith. expr. to RPN.

   Type of Question: Use a stack to evaluate an RPN expr. consisting of digit operands and operators.

   ---

7. Grammars:
   Type of Question: I might give you a grammar and ask questions about the grammar. (What are the names of the different parts? Give a derivation for a given sentence. Write the parse tree for a given sentence. What does it mean for the grammar to be ambiguous? Etc., etc.)

   Type of Question: I might give you a grammar and ask you questions about the language accepted by the grammar.

   ---

8. S-R Parsers:
   Favorite Question: I might give you a grammar, shift-reduce table, and input to use. Then I might ask you for the start of the SR parsing (not the whole parse). Or I might give you the parse up to a certain point and ask you to continue it.

   ---

9. R-D Parsers,:
   Favorite Question: I might give you a grammar and ask you to show the code for part of the RD parser for this grammar, say for one of the functions (corresponding to one of the non-terminals).

   ---

10. Tiny Parser: (I can't think of any reasonable questions here.)

    ---

11. MIPS Assembly Language:
    Type of Question: Explain roughly how one multiples two numbers from memory and leaves the result back in memory. (The syntax doesn't have to be exact.)

    Type of Question: Using our convensions for storing a constant digit and a variable in memory, where would one find the number 3.0 in memory? Where would the variable c be stored in memory? Give a command to loaad 3.0 into register $f4. Give a command to load the value already in b into register $f6.