Automaadid, keeled ja translaatorid 2016/17 kevad

Kontekstivaba grammatika

Teooria

Tähtis on aru saada, mismoodi grammatika spetsifitseerib keele. Kuna tema sõnade hulk on täpselt need sõned, mis on tema algsümbolist tuletatavad, siis on kõige kesksem mõiste just derivatsioon. Alustame sellise mitmese grammatikaga:

(Kasutame lekseemi klassi id asemel lihtsalt üks konkreetne muutuja "x".)

1. Vaatame Varmo näide x+x*x. Teeme sellest sõnest kokku neli derivatsiooni: kaks vasak ja kaks paremderivatsioon! Sõnade hulga seisukohalt ei ole derivatsiooni strateegia oluline. Iga derivatsioon on tõend, et antud sõne kuulub meie keelde.
2. See on nüüd selge, et x+x*x kuulub meie keelde, aga derivatsiooni põhjal saame ka kätte avaldise struktuuri. Võtta need derivatsioonid ja joonista nendele vastavad süntakspuud.
3. Ürita aru saada, mis seos on derivatsiooni ja süntakspuu vahel. Selleks on hea mõelda, millised valikud on meil derivatsiooni teostamisel. Meil on kahte tüüpi valikud. Milline nendest valikutest on süntakspuu seisukohalt olulisem?
   • Me saame valida millist reeglit rakendada, kuna näiteks E jaoks on mitut reeglit, siis saab meie derivatsioonide algul E asendada nii liitmise kui ka korrutamise avaldistega.
   • Me saame valida, millist mitte-terminali asendada, näiteks E+E saab asendada esimest või teist mitte-terminali.
4. Fikseeritud derivatsiooni strateegia võtab meilt teist laadi valikuid ära. Fikseeri endale oma lemmikstrateegia: vasak või parem... jah, oleme siin ekstremistid. Vaata nüüd sõne x+x*x kõik derivatsioonid, mis kasutavad sinu valitud derivatsioonistrateegia. Need peaksid ka viima kahe erineva süntakspuudeni.
5. Veendu, et iga süntakspuu pealt saab süstemaatiliselt (näiteks) vasakderivatsioon välja lugeda. (See tähendab, et sa pead südamest tunnetama, et sul ei ole mingit valikut: puu määrab millist reeglit valida ja strateegia fikseerib millist mitte-terminali asendada). Kui strateegia on fikseeritud, siis saadki puu käest alati üks ja sama derivatsioon.

Kokkuvõtteks:

• Igale (suvalisele) derivatsioonile vastab üks süntakspuu.
• Igale süntakspuule vastab täpselt üks fikseeritud strateegiaga derivatsioon.
• Seega, kui maailmas oleks ainult lubatud vasak-derivatsioone (või ainult parem-derivatsioone), siis oleks süntakspuu ja derivatsiooni mõiste sisuliselt eristamatud.
• Grammatika on mitmene kui ühele sõnale leidub mitut süntakspuud (ehk mitut fikseeritud strateegiaga derivatsiooni).

Praktilisem lähenemine

Kui sa õppid paremini programmeerides, siis võid proovida grammatika oma käega katsetada ja implementeerida mõned meetodid, et genereerida derivatsioone. Oletame, et meil on selline lihtne grammatika:

Mis on sellele keelele vastavad sõned? Kas grammatika on mitmene? Milline sõne saab sel juhul mitmel moel tuletada? Kirjutame programm, mis laseb meil neid kõik defineerida.

Ülevaade klassidest

See programm on avalikus repos kättesaadav praks6/grammatika all. Seal on järgmised klassid, mida võib võrrelda Varmo definitsiooniga:

• Symbol: ülemklass meie kahte liiki sümbolitele V = N ∪ T.
  • NonTerminal: mitte-terminaalid N.
  • Terminal: terminalsümbolid T.
• Grammar: grammatika koosneb siis produktsioonireeglite järjendist (P) ja algsümbol (S).
• Production: produktsioonireegel kujul N → α, kus α on lausevorm.
• SententialForm: lausevorm on lihtsalt sümbolite järjend.
• Derivation: derivatsioon on siis lausevormide järjend.

Grammatikate defineerimine

Seal on üsna palju koodi ja tasub alustada Grammar.java main meetodiga, et aru saada, mida me lõpuks tahame saavutada. Seal faili lõpus on hunnik staatilised meetodid, mis teevad grammatikate loomine mugavamaks. Meil on seega suurepärane embedded DSL grammatikate kirjeldamiseks, et saame oma grammatika näiteks nii kirja panna:

        Grammar test = grammar(
                rule('S', "aABA"),
                rule('A', "b"),
                rule('A', ""),
                rule('B', "a"),
                rule('B', "bb")
        );

Derivatsiooni koostamine

Ülesanne on siis implementeerida derivatsioonid Javas. Selle programmi main meetodi käivitamise tulemuseks tahaks saada kõik derivatsioonid (kuni mingi piirini). Meie grammatika on aga lõplik, et peaks saama kõik derivatsioonid ära loendada küll. Tulemusena võiks olla näiteks järgmine:

Found 8 random derivations:
S -> aABA -> abBA -> abbbA -> abbb
S -> aABA -> aBA -> aaA -> aa
S -> aABA -> abBA -> abaA -> aba
S -> aABA -> abBA -> abbbA -> abbbb
S -> aABA -> aBA -> abbA -> abbb
S -> aABA -> abBA -> abaA -> abab
S -> aABA -> aBA -> abbA -> abb
S -> aABA -> aBA -> aaA -> aab

Resulting in 7 unique words:
[aa, abb, aba, aab, abbbb, abbb, abab]

Me valisime üsna rumal strateegia derivatsiooni koostamisel. Me ei otsi süstemaatiliselt vaid rakendame lihtsalt suvaline reegel, mis antud olukorras sobib. Meetod getRandomRhsFor(nt) tagastabki etteantud mitteterminaali jaoks suvalise lausevormi (ehk reegli parema pool: right-hand side). Seega jääb lihtsalt defineerida kaks asja:

1. SententialFormi juures võiks implementeerida meetodi, millega asendada antud mitte-terminal tema parema poolega. Selle meetodi juures me siis julmalt muudame lausevormi. (Üldiselt on ilusam uue tagastada, aga seekord oleme pisut nahaalsed.)
2. Grammari klassis defineerida meetod randomDerivation, mis järjest rakendab suvalist reeglit, kuni tal on sõna juba käes. Iga samm tuleb lisada Derivationile selle add meetodiga. (Derivation klass teeb koopia derivatsioonist... seda ei oleks vaja, kui replace ei oleks nii destruktiivne.)

Ja nüüd korralikult...

See oli päris rumal lähenemine asjale. Sisuliselt on ju tegemist otsingu ülesannega ja selline juhuslik pimedas eksimine ei ole kõige mõistlikum strateegia. Jääb siis lihtsalt implementeerida süstemaatilisem otsing, mis leiab kõik derivatsioonid kuni teatud pikkuseni. Selle ülesanne jaoks võib kõik klassid muuta ja parandada, et lahendus oleks võimalikult ilus.

Teine asi on see, et kui derivatsiooni strateegia on fikseeritud, siis saaks derivatsiooni esitada kui algsümbol ja produktsioonide järjend. Defineeri klass LeftDerivation, mis esitab derivatsioone selliselt. Sellele klassile saaks siis defineerida meetod toParseTree(), mis looks ka vastava puu. Selleks pead ise ka muidugi ParseNode klassi looma. (Tegelikult saab toParseTree() praegusele Derivation klassile defineerida, kui vaikimisi eeldada, et tegemist on vasakderivatsiooniga, aga siis peab tuvastama, mis reeglit rakendati.)

Oma lahendust võiks Vesalile näidata individuaalse nõustamise tunnis (E 16:15-18:00). Heade lahenduste eest võin jagada boonuspunkte.