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