Computer Science 3675
Summer 2002
Answers to practice questions for quiz 1

The answers are in bold blue

  1. Write a clearly legible T to the left of each of the following that is true, and a clearly legible F to the left of each that is false. (Note: I have written the answers after the question instead of before because that is easier to typeset. When you answer questions like this, please write your answer to the left of the question.)

    1. All compilers translate to machine language. F
    2. All programming language implementations are compilers. F
    3. A garbage collector based on reference counts cannot collect cyclic structures. T
    4. A simple value is a value that has no visible internal structure. T
    5. Characters are typically considered complex values. F
    6. A data structure that changes over time is not considered to be a value. T
    7. A token can only have one associated lexeme. F
    8. A variable name is typically a single lexeme in a program. T
    9. Backus-Naur Form is a notation for giving precise definitions of syntax. T

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

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

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

    Random access and reduced memory requirements for individual lists are important advantages.

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

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

    It suffices to show two different parse trees for string aa. Here they are. 

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

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

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

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

    x = 7, y = 98.