Programming language principles, part 1
CS 288
May 11, 2005

 

  1. Recall that in Ada, modules are implemented as packages (not to be confused with Java packages). Ada package headers (also known as package specifications) are similar but not identical to C++ headers. A package header and a package body may be separated into different compilation units in Ada. A typical use of a package header is to define types; an example from Scott is reproduced below. The part of the header before the private keyword is public. 
       package foo is            -- header
     ...
     type T is private;
     ...
   private                   -- definitions below here are inaccessible to users
     ...
     type T is ...           -- full definition
     ...
   end foo;
    a) Suppose that a package body is changed. Should a user of the package ever need to have its code changed? Should this user ever need to be recompiled? Give a brief justification of your answers.

    b) Suppose that the public part of a package header is changed. Should a user of the package ever need to have its code changed? Should this user ever need to be recompiled? Give a brief justification of your answers.

    c) Suppose that the private part of a package header is changed. Should a user of the package ever need to have its code changed? Should this user ever need to be recompiled? Give a brief justification of your answers.

    d) If definitions like that of type T in the example are inaccessible to users, why do they appear in the package header rather than the package body?

     

  2. Using the top-down attribute grammar with start symbol E and productions given below, consider the parsing of the string (1+2).

    a) Show the parse tree, without attributes, for this string.

    b) Show the partially constructed parse tree and the values of all relevant attributes immediately after the application of the rule F → ( E )

    c) Show the partially constructed parse tree and the values of all relevant attributes immediately after the application of the rule TT1 → + T TT2

    d) Show the final parse tree and the values of all relevant attributes.

    In (b)-(d), you needn't show leaves of the final parse tree (that is, nodes that correspond to terminal symbols or to ∊). 

    
E → T TT
    ⊲ TT.st := T.ptr
    ⊲ E.ptr := TT.ptr
TT1 → + T TT2
    ⊲ TT2.st := make-bin-op ("+", TT1.st, T.ptr)
    ⊲ TT1.ptr := TT2.ptr
TT → ∊
    ⊲ TT.ptr := TT.st
T → F FT
    ⊲ FT.st := F.ptr
    ⊲ T.ptr := FT.ptr
FT1 → * F FT2
    ⊲ FT2.st := make-bin-op ("*", FT1.st, F.ptr)
    ⊲ FT1.ptr:= FT2.ptr
FT → ∊
    ⊲ FT.ptr := FT.st
F1 → - F2
    ⊲ F1.ptr := make-un-op ("-", F2.ptr)
F → ( E )
    ⊲ F.ptr := E.ptr
F → const
    ⊲ F.ptr := make-leaf (const.val)

     

  3. Some languages, like Java, provide automatic garbage collection. Other languages, like C, do not.

    a) What is the problem that garbage collection is intended to solve?

    b) In C, how is this problem solved?

    c) Give an advantage and a disadvantage of using garbage collection.

    d) Give an example and a brief description of a garbage collection algorithm.