Automaadid, keeled ja translaatorid - Kursused

Ennustav parsimine

Sellesse teemasse võib rohkem süveneda järgmine nädal, kui loengu ja kordamistestidega jõuame praktikale järgi.

Parseri kood asub parsers paketis. Sisendi läbimiseks vajalikud abifunktsioonid on defineeritud ülemklassis Parser. Kõige olulisem on seal funktsioon match, mis realiseerib sisendsümbolite lugemise reeglid. Eelnevalt oleme tutvunud peamise skeemiga, kuidas teisendada grammatika Java koodiks, aga me jätsime üsna lahtiseks, kuidas reeglite vahel valitakse.

Sisendi põhjal õige produktsiooni valimine

Paketis wisdom on mõned erinevad mõtteid, kuidas seda teha. Üks võimalus oleks lihtsalt juhuslikult valida kahe variandi vahel. Random käitub täpselt nii ja töötab üllatavalt hästi väikeste sisendite korral. Juhusliku valiku tegemine ei ole väga tõsiseltvõetav lähenemine, aga kõikide variantide süstemaatiline läbivaatamine jõumeetodil (Brute) ei ole piisavalt efektiivne.

Mõnede grammatikate korral aga õnnestub teatud sümbolite ette piilumisega kohe ära öelda, milline valik on õige. Vaatame näiteks antud grammatikat:

S → aSb

S → ε

Kuna esimene produktsioon algab tähega "a", siis võiks seda valida, kui järgmine täht sisendis on "a". Ainus probleem võib olla see, et teine reegel äkki sobib ka siis, kui sisendiks on "a". Kuidas saame kindlaks teha, millal "S → ε" on sobilik produktsioon? Kuna parem pool on tühi, siis peab vaatama, mis võib S-ile järgneda. Vaatame kõik grammatika produktsioonide paremad pooled läbi ja kirjutame üles kõik, mis S-ile võib järgneda. Esimeses produktsioonis (aSb) näeme, et S-ile võib järgneda "b". (Lisaks, kuna S on algsümbol, siis võib ka talle järgneda teksti lõpp (EOF), mida teoorias tihti tähistatakse dollar-märgiga "$")

Seda, millise reegli peaks valima, saab ka süstemaatiliselt välja arvutada. Loengus tuleb sellest järgmine nädal juttu, aga ma soovitan kõigepealt JFLAP-i abil kontrollida, et ülalolev intuitiivne arutelu on korrektne. Selleks tuleb sisestada grammatika JFLAP-is ja siis valida "input" -> "Build LL(1) parse table". Kui vajutada seal "do all", siis peaks all paremal olema tabeli kujul näidatud:

	a	b	$
S	aSb	ε	ε

Kõige olulisem on siinjuures see, et need hulgad ei kattu: esimest reeglit tuleb rakendada ainult siis, kui sisendis on "a" ja teist reeglit ainult siis, kui sisendis on "b" või "$". Sellega oleme ennast veennud, et sisendi ühe tähe ette vaatamisega saab üheselt valiku ära teha. Nüüd võime seda informatsiooni kasutada, et kirjutada deterministliku parseri. LL1 teeb juhusliku valiku asemel mõistliku valiku tänu sellele, et vaatab ühe tähte sisendis ette funktsiooniga peek:

        switch (peek()) {
            case 'a':
                // S -> aSb
                match('a');
                s();
                match('b');
                break;
            case 'b':
            case '$':
                // S -> ε
                epsilon();
                break;
            default:
                // Viskame ootamatu sisendi kohta erindi (lubatud on 'a', 'b' või EOF).
                expected('a', 'b', '$');
        }

Kui nende expected hulkade arvutamine tundus segane, siis ära muretse. Nendest räägitakse loengus palju põhjalikumalt.

Parsepuu loomine

Parsepuu genereerimine väga palju keerukust juurde ei lisa. Tagastame lihtsalt ehitatud puu. ParserDemo peamine funktsioon on nüüd defineeritud järgmiselt:

    Node s() {
        Node n = new Node("S");
        switch (peek()) {
            case 'a': 
                // S -> aSb
                n.add(match('a'));
                n.add(s());
                n.add(match('b'));
                break;
            case 'b':
            case '$':
                // S -> ε
                n.add(epsilon());
                break;
            default:
                expected('a', 'b', '$');
        }
        return n;
    }

Parsepuu genereerimine on üldiselt üsna lihtne, aga kui teisendame grammatikat vasakrekursiooni eemaldmisel, siis tahaks ikkagi tagasi saada esialgsele grammatikale vastava struktuuri. Vaateme näitena avaldisgrammatikate teisendamist ja kuidas sealt saada tagasi õige AST. Meil on siis vaja natuke akrobaatikat, et tagastada avaldis õigel kujul: näiteks 7-2-1 tulemuseks peaks tulema (7-2)-1. Vaatame loengus esitatud avaldise grammatikat, kus on vasakrekursioon eemaldatud:

S → T R

R → '+' T R | ε

T → F Q

Q → '*' F Q | ε

F → 'x' | '(' S ')'

Parsepuu

Sellele vastav parser on failis astdemo/AvaldisParser. Kui seda käivitada sisendiga x+x*x+x, siis saame järgmise parsepuu, mis ei ole just kõige elegantsem:

Abstraktne süntakspuu

Proovige nüüd luua selle asemel abstraktne süntakspuu. Selleks peab mõtlema, mida produktsioonid R ja Q looma peaksid. Kuna nad on avaldise struktuuri mõttes poolikud, siis peab neile vasakpoolse konteksti argumendina kaasa andma! Selline realisatsioon on klassis AvaldisAst, aga palju lihtsam on abstraktne süntakspuu kätte saada, kui vasakrekursioon eemaldada kasutades regulaaravaldise notatsiooni:

E → T(+T)^*

T → F(*F)^*

F → (E)

F → x

Proovige ise teha õige AST while-tsüklite abil. See on palju lihtsam!

Harjutused (näidislahendustega)

MiniParser
Esimene Tase	Teine Tase	Kolmas Tase
S → aAa S → ε A → bB B → b	S → aAa S → ε A → bB A → bSc B → b	S → aAa S → ε A → bB A → bSc B → b B → Bc

AbbaParser
Esimene Tase	Teine Tase	Kolmas Tase
S → ABAR A → a B → bb R → +S R → ε	S → ABAR A → a A → aAb B → bb R → +S R → ε	S → ABAR A → a A → aAb B → bb B → BbSb R → +S R → ε

BoratParser
Esimene Tase	Teine Tase	Kolmas Tase
S → AB A → boA A → ε B → rat	S → AB A → boA A → baA A → ε B → rat	S → AB A → boA A → baA A → ε B → rat B → Bbi B → Blo

AktParser
Esimene Tase	Teine Tase	Kolmas Tase
S → AkT A → aA A → ε T → t	S → AkT A → aA A → ε T → t T → tSp	S → AkT A → aA A → ε T → t T → tSp T → Tt

Kõigepealt vaadake MiniParser grammatika lahendusi (parsers.mini.levels), mida võib eeskujuks võtta. Seal on näitena toodud lisaks rekursiivsele lahendusele ka erinevad lahendused vastavalt raskusastmetele. Kui oled seda näidet uurinud, siis võid proovida lahendada järgmised ülesanded eelmistest aastatest:

AbbaParser ( )
BoratParser ( )
AktkParser ( )

Nende lahendused ilmuvad ka sols kataloogi.

Lisatöö: Ennustav parsimine

Selles ülesandes harjutame natuke kontekstivabade grammatikate käsitsi teisendamist parseriteks ja parsepuu loomist. Projekti aluseks tuleks võtta week6.parsers.xtra paketi klassid. Kõik parserid tuleb ehitada parsers paketti koodi põhjal, s.t. nad võiksid olla Parser alamklassid.

Esitada saab moodle'is. Kokku on kümme testi, kusjuures kaks neist on iga ülesanne juures ainult keele äratundmise kohta, aga siis on iga ülesanne juures mõned natuke raskemad ülesanded, mis puudutavad puude ehitamist või veatöötlust.

1) SAParser

Esimesena tuleks kirjutada Parser järgmise keele jaoks:

S → aSb | aA | c

A → bAb | d | Ac

Esimeses reeglis on kaks valikut, aSb ja aA, mis algavad sama tähega. Teine reegel on vasakrekursiivne. Grammatikat peab seega teisendama: paneme esimese reegli jaoks uue mitte-terminali nimeks R ja teise reegli jaoks uue mitte-terminali nimeks Q. Paremal on toodud parsepuu näide sisendi abdb korral.

2) AC/DCParser

Järgmises grammatikas peab samuti vasakrekursiooni elimineerima:

S → aSdS | CS | ε

C → c | C/

Seekord tuleb aga originaalse grammatika parsepuu tagastada. Näiteks ac/dc parsepuu peaks tulema nagu paremal joonisel.

3) TypeParser

Viimane grammatika on inspireeritud C keele tüübideklaratsioonide grammatikast:

S → TD

T → int | void

D → *D | A

A → (D) | A[] | ε

Siin tuleb kõigepealt lihtsalt parsida. See vajab vasakrekursiooni elimineerimist. Lisaks tahame aga ka luua abstraktse süntakspuu, mis kirjeldab tüüpide päris tähendusi:

int*[] → TArray(TPtr(TInt)).
int(*)[] → TPtr(TArray(TInt)).

Kahjuks ei ole C keel eriti LL-parsimiseks sõbralik keel ja see ülesanne on oluliselt raskem, kui esialgu võib tunduda. Väga puhtalt või ilusalt ei õnnestugi seda ära teha.