Dette emnet er nedlagt

Obligatorisk oppgave 2.

Leveres som vedlegg i epost til Andre og Tore innen 16. november klokken 2400.    Inntil to studenter kan jobbe og levere sammen.

I denne oppgaven skal du lage en liten eksperimentapplikasjon for testing av forskjellige varianter av chart-parsing.  (Egentlig for testing av chart-recognizere – du trenger ikke tenke på retur av parsetrær).  Den skal være implementert i Common-Lisp.

 

Utgangspunktet kan være bottom-up-chartparseren (igjen recognizeren)  recog som ble gjennomgått på gruppen 26/10, men den skal være i stand til å fungere med vilkårlige regler for avledning av nye kanter fra gamle.  Istedenfor fundamentalregelen og de andre reglene som er “hardkodet” inn i recog.lsp, skal du kunne mate inn vilkårlige regler – representert som lisp-funksjoner – og teste ut den resulterende recognizeren.

 

Koden skal være uavhengig av hvilken grammatikk som brukes, men vi kan anta at det er en kontekstfri grammatikk uten tomme produksjoner, hvor hver regel enten bare har ikketerminaler til høyre, eller har et enkelt terminalsymbol til høyre.  Du kan gjerne bruke egne konvensjoner som gjør det klart hva som er terminalsymboler og hva som er ikketerminaler.  For enkelhets skyld kan vi anta at grammatikken ligger i en global variabel som alle prosedyrene har tilgang til.  Husk at grammatikken også skal spesifisere hva som er startsymbol.  Alternativt kan du bruke en konvensjon om at dette alltid er et bestemt symbol, for eksempel S.  (Det enkleste er selvsagt å bruke samme format som i recog.lsp.)

 

Applikasjonen skal fungere som følger:

 

Du starter den ved å skrive (cp_tester).  Deretter kan du gi kommandoer for å:

 

1)      Legge  inn en ny regel for avledning av nye kanter fra gamle. Denne kommandoen har tre parametre:

      - en streng som siden vil fungere som navn på regelen,

      - et tall som forteller hvor mange argumenter (kanter) regelen tar.  (Fundamentalregelen tar to argumenter, BU-predikasjonsregelen tar en, og initiering tar null.  Det er helt greit om du  begrenser deg til disse tre tallene.)

     - og til slutt selve regelen, representert som en funksjon som tar inn en liste av kanter og gir tilbake de kantene som kan avledes fra input-kantene ved hjelp av regelen.

     Ved innlasting av fundamentalregelen kan du da for eksempel gi inn strengen ”fundamental”, tallet 2, og en passende prosedyre som tar inn en liste av to kanter og leverer ut en tom liste hvis fundamentalregelen ikke kan brukes på disse to, og en liste inneholdende den (det vil her aldri være mer enn en) kanten som kan avledes fra disse to ved hjelp av fundamentalregelen.  Ved innlasting av BU-prediksjonsregelen kan du tilsvarende gi inn “bu_prediksjon”, tallet 1 og en passende prosedyre som tar inn en liste bestående av en enkelt kant og leverer ut listen av kanter som kan avledes fra denne ved hjelp av BU-prediksjon.  Denne listen kan være tom (for eksempel hvis kanten som kommer inn ikke er passiv) men kan også inneholde flere kanter.  Legg merke til at output i dette tilfellet vil være avhengig av den aktuelle grammatikken.

2)      Spørre hvilke regler som nå ligger inne.  Man får da tilbake listen av merkelapper på de innlastede reglene.

3)      Ta bort igjen en innlastet regel. Parameteren er da merkelappen på regelen.

4)      Parse en setning. Parameteren er da en liste av terminalsymboler som skal sjekkes for medlemskap i språket definert av grammatikken.  Det er nå du skal kjøre selve chart-parseren.  Hovedgangen finner du skissert side 22 i slidene fra forelesningen 31/10. Man får tilbake JA/NEI, avhengig av om det ferdige chartet inneholder en passiv kant fra start til slutt med startsymbolet til venstre.  (Legg  merke til at vi da godt kan få et NEI-svar selv om strengen faktisk er en lovlig setning i forhold til grammatikken.  Dette kan skje hvis de innlastede reglene ikke er tilstrekkelige til å avlede de kantene vi trenger.)  I tillegg returneres det totale tallet på kanter i chartet under den aktuelle kjøringen.

5)      Avslutte applikasjonen.

 

I tillegg bør du implementere en del passende regler som kan brukes som input til applikasjonen.  BU-prediksjon og fundamentalregelen er nevnt, og skal være blant disse, men du bør minimum også ha med top-down-prediksjon og en top-down initieringsregel, pluss en regel til.  Top-down-prediksjon er regelen som tar inn en enkelt kant og leverer ut en tom liste av kanter hvis inputkanten er passiv, men som derimot – når input er en aktiv kant fra i til j med punktert (“dotted”) regel A ®a×·B – leverer ut listen bestående av en kant fra j til j merket B ®×· g for hver grammatikkregel B ®×g.  (Altså en kant i outputlisten for hver regel i grammatikken med B på venstresiden.)  Top-down initieringsregelen er en regel som tar inn en tom liste av kanter og returnerer listen av alle kanter fra 0 til 0 merket med punkterte regler av typen S ®×· g. (Altså en kant i outputlisten for hver grammatikkregel som har startsymbolet S  på venstresiden.)      Et enkelt forslag til den siste regelen kan være en variant av BU-prediksjon som fra inputkant mellom i og j merket med B ®×b  ·  ikke (som BU-prediksjon slik den for eksempel ble presentert på forelesningen 31/10, se slides) returnerer en liste av kanter fra i til j merket A ® B·g men derimot en liste av kanter fra i til i merket  med A ® · Bg.   Initialiseringsregelen kan godt være hardkodet inn. Her tenker jeg på regelen som i læreboken (på nettet) legger inn en kant fra j-1 til j merket A ® a· hvis setningen som skal sjekkes har a i posisjon j og A ® a er en regel i grammatikken.  I recog.lsp er dette erstattet av noe som i de samme tilfellene i stedet legger inn den passive kanten fra j-1 til j merket a ® · .  Resultatet blir ofte det samme, avhengig av hvilke andre regler som er på plass.  Siste versjon er definert som regelen readwords i denne kodefilen med noen forslag til implementasjon av regler.  Så har dere noe å bygge ut fra.