Automaadid, keeled ja translaatorid - Kursused

Vasakrekursiooni elimineerimine

Loengus käsitletakse palju formaalsemalt vasakrekursiooni eemaldamist ja sellisel tasemel on kasulik see endale eksami teooria osaks selgeks teha, aga praegu on peamine eesmärk näidede põhjal kõhutunnet arendada. Kuna regulaaravaldised on juba selged ja me teame, et iga regulaaravaldis on ka grammatikana kirja pandav, siis väljendame asju pigem regulaaravaldistena.

Kirjutage järgmised grammatikad ümber regulaaravaldistena:

S → Sa | x
S → Sa | x | y
S → Sa | Sb | x | y
S → Sa | Sb | x | y | ε

Nüüd võib, kui on aega palju, ka vaadata, kuidas neid teisendada tagasi grammatikaks, aga pigem kasutades paremrekursiooni. Selleks tuuakse sisse lisareegel, mis selle kordamist teostab.

Originaalne	Regulaaravaldis	Teisendatud
S → Sa S → x	S → xa*	S → xR R → aR R → ε

Natuke suurem näide

Kui oled ülalolevad näited läbi teinud, siis tegelikult oled juba kõiki võimalusi näinud, aga Sa pead lihtsalt ära tabama, et vasakrekursiooni eemaldamise mõttes on järgmised kolm grammatikat samamoodi käsitletavad:

S → Sa | x
S → SaS | x
S → Sõöäü | aSbS | ε

Kui Sa ei usu, siis pane õigetesse kohtadesse sulud, näiteks S(õöäü) ja a(SbS). Proovime järgmisest grammatikast vasakrekursiooni elimineerida:

S → 'sala'

S → S 'kala'

S → S 'maja'

S → ε

Meil on siin kaks produktsiooni S → 'sala' ja S → ε, mis ei ole vasakrekursiivsed, ja kaks produktsiooni S → S 'kala' ja S → S 'maja', mis on vasakrekursiivsed. Mis on tulemus?

Alustame mitterekursiivsetest reeglitest, mida saab regulaaravaldisena kokku kirjutada: ('sala' | ε) ehk lihtsalt ('sala')?. Edasi jätkame vasakrekursiivsete reeglite S-ile järgnevate osade itereerimisega: ( 'kala' | 'maja' )*. Kokku saame siis:

S → ('sala')? ('kala'|'maja')*

EBNF Grammatika teisendamine koodiks

Grammatikates kasutatakse väga tihti neid regulaaravaldiste lisamugavusi. Sellist notatsiooni nimetatakse EBNFiks (Extended Backus–Naur form). Sellisel kujul grammatika saab ka teisendada koodiks ja ASTi tagastamiseks on see lihtsam võrreldes Varmo meetodiga. Kui oled ise lahendanud, siis võid eelmise näite vastuse ära vaadata ja võrrelda järgmise koodiga:

    void s() throws ParseException {
        if (peek() == 's') {
            match("sala");
        }
        while (peek() == 'k' || peek() == 'm') {
            switch(peek()) {
                case 'k':
                    match("kala");
                    break;
                default:
                    match("maja");
            }
        }
    }

Lihtsad ülesanded

Proovi nüüd ise järgmise grammatikaga seda teha:

S → a | b | c

S → Sx | Sy

Ja mis nüüd saab, kui lihtsate tähtede asemel paneme midagi keerulisemat?

S → A | b | cA

S → SX | SyX

A → aA | a

X → x | zXz

Avaldisgrammatika ASTi genereerimine

Mõtleme nüüd ka selle peale, kuidas avaldisgrammatikate korral abstraktset süntaksipuud tagastada. Näiteks avaldise x+x*x+x jaoks tahame sellist lihtsat puud nagu paremal pildil kujutatud. Kui seda teha meie soovitud EBNF grammatika põhjal, siis see ei ole väga keeruline:

E → T(+T)^*

T → F(*F)^*

F → (E)

F → x

Mõtle kõigepealt näidetega see kõik läbi, kui Sul on lihtsalt terve rida plussiga eraldatud liidetavaid. Ehk joonista järgmiste avaldiste ASTid:

x
x+x
(x+x)+x
... kuni saad aru, kuidas saad seda programmis esitada.

Pane siin tähele, et sellise avaldise, kus kogu aeg "lisad" ühe x-i juurde, ei tohiks ju olla struktuuri mõttes väga erinev programmist arvutab 0, 0+1, (0+1)+1, ... Seega, kui oskad kirjutada (enam-vähem mõistliku) programmi, mis väljastab ekraanile arvud 0,1,2,3,..., siis sealt ei ole üldsegi suur samm kirjutada programm, mis vasakassotsiatiivse operaatori ASTi ehitaks.