INF5110 - Vår 2008

Obligatorisk oppgave 2 i INF5110 v�ren 2008

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

Merk: Koden for interpreten er n� klar. Det vil kommer det mer dokumentasjon om bytekoden.

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

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:

Analyse av et programs statiske semantikk.
Anvendelse av et abstrakt syntakstree.
Typesjekking, sjekking av bruk av navn og blokkstrtuktur i spr�k.
Kodegenerering til en bytekode fra et abstrakt syntakstre og litt om interpretering av bytekode.

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. Det holder med � levere inn �n parser. I tillegg skal resultatene fra kj�ring av en testsuite leveres. Dere skal ogs� levere inn listing av byte-koden for eksempelprogrammet RunMe.d.

Ta utgangspunkt i et abstrakt syntakstre og sjekke om treet oppfyller alle kravene gitt av spr�kets semantikk.
Gj�re om p� det treet som ble laget i oblig 1 om n�dvendig og lage en oversiktlig kode som benytter abstrakte klasser og funksjoner.
Dersom man finner feil, gi en kort melding, som skrives ut p� skjermen.
Returnere en verdi fra kompilatoren som forteller om koden var godkjent (0), om det var syntaksfeil (1) eller om det var semantikkfeil (2).
Generere byte-kode ved hjelp av det utdelte biblioteket for byte-kode (Se pakken bytecode.* og underpakkene og spesielt klassen CodeFile). Legg merke til at det er begrensninger i byte-koden, slik at det ikke er mulig � generere byte-kode for alle eksemplene i katalogen test. Les mer om det under Virtuell maskin og byte-kode.

Frist

Fristen er fredag 9. mai. Fristen er endelig.

Virtuell maskin og byte-kode

Merk: Det vil komme mer detaljert dokumentasjon til bytecode-biblioteket. Mens dere venter kan dere jo kikke i koden i pakken bytecode.*

Det er laget en pakke med klasser for � lage byte-kode. Det er bare � opprette et objekt av klassen CodeFile og s� legge til variabler, structer metoder, osv. N�r man er ferdig med � legge til alt henter man ut byte-koden med getBytecode() som lager en array med bytes (byte[]). Se 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. Her kommer et notat med flere detaljer om instruksjonene, bytecode-biblioteket og den virtuelle maskinen.

Byte-koden er ikke like uttrykkskraftig som spr�ket D_b, 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 referanseparamtere, s� basisparamterene overf�re 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 prosedyre med to parametere (float og Complex) og en lokal variabel (int). Den printer ut float-parameteren og returnere. Strukten Complex blir ogs� definert. Legg spesielt merke til at alle deklarasjonene blir definert f�rst og oppdatert senere. Legg ogs� merke til at parameterene 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.

  // 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 prosjktet 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()` returnere en `int` 0, 1, eller 2, som forklart ovenfor.

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) kompilerer 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 opp klassen Compiler for alle testene i katalogen `./tests/`. Det skrives ut �n linje pr test og 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 D_b:

Multiple deklarasjoner av ett navn i samme skop m� detekteres.
Typekonvertering: int is-a float, int kan forfremmes til float i aritmetiske uttrykk, returverdier, og som aktuelt argumentuttrykk i funksjonskall.
Main-funksjonen
1. Funksjonsdeklarasjonen til Main, m� finnes p� �verste blokkniv� av programmet.
2. Signaturen m� matche func Main(), d.v.s. ingen argumenter og ingen returverdi.
Funksjonsdeklarasjoners returverdi er:
- ikke noe, eller
- type i symboltabellen (predefinert eller brukerdefinert struct)
Stmts
- AssignStmt
  1. Variabelen p� venstresiden m� v�re deklarert.
  2. Typene p� vs. og hs. m� v�re like, etter evt. typekonvertering.
- ReturnStmt
  1. Forekommer bare i en funksjonsblokk (en FuncDecls liste av Stmts), ikke i de anonyme blokkene til IfStmts og WhileStmts.
  2. Typen til uttrykket stemmer overens med funksjonens deklarerte type. Merk ogs� s�rtilfelle uten returverdi, da blir argumenter til return-setningen en feil.
- WhileStmt: m� ha en betingelse av typen bool.
- IfStmt: m� ha en betingelse av typen bool.
Exps
- NewExp: argumentet m� v�re deklarert som en struct-type.
- Literals: M� v�re av en de forh�ndsdefinerte typene i spr�ket: float, int, string, bool eller null.
- Bin�re uttrykk (felles for alle operatorene bortsett fra negasjon) m� ha samme typer, etter evt. typeforfremming, p� begge sider av operatoren.
- Aritmetiske uttrykk: som for bin�re uttrykk, men typene m� ogs� begrenses til aritmetiske (int eller float).
- Logiske uttrykk (med "&&", "||" eller "!"): begge operander m� v�re av typen bool.
- CallStmt
  1. Navnet som kalles m� v�re deklarert som funksjon.
  2. Kallet m� ha samme antall aktualparametre som formalparametre.
  3. Aktualparametrene m� ha samme type (eller mulig � tilordne) som formalparametrene.
  4. Bruk av referanser ("ref") m� stemme overens med funksjondeklarasjonen.
- Var
  1. Evt. strukt-type m� v�re deklarert.
  2. Navnet m� v�re deklarert.

Gjennomf�ring og levering

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

En forside med navn og brukernavn til de som leverer besvarelsen.
En kort rapport om gjennomf�ringen med forklaring av designet.
All kode som trengs for � bygge og kj�re parserne, herunder:
- JFlex-koden for skanneren
- CUP-koden for en av syntaksvariantene
- Java-koden for syntakstreet og semantikksjekking
- Byggeskript: build.xml eller Makefile
Instruksjoner for bygging og kj�ring
Utskrift fra kj�ring med testesuiten (ant test).
Utskrift av listing av byte-koden til eksemplet RunMe.d (ant list-runme).

Levering

Besvarelsen leveres som ett pakket filarkiv (zip- eller tgz-format) til gruppel�rer Fredrik S�rensen <fredrso@ifi.uio.no>.

Subversion-brukere kan ogs� levere via et repository (bare gi meg leseaksess, og kommandoen for � lese ut prosjektet). Rapporten skal ved bruk av SVN enten sendes p� epost, eller ligge p� "roten" (/) i repositoriet.

Sist oppdatert 2008-04-10 21:24
Fredrik S�rensen