Automaadid, keeled ja translaatorid
MTAT.05.085, 4AP, 30L, 30P, 60i., Ain Isotamm.
Automaadid ja formaalsed keeled
- 1. Formaalsete grammatikate Chomsky klassifikatsioon.
- 2. Paremlineaarne grammatika.
- 3. Determineeritud ja mittedetermineeritud lõplik automaat.
- 4. Lõpliku automaadi ja paremlineaarse grammatika ekvivalentsus.
- 5. Regulaaravaldis.
- 6. Regulaaravaldise ja lõpliku automaadi ekvivalentsus.
- 7. Kasvatamise lemma regulaarsete keelte jaoks.
Translaatorid
- 1. Programmeerimiskeelte klassid ja nende realiseerimine arvutil.
Assembler, makroassembler, interpretaator ja kompilaator.
- 2. Translaatorite tegemise süsteem. Üldine skeem. Kontekstivaba
grammatika (KVG). Derivatsioon, keel. Analüüsi puu. Kanooniline
derivatsioon. Süntaksi analüüsi ülesanne. Eelnevusrelatsioonid,
eelnevusgrammatika.
- 3. KVG teisendamine eelnevusgrammatikaks. Pööratavate eelnevusgrammatikate
analüsaator.
- 4. Konteksti kasutamine redutseerimiseks ja vastav analüsaator.
- 5. Derivatsioonist sõltuv kontekst. Konteksti juurdetoomine.
- 6. Konstruktor. Andmestruktuurid, grammatika salvestamine.
- 7. Eelnevusmaatriksi moodustamine, eelnevusteisendused.
- 8. Redutseerimistabel, sõltumatu konteksti hulkade moodustamine.
- 9. Sõltuva konteksti hulkade moodustamine. Semantika. Tabelite
kirjutamine kettale.
- 10. Analüsaator. Konstruktori tabelite sisestamine. Skanner. Vahekood.
Identifikaatorite ja konstantide tabelid.
- 11. Analüsaatori põhiprogramm. Analüsaatori väljund.
- 12. Trigol-keel. Interpretaator. Andmestruktuurid, algoritm.
- 13. Kompilaator Trigolist assemblerisse. Andmestruktuurid, analüüsi puu
teisendamine. Kompilaatori algoritm.
- 14. Optimiseerimine. Optimiseeriva kompilaatori algoritm.