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 iSOLUTIONS
(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