Homework 2
                     Due 2/20/98 in class 

Note: Questions or discussion should be directed to the class newsgroup.

(1) Let's try something like the exam question again:
(a) Write a grammar that will unambiguously parse expressions involving
identifiers and the following operators, with the indicated precedence
levels:

    Precedence:  Highest:  ()
                           **
                           * /
                 Lowest:   + -

   Associativity: Left-to-right

(b) How would your grammar have to change to make the associativity of **
be right-to-left?

(2) Consider the following Prolog code added to what you were given for
programming assignment 1.

  scheduleCourse(section(C,S),Time,Lecturer,Location) :-
      lectureTime(Time),not(busy(Lecturer,Time)),roomOpen(Time,Location).
  busy(Lecturer,Time) :- course(_,Time,Lecturer,_).
  lectureTime(time(D,T)) :- getHour([1,2,3,4,5],T),day(D).
  getHour([H|_],H).
  getHour([_|L],H) :- getHour(L,H).
  day(mwf).
  day(tx).
  roomOpen(Time,Location) :- room(Location),not(course(_,Time,_,Location)).
  room(101).
  room(102).

The scheduleCourse rule is used to generate a time and a room for a
lecturer to teach a course.  Because the set of rooms and times are
constrained by physical space and allowable times, we need to limit the
possible values generated.  Most of the other rules generate legal values
for these variables, which are then tested to see if they work relative to
the other courses already on the schedule.

Answer the following questions about this code.  Feel free to use the
interpreter to help you understand how it works.

(a) getHour is recursive; thus, some case must stop the recursion by
causing a failure.  When will this happen?

(b) Rewrite lectureTime to allow 1:30,3:00 and 4:30 as the allowable
lecture times on Tuesday & Thursday (instead of the same hours as mwf).

(c) What happens if you attempt to schedule a course (using ScheduleCourse)
without providing a value for the Lecturer?  Is this the right behavior?
Why or why not?

(3) Write a simple assignment statement with one arithmetic operator in some
language you know.  For each component of the statement, list the various
bindings that are required to determine its semantics (both static and
dynamic).  For each binding, indicate the binding time used for the language.
 
(4) What information is required to describe a single-dimensioned Pascal
array?  How much of this information must be available for use at run-time
if subscript checking is done?  if such checking is not done?