CS 3040, Exam 2 Review

The exam will be open-book, open-note, but individual (with no discussion on exam content with anyone until the exam is graded).

Review questions (for reference only - the exam may include other topics!):
  1. Week 4
  2. Give two primary reasons why program input needs to be parsed (remembering a compiler is just a program!).
  3. Using BNL, give a parse tree for "10.01"
  4. Why not use written languages (Mandarin, English, French, etc.) to define the syntax of programming languages?
  5. Give another example of a metalanguage besides BNF or EBNF.
  6. 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 (⟨...⟩)
  7. Extend the "classic expression grammar" (slide 10 in the notes) to include calling functions with multiple arguments.
  8. 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?
  9. Using the expression grammar in the notes, give a derivation sequence for 3 + 4 * 5.
  10. Give a CFG (formally defined) for anbn.
  11. Give a railroad diagram for anbn.
  12. Give an ambiguous grammar for 1*. (You might have to ask your instructor for help on this one!)
  13. Week 5
  14. Give a left-recursive grammar for a*, then give a right-recursive grammar for a*.
  15. Pick two features of the grammar for C or C++ that negatively impact reliability.
  16. Pick two features of the grammar for Java that negatively impact reliability.
  17. Briefly explain why all regular expression languages (using the core with just sequence, |, and *) have context free grammars.
  18. Week 6
  19. Explain two sentences how to write a recursive descent parser.
  20. Explain in two sentences how a bottom-up parser works (assuming the viewer knows what a bottom-up parser is).
  21. Explain in two sentences how a top-down parser works (again, assuming the viewer knows what one is).
  22. 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++.
  23. Suppose a grammar has n productions, what is the maximum size of the stack (z in the notes) with a bottom-up parser?
  24. Week 7
  25. Write a Haskell function that uses pattern matching and recursion to return whether a list has an even length. Do not use length.
  26. Why is is_empty x = (length x) == 0 a bad idea?
  27. A restaurant has two menus, one for lunch and one for dinner. Each menu is a list of food items. Create a type to track the two types of menus, and use that type to write a function that takes a list of menus and counts the number of ones for dinner.
  28. 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.
  29. Week 8
  30. 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.