Automata, Languages and Compilers 2020/21 spring

Parserite kirjutamine Javas

Siin on eesmärgiks aru saada käsitsi parserite tööpõhimõtetest. Maitsed on erinevad ja praktikumides võidakse seda käsitleda teistmoodi, aga üks hea viis aru saada sellest meetodist ja omandada ka natuke sügavam arusaamine rekursioonist on vaadata, kuidas magasinmäluga automaat parserit implementeerib. Igal juhul võiks alustada lihtalt väikese parseri kirjutamisega. Failid asuvad pakettis kalaparser:

• Kirjutame keele aⁿbⁿ jaoks parseri IntroParser.java, mis tunneks neid sõnu, mis sinna keelde kuuluvad. Eesmärk on tüüpilise parseri operatsioonidega tutvuda.
• Lõpuks oleme siiski huvitatud ka süntakspuust. Teeme nüüd ka meie kalalekseri jätkuks ühe kalaparseri.

IntroParser

Teemat tutvustav video: Käsitsi parsimine (slaidid).

Proovime nüüd JFLAP-i abil aru saada ülalt-alla parsimise põhimõttest. Alustame lihtsa näidisgrammatikaga (simple.jff):

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 vastavust. Lisaks alguse ja lõpu üleminekutele on loodud kahte liiki üleminekud:

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

Arendame koos selle parseri failis IntroParser, mis tunneb selle grammatika sõnad ära ehk vastab ainult "jah" või "ei". Tegelikult viskab see erindi, kui sõna ei kuulu keelde, ja ei tee midagi, kui kõik on hästi. Parseri põhiosa tuleb meil selline:

    public void s() {
        switch (...) {
            case 0: // S -> aSb
                match('a');
                s();
                match('b');
            case 1: // S -> ε
                epsilon();
        }
    }

Kui uurisid ka automaate, siis on siinkohal oluline näha, et see kood käitub täpselt nagu JFLAP-i magasinmäluga automaat:

1. Iga produktsioon ekspandeerub läbi funktsiooni väljakutse selliselt, et tema parem pool tuleb ükshaaval töödelda. Miljoni dollari küsimus: kuhu on magasin kadunud?
2. Edasi lähme siis, kui sisendsümbol ühtib meie eeldatava tähega, mida kontrollime funktsiooniga match.

Me oleme siin ignoreerinud, kuidas valida reeglite vahel. See on eelkõige järgmiste loengute teema, aga konkreetsete näidete puhul saab seda lihtsalt läbi näha! Siin on näiteks kohe näha, et esimene reegel algab tähega 'a' ja selle järgi teeme lihtsalt valikut.

KalaParser

Proovime nüüd KalaLekseri pealt parsida sõned nagu (kala, (x,y , null, (), (kala,()) ). Kuna lekser tegeleb sõnadega, siis jääb meil sellise sisendi puhul struktuuri ära tunda justkui sellisel sõnel (w,(w,w,0,(),(w,()). Ja selliseid parsereid oleme muidugi kirjutanud...

Grammatika on järgmine:

Parser peab tagastama vastavad AST klassid, mis on defineeritud klassis KalaNode. Nad on aja kokkuhoidmiseks nüüd ette antud. Vaata need korra üle ja otsi implementeerimata jäänud meetod ja lisa see puuduolev rida.

Parser saab klassi isendid luua staatiliste meetoditega mkNull, mkIdent ja mkList. (Listi argumentide kogumisel pead võib-olla vahepeal ise haldama oma listi ja alles siis, kui oled valmis, saad mkList meetodiga AST klassi objekti luua.)