1. (cons 'a '(b c)) (A B C)
2. (cons '(a b) '(c d e)) ((A B) C D E)
3. (list '(a b) '(c d e)) ((A B) (C D E)
4. (append '(a b) '(c d e)) (A B C D E)

( (a b) c (d) ). See Internal List Representation for what the answer should look like.

S --->  b M b      (S = start symbol)
M --->  ( L  |  a
L --->  M a )

1. Which symbols are terminal symbols? a b ( )

2. Which symbols are non-terminal symbols? S M L
   Note: | and ---> are metasymbols.

3. Write code for the function M that is part of a recursive-descent parser for this language. (Just the code for M, not the entire parser.) You may write in either Java or C (not much difference). You must include calls to the scanner and calls to report any error. (Assume that the next terminal is always in a variable next, that scan( ) replaces what is in next with the next terminal, and that the next terminal has already been scanned as you enter M. These are the assumptions we usually made in the course.) See Answer to Rec 5, Question 2 where your answer should be just the code for the function M.

#!/usr/bin/ruby
re = /(\d\d):(\d\d)/
while line = gets 
   m = re.match(line)
   print m[1], ":" , m[2], " means ---> "
   print m[2].to_i, " minutes past "
   if m[1] == "00"
      print "12 am"
   elsif m[1].to_i <= 12
      print m[1].to_i, " am"
   elsif m[1].to_i > 12
      print (m[1].to_i - 12), " pm"
   end
   print "\n"
end

00:08
01:02
02:22
10:01
12:09
13:13
17:17
21:21
22:22
23:55

00:08 means ---> 8 minutes past 12 am
01:02 means ---> 2 minutes past 1 am
02:22 means ---> 22 minutes past 2 am
10:01 means ---> 1 minutes past 10 am
12:09 means ---> 9 minutes past 12 am
13:13 means ---> 13 minutes past 1 pm
17:17 means ---> 17 minutes past 5 pm
21:21 means ---> 21 minutes past 9 pm
22:22 means ---> 22 minutes past 10 pm
23:55 means ---> 55 minutes past 11 pm

1. In the Ruby program above, identify the regular expression. In line 2, what is assigned to "re".

2. When this program handles the first line of data, what gets stored in m[0]? Where could m[0] have been used to slightly simplify the code above? m[0] gets the entire string that matched. In the first case, this is "00:08". m[0] could have been used by itself in the first print of the program.

3. The Ruby program translates the input international hours and minutes into a more verbose American style. But there are two errors in the output, shown in bold above: it should be "1 minute" and "12 pm". Make changes to the code above to correct these two problems. (The code given runs, but it is also permissible to completely rewrite this code.) This is straightforward, though a number of people thought that for the second part, you could just change "<= 12" to "< 12" and "> 12" to ">= 12". With those changes, the program prints "0 pm" instead of "12 pm".

1. In standard Ruby classes (including the classes in Recitation 11), what form does the constructor take? The constructor is called "initialize".

2. If one writes print abc where abc is a class instance (a declared class), what determines what is printed? Whatever is defined by "to_s".

3. In Recitation 11, what does the the following first line of a class mean?

   class Time1 < Date1
     ...
   end

   Means that Time1 extends Date1, or that Time1 is a subclass of Date1, or that Date1 is a superclass of Time1. Time1 inherits the methods and data of Date1.

/Times-Bold findfont 100 scalefont setfont
% assume page is 612 by 792 points
50 50 moveto (ABC) show
90 rotate % positive is counter-clockwise
50 50 moveto (DEF) show
0 -612 translate
50 50 moveto (GHI) show
showpage

Here is this part as a PDFs: 7.pdf.
In order to understand this part, it's important to realize that the "ABC" remains exactly where it was placed, regardless of any subsequent rotations or translations. The rotation by 90 degrees counter-clockwise puts the "DEF" vertically and off the page to the left. Then the translation allows the "GHI" to be printed vertically and at the right of the page, as shown.

1. In the geneology example (a family with parents, children, etc.), explain carefully what the rules below say. (What do they say about the variables X and Y?)

   ancestor(X,Y) :- parent(X,Y).
   ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

   These two rules give two ways in which X can be the ancestor of Y: Either X is the parent of Y, or else X is the parent of some Z, and the same Z is the ancestor of Y (recursive definition).

2. Explain how the following manages to print the ancestors of the object "neal".

   print_ancestors_neal(_) :- ancestor(X, neal), write(X), write(', '), fail.
   

   Mr. Barnes pointed out that in order to use this rule, the rule needs to be loaded in (with "consult") and at the command line one needs to type "print_ancestors_neal(_)." (with the period at the end)
   In following the rule, prolog tries to make the left side true. To do this, it finds an X such that "ancestor(X, neal)" is true. Then it prints that X along with ", ". Finally, that attempt is explicitly made to fail, so that prolog will try again. Prolog keeps trying until it can't find any more such value for X. The output looks like:

   ?- consult(family).
   % family compiled 0.00 sec, 18,960 bytes
   true.
   
   ?- print_ancestors_neal(_).
   ralph, alberta, albertus, albert, lydia, may, 
   false.

void T(void) {
   U();
   if (next == '*') {
      scan();
      U();
   }
}

Add to the function above showing what four MIPS instructions would be added in case a "*" was encountered during T's processing. Show where they are added, what information must by used to output these instructions, and what kind of value is returned. (The MIPS syntax doesn't have to be correct, but you need to describe the general ideas.)