CS 3723  Programming Languages  Spring 2014
Mid-Term Exam     Topics and Review

Exam date/time: Thursday, 6 March 2014, 11:30 am - 12:50 pm.

---

1. Introductory material: Contrasts and Compiler Phases.
   Type of Question: Given a specific contrasting pair, explain the contrast.

   ---

2. 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.

   ---

3. 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.

   ---

4. R-D Parsers: Recursive Descent.
   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).

   ---

5. Tiny Parser:
   Type of Question: Similar to the previous item, only specific for this parser.

   ---

6. 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 conventions 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 load 3.0 into register $f4. Give a command to load the value already in b into register $f6.

   ---

7. Regular Expressions:
   Type of Question: Give an intuitive description of the language described by the regular expression ab*(c|d*). Give 6 distinct strings accepted by this language, where no symbol appears more than once.

   ---

8. RPN:
   Type of Question: Translate a given ordinary arithmetic expression to RPN: What is the RPN form of
   (2 + 3)*(4 + 5)?

   Type of Question: Evaluate a given regular expression: Find the value of the RPN expression: 23+45+*.

   Type of Question: Describe briefly and roughly the code we added to our parser for arithmetic expressions so that it would translate to RPN.

   ---

9. Tiny Compiler:
   Favorite Question: Consider the functionA() that handles assignment statements. What information from outside itself does this function use to output its MIPS statements. As specific as you can, say what statements are written out. What does A return? (A trick question, of the type I don't use on actual exams.)

   Favorite Question: Consider the function E(), and suppose it is handling a single addition. What information from outside itself does this function use to output its MIPS statements. As specific as you can, say what statements are written out. What does E return?

   Other Favorite Questions: Similar questions for the function W() that handles a while statement, or for the function I() that handles an if-then-with-optional-else statement.

   ---

10. Storage Management:
    Type of Question: What two mistakes can you make with explicit deallocation? Which one is more serious than the other? What is a memory leak? What is garbage?