UPPSALA UNIVERSITET  
Inst. f. lingvistik och filologi Lärare: Marco Kuhlmann
Uppsala universitet
Hoppa över länkar



Parsningsalgoritmer

Earley-algoritmen

Avsedda lärandemål: Att kunna implementera en chartparser (här: Earley-algoritmen) i Java samt testa och informellt förklara arbetssättet hos denna implementation. Dokumentera aktuell kod på ett användbart sätt.

Utgångsmaterial

Rapportering Lab 2-3

Rapportering: Lämna in den kommenterade källkoden. Testa implementationen. Demonstrera programmet för läraren och redogör för hur testet.

Bedömning: Betyget G kräver att du lämnat in kommenterad källkod för huvuduppgiften samt den testgrammatik som du använt för (test)-uppgiften. Koden måste kunna kompileras och utföras utan ändringar och implementationen måste fungera med din testgrammatik. Betyget VG kräver att du ytterligare utfört uppgift (vg).

Uppgifter Lab 2

(2) Fyll i kod som implementerar metoderna getAxioms(), getConsequencesScan() och getConsequencesComplete() i EarleyBU.java. Den färdiga klassen ska implementera bottom-up versionen av Earley-algoritmen.

(2 test) Hitta på en grammatik (med någon grad av lingvistisk plausibilitet) och testa din implementation med den. Använd gärna debug-funktionaliteten i skelettfilarna. Redogör för din testmetod.

(2 vg-uppgift) Ponera att man byter ut kodbiten A mot B i AbstractParser.java:

A: if (chart.add(item)) { agenda.put(item); }
B: chart.add(item); agenda.put(item);

Skriv en grammatik som accepterar bara en mening men som gör att Earley-parsern loopar i all oändlighet i fall (B) och terminerar i fall (A). Förklara hur du tänkt. Hur många parseträd tillåter din grammatik för meningen?

Uppgifter Lab 3

(3) Fyll i koden som behövs för att implementera metoderna getAxioms() och getConsequencesPredict() i EarleyCanonical.java. Den färdiga klassen ska implementera den kanoniska versionen av Earley-algoritmen.

(3 test) Hitta på en grammatik (med någon grad av lingvistisk plausibilitet) och testa din implementation med den. Använd gärna debug-funktionaliteten i skelettfilarna. Redogör för din testmetod.

(3 vg) I en ny version av koden (PA-2009-05-13.tar.gz) hittar ni två nya klasser:

    Derivation.java
    ParseForest.java

Med hjälp av dessa två klasser kan man transformera de algoritmerna som ni har implementerat, som hittills bara är igenkänningsalgoritmer, till riktiga parsrar. I den här uppgiften ska ni göra detta för CKY.java.

Idén är att man lägger till en ny instansvariabel parseForest till CKY.java, på samma sätt som grammar och input i AbstractParser.java. Sedan måste man tala om för denna ParseForest att komma ihåg vilka slutsatser man har dragit. Den centrala metoden för detta heter infer(); ni hittar den i ParseForest.java.

(a) Lägg till en ParseForest till CKY.java. Anropa metoden infer() i denna ParseForest på det rätta sättet på varje ställe där man ta fram ett nytt item (axiom eller konklusion).

(b) Lägg till en metod Set<Derivation<CKYItem>> getDerivations(CKYItem item) till CKY.java som returnerar mängden av alla härledningar för det angivna item. Den kan helt enkelt kalla motsvarande metod i ParseForest.java.

(c) Modifiera PA.java så att den inte bara skriver ut chartena, utan också mängden av alla härledningar för item [S 0-n], där S är grammatikens startsymbol och n är inputföljdens längd. Skriv också ut storleken på denna mängd.

(d) Testa din implementation genom att köra parsern med grammatiken grammar1.txt och längre och längre följder av "a". Implementationen är korrekt om du kan reproducera Catalan-talen, som du hittar här.