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.