Parsing and Compilers
Code | Completion | Credits | Range | Language |
---|---|---|---|---|
NI-SYP | Z,ZK | 5 | 2P+1C | English |
- Course guarantor:
- Jan Janoušek
- Lecturer:
- Jan Janoušek
- Tutor:
- Jan Janoušek, Štěpán Plachý
- Supervisor:
- Department of Theoretical Computer Science
- Synopsis:
-
The module builds upon the knowledge of fundamentals of automata theory, formal language and formal translation theories. Students gain knowledge of various variants and applications of LR parsing and are introduced to special applications of parsers, such as incremental and parallel parsing.
- Requirements:
-
Knowledge of fundamentals of the theory of formal languages and translations. Knowledge of finite and pushdown automata, construction of an LL parser, and compiler directed by an LL parser.
- Syllabus of lectures:
-
1. Recapitulaton of basic notions, LL parsing.
2. Classification of LR parsers.
3. Strong LR(k) parsing.
4. LR(0) and SLR(1) parsing.
5. LALR(k) and LR(k) parsing.
6. Translation directed by an LR parser.
7. Evaluation of attributes during LR parsing.
8. LR attributed translation.
9. Intermediate representation.
10. Incremental LL parsing.
11. Incremental LR parsing.
12. Parallel LL parsing.
13. Parallel LR parsing.
- Syllabus of tutorials:
-
1. Revision - construction of weak and strong LL parsers.
2. Revision - compiler directed by LL parser.
3. Strong LR(k) parsing.
4. LR(0) parsing.
5. SLR(1) parsing.
6. LALR(k) parsing.
7. LR(k) parsing.
8. Translation directed by LR parser.
9. Evaluation of attributes during LR parsing, LR attributed translation.
10. Incremental LR parsing.
11. Parallel LL parsing.
12. Parallel LR parsing.
- Study Objective:
-
Knowledge acquired in this module can be used for compiler construction or other types of programs for parsing and processing structured texts.
- Study materials:
-
1. Melichar, B., Holub, J., Mužátko, P. ''Languages and Translations''. Praha: Publishing House of CTU, 1997. ISBN 80-01-01692-7.
3. Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D. ''Compilers: Principles, Techniques, and Tools (2nd Edition)''. Addison Wesley, 2006. ISBN 0321486811.
4. Grune, D., Jacobs, C. J. H. ''Parsing Techniques. A Practical Guide (2nd Edition)''. Springer, 2008. ISBN 038720248X.
- Note:
- Further information:
- https://moodle.fit.cvut.cz/courses/MI-SYP.16/
- Time-table for winter semester 2024/2025:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Wed Thu Fri - Time-table for summer semester 2024/2025:
- Time-table is not available yet
- The course is a part of the following study plans:
-
- Bachelor program Informatics, unspecified branch, in Czech, 2015-2020 (elective course)
- Bachelor branch Security and Information Technology, in Czech, 2015-2020 (elective course)
- Bachelor branch Computer Science, in Czech, 2015-2020 (elective course)
- Bachelor branch Computer Engineering, in Czech, 2015-2020 (elective course)
- Bachelor branch Information Systems and Management, in Czech, 2015-2020 (elective course)
- Bachelor branch Web and Software Engineering, spec. Software Engineering, in Czech, 2015-2020 (elective course)
- Bachelor branch Web and Software Engineering, spec. Web Engineering, in Czech, 2015-2020 (elective course)
- Bachelor branch Web and Software Engineering, spec. Computer Graphics, in Czech, 2015-2020 (elective course)
- Master specialization Computer Science, in Czech, 2018-2019 (PS)
- Bachelor branch Knowledge Engineering, in Czech, 2018-2020 (elective course)
- Master specialization Computer Security, in Czech, 2020 (elective course)
- Master specialization Design and Programming of Embedded Systems, in Czech, 2020 (elective course)
- Master specialization Computer Systems and Networks, in Czech, 202 (elective course)
- Master specialization Management Informatics, in Czech, 2020 (elective course)
- Master specialization Software Engineering, in Czech, 2020 (elective course)
- Master specialization System Programming, in Czech, version from 2020 (PS, elective course)
- Master specialization Web Engineering, in Czech, 2020 (elective course)
- Master specialization Knowledge Engineering, in Czech, 2020 (elective course)
- Master specialization Computer Science, in Czech, 2020 (PS, elective course)
- Mgr. programme, for the phase of study without specialisation, ver. for 2020 and higher (VO)
- Bachelor Specialization Information Security, in Czech, 2021 (elective course)
- Bachelor Specialization Management Informatics, in Czech, 2021 (elective course)
- Bachelor Specialization Computer Graphics, in Czech, 2021 (elective course)
- Bachelor Specialization Computer Engineering, in Czech, 2021 (elective course)
- Bachelor program, unspecified specialization, in Czech, 2021 (elective course)
- Bachelor Specialization Web Engineering, in Czech, 2021 (elective course)
- Bachelor Specialization Artificial Intelligence, in Czech, 2021 (elective course)
- Bachelor Specialization Computer Science, in Czech, 2021 (elective course)
- Bachelor Specialization Software Engineering, in Czech, 2021 (elective course)
- Bachelor Specialization Computer Systems and Virtualization, in Czech, 2021 (elective course)
- Bachelor Specialization Computer Networks and Internet, in Czech, 2021 (elective course)
- Study plan for Ukrainian refugees (elective course)
- Master Specialization Digital Business Engineering, 2023 (VO)
- Master specialization System Programming, in Czech, version from 2023 (PS, elective course)
- Master specialization Computer Science, in Czech, 2023 (PS, elective course)
- Bachelor Specialization Information Security, in Czech, 2024 (elective course)
- Bachelor program, unspecified specialization, in Czech, 2024 (elective course)
- Bachelor Specialization Management Informatics, in Czech, 2024 (elective course)
- Bachelor Specialization Computer Graphics, in Czech, 2024 (elective course)
- Bachelor Specialization Software Engineering, in Czech, 2024 (elective course)
- Bachelor Specialization Web Engineering, in Czech, 2024 (elective course)
- Bachelor Specialization Computer Networks and Internet, in Czech, 2024 (elective course)
- Bachelor Specialization Computer Engineering, in Czech, 2024 (elective course)
- Bachelor Specialization Computer Systems and Virtualization, in Czech, 2024 (elective course)
- Bachelor Specialization Artificial Intelligence, in Czech, 2024 (elective course)
- Bachelor Specialization Computer Science, in Czech, 20214 (elective course)