INF 5110 V2005: Obligatorisk oppgave

---

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

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

Hensikten med oppgaven

• Omarbeide en grammatikk fra ?n form (utvidet BNF) til en annen (BNF som passer til Yacc).
• Bruke Lex og Yacc (eller lignende, f.eks. Flex og Bison).
• Kunne kontrollere presedens og assosiativitet p? to m?ter:
  (1) Ved ? lage en entydig grammatikk som gir riktig presedens/assosiativitet, og
  (2) gi en flertydig grammatikk og styre presedens og assosiativitet ved passelige kommandoer i Yacc.
• Designe noder til et passelig abstrakt syntaks-tre, og komme i inngrep med Lex/Yacc 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.

Implementasjonsspr?k

Det er lagt opp til at man implementerer kompilatoren i C eller C++. Dersom man ?nsker ? utf?re oppgaven i C# eller Java vil dette ogs? bli godtatt, men man er da i st?rre grad p? egen h?nd. Man m? da f.eks finne alternativer til yacc/lex p? disse platformene (de finnes). Implementasjoner i mer obskure spr?k vil ikke bli rettet (ingen kompilatorer i SML, Prolog eller lisp, takk). Hvis i tvil, sp?r gruppel?rer.

Selve oppgaven

Oppgaven g?r ut p? ? lage et program, ved hjelp av Lex og Yacc (eller tilsvarende), 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 program er semantisk korrekt. Man kan trygt ignorere alt som st?r i notatet vedr?rende sjekking av semantikk og/eller har med kj?retidsforhold ? gj?re. Glupe hoder vil muligens komme til den slutning ut fra dette at semantisk sjekking blir en del av oblig 2, og man ser ingen grunn til ? avkrefte slike spekulasjoner.

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

Syntaks-tre

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 Yacc's $-variable p? stakken, som dermed m? defineres til ? v?re pekere til tre-noder.

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 syntaks-tre

N?r man har bygget opp et abstrakt syntaks-tre, skal dette skrives ut i prefiks-form. 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 et 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 uttrykks-grammatikker

1. Det skal brukes en grammatikk for hele Diss, 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 den som er angitt i spr?kdefinisjonen av Diss. Her skal de konfliktene som da n?dvendigvis oppst?r l?ses ved ? spesifisere assosiativitet og presedens til Yacc (med %left, %right, %nonassoc, etc.).

Merk at det er et problem med grammatikken n?r det gjelder if/else-setningen (jfr Louden 120-122). Man kan l?se dette p? to m?ter: Enten bruke fremgangsm?ten angitt i Louden (s 121), eller bruke Yacc-direktivet %expect 1. Dette vil fortelle Yacc at  man forventer at grammatikken inneholder ?n (og bare ?n) shift/reduce konflikt, og man vil ikke f? advarsler om dette. Yacc vil i dette tilfelle gj?re det "riktige" valget ved ? foretrekke en shift fremfor en reduce og assosierer dermed en else med n?rmeste if (jfr Louden 235-236).

Leksikalsk analyse

Feil i Diss-programmet

Gjennomf?ring og levering

• En forside med det fulle navnet og bruker-navnet p? den/de som er med p? denne besvarelsen.
• En kort rapport om gjennomf?ringen, hvor mange tilstander det ble med de to versjonene av uttrykk, etc.
• Lex-koden for scanneren
• Yacc-koden for de to syntaks-variantene
• Utskrift av noen gitte testprogrammmer (blir lagt ut, og beskjed gitt) og dump av syntaks-tre for disse, ved de to syntaks-variantene.

Dokumentasjon av Lex og Yacc

Det finnes ogs? to tilsvarende Gnu-produkter Flex og Bison som er noks? like Lex og Yacc, og som det ogs? finnes en del dokumentasjon om. Se http://www.gnu.org/software/flex/manual/ og http://www.gnu.org/software/bison/manual/