Languages and Translations
Semestr: Winter
Range: 14+4c
Completion:
Credits: 4
Programme type: Undefined
Study form: Parttime
Course language:
Summary:
Theory of formal languages, definition and classification of grammars, regular languages, regular grammars and regular expressions, deterministic and non-deterministic finite automata, context-free grammars, parsing, pushdown automata, LL and LR grammars (parsing, transformations), formal translation, translation grammars, finite transducers and regular translation grammars, pushdown transducer and context-free translation grammars, LL and LR translations, attribute grammars, evaluation of attributes.
Keywords:
Course syllabus:
1. Basic notions of the theory of languages, definitions and grammar classification
2. Regular languages, regular grammars, and regular expressions
3. Nondeterministic and deterministic finite automata
4. Context-free grammars, parsing of context-free languages
5. Pushdown automata, relation between context-free grammars and pushdown automata
6. LL grammars, parsing tables, parsing
7. Transformations of context-free grammars to LL grammars
8. LR grammars, basic notions
9. LR grammars, parsing
10. LR grammars, parsing table construction
11. Formal translations, basic notions, translation grammar
12. Translation automata and grammars
13. Formal translation directed by LL parser
14. Formal translation directed by LR parser
Seminar syllabus:
1. Construction of grammars for simple languages
2. Finite automata for simple languages
3. Relation between regular grammars and finite automata
4. Relation between regular expressions and finite automata
5. Relation between regular expressions and regular grammars
6. Context-free grammars, basic transformations
7. Pushdown automata
8. LL grammars, parsing table construction, parsing
9. Transformations of context-free grammars to LL grammars
10. LR grammars - table construction
11. LR grammars - parsing
12. Translation grammars and automata
13. Formal translation in LL parsing
14. Formal translation in LR parsing
Literature:
1. Melichar, B., Holub, J., Mužátko, P.: Languages and Translations. Publishing House of CTU, Praha 1997.