bild
Skolan för
datavetenskap
och kommunikation

2D1373 Artificiella språk och syntaxanalys

Labbar

Några tips till minijavaprojektet finns i slutet.

Bokning

Tryck här för att hämta bokningslistor:

Verktyg

Genom att göra
module add /info/syntax05/module/mod_syntax05
får du tillgång till verktygen som används på kursen. Om du föredrar att ordna dina sökvägar själv kan detta vara bra att veta:
  • lex och yacc finns i standardmiljön.
  • flex och bison kräver modulen gnu-make eller gnu
  • javacc finns i /info/syntax05/bin/
  • jflex finns i /info/syntax05/bin/
  • java_cup finns i /info/syntax05/bin/
    OBS: Den parser som Cup genererar behöver klasser som finns i /info/syntax05/Cup/. Se till att sätta din CLASSPATH så denna katalog finns med. Gäller både vid kompilering och exekvering.

Applex

Projekt

Projektet går ut på att göra lexikal och syntaktisk analys samt typkontroll av MiniJava. I kursen programmspråksimplementation bygger du sedan ut projektet till en kompilator. Det finns också möjlighet att i samråd med kursledaren definiera och genomföra ett eget projekt. Eftersom projektet är en del av examinationen gäller Nadas hederskodex.

Typkontroll för MiniJava

Hemsidan för Appels Modern compiler implementation, second edition innehåller bland annat en MiniJava-grammatik. Under rubriken Framework hittar ni länkar till readme-filer för kapitlen. Dessa innehåller programmeringsuppgifter. Projektuppgiften är att implementera Type Checking, kapitel 5. Man behöver också göra stora delar av kapitel 2-4. Uppgifterna i kapitel 2-4 är dessutom bra alternativ till applex 2 och 4.
Grunduppgift
Appel beskriver hur MiniJava skiljer sig från riktig Java. Det innebär att sådant som inte defineras särskilt i MiniJava ska vara som i riktig Java. Detta gäller till exempel prioriteten mellan de olika operatorerna. Operatorprioriteten är viktig för att du ska kunna skriva en konfliktfri grammatik. Ett MiniJava-program som varken innehåller syntaktiska fel eller typfel bör gå att kompilera med javac.

MiniJava tillåter inte överlagring av funktioner (dvs att en klass har flera metoder med samma namn men olika parametrar). Det ingår i typkontrollen att kontrollera detta. Att hantera överalgring på ett korrekt sätt är betydligt svårare.

Du behöver inte hantera nästlade kommentarer (vilket Appel tycker att man ska hantera). Du behöver inte heller kontrollera att variabler inititeras innan de används (vilket javac gör och Appel inte kommenterar).
Hjälpfiler
I katalogen /info/syntax05/project hittar du bland annat katalogerna syntaxtree/ och visitor/ som är två javapaket frå kursbokens hemsida. Tänk på att dessa är java-paket så att du kopierar hela katalogerna och lägger dem så att du hittar dem i din CLASSPATH.
Extrauppgift: arv
Hantera även arv. Tänk på att...
  • ...arv inte får vara cirkulärt.
  • ...ta hänsyn till att överlagring inte är tillåten. Anta att B ärver av A och A har metoden f. Om B definerar en egen f måste returtyp och parametertyper stämma med As f
  • ... om B ärver av A så måste båda vara definierade i MiniJava-programmet, men B kan definieras före A.
Redovisning
Projektet redovisas både muntligt och skriftligt. Mer information kommer.

Förutom en fungerande implementation ingår följande:
  1. Dokumentation av de klasser och gränssnitt som används för att bygga upp syntaxträdet (gärna, men inte nödvändigtvis, som html-sidor genererade med javadoc).
  2. Dokumentation av de klasser och gränssnitt som implementerar symboltabellen (gärna, men inte nödvändigtvis, som html-sidor genererade med javadoc).
  3. En kortfattad rapport som beskriver hur typkontrollen utförs. Rapporten kan referera till dokumentationen i de ovanstående punkterna.
  4. Minst 7 exempel på MiniJava-program som innehåller olika syntaktiska och lexikala fel. Minst 7 exempel som är syntaktiskt korrekta men innehåller typfel.
    Syftet är att få en uppsättning testfall för implementationer av syntax- och typ-kontroll. Se därför till att så många olika saker som möjligt testas
Krav
Lösningen ska följa den struktur som Appel anger. Ett syntaxträd ska konstrueras och typkontrollen ska använda "visitors" som traverserar syntaxträdet. Implementationen måste uppfylla rimliga krav på kodkvalitet (inte vara ett "fulkodshack") och rapporten ska uppfylla rimliga språkliga krav.
Tips
Om du använder java cup så är det lite besvärligt att komma ifrån en shift reduce-konflikt i metoddeklarationerna. Beroende på hur du skriver grammatiken kan du få problem med metod-kroppen. Båda dessa kodsnuttar är rätt.
{
int a;
B b;
}
{
int a;
B = 2;
}
Konflikten beror på att din grammatik tvingas välja om "int a;" är den sista variabeldeklarationen när den bara sett "B" och alltså inte vet om B är en typ eller en variabel.

Antagligen har du ickeslutsymboler som heter ungefär VarDeclList och StatementList. Om VarDeclList är högerrekursiv är det regeln
VarDeclList ::= tom
som ger problem. Om StatementList är vänsterrekursiv får man på liknande sätt problem med
StatementList ::= tom

Problemet försvinner nog om regeln för VarDeclList görs vänsterrekursiv och regeln för StatementList görs högerrekursiv.

Egen projektuppgift

Om du vill kan du föreslå en egen projektuppgift. Den ska då innehålla moment som motsvarar minijava-projektet: lexikal analys, syntaktiskt analys och någon sorts bearbetning. Innan du sätter igång behöver du skriva en specifikation av uppgiften och få specifikationen godkänd av kursledaren.

topp>>

Sidansvarig: Mikael Goldmann <migo@kth.se>
Uppdaterad 2005-11-03