Automaadid, keeled ja translaatorid - Kursused

20. märtsi praktikum

Eclipse'i AST View

Help -> Eclipse Marketplace -> otsi "AST View"
Süntaksanalüüsi osa lõppeesmärk on sellise abstraktse süntakspuu kättesaamine.

Regulaaravaldised ja Kontekstivabad grammatikad.

Miks ei ole Varmo sulgude keel regulaarne? (Sellele vastav PCRE regex.) Kuidas saab veenduda, et mitte keegu ei oska kirjutada sellele vastav klassikaline regulaaravaldis?
Veendume nüüd JFLAP abil, et iga regulaarne keel on kontekstivaba.
- Teeme JFLAP-is lahti järgmine automaat: cfg.jff.
- Valime menüüst "Convert" -> "Convert to Grammar".
Konverteerime ka saadud grammatika tagasi automaadiks. Sellega loodetavasti selgub, kuidas igast paremlineaarsest grammatikast võib luua samaväärse automaadi. Seega, iga paremlineaarne grammatika spetsifitseerib regulaarse keele.
Loome sellele keelele vastav magasinmäluga automaat (PDA). Automaatide loomise kohta on võimalik informatsiooni leida siit.

Käsitsi kirjutatud parserid

Kõigepealt proovime JFLAP abil aru saada ülalt-alla parsimise põhimõttest. Alustame järgmise lihtsa grammatikaga (simple.jff):

S → aSb

S → ε

Teisendame selle magasinmäluga automaadiks kasutades "Convert CFG to PDA(LL)". Kõige olulisem on näha läbi JFLAP-i konstruktsiooni ja järgmise käsitsi kirjutatud parseri vastavus. Lisaks alguse ja lõpu üleminekutele on loodud kahte liiki üleminekud:

Iga produktsiooni jaoks võib produktsiooni vasaku poole asendada selle kehaga.
Sisendsümboli lugemise reeglid: sisendsümboli võime lugeda siis ja ainult siis, kui magasini tipus on oodatud sümbol.

Parseri kood asub meie bitbucketi repos. Alustame kõigepealt käsitsi kirjutatud keelde kuuluvuse kontrollijaga. See ainult vastab küsimusele, kas sõna kuulub keelde või mitte, aga süntakspuu ehitamisega see veel ei tegele. Selle vajalikud abifunktsioonid on defineeritud ülemklassis Recognizer.java. Kõige olulisem on seal funktsioon match, mis realiseerib sisendsümbolite lugemise reeglid.

Üks võimalus implementeerida ülaloleva grammatika produktsioonidele vastavad reeglid on juhuslikult valida kahe variandi vahel. Pärast tahame sisendi põhjal ennustada, milline variant on õige, aga koodi struktuur jääb samaks. RandomRecognizer.java käitub täpselt nii ja töötab üllataval hästi väikeste sisendite korral.

    void s() throws ParseException {
        if (generator.nextBoolean()) {  
            // S -> aSb
            match('a');
            s();
            match('b');
        } else   
            // S -> ε         
            epsilon();
    }

Siin on moodustavad grammatika reeglid loogilise avaldise, aga me käitume muidu täpselt nagu JFLAP-i magasinmäluga automaat:

Iga produktsioon ekspandeerub läbi funktsiooni väljakutse selliselt, et tema parem pool tuleb ükshaaval töödelda.
Edasi lähme siis, kui sisendsümbol ühtib meie eeldatava tähega, mida kontrollime funktsiooniga match.

Miljoni dollari küsimus: kuhu on magasin kadunud?

Sisendi põhjal õige produktsiooni valimine

Juhusliku valiku tegemine ei ole väga tõsiseltvõetav lähenemine, aga isegi kõikide variantide süstemaatiline läbivaatamine jõumeetodil 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 grammatika:

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 võib-olla 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 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. LLRecognizer.java teeb juhusliku valiku asemel mõistliku valiku tänu sellele, et vaatab ühte tähte sisendis ette funktsiooniga peek:

    void s() throws ParseException {
        switch (peek()) {
            case 'a': // S -> aSb
                match('a');
                s();
                match('b');
                break;
            default:  // S -> ε
                epsilon();
        }
    }

Süntakspuu genereerimine

Me oleme siiski huvitatud ka süntakspuust. Süntakspuu genereerimine väga palju keerukust juurde ei lisa. Loogilise avaldise asemel ehitame nüüd puu servad. LLParser.java peamine funktsioon on nüüd defineeritud järgmiselt:

    Node s() throws ParseException {
        Node n = new Node("S");

        switch (peek()) {
            case 'a': // S -> aSb
                n.add(match('a'));
                n.add(s());
                n.add(match('b'));
                break;
            default:  // S -> ε
                n.add(epsilon());
                break;
        }
        return n;
    }

Kui tahame programmeerimiskeele süntakspuud edasi töödelda, siis tahame tihti saada natuke abstraktsemal kujul süntakspuu, kui see, mis oli otseselt grammatika põhjal saadud. Vaatame näiteks loengus esitatud grammatikat, kus on vasakrekursioon eemaldatud:

E → TR

R → +TR

R → ε

T → FQ

Q → *FQ

Q → ε

F → (E)

F → x

See grammatika (leftfac.jff) on mõeldud JFLAP-ile ja viimane reegel on siis muutuja või literaali rollis. Teeme nüüd "build LL(1) parse table", "do all" ja "parse". Kui proovida näiteks sisendiga x*x+(x+x)*x, siis peaks olema selge, et süntakspuu ei näe üldse nii välja nagu me tahaks. Palju lihtsam on mõistliku abstraktse süntakspuu kätte saada, kui vasakrekursiooni eemaldada, kasutades regulaaravaldise notatsiooni:

E → T(+T)^*

T → F(*T)^*