Computer Science 3675
Fall 2003
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 semantics. F

  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 of a program, and uses the compiled versions of those blocks for efficiency.

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

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

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

  6. Explain what fragmentation is, and how a garbage collector can eliminate it.

    Fragmentation occurs when there is plenty of free memory, but it is cut up into small blocks so that it is not possible to find a single large block. Eliminating fragmentation requires moving used blocks so that they are together, which makes it possible to coalesce the free space into a single large block. Moving the blocks requires relocating pointers, since each pointer must refer to the new location of an item, not to the old location.

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

  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]? What is the tail of list [2,4]?

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