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.