Com Sci 221 _ Programming Languages

                       Assignment #2 _ Winter 1993

                           Due Monday, January 25


1.  Do problem 1.1 c on p. 21 of the text.


2.  Do problem 1.2 on pp. 21 of the text. Explain briefly but as precisely as possible the

    significance of the concepts Expression, Term, and Factor.


3.  Do problems 2.2, 2.3, and 2.4 on p. 59 of the text, but only parts c, d, and e.


4.  We saw in class that, although the stack implementation of expression evaluation is

    designed primarily for left-to-right innermost evaluation, it allows certain types of

    outermost evaluation (called "selective evaluation" in the text), such as that required

    to produce the usual behavior of conditionals under the set of rules


                              ifT then ff elsefi  =)  ff


                              ifF then ff elsefi  =)  fi


    and the slightly unusual, but extremely useful, behavior of and and or under the set

    of rules

                                  F and fi  =)  F


                                   T and fi  =)  fi


                                   T or fi  =)  T


                                   F or fi  =)  fi


    Comment on the problems involved in trying to do outermost evaluation on a stack

    with sets of rules such as

    (a)


                                     ff orT  =)  T


                                      ff orF  =)  ff

    (b)


                                     ff orT  =)  T


                                      T or fi  =)  T


                                     F or F  =)  F

     (c)


                                if ff then fi elsefi  =)  fi


                                if T then ff elsefi  =)  ff


                                if F then ff elsefi  =)  fi



                                       1

    This is a deliberately open-ended question. You will get more credit the more insight

    you can generate about why each set of rules is not only problematic, but more prob-

    lematic than the ones before.  Long answers, however, are not recommended.  It is

    possible in each case to get the essential points in a few sentences.


5.  Imagine a small company office with only 10 employees, numbered 1-10 (to imitate

    the impersonal charm of a large corporation).  Each employee has a supervisor, but

    not necessarily within the local office.  The number of the ith employee's supervisor

    is given by the array element supervisor[i], where an entry larger than 10 indicates a

    supervisor outside the local office. Similarly, the number of employees supervised by

    employee number i is given by the array element employees[i].  You wish to find an

    employee whose supervisor is in charge of only that one employee. The basic structure

    of your program to find a solution should be


        i := 1;

        While i   10, but the  ith employee's supervisor has other employees do

              i := i+1

        end while


    Realize the structure above as well as you can in Pascal and C. You should do better in

    C, by using the conditional forms of and and or (written "&&" and "k"). Demonstrate

    your programs on an interesting set of inputs.


6.  Look up the precedence and associativity rules for the binary integer and boolean

    infix operators of Pascal and C, as well as the unary minus. Compare the two. Find

    examples of textual expressions that denote different abstract syntax trees in the two

    languages (ignoring any differences between symbols used for the same operation).

    Discuss the relative advantages and disadvantages of each interpretation.

                                       2