DOC PREVIEW
UA CSC 520 - Assignment

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UA CSC 520 - Assignment

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Recursion

Recursion

18 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Assignment
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Assignment and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Assignment 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?