INF5110 - Vår 2009

Obligatorisk oppgave 2 i INF5110 v�ren 2009

Merk: Dette er en tidlig utgave. Det kan komme presiseringer.

Dette er den andre av to oppgaver v�ren 2009. Den bygger videre p� det som er gjort i oblig 1.

Innhold

Hensikten med oppgaven

Tanken bak denne oppgaven er at man skal f� enn� mer praktisk erfaring med hva som gj�res i en kompilator, nemlig:

Oppgaven

Del to av den obligatoriske oppgaven bygger p� den f�rste delen, og g�r ut p� � implementere kravene til statisk semantikk, beskrevet i spr�knotatet. Resultatene fra kj�ring av en testsuite skal leveres. I tillegg skal det ogs� leveres en listing av byte-koden for eksempelprogrammet RunMe.d.

Frist

Fristen er fredag 8. mai.

Virtuell maskin og byte-kode

Den virtuelle maskinen og byte-kode er grundig beskrevet i notat om bytecode og interpreter.

Det er laget en pakke med klasser for � lage byte-kode. For � lage byte-kode, opprettes et objekt av klassen CodeFile, hvor variabler, structer, metoder m.m. kan legges til. N�r alt er lagt til, kan man hente ut byte-koden med getBytecode() som lager en array med bytes (byte[]). F.eks. se p� dette skallet: 

  CodeFile codeFile = new CodeFile();

  // Her bygges bytekoden opp ...

  byte[] bytecode = codeFile.getBytecode();
  DataOutputStream stream = new DataOutputStream(new FileOutputStream ("Navnet p� filen her ..."));
  stream.write(bytecode);
  stream.close();

Bytekoden er stack-basert og har ca. 30 instruksjoner.

Byte-koden er ikke like uttrykkskraftig som spr�ket Db, derfor er reglene for programmene dere skal generere byte-kode for forskjellige fra de dere skal implementere i semantikksjekken. Forskjellen er:

  • Det er ikke blokkniv�er. Alts� m� alle strukter v�re deklarert p� det �verste niv�et og det er ikke funksjoner inne i funksjoner.
  • Det er ikke referanseparametere, s� basisparameterene overf�rer by-value og struktvariablene er pekerverdier og overf�res ogs� by-value. Alts�, det er p� sammen m�te som i Java.
  • Det er ogs� brukt litt andre navn, slik som at funksjonene kalles prosedyrer (Procedure).
Et eksempel p� et program som f�lger de begrensede reglene er ./code-examples/RunMe.d.

Her er et kort eksempel p� hvordan man bygger opp byte-koden til et enkelt program med en global variabel og en enkel metode med to parametere (float og Complex) og en lokal variabel (int). Metoden printer ut float-parameteren og returnerer. Strukten Complex blir ogs� definert. Legg spesielt merke til at alle deklarasjonene blir definert f�rst og oppdatert senere. Legg ogs� merke til at parameterne f�r nummer fra 0 og oppover og at variabler inne i metoden blir nummerert etter det. Man m� ogs� fortelle den virtuelle maskinen hva som er main-funksjonen. Dette vil alts� v�re kode som for eksempel er spredt rundt i det abstrakte syntakstreet, hvor hver node har ansvar for sine egne instruksjoner. 

  // Lage example.bin:
  CodeFile codeFile = new CodeFile();
  codeFile.addProcedure("Main");
  codeFile.addVariable("myGlobalVar");
  codeFile.addProcedure("test");
  codeFile.addStruct("Complex");

  CodeProcedure main = new CodeProcedure("Main", VoidType.TYPE, codeFile);
  main.addInstruction(new RETURN());
  codeFile.updateProcedure(main);

  codeFile.updateVariable("myGlobalVar", new RefType(codeFile.structNumber("Complex")));

  CodeProcedure test = new CodeProcedure("test", VoidType.TYPE, codeFile);
  test.addParameter("firstPar", FloatType.TYPE);
  test.addParameter("secondPar", new RefType(test.structNumber("Complex")));
  test.addInstruction(new LOADLOCAL(test.variableNumber("firstPar")));
  test.addInstruction(new CALL(test.procedureNumber("print_float")));
  test.addInstruction(new RETURN());
  codeFile.updateProcedure(test);

  CodeStruct complex = new CodeStruct("Complex");
  complex.addVariable("Real", FloatType.TYPE);
  complex.addVariable("Imag", FloatType.TYPE);
  codeFile.updateStruct(complex);
		
  codeFile.setMain("Main");

  byte[] bytecode = codeFile.getBytecode();
  // ... Lagre i filen ./code-examples/example.bin
Resultatet (listingen) av dette blir (Ved � kj�re biten med kode ovenfor og s� kj�re komandoen java runtime.VirtualMachine -l ./code-examples/example.bin) 
  Loading from file: ./code-examples/example.bin
  Variables:
  0: var Complex myGlobalVar
  Procedures:
  0: func void Main()
      0: return
  1: func void test(float 0, Complex 1)
      0: loadlocal 0
      1: call print_float {100}
      2: return
  Structs:
  0: Complex
      0: float
      1: float
  Constants:
  STARTWITH: Main

Testsuite

Det er laget en patch til det prosjektet som ble delt ut og som dere har bygd p� i oblig 1. Den ligger her og best�r av f�lgende:

  • En ny Compiler-klasse (.\src\compiler\Compiler.java). Den inneholder et skall som brukes av testen. Den forutsetter at metoden compile() returnerer en int 0, 1 eller 2, som nevnt tidligere.
  • En hjelpeklasse til testen (.\src\test\FileEndingFilter.java).
  • Klassen som utf�rer testen (.\src\test\Tester.java).
  • En katalog med filer det testes mot (./tests/). Filene med navn som inneholder fail skal gi semantikkfeil (2). Ingen av filene skal gi syntaksfeil (1).
  • Et testprogram for den virtuelle maskinen (./code-examples/RunMe.d).
  • Noen linjer som kan legges til build-filen for �
    (1) kalle testen (compile-test, test).
    (2) kompilere og kj�re eksemplet RunMe (compile-runme, list-runme, run-runme).
    De ligger i filen ./build.xml.patch.

Plass�r filene slik katalognavnene er angitt her relativt til banen til prosjektet deres (Pass p� � legge til innholdet i Compiler.java og build.xml uten � skrive over de filene dere har).

Etter det kan testen kj�res med ant test og dere kan kompilere RunMe med ant compile-runme og liste ut byte-koden med ant list-runme.

Klassen Tester kaller klassen Compiler for alle testene i katalogen ./tests/. Det skrives ut �n linje for hver test, samt en oppsummering.

Sjekkliste for del to

Under f�lger en sjekkliste for semantikken (merk at det kan v�re flere krav, les ogs� spr�knotatet) i Db:

Gjennomf�ring og levering

Man leverer sammen med den samme gruppen som man leverte oblig 1. Det som skal leveres er:

Levering

Besvarelsen leveres som ett pakket filarkiv (zip- eller tgz-format) til gruppel�rer Andreas Svendsen <Andreas.Svendsen@sintef.no>.

Subversion-brukere kan ogs� levere via et repository (bare gi meg leseaksess, og kommandoen for � lese ut prosjektet).

Sist oppdatert 2009-03-24 14:45
Andreas Svendsen