Selected Topics on Language Parsing and Translation
FIT-APDAcad. year: 2020/2021
This course discusses selected advanced topic on language parsing and compilation. It concentrates especially on the recent research results from the studied area. Nevertheless, it also presents topics usually not discussed because of their complexity even if the topics are not new. In details, it is presented theory of the parsing and compilation together with practical aspects of analyzer/compiler construction.
Doctoral state exam - topics:
- LL (k) languages and their syntax analysis.
- LR and LALR languages and their syntax analysis, parsing table creation.
- Semantic and context addicted lexical analysis.
- Attributed grammars and their use for formal language analysis.
- Scattered context grammars and their variants, mutual relation of these variants, properties.
- Relation of scattered context grammars and their variants to Chomsky formal language hierarchy.
- Regulated pushdown automata, deterministic variants, relation to TM.
- LL scattered context grammars as an input for formal language analysis, construction of regulated pushdown automata.
- Practical implementation of parser/analyzer based on scattered context grammars - variants, optimization, limitations.
- The role of priorities and attributes for parsing/analyzing formal languages exploiting scattered context grammars.
Learning outcomes of the course unit
Both theoretical and practical knowledge and experience from language analyzer/compiler construction based on new and advance technology.
formal languages and automata, principles of compiler construction, graph theory, complexity
Recommended optional programme components
Recommended or required reading
A copy of lectures
Kolář Dušan, Meduna Alexander: Regulated Automata: From Theory towards Applications, In: Proceeding of 8th International Conference on Information Systems Implementation and Modelling ISIM'05, Ostrava, CZ, MARQ, 2005, pp. 33-48, ISBN 80-86840-09-3.
Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, Addison Wesley, Reading MA, 1986, ISBN 0-201-10194-7.
Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, Second Edition, Addison Wesley, Pearson, 2007, ISBN 0-321-48681-1.
Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling, Volume I: Parsing, Prentice-Hall, Inc., 1972, ISBN 0-13-914556-7.
Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling, Volume II: Compiling, Prentice-Hall, Inc., 1972, ISBN 0-13-914564-8.
Meduna, A., Kolář, D.: Regulated Pushdown Automata, Acta Cybernetica, Vol. 14, pp. 653-664, 2000.
Kolář, D.: Pushdown Automata: Another Extensions and Transformations, Brno, CZ, FIT VUT, 2005, pp. 76.
Křoustek, J., Kolář D.: Context Parsing (Not Only) of the Object-File-Format Description Language. Computer Science and Information Systems (ComSIS), Vol 10/4, pp. 1673-1702. ISSN 1820-0214.
Planned learning activities and teaching methods
Assesment methods and criteria linked to learning outcomes
Language of instruction
In-depth study of new and complex methods for language analysis and compilation tightly coupled with practical development of programs exploiting such methods.
Specification of controlled education, way of implementation and compensation for absences
Several papers on a given topic, program construction-compiler/analyzer construction using specific techniques).
Type of course unit
39 hours, optionally
Teacher / Lecturer
- Introduction - review, LL(1) languages and their analysis.
- LL(k) languages.
- Analysis of LL(k) languages.
- SLR languages.
- LR and LALR languages - I.
- LR and LALR languages - II.
- Semantically driven lexical analysis.
- Attributes - role and processing.
- Scattered context grammars, LL modification.
- Regulated pushdown automata.
- Context languages analysis.
- LL scattered context grammars analysis using regulated pushdown automata.
- Selected topics on optimization.
Guided consultation in combined form of studies
26 hours, optionally
Teacher / Lecturer
13 hours, compulsory
Teacher / Lecturer
- An essay based on language analysis related to student's dissertation.
- A program based advanced compiler technology presented during lectures.