Computer Science 3675
Fall 2014
Practice Questions for Quiz 4

1. True or false.
   1. A token can only have one associated lexeme. Answer
   2. A variable name is typically a single lexeme in a program. Answer
   3. Most programming languages have a comment token in their grammars. Answer
   4. Most programming languages require two consecutive lexemes to be separated by a space or spaces. Answer
fall14

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

   Answer

3. Show a parse tree for string aacacab according to the following grammar, where the start nonterminal is S. In this grammar, upper case letters are nonterminals and lower case letters are tokens.

       S -> F a S
         |  b
   
       F -> a F
         |  c
   

   Answer

4. Show that the following grammar is ambiguous. The start symbol is S. Upper case letters are nonterminals and lower case letters are tokens.

       S -> S a
         |  a S
         |  a
   

   Answer

5. Write a grammar that describes 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.

   Answer

6. Scheme is a typeless language. What does that mean? Can type errors ever occur?

   Answer

7. What is the value of Scheme expression (car (cdr (cons 'horse (cons 'zebra '( )))))?

   Answer

8. What is the value of Scheme expression (cons 'salamander (list 'frog 'toad))

   Answer

9. Write a Scheme function called prefix so that (prefix x y) returns true if list x is a prefix of list y (and false if not). It is not necessary for x to be a proper prefix of y. Every list is a prefix of itself, and the empty list is a prefix of every list. Be careful to use Scheme syntax correctly.

   Answer

10. Write a Scheme function called descending so that (descending L) is true for a list of numbers L if L is in descending order. (The Scheme function < does a less-than test, and > does a greater-than test.) List (a b c d) is in descending order if a > b > c > d. The empty list is in descending order by definition, as is a singleton list. Be careful to use Scheme syntax correctly.

    Answer

11. Write a Scheme function called drop so that (drop n L) returns the result of removing the first n members from list L. If L has fewer than n members, then (drop n L) should return the empty list. For example, (drop 2 '(4 8 3 5 7)) = (3 5 7) and (drop 3 '(5 2)) = ( ). Be careful to use Scheme syntax correctly.

    Answer

12. Write the filter function in Scheme. That is, write a filter function so that (filter f L) returns a list of all members x of list L such that (f x) is not #f. Be careful to use Scheme syntax correctly.

    Answer