Computer Science 3675
Section 001
Fall 2009
Practice questions for quiz 4

1. What is Backus-Naur Form, and what is it used for?

2. Show a parse tree for string aacacab according to the following grammar, where the start symbol is <S>.

       <S> ::= <F> a <S>
            |  b
       <F> ::= a <F>
            |  c
     

3. Show that the following BNF grammar is ambiguous. The start symbol is <S>.

       <S> ::= <S> a
            |  a <S>
            |  a
     

4. Write a BNF grammar for sequences of left and right parentheses that are balanced. A sequence of parentheses is balanced if parentheses match and are well nested. For example, (()(())) is balanced, but )( and ())()( are not balanced.

5. What is one important motivation for including exception handling in a programming language?

6. Are backtracking and exception handling the same thing? For example, can you use the exception handling mechanism of Java to do backtracking?

7. Using backtracking, write a Cinnameg program fragment that will print all solutions (x,y) to equation xy - 2x² + y = 10, where x and y are both integers in the range 0,...,100. Do not use a loop or recursion. Your program fragment can fail when it is done.

8. Unification is a form of pattern matching. Which of the following is not a characteristic of unification?

   1. Unification never changes the binding of a bound variable.
   2. Unification is symmetric; unifying A with B has exactly the same effect as unifying B with A.
   3. Unification is very slow, and is only used rarely during computations of logic programs.
   4. Unification can bind unbound variables.