INF5110 - V?r 2009

Obligatorisk oppgave 1 i INF5110 v?ren 2009

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

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

Innhold

Hensikten med oppgaven

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

Verkt?y

Dere skal implementere kompilatoren i Java, ved hjelp av skannergeneratoren JFlex og parsergeneratoren CUP. Vi anbefaler ogs? ? bruke Ant eller GNU make til bygging av kildekoden, slik at hele innleveringen kan bygges og testes med noen f? kommandoer. Det er lagt ut en beskrivelse av hvordan man installerer verkt?yene og bruker Ant her.

Selve oppgaven

Oppgaven g?r ut p? ? lage et program, ved hjelp av JFlex og CUP, som skal sjekke at programmer i spr?ket Db er syntaktisk korrekte. Spr?ket er definert i et eget notat. 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 dette notatet vedr?rende sjekking av semantikk og/eller har med kj?retidsforhold ? gj?re. Dette blir tatt opp i oblig 2.

Syntakstre

Man skal under parseringen av spr?ket bygge opp et abstrakt syntaks-tre. 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 gj?res greiest med aksjonskode og returverdier fra produksjoner i en CUP-grammatikk. Ikke-terminaler i gramatikken m? deklareres som de egendesignede nodetypene.

Trenodene lages i et hierarki, med arv, hvor man typisk har en veldig generell klasse p? toppen, for eksempel en generell node-klasse. Det er naturlige forhold mellom subtyper av noder, for eksempel vil if statement v?re en subtype av et generelt statement, som igjen vil v?re en subtype av for eksempel node. Virtuelle metoder i klassene kan da brukes ved traversering og bruk av treet.

Legg merke til at bare det abstrakte syntaks-treet skal lages og skrives ut. For produksjoner av typen "stmt -> if_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:

Whitespace er valgfritt i utskriften. Dog, for ? bevare egen og andres mentale helse, vil vi p? det sterkeste anbefale en layout tilsvarende den i eksempelet.

To grammatikker

Oppgaven skal l?ses med to forskjellige grammatikker:
  1. Det skal brukes en grammatikk for hele Db, der man lager en egen entydig syntaks for uttrykk. Denne skal alts? uttrykke alt om 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.
  2. Det skal ogs? lages en versjon der det bare er en enklest mulig flertydig syntaks for uttrykk som omfatter b?de logiske og aritmetiske uttrykk. Denne skal alts? likne mer p? den som er angitt i spr?kdefinisjonen av Db. Her skal de konfliktene som da n?dvendigvis oppst?r l?ses ved ? spesifisere assosiativitet og presedens til CUP (med %left, %right, %nonassoc, etc.).

Sammenlikne de to parserne: Unders?k og karakteriser konfliktene i den opprinnelige grammatikken og forklar hvordan du l?ste dem. Unders?k ogs? hvor mange tilstander CUP-automaten f?r for de to grammatikkene. Diskut?r ogs? om valg av gramatikk har noe ? si for hvor greit det er ? designe nodene og bygge syntakstreet.

Merk: Det er tilstrekkelig ? bygge og skrive ut syntakstreet fra ?n av grammatikkfilene. Den andre grammatikken trenger derfor ingen aksjonskode, bare CUP-grammatikk som kan generere et program som gjenkjenner Db-kode.

Leksikalsk analyse

Leksikalsk analyse skal utf?res med JFlex, som leverer ett og ett token til parseren ved kall p? metoden next_token();. Hovedoppgavene til skanneren blir ? gjenkjenne identifikatorer og konstanter, samt ? hoppe over kommentarer og blanke tegn. Hvordan man benytter JFlex og CUP sammen er beskrevet under emnet Working together - JFlex and CUP i manualen til JFlex. Det vesentlige ved integrasjonen er interfacet java_cup.runtime.Scanner som m? implementeres av scanneren. JFlex implementerer dette interfacet automatisk n?r man bruker %cup switchen i JFlex. Ved levering av et token fra skanneren vil det v?re av typen Symbol og metoden Symbol.value benyttes for ? levere tekster eller andre objekter fra scanneren til parseren.

Feilh?ndtering

Dersom det oppdages en syntaktisk feil i programmet skal man bare stoppe analysen av Db-programmet, og melde at det er funnet en feil. Det er ikke krav om noen spesielt intelligent feilmelding (men det er morsomt om man kan f? til noe her).

Frist

Fristen er fredag 20. mars.

Gjennomf?ring og levering

Man kan arbeide i grupper p? opp til tre personer. Det som skal leveres er:

Levering

Besvarelsen leveres som ett pakket filarkiv (zip- eller tgz-format) til gruppel?rer Andreas Svendsen <Andreas.Svendsen@sintef.no>. Subversion-brukere kan ogs? levere via et repository (bare gi meg leseaksess, og kommandoen for ? lese ut prosjektet).

Ressurser

Det viktigste her er det som st?r i l?reboka i kap 2.6 og 5.5 (Men der refereres det til de tilsvarende verkt?yene Lex og Yacc),

JFlex- og Cup-dokumentasjon

Sist oppdatert 2009-02-10 10:32
Andreas Svendsen