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



Parsningsalgoritmer

Uppvärmningsuppgift (enbart övning)

För att repetera Java-programmering och komma igång med de software-verktyg som vi kommer att använda under kursen har Marco förberett en liten uppgift åt er.

I denna uppgift ska ni implementera den abstrakta datatypen Stack som en Java-klass. Ni får specifikationen på gränssnittet i Javadoc-formatet och en Java-fil med skelettkod. Er uppgift är att fylla på skelettet med riktig kod, och att lägga till kod för att testa att er klass fungerar.

Utgå från filen PA.tar.gz, och i denna några filer som ska hjälpa er att komma igång. För närmare instruktioner, titta på filen README som ni får fram när ni packar upp arkivet. Där står bl.a. hur man kompilerar kod, och hur man får ut gränssnittsspecifikationen i form av en HTML-sida som ni kan öppnar. Själva skelettkoden finns i filen src/util/Stack.java.

Packa upp med: tar -xzf PA.tar.gz. Kika gärna lite på byggsystemet Apache Ant och innehållet i filen build.xml, vars uppgift är att hålla reda på källfiler och andra filer. (Det räcker om ni har ett hum om vad som händer.) Lycka till med uppgiften!

Om någonting förblir oklart, kontakta Mats eller Marco så hjälper vi till.

Laboration 1: Shift-reduce, transitionssystem och backtracking

Rapportering: Beskriv hur ni har tänkt/gjort. Inkludera relevant källkod i rapporten. Testa på något bra sätt och redogör för det i rapporten. Demonstrera resulterande program för läraren.

Bedömning: Godkänt kräver att (1) och (2) utförts. Väl godkänt kräver att (1) och (2) utförts på ett riktigt bra sätt jämte en av (3) och (4).

Uppgiften kan ersättas av en individuellt upplagd jämförbar insats.

Utgångsmaterial

Packa upp med: tar -xzf ALSY.tar.gz. Kika gärna lite på byggsystemet Apache Ant och innehållet i filen build.xml, vars uppgift är att hålla reda på källfiler och andra filer. (Det räcker om ni har ett hum om vad som händer.) Kommandot ant exekverar build.xml, som kompilerar och kör igång programmet (mainklass ALSY). Kommandot ant doc skapar dokumentationen (javadoc). Finn den i dist/api. En översikt ges i overheadbilderna. Källkoden finns i src. Titta runt lite så ser ni.

Programmet har ett grafiskt gränssnitt Några exempelgrammatiker finns i mappen gram. Testa systemet med två fördefinierade exempel, som finns i menyn.

En spårning av backtrackingarn/parsningarna hamnar i filen trace.html. Gränssnittets bild sparas som snapshot.png. Ett minianrop av transitionssystemet/backtrackern kan göras med:

java -jar dist/lib/TxtALSY.jar Jag var på mötet igår

Resultatet hamnar i trace.html. Källkoden src/TxtALSY.java sammanfattar det viktiga i det överordnade anropet på ett genomskinligt och komprimerat sätt.

Uppgifter

Det här handlar mest om att begripa hur saker och ting fungerar. Själva programmeringsinsatsen är ganska liten.

(1) Hitta på och testa en grammatik (med någon grad av lingvistisk plausibilitet) som leder fram till en shift/shift-konflikt mellan två lexikoningångar och en reduce/reduce-konflikt mellan två regler.

(Extra övning) Ändra prioriteringen mellan shift och reduce till reduce före shift. Se vad som händer med den ordning i vilken parsningsstegen sker.

(2) Backtrackingen sköts av metoden LinkedList<BTState> parse() i Backtracker. Modifiera denna på två sätt (utan att någon annan del av programmet skall påverkas än mindre sluta fungera):

(2 a) Lägg till en metod parseDetermin som för varje konfiguration bara följer första tillgängliga transitionen. (Den kommer alltså inte att göra någon backtracking.)

(2 b) Lägg till en metod parseFirst som avbryter när en accepterande konfiguration nåtts. Den backtrackar, men kan bryta tidigare än parse.

VG-uppgifter

Dessa programmeringsinsatser kan behöva gå in på flera klasser, men gäller mest ShiftReduce.

(3) Gör om shift så att den bara flyttar över terminaler till stacken och så att lexikonuppslagning blir en aspekt av reduce.

(4) Vanlig reduce opererar överst på stacken. Förändra systemet så att reduce kan göras på godtyckligt djup i stacken (som därmed behandlas mer som en lista vilken som helst). Detta gör systemet mer mångfaldigt icke-deterministiskt, utan att egentligen tillföra något, men det kan vara en bra övning.