University of Arizona, Department of Computer ScienceCSc 520 — Assignment 4 — Due noon, Wed, Apr 6 — 15%Christian CollbergMarch 23, 20051 IntroductionYour task is to write an interpreter and a garbage collector for a small MODULA-2-like language calledLuca. You can choose between mark-and-sweep, copying collection, and generational collection.The Luca compiler, code for parsing S-expressions, and some simple test-cases can be downloaded from theclass web page: http://www.cs.arizona.edu/~collberg/Teaching/520/2005/Assignments.This assignment can be done individually or in a team of 2 students.Make sure to hand in a README file describing, in detail, your implementation.For this assignment efficiency of the garbage collector counts!2 The Luca LanguageHere’s is a Luca program list.luc that creates a list of integers and prints it out:PROGRAM list;TYPE T = REF R;TYPE R = RECORD[a:INTEGER; next:T];VAR first : T;VAR last : T;VAR x : T;VAR i : INTEGER;BEGINfirst := NEW T;first^.a := 0;first^.next := NULL;last := first;FOR i := 1 TO 5 DOx := NEW T;x^.a := i;x^.next := NULL;last^.next := x;last := x;ENDFOR;1x := first^.next;WHILE x # NULL DOWRITE x^.a;WRITELN;x := x^.next;ENDDO;END.The Luca language supports many data types (including arrays, records, classes and reals) and controlstructures and procedures/methods. Your interpreter, however, only needs to support• INTEGER, BOOLEAN, records, and reference (pointer) types.• Assignment statements and the IF, WHILE, REPEAT, LOOP, EXIT, and FOR control statements.• The built-in function NEW.• Integer constants and the built-in constant NULL.• Integer and boolean expressions as well as the field and pointer dereferencing operators (. and ^).This will be enough to construct elaborate heap-structures that our garbage collector can work on. I.e. therewill be no need for you to handle procedures, classes, reals, and arrays.A complete grammar of Luca is given in Appendix A.3 The InterpreterA Luca compiler that generates stack virtual machine code will be given to you. You should write aC-program lexec.c that is called like this:$ luca_lex list.luc | luca_parse | luca_sem -agvm | luca_AST2tree -agvm | \luca_tree2vm > list.vm$ lexec list.vm12345The first command compiles the program list.luc into a virtual machine code list.vm. The second runsyour interpreter on this virtual machine code. All of the phases of the compiler pipeline read and generateS-expressions. The -h options lists other arguments to the different phases.Your program should take two optional arguments:-h size: Set the total heap size to size.2-t Trace all heap operations. For every NEW operation print (to stderr)NEW: allocated X bytes for type T.Every time a garbage collection is triggered printGC: START USED=... FREE=...GC: END USED=... FREE... WALL=... CPU=...where FREE and USED is the amount of heap memory (in bytes) available and used and where WALLand CPU is the time (in seconds) used by the garbage collector as computed by this code:#include<sys/resource.h>#include<sys/time.h>double GetTime () {struct timeval Time;double cpu, wall;struct rusage Resources;getrusage(RUSAGE_SELF, &Resources);Time = Resources.ru_utime;cpu = (double)Time.tv_sec +(double)Time.tv_usec/1000000.0;gettimeofday(&Time, NULL);wall = (double)Time.tv_sec +(double)Time.tv_usec/1000000.0;}Note:• Don’t worry too much about the efficiency of your interpreter. Do worry about the efficiency of thegarbage collector.• The compiler (in particular the parser) is flaky.• You should trigger a garbage collection whenever a NEW is called and the heap has not enough freememory to honor the request.• Don’t grow the heap.• The default heap size shall be 1M bytes.• Pointers and INTEGERs are 32-bit quantities.• The virtual machine code is word addressed.• We will test the interpreter on a Linux/x86 system.34 Virtual Machine CodeFrom this Luca programPROGRAM min;TYPE T = REF INTEGER;VAR x : T;BEGINx := NEW T;WRITE x^;END.the Luca compiler generates this virtual machine code:(((1 TypeSy INTEGER 0 0 BasicType 1)(2 TypeSy REAL 0 0 BasicType 1)(3 TypeSy CHAR 0 0 BasicType 1)(4 TypeSy STRING 0 0 BasicType 0)(5 TypeSy BOOLEAN 0 0 EnumType(6 7)1)(6 EnumSy TRUE 0 0 5 0 1)(7 EnumSy FALSE 0 0 5 0 0)(8 TypeSy $NOTYPE 0 0 BasicType 0)(9 TempSy $NOSYMBOL 0 0 8 0 0)(10 TypeSy $ADDRESS 0 0 BasicType 1)(11 TypeSy OBJECT 0 0 ClassType()8 0 0 0)(12 ConstSy NIL 0 0 11 0 0)(13 ConstSy NULL 0 0 10 0 0)(14 ProcedureSy $MAIN 8 0()(16)0 0)(15 TypeSy T 3 0 RefType 1 0)(16 VariableSy x 4 0 15 0 0))((Info 8 7 8 10 0 14 16)(ProcBegin 8 14 0 1 9 0 0 $MAIN)(PushAddr 6 16 x)(NEW 6 15)(Store 6 15)(PushAddr 7 16 x)(RefOf 7 15)(Load 7 1)4(Write 7 1)(ProcEnd 8 14 $MAIN)))The vm code is in an S-expression format. The first part is the symbol table, the second part the codesection.5 Submission and AssessmentThe deadline for this assignment is noon, Wed, Apr 6. You should submit the assignment (a text-file con-taining the function definitions) electronically using the Unix command pturnin cs520.4 lexec.c READMEq.This assignment is worth 15% of your final grade.Don’t show your code to anyone, don’t read anyone else’s code, don’t discuss the details ofyour code with anyone. If you need help with the assignment see the instructor or TA.A The Luca SyntaxLuca has constant and variable declarations, integer arithmetic, assignment statements, READ, WRITE,and WRITELN statements. Only integers and characters can be read, strings can also be written. Identifiershave to be declared before they are used. Identifiers cannot be redeclared. There are three (incompatible)built-in types, INTEGER, BOOLEAN and CHAR. The identifiers TRUE and FALSE are predeclared in the language.INTEGERS and REALS are 32-bit quantities.hprogrami ::= ‘PROGRAM’ hident i ‘;’ hdecl listi hblock i ‘.’hblocki ::= ‘BEGIN’ hstat seqi ‘END’hdecl listi ::= { hdeclarationi ‘;’ }hdeclarationi ::= ‘CONST’ hident i ‘:’ hidenti ‘=’ hexpressioni‘VAR’ hidenti ‘:’ hidentihexpressioni ::= hexpressioni hbin operator i hexpressioni |hunary operator i hexpressioni |‘(’ hexpressioni ‘)’ | hinteger literal i | hchar literal i | hdesignator ihdesignatori ::= hidentihbin operator i ::= ‘+’ | ‘−’ | ‘∗’ | ‘/’ | ‘%’hunary operator i ::= ‘−’hstat seqi ::= { hstatement i ‘;’ }hstatementi ::= hdesignator i ‘:=’ hexpressioni‘WRITE’ hexpressioni | ‘WRITELN’ |‘READ’ hdesignatoriLuca has
View Full Document
Unlocking...