University of Arizona, Department of Computer ScienceCSc 520 — Assignment 1 — Due noon, Mon Feb 11 — 10%Christian CollbergJanuary 28, 20081 IntroductionYour task is to write an interpreter for a small subset of the language Luca. You will be given a front-endthat performs lexing, parsing, semantic analysis, and intermediate code generation on Luca source files.You will write an interpreter that reads in the code produced by the front-end, and then executes this code.1. The interpreter should be implemented using indirect threaded code.2. You should write your interpreter in C or C++ using gcc.3. The interpreter should be named lucax. It should read the virtual machine code (in an S-expressionformat) from standard input.4. You only have to implement control structures (IF, WHILE, etc.), integer and real arithmetic, a WRITEstatement, and array indexing.5. You should test the interpreter on lectura.6. You should work in a team of two students.7. Future assignments will build on this one so it is in your best interest to do a good job! If you haveplenty of time on your hand now at the beginning of the semester you can go ahead and implementprocedures (which we’ll need for the assignments on object oriented programming) and/or records andpointers (which we’ll need when we implement a garbage collector). We won’t test any of these featuresfor this assignment, though.The Luca front-end can be downloaded from http://www.cs.arizona.edu/~collberg/Teaching/520/2008/Assignments. The compiler/interpreter is invoked like this:> lc quicksort.luc | lucaxIf you’re curious of how the Luca compiler works internally, you can look at the output from the variouscompiler phases:> lc quicksort.luc -L lex> lc quicksort.luc -L parse> lc quicksort.luc -L sem> lc quicksort.luc -L tree> lc quicksort.luc -L stack12 The Luca LanguageLuca is similar to Modula-2 and Modula-3. The complete syntax is given in Appendix A. Below is Ack-ermann’s function coded in Luca. However, you will only have to implement a small subset consisting ofinteger and real arithmetic, control structures, and arrays.PROGRAM Ackermann;PROCEDURE Pow(base : INTEGER; exp : INTEGER; VAR Out : INTEGER);VAR i : INTEGER;BEGINOut := 1;FOR i := 1 TO exp DOOut := Out * base;ENDFOR;END;PROCEDURE A(i : INTEGER; j : INTEGER; VAR R : INTEGER);VAR R1 : INTEGER;BEGINIF i = 1 AND j >= 1 THENPow(2, j, R);ELSEIF i >= 2 AND j = 1 THENA(i-1, 2, R);ELSEIF i >= 2 AND j >= 2 THENA(i, j-1, R1);A(i-1, R1, R);ENDIF;ENDIF;ENDIF;END;VAR R : INTEGER;BEGINA(2, 3, R);WRITE R;WRITELN;END.In a Luca program the main program is between the last BEGIN-END. A formal VAR-parameter is passedby reference, i.e. its address is passed rather than its value.3 The BytecodeThe front-end reads, parses, and performs semantic analysis on Luca programs. it also generates interme-diate code; a typed stack code. Here’s a simple Luca program:2PROGRAM P;VAR X : INTEGER;BEGINX : = 5 ;WRITE X;END.Here is the corresponding stack code:((...(15 VariableSy X 2 0 1 1 0))((info 6 8 0 9 1 14 15)(begin 6 14 0 1 9 0 1 $MAIN)(apush 4 15 X)(ipush 4 5)(istore 4)(apush 5 15 X)(iload 5)(iwrite 5)(end 6 14 $MAIN)))There are two major parts: the symbol table and a list of stack instructions.The instructions of each procedure are numbered starting at 1. In the example above there is one instructionper line. The first word is the opcode, the second the source postion, then follows a possibly empty list ofextra arguments.Appendix B has a complete listing of all the bytecodes.4 OK, so what do I have to do???For this assignment you don’t have to implement all of Luca! You don’t have to implement procedures,records, and pointer types, for example. Rather, the only instructions you have to worry about are:1. load and store instructions for integers and reals (iload, rload, istore, rstore),2. arithmetic instructions for integers and reals (iadd, radd, . . . , iuminus, ruminus, trunc, float),3. comparison instructions for integers and reals (ine, rne, . . . ),4. the unconditional branch (jmp),5. the array indexing operator (indexof),6. the instructions for pushing integer and real literal values (ipush, rpush),37. apush, the instruction for pushing the address of a variable onto the stack, and8. the output instructions for integers and reals iwrite and rwrite, and writeln.The only part of the symbol table you need to read is VariableSy (to get the offset of each variable whichthe apush instruction pushes on the stack) and ArraySy (to get the length of the array so that you canimplement bounds checks).So, what, do you ask, should I do???? Well,, here’s a schedule for you:1. Start by downloading the compiler and try it out on some simple programs. Learn what each bytecodedoes by looking at the generated code and the description of the bytecode in Appendix B.2. A C module sexpr will be given to you. It parses an S-expression (the representation that the inter-mediate code is stored in) into a data structure which you can then walk to get the information youneed. Try it out:#i nc l u d e < s t d i o . h>#i n c l u d e ” sexpr . h”i n t main ( i n t argc , char ∗ ∗ argv ) {SExpr ∗ ro o t ;i f ( ! p a r se ( argv [ 1 ] , & r oo t ) ) {p r i n t f ( ” can ’ t open f i l e \n ” ) ;} e l s e {printSExpr ( r o o t ) ;fr e eSE x pr ( r o o t ) ;}}3. Continue playing with sexpr: learn how to walk the S-expression data-structure to get out eachinstruction and its arguments.4. Assign bytecodes to each instruction. For example, let iadd=1, isub=2, etc. Read in each instructionfrom the S-expression, convert to the bytecode, and store the result in a bytecode array. Keep in mindthat some instruction arguments are one word long, not one byte. This is true of the ipush and rpushinstructions, for example, whose constant value argument is 32 bits long.5. Code up an evaluation stack with push and pop functions. While you’re at it, add a printstackfunction for debugging.6. Write a simple switch-based interpreter for a small subset of the instructions: iadd, ipush, iload,istore, iwrite, and writeln. Debug! See, that wasn’t hard, was it?7. Now convert the switch-based interpreter to the indirect threaded one. Ooops! Segmentation fault???Well, time for more debugging!8. Add the remaining instructions. Debug your interpreter on larger programs. Cover all the corner cases.9. Submit!Note that we will test your interpreter by running it on a set of micro-programs. For example, to testwhether + works, we
View Full Document