INF5110 - Vår 2008

Obligatorisk oppgave 1 i INF5110 v�ren 2008

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

Dette er den f�rste av to oppgaver v�ren 2008. 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 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 (abstrakt?), 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. 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 ett 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 28. mars. Fristen er endelig.

Gjennomf�ring og levering

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

Levering

Besvarelsen leveres som ett pakket filarkiv (zip- eller tgz-format) til gruppel�rer Fredrik S�rensen <fredrso@ifi.uio.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 2008-02-19 16:12
Fredrik S�rensen