CS 3040, Exam 2 Review, 2022

The exam will be closed-book, closed-note. You can bring a single page (up to 8.5 by 11) of notes, front and back.

Review questions (for reference only - the exam may include other topics!):
  1. Review answers for the matrix programming language grammar.
  2. Define a Haskell type for
    • Full names (first, last, middle)
    • A course roster, including the major (eg: "SE" or "CS"), the course number, and all students, where each student is specified by their full name
  3. Give two primary reasons why program input needs to be parsed (remembering a compiler is just a program!).
  4. Using BNL, give a parse tree for "10.01"
  5. Why not use written languages (Mandarin, English, French, etc.) to define the syntax of programming languages?
  6. Give another example of a metalanguage besides BNF or EBNF.
  7. Create a grammar (a CFG) for the language captured by the regular expression (0|1)*1(0|1)*. Specify the grammar formally using a quadruple (⟨...⟩)
  8. Extend the "classic expression grammar" (approximately slide 10 in note 3) to include calling functions with multiple arguments.
  9. A CFG is formally described as a quadruple with the fourth item being the start non-terminal. Why can't we just assume the first non-terminal is the start symbol?
  10. Using the expression grammar in the notes, give a derivation sequence for 3 + 4 * 5.
  11. Give a CFG (formally defined) for anbn.
  12. Give a railroad diagram for anbn.
  13. Give an ambiguous grammar, written in BNF, for 1*.
  14. Give a left-recursive grammar for a*, then rewrite it as a right-recursive grammar.
  15. Give a proof that any regular expression (using just sequence, |, and *) can be written as a context free grammar written using just BNF (that is, productions without regular expression notation like * and |).
  16. In two sentences, explain how to write a recursive descent parser.
  17. Explain in two sentences how a bottom-up parser works (assuming the reader knows what a bottom-up parser is).
  18. Explain in two sentences how a top-down parser works (again, assuming the reader knows what one is).
  19. Write a recursive descent parser for the CFG ⟨{X}, {a}, {X → a X a, X → b}, X⟩ assuming you have a next_token method that returns the next token (a character, in this case) and advance that advances to the following token. Write the parser in C++.
  20. Is there a bound on the size of the stack to_match (z in the notes) for a bottom-up parser?
  21. Write a Haskell function that uses pattern matching and recursion to return whether a list has an even length. Do not use length.
  22. Why is is_empty x = (length x) == 0 a bad idea?
  23. A restaurant has two menus, one for lunch and one for dinner. Each menu is a list of food items. Create a Haskell type to track the two types of menus, and use that type to write a Haskell function that takes a list of menus and counts the number of ones for dinner.
  24. Using Haskell, write a recursive descent parser for the CFG ⟨{X, Y}, {a, b, c}, {X → aY, X →c, Y → bX}, X⟩. The function should take a list of characters (a string) such as "ababc" and return True if the string is accepted by the grammar and False otherwise.
  25. Modify nats.hs to include a subtraction operation so that 
            subst (Succ (Succ (Succ Zero))) (Succ (Succ Zero))
    gives (Succ Zero) (that is, 3 - 2 gives 1). If the second argument is greater than the first, return Zero.
  26. Select an ANTLR specification file and name all of the elements in that file.
  27. Explain ad-hoc vs. operational semantics. Give an advantage of each.