Automaadid, keeled ja translaatorid - Kursused

Kontekstivabad grammatikad ja automaadid

Paremlineaarsed grammatikad ja lõplik automaat

Veendume 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.

Kontekstivaba grammatika ja magasinmäluga automaat

Igale kontekstivabale keelele vastab magasinmäluga automaat (PDA). Nende automaatide loomise kohta on võimalik informatsiooni leida siit. Alustame järgmise lihtsa grammatikaga (simple.jff):

S → aSb

S → ε

Loome koos sellele vastava automaadi:

Kõigepealt mõtleme, kuidas keele äratundmine võiks toimida. Idee on lihtne: kasutame magasini, et loendada 'a'-sid ehk iga 'a' korral toppime midagi magasini ja siis hakkame iga 'b' korral elemente magasinist välja võtma.
Joonista seisund, mis esitab seda, et hakkame 'a'-sid loendama. Tal on seega endale üleminek.
Kui näeme 'b'-d, siis lähme järgmise seisundisse, kus hakkame elemente magasinist välja võtma.

Seejärel proovige ise luua järgmise grammatikale vastav automaat.

S → aSa

S → bSb

S → x

Tegelikult saab süstemaatiliselt teisendada iga grammatika automaadiks. Selleks on kaks põhilist konstruktsiooni, üks mis vastab LL parseritele ja teine vastab LR parseritele. Võite proovida "Convert CFG to PDA(LL)", aga see on rohkem tuleviku teema.

Lisatöö: Magasinmäluga masinad

Magasinmäluga masinatega proovime nüüd vanale heale esimese kodutööle, kus olid plus-miinus avaldised, lisada sulud. Selleks on vaja kasutada magasinmälu! Kasutusel on taaskord EU arengutoetusega valminud raamistikud, et sundida teid sammhaaval sisendit läbi töötlema. Raamistiku kood on repos week5.stack paketis. Tuleb lahendada kaks ülesannet failides EvalMachine ja AstMachine, sest meie poolt fikseeritud Evaluator raamistik kasutab need klasse, et avaldist väärtustada ja süntakspuu luua.

Väärtustamine

EvalMachine on meie avaldiste väärtustaja. Tuletame meelde, kuidas esimest kodutööd saab lahendada automaadi abil. Klassis Evaluator on juba tükeldaja olemas. Tema meetod compute loob meie EvalMachine klassi isendi ja sellega töötleb tükeldatud avaldist. Kui käivitada AktkPdaTest, siis peaks olema näha, et esimese kodutöö kõik testid (kus ei ole poolikud avaldised) lähevad läbi.

Ei ole palju puudu, et see töötaks ka sulgavaldiste korral, aga tasub natuke mõelda ja siis tegutseda, sest õige lahendus on hästi lihtne (4 rida vaja muuta/lisada). Selle jaoks on testid olemas klassis EvaluatorTest. Enne lahendamist vaata hoolikalt need testid läbi. Näiteks peab väärtustaja suutma ka poolikute (aga muidu korrektsete) avaldiste korral oma hetkeväärtust tagastada.

Süntakspuu loomine

AstMachine loob avaldise süntakspuu. Ehitame siin süntakspuu lihtsalt homogeense Node klassiga. Kui selle lahendamiseks ei tule ideid, siis võib otsida inspiratsiooni JFLAP-ilt, kui teha S → (S) | x-tüüpi grammatika ümber PDA-ks kasutades "Convert CFG to PDA(LR)". Võimalik, et saab ka palju lihtsamalt, aga kuna ma ise juba tean seda konstruktsiooni, siis oli raske teistmoodi mõelda.

Selle ülesande juures võib eeldada, et avaldis on süntaktiliselt korrektne. Me isegi ei testi seda meetodit vigaste sisenditega, seega ei pea siin veateateid väljastama ja pooliku sisendi puhul võib tagastada ükskõik mida.

Kui oled nii kaugele jõudnud, siis palun esita oma EvalMachine ja AstMachine lahendusi moodle'is.