Informasjon om obliger i INF5110

Denne siden inneholder informasjon om obligene i INF5110 v?ren 2006.

Innhold

• Oblig 1
• Oblig 2
• FAQ
• Installasjon av Antlr
• Eksempler
• Notat om ?rets verkt?yvalg (bakgrunn og sammenlikningsgrunnlag med andre verkt?y)

Oblig 2

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. Kravene til innleverte filer og format er de samme som sist, bortsett fra at det holder med en parser. I tillegg skal resultatene fra kj?ring av en testsuite leveres.

Fristen er torsdag 18. mai.

Testsuiten

Testsuiten er ett python-skript som rapporterer fra kj?ring av analyseprogrammer mot testfiler for Diss. Testene kj?res ved ? bruke en kommando som f?lger, med arbeidskatalog der du har pakket ut testene (e.g. "tests"), i ett Unix-skall:

      $ ./runtests.py "java -classpath /sjk/programs/antlr-2.7.6/antlr.jar:../solution/build/classes Dissent"
    

Merk:

• Anf?rselstegn rundt java-kommandoen for at python skal oppfatte hele kommandoen som ett argument.
• Juster klassestien til din lokale installasjon og katalogstruktur (etter "-classpath"), samt klassenavnet p? ditt analyseprogram ("dissent" over).

Sjekkliste for del to

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

• 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 void Main(), d.v.s. ingen argumenter og ingen returverdi.
• Funksjonsdeklarasjoners returverdi er:
  • void, 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 med void 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.

Installasjon av Antlr

Jeg har pr?vd ? gj?re min installasjon av Antlr lesbar og eksekverbar for alle. Den ligger p?: ~svenjok/programs/antlr-2.7.6/. For ? bruke denne, bytt ut alle forekomster av antlr.jar med ~svenjok/programs/antlr-2.7.6/antlr.jar i kommandoer og byggeskript.

Fullversjonen

De som vil installere sj?l, kan bruke f?lgende oppskrift (dette virker ogs? greit p? Windows XP med Cygwin):

1. Last ned siste versjon (2.7.6) av Antlr
2. Pakkes ut med:

   $ tar xzvf antlr-2.7.6.tar.gz

3. Bygges med:

   $ cd antlr-2.7.6/
   $ ./configure --disable-examples
   # "make install" kan ogs? kj?res, hvis du har skriverettigheter til
   # /usr/local/lib .
   $ make 	
   	

Dette produserer antlr-2.7.6/antlr.jar, som trengs for ? kj?re verkt?yet og genererte programmer.

Antlr-eksempler

Alle eksemplene kan lastes ned her.

Bruke byggeskriptet p? din egen kode

For ? bruke build.xml (krever Ant 1.6.5) p? din egen kode, trenger du bare ? bytte ut filnavn i m?let run-antlr, og sette innstillingen antlr.home. ? sette antlr.home kan gj?res p? (minst) to m?ter:

1. Rediger build.xml, bytt ut linja:

   <property name="antlr.home" value="/usr/local/lib"/>

   med

   <property name="antlr.home" value="/ifi/fenris/h05/svenjok/programs/antlr-2.7.6"/>

2. Overstyres fra kommandolinja:

   $ ant -Dantlr.home=/ifi/fenris/h05/svenjok/programs/antlr-2.7.6

Oversikt over eksemplene

build.xml

Ant-byggeskript for eksemplene.

SimpleExp.g

Arne Maus' enkle uttrykksgrammatikk, fra forelesningen 14.02, formulert i Antlr. Demonstrerer omskriving til h?yrerekursjon, EBNF, enkel main-metode som leser fra std. input, linjetelling i skanneren.

SimpleExpWithAST.g

Samme som SimpleExp.g, men lager ett syntakstre og skriver det ut til std. output. Demonstrerer header-seksjon, gjenbruk av skanneren til SimpleExp.g via importVocab-opsjonen, buildAST-opsjonen og Antlrs operatorer for trebygging.

AmbigiousExp.g

En litt vanskeligere infiks uttrykksgrammatikk, med aksjonskode som bygger ett heterogent AST. Demonstrerer returverdier fra produksjoner, tempor?re variabeldeklarasjoner i initialiseringsaksjoner ("init actions"), labels for ? holde terminaler fra skanneren, tilordninger for ta vare p? returverdier fra parsering av andre regler, aksjoner som bygger syntakstrenoder, og import og eksport av token-vokabularer (for at to parsere og en skanner skal bruke samme terminaler).

AmbigiousExpAST.g

Samme som AmbigiousExp.g, men bruker Antlrs AST-operatorer til ? bygge treet. Merk at defn. av heterogene AST-typer for terminalene er i en token-seksjon for skanneren, i AmbigiousExp.g. Inneholder ogs? ett eksempel p? en treparser som beregner verdien av uttrykket. I tillegg demonstrerer den deteksjon av parseringsfeil i Antlrs defaulte feilh?ndtering, ved ? overstyre LLkParser.reportError.

Exp.java

Grensesnittet til toppniv?-noden i AmbigiousExps AST.

BinaryExp.java

Impl. av en AST-node for bin?re uttrykk (skulle egentlig v?rt, mer presist, artimetiske uttrykk) i AmbigiousExps grammatikk.

NumberExp.java

AST-node for talluttrykk fra AmbigiousExps grammatikk.

LL2.g

Enkelt eksempel p? en grammatikk som trenger to terminaler lookahead. Viser bruk av opsjonen k = 2 p? parserklassen.

NonLLk.g

En variant av ifelse-problemet, l?st med bruk av ett syntaktisk predikat. Viser ogs? gjenbruk av en skanner fra en annen fil, v.h.a. av opsjonen exportVocab, som har omtrent samme effekt som om skanneren var plassert til slutt i samme fil som parseren.

SimpleScanner.g

Standalone skanner i egen fil. Viser hvordan man kan teste skanneren separat i main-metoden.

SimpleXML.g

Forenklet eksempel p? en XML-parser, parser ett lite subsett av gyldig XML. Viser ogs? bruk av protected regler i skanneren (produksjoner som er private for skanneren, og ikke kan kalles fra parseren), og en mer fleksibel main, som h?ndterer stdin eller en liste inputfiler, og setter filnavnet i parseren (for at std. feilh?ndtering prefikser meldinger med filnavnet).