COS 126: Fall 1996 Exercise Set 7

Answers

These exercises are intended help review the material on languages and grammars. Do not turn in solutions.

1. Rewrite the function SUM on page 11-6 of the lecture slides to TOY assembly language in the style shown on page 18-7; that is, use the symbolic instructions shown on page 18-6 and use symbolic labels (the code is in /u/cs126/toy/sum2.toy).
2. Translate your solution the previous problem into relocatable object code like that illustrated on page 18-8.
3. Using the grammar given in assignment 10, show the derivation for the assignment average = (score*weight)/max + average.
4. Given reverse Polish (a.k.a Polish suffix) for average = (score*weight)/max + average.
5. Write a grammar that generates sentences with zero or more 0s followed by 1 or more 1s, e.g., 1, 000001, 01111, etc. In this language, the tokens are just the characters 0 and 1.
6. Write a grammar that generates sentences with 1 or more 0s followed by an equal number of 1s.

Answers

As always, try to solve the problems before looking at the suggested solutions.

1. SUM     LI  R2,1        push the return address
           SUB R7,R7,R2
           ST  R6,(R7+0)
           LD  R1,(R7+1)   R1 <- n
           SUB R3,R1,R2    R3 <- n - 1
           JLT R3,DONE     if (n == 0) return 0
           SUB R7,R7,R2    push n - 1
           ST  R3,(R7+0)
           JAL R6,SUM      call sum
           LI  R2,1        pop n - 1
           ADD R7,R7,R2
           LD  R2,(R7+1)   R2 <- n
           ADD R1,R1,R2    R1 <- sum(n-1) + n
   DONE    LD  R6,(R7+0)   pop return address
           LI  R2,1
           ADD R7,R7,R2
           RET             return

2. 00:     B201    =SUM                    push the return address
   01:     2772
   02:     A670
   03:     9171                            R1 <- n
   04:     2312                            R3 <- n - 1
   05:     630D    +starting address       if (n == 0) return 0
   06:     2772                            push n - 1
   07:     A370
   08:     8600    +SUM                    call sum
   09:     B201                            pop n - 1
   0A:     1772
   0B:     9271                            R2 <- n
   0C:     1112                            R1 <- sum(n-1) + n
   0D:     9670                            pop return address
   0E:     B201
   0F:     1772
   10:     7600                            return

3. pgm			average = expr
   			average = expr + expr
   			average = expr / expr + expr
   			average = ( expr ) / expr + expr
   			average = ( expr * expr ) / expr+ expr
   			average = ( score * expr ) / expr + expr
   			average = ( score * weight ) / expr + expr
   			average = ( score * weight ) / max + expr
   			average = ( score * weight ) / max + average

4. Depending on the code in expr, the Polish suffix is either of the following lines

   average score weight * max average + / =
   average score weight * max / average + =

5. S A B
   S B
   A 0 A
   B 1 B
6. S A
   A 0 1
   A 0 A 1