Solutions -- programming language principles, part 1, CS 288, April 23, 2007

 

    1. FIRST(S) = {a, the}. FIRST(VP) = {arrived, saw, chased}. FOLLOW(VT) = {a, the}. FOLLOW(Det = {big, dog, cat}.

    2. They are used "to label the arms of the case statements in the functions that process the nonterminals of the grammar.

    3. They are used to construct the table that drives the parsing algorithm.

    4. They are used to construct the table that drives the parsing algorithm.

     

    1. The value is 2 + 3 + 4 + 0, or 9.

    2. Since C allows pointers to functions to be passed as arguments, a pointer to the comparison function could be passed to the sorting function.

    3. Java can and does include a compare method (of two explicit arguments) in its Comparator interface. The sort method can thus invoke this method to compare any two values of the input list.

    4. In Scheme, the environment of a function f would be initialized when the define function is invoked for f. The appropriate environment for f's closure is simply the current environment at this point, and is thus initialized to refer to this environment.

    5. C does not allow nested function definitions, so that the relevant environment does not differ from function to function.

     

    1. A frame is a portion of memory that at run time hold local variables and other information related to a particular block of code. A frame pointer points to a known location within a frame. A given local variable can be stored at a fixed location relative to the value of the frame pointer. Since accessing local variables is done frequently at run time, it's more efficient to keep the frame pointer in a register than in memory.

    2. Memory access is expensive, but less so for cache access than for other areas of memory. So for example in the event of a cache miss for a read operation, other instructions in the pipeline that are waiting to consume the value to be read may have to wait for many cycles for the value to be found. Unlike the case of a cache hit, it's unlikely that the waiting time can be filled profitably by reordering of instructions.

    3. Three possibilities are: resource hazards, data hazards, and control hazards. See Scott, p. 211 (or pp. 227-8 of the first edition).

      1. Instructions that take different amounts of time complicate instruction scheduling.
      2. Pipelining requires quick access to the next instruction in sequence. If instructions have different lengths, significant computation is generally required to determine where the current instruction ends and the next one begins. Fixed-length instructions of an appropriate length can also allow branch instructions to access more memory, since instructions can be aligned in memory.

    5. A condition code is a bit that is set or cleared based on the results of a particular instruction (e.g., did it give overflow, a value of 0, etc.). Since condition codes are modified by most instructions, reordering of instructions during code optimization becomes very difficult.