Computer Science 3675
Fall 2005
Solutions to practice questions for quiz 1

1. Which of the following are true, and which are false?

   1. All compilers translate to machine language. False
   2. All programming language implementations are compilers. False
   3. A simple value is a value that has no visible internal structure. True
   4. Characters are typically considered complex values. False
   5. A token can only have one associated lexeme. False
   6. A variable name is typically a single lexeme in a program. True
   7. Backus-Naur Form is a notation for giving precise definitions of semantics. False
   8. Pattern matching can be used to bind names by solving simple equations. True
   9. The scope of a binding is that part of the program where that binding is in effect. True

2. What is a just-in-time compiler?

   A just-in-time compiler is a hybrid between a compiler and an interpreter where an interpreter compiles frequently used blocks or subprograms of a program, and uses the compiled versions of those blocks or subprograms for efficiency.

3. What is shadowing, and how can it occur? Give an example.

   Shadowing occurs when an identifier is bound within the scope of another binding of the same identifier. The more recent binding shadows the older one. Here is an example in C++.

       {int x;
        x = 3;
        {int x;
         x = 6;
        }
       }
     

   The inner binding of x shadows the outer one. (Both bindings of x are to variables, not to numbers.)

4. An implementation of a programming language is not normally considered to be an adequate definition of the language. Why not? What would be the consequences of using an implementation as a definition?

   Possible consequences:

   • The definition is very difficult to understand.
   • If there is a bug in the implementation, it cannot be fixed.
   • It is impossible to have partially defined features, such as an undefined order of evaluation of certain expressions.

5. What is an important advantage of the linked representation of sequences over the sequential representation?

   It is easy to extend sequences by adding values to the start. Also, the linked representation permits structure sharing, which sometimes greatly reduces memory requirements. There are other advantages, such as the ability to add values into the middle of the sequence.

6. What is an important advantage of the sequential representation of sequences over the linked representation?

   Random access (constant time indexing) and reduced memory requirements for individual lists are important advantages.

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

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

   To show that a grammar is ambiguous, you need to show two different parse trees for the same sequence of tokens. In this case, it suffices to show two different parse trees for aa. Here they are.

                S                       S
               / \                     / \
              S   a                   a   S
              |                           |
              a                           a
            
     

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

                                S
                               /|\
                              / | \
                             /  |  \
                            /   |   \
                           /    |    \
                          /     |     \
                         /      |      \
                        F       a       S
                       / \             /|\
                      a   F           / | \
                         / \         F  a  S
                        a   F        |     |
                            |        c     b
                            c 
                                      
     

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

   The following is an ambiguous grammar. The start nonterminal is B. I am using e for the empty string.

       <B> ::= <B> <B>
   
           |   ( <B> )
   
           |   e
     

   The following is an unambiguous grammar for the same thing. The start nonterminal is B.

       <B> ::= ( <B> ) <B>
   
           |   e
     

10. What is a solution to pattern match equation [x,y+1] = [7,99]?

    x = 7, y = 98.

11. What is the head of list [2,4,6]? What is the tail of list [2,4,6]?

    head([2,4]) = 2 and tail([2,4]) = [4,6].