Obligatorisk oppgave i INF5110 v�ren 2006

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

Dette er den f�rste av to oppgaver v�ren 2006. Oblig 2 vil bygge videre p� det som gj�res i oblig 1.

Innhold

• Hensikt
• Verkt�y
• Oppgaven
  • Syntakstre
  • To grammatikker
  • Leksikalsk analyse
  • Feilh�ndtering
• Administrivia

Hensikten med oppgaven

Tanken bak denne oppgaven er at man skal f� litt praktisk erfaring med f�lgende:

• Bruke skannings- og parseringsverkt�y, i dette tilfellet Antlr.
• Omarbeide en grammatikk fra �n form (utvidet BNF) til en annen (BNF som passer verkt�yet).
• Kunne kontrollere presedens og assosiativitet i parserverkt�yet ved �:
  1. Skrive om grammatikken, og
  2. Rette opp abstrakte syntakstr�r fra h�yrevridde parsetr�r ved � parametrisere produksjoner (og, indirekte, genererte recursive descent-metoder) .
• Designe noder til et passelig abstrakt syntaks-tre, og komme i inngrep med parserverkt�yet slik at man f�r bygget opp disse tr�rne.
• Gj�re noe passelig med tr�rne som blir bygget. Vi skal skrive det abstrakte syntakstreet til standard ut i et gitt format. I tillegg skal uttrykk dumpes i en parentetisk form med korrekt presedens og assosiativitet.

Verkt�y

I �r skal dere implementere kompilatoren i Java, ved hjelp av skanner- og parser-generatoren Antlr. Vi anbefaler ogs� sterkt � bruke Ant eller GNU make til bygging av kildekoden, slik at hele innleveringen kan bygges og testes med noen f� kommandoer.

Selve oppgaven

Oppgaven g�r ut p� � lage et program, ved hjelp av Antlr, som skal sjekke at programmer i spr�ket Diss er syntaktisk korrekte. Spr�ket er definert i et eget notat som kan hentes her. Merk at det i oblig 1 ikke er n�dvendig � sjekke at programmer er semantisk korrekte. Man kan trygt ignorere alt som st�r i notatet vedr�rende sjekking av semantikk og/eller har med kj�retidsforhold � gj�re. Dette blir tatt opp seinere i oblig 2.

Det ville v�rt naturlig med en del 3 der man laget en kodegenerator for spr�ket, men vi avst�r fra dette.

Syntakstre

Man skal under parseringen av spr�ket bygge opp et abstrakt syntakstre. Man skal designe noder (og implementere dem) for dette treet. Man m� holde greie p� subtr�r til treet mens parseringen av uttrykk foreg�r. Dette kan gj�res med aksjonskode og returverdier fra produksjoner i en Antlr- grammatikk. Returverdier og midlertidige variable som holder subtr�r ved rekursiv parsering, deklareres som passende nodetyper.

Legg merke til at bare det abstrakte syntaks-treet skal lages og skrives ut. For produksjoner av typen "if_stmt ->stmt" skal det alts� ikke lages noen ny node.

Utskrift av syntakstre

N�r man har bygget opp et abstrakt syntaks-tre, skal dette skrives ut i prefiksform. Hver node i det abstrakte treet skal representeres med ett par av parenteser, og hvert "barn" av denne noden skal inng� i mellom disse parentesene. Rett etter f�rste parentes kommer navnet p� noden (som angitt i grammatikken), fulgt av attributtene (barna) til noden. Dette illustreres best ved ett eksempel:

• Canonical.diss - input til kompilatoren
• Canonical.ast - output fra kompilatoren

Eksempelet kan anses som definitivt. Whitespace er valgfritt. Dog, for � bevare egen og andres mentale helse, vil vi p� det sterkeste anbefale en layout tilsvarende den i eksempelet.

Oppgaven skal l�ses med to forskjellige grammatikker

1. En konsis, men flertydig grammatikk. Her skal grammatikken, i sin originale form brukes s� langt som mulig, og konflikter l�ses ved � bruke Antlrs LL(k)- egenskaper (opsjonen k=n, syntaktiske og semantiske predikater).
2. En (mest mulig) entydig grammatikk for spr�ket som er (n�r) LL(1). For � f� den i utgangspunktet ambisi�se EBNF-grammatikken til LL(1), m� den venstrefaktoriseres.

Merk at i begge tilfellene m� grammatikken skrives om manuelt for � oppfylle kravene til presedens og assosiativitet. Man m� da alts� innf�re en egen ikke-terminal for hvert presedens-niv�, og gjennom grammatikken s�rger for riktig presedens og assosiativitet (og ikke-assosiativitet) for operasjonene.

Sammenlikne de to parserne: unders�k og karakteriser konfliktene i den opprinnelige grammatikken (Antlr advarer om non-determinisme), og forklar hvordan du l�ste dem. Det er tilstrekkelig � bygge og skrive ut syntakstreet fra �n av grammatikkfilene. Den andre grammatikken trenger derfor ingen aksjonskode, bare Antlr-grammatikk som kan generere ett program som gjenkjenner Diss-kode.

Leksikalsk analyse

Man trenger ikke gj�re noe s�rlig ut av terminaler av konstante tegnstrenger, det enkleste er � bruke dem bokstavlig i parseren og stille inn skanneren til � sl� dem opp ved matching av tokens fra ett supersett (f.eks. "if" ved skanning av en identifikator). Opsjonen testLiterals kan brukes til dette.

Hovedoppgavene til skanneren blir � gjenkjenne identifikatorer og konstanter, samt � hoppe over kommentarer og blanke tegn. Ved levering av et token fra skanneren vil metoden Token.getText() gi angi den tekstlige attributtverdien til symbolet.

Feilh�ndtering

Gjennomf�ring og levering

Man b�r arbeide i grupper p� tre personer (p� grunn av arbeidsmengden). Det som skal leveres er:

• En forside med navn og brukernavn fra dem som leverer besvarelsen.
• En kort rapport om gjennomf�ringen: forklaring av designet og konfliktene i grammatikken og l�sningene i de to grammatikkvariantene.
• All kode som trengs for � bygge og kj�re parserne, herunder:
  • Antlr-koden for skanneren
  • Antlr-koden for de to syntaksvariantene
  • Java-koden for syntakstreet
  • Byggeskript: build.xml eller Makefile
• Instruksjoner for bygging og kj�ring
• Utskrift fra kj�ring med Canonical.diss som input

Levering

Besvarelsen leveres som ett pakket filarkiv (zip- eller tgz-format) til gruppel�rer Sven-J�rgen Karlsen. Subversion-brukere kan ogs� levere via ett repository (bare gi meg leseaksess, og kommandoen for � lese ut prosjektet).

Ressurser

Det viktigste her er det som st�r om LL-parsing i l�reboka i kap 4, og om omskriving av flertydige grammatikker i 3.4. Bakgrunnskunnskaper om DFA-baserte skannere, som Lex, fra 2.6 i l�reboka, er nyttig, men det er viktig � v�re klar over at skanneren til Antlr ikke er DFA-basert, men recursive descent! Noe som b�de legger til muligheter for kontekstlig analyse, og skaper nye problemer, jfr. omfatttende kapittel om skanning i ref.manualen.

Antlr-dokumentasjon

• Nettsted
• Referansemanual: det nyttigste er de to f�rste kapitlene, om metaspr�ket, og om leksikals analyse (hvor dessverre mye man trenger � vite om avanserte lookahead- predikater er begravd).
• FAQ