Automata, Languages and Compilers 2018/19 spring

Ennustav parsimine

Parseri kood asub parsers paketis. Sisendi läbimiseks vajalikud abifunktsioonid on defineeritud ülemklassis Parser.java. 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.java 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.java) 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:

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:

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.java teeb juhusliku valiku asemel mõistliku valiku tänu sellele, et vaatab ühte 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 sisend kohta erind (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.java 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:

Parsepuu

Sellele vastav parser on failis astdemo/AvaldisParser.java. 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 vasakpoolset konteksti argumendina kaasa andma! Selline realisatsioon on klassis AvaldisAst.java, aga palju lihtsam on abstraktne süntakspuu kätte saada, kui vasakrekursioon eemaldada kasutades regulaaravaldise notatsiooni:

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