The following are class exercises from previous semesters, provided here for your pratice. Ignore any due-dates in the text below. Links to the solutions are at the bottom of this page.

1. [Aug 27] Rewrite the following program stepwise until it is fully parsed

    BEGIN Read(e,e468); ee468=e+e468; Write(ee468,12345); END

2. [Aug 29] Write a 10-15 line program that performs a scanner operation based
   on a transition table.

3. [Sep 3] 
   3.1 Create a DFA and a transition table for the 
   regular expression a((b)*c)+

   3.2 Give three examples of scanners and input character strings that
   need multi-character lookahead. Explain in each case how the scanner
   identifies the correct tokens

4. [Sep 12] 
   (a) For the above regular expresion, create a FA using the constructs
       on slide 66. Compare it with the DFA of exersice 3.
   (b) Given the productions on Slide 32, create  a parse (or derivation) tree
       for the expressions  B+C*D and for (B+C)*D.

  
5. [Sep 16] 
   (a) write three examples of constructs that have common prefixes and turn
       them into LL(1)
   (b) write the steps in which the algorithm on page 125 turns the following 
       left recursion into LL(1)
          A -> A+B
          A -> B
   (c) create the CFSM for the grammar on slide 86:
          S  -> [ S1
          S  -> S1
          S1 -> [ S1 ]
          S1 -> lambda

6. [Sep 18] (no penalty for late submission, as this assignment was late as
   well) 
   Complete the exercise on slide 104 (goto and action table for G3)

7. {Sep 24] Write/draw the sequence of parse and semantic stack actions when
   parsing the following MICRO program with an LL and also with an LR parser.
       BEGIN Read(x); Write(x+2); END

8. [Sep 26] 
    (a) write the semantic routines (action procedures) for the FOR statement
    (b) write the semantic routines (action procedures) for a CASE statement
       (= SWITCH statement in the C language)

9. [Oct 1]
     using the semantic routines written in exercise 8 (plus other semantic
     routines as needed), generate code for the
     following program segment:

     n=0
     FOR i IN 10..20
     LOOP
      n=n+2
     ENDLOOP

     CASE m+10 IS
     WHEN 5: WRITE("five");
     WHEN 3: WRITE("three");
     WHEN 10..15: WRITE("ten to 15");
     ELSE : WRITE("other than 3,5,10-15");
     ENDCASE

     Annotate each code section with the semantic routine that generated it.

10. [Oct 3]
    Draw/write the stack frame, 3-address code and assembly code for the
    following code segments

     ...
     res = compute(a,b)
     ...
     int compute(int x, int & y){
     int i1,i2;
     i1 = x+4;
     x = i1*3;
     y = x/i1;
     return i1-x+y;
     }

     
11.[Oct 10]
   a) Mark the common subexpression that can be reused in each statement. In each
   case, circle and connect the two involved subexpressions (the expressions
   are evaluate from left to right)

   X = Y*Z+U
   K = Y*Z+U
   L = Y+Z+U
   U = T+Y*Z
   Y = Y*Z+U
   K = Y*Z+T

   
   b) write a code example for each category of aliasing on slide 164

12. [Oct 22]
    Do register allocation on the following tuple code, using both the top-down
    and bottom-up register allocatiaon algorithm. 

    add A B C
    add D E F
    mul C F G
    add B A H

    Assume an architecture with 3-address instructions and three registers.
     
13. [Oct 29]
    Apply the register tracking algorithm on the following code. Choose the
    same machine  model as in Fig 15.10

    F := D-C*A
    D := B*C+D*F
    A := D+E*C
    F := E+A+C
    
    
14. [Nov 6]
    (a) determine the register need for the expression a*b+(c+d)*(e+f), using  
    the recursive tree algorithm. How many registers would a naive algorithm
    need? Assume that at most one memory location can be accessed per
    instruction. 
    
    (b) Apply list scheduling to the following code (assume same latencies as
    in class)
    load A R0
    load B R1
    mul R0 R1 R0
    load C R1
    load D r2
    div R1 R2 R3
    sub R0 R1 R0
    store R0 E

    - how many virtual registers do you need?
    - what is the cumulative latency of the first intrsuction?
    - how many execution cycles do the original and scheduled code take?

15. [Nov 7]
    Create Local Def and Use sets of the program on page 632 in the textbook. 
    Compute the Global Def and Use Sets using the iterative algorithm.

16. [Nov 12]
    a) apply invariant code motion to the following loop. Write down def sets
    and relevant variables.
       while x>y {
          sub = x*15+d/e
          b[sub] = (a-b)*(x-y)
       }
     
    b) Apply strength reduction to the following loops. Perform the operation
       *after* generating code for the subscript expression.

       double a[5,27]
  
       while i


SOLUTIONS


(These are just samples from submitted homeworks. So the answers may 
not be correct.)


 Ex1

 Ex2

 Ex3

 Ex4

 Ex5

 Ex6

 Ex 7. page1 
 page2
 page3

 Ex8

 Ex9

 Ex10

 Ex11

 Ex12

 Ex13

 Ex14

 Ex15 and Ex16

 Ex17 and Ex18