Course detail

Selected Topics on Language Parsing and Translation

FIT-APDAcad. year: 2010/2011

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.

Language of instruction

Czech, English

Mode of study

Not applicable.

Guarantor

doc. Dr. Ing. Dušan Kolář

Department

Department of Information Systems (UIFS)

Learning outcomes of the course unit

Both theoretical and practical knowledge and experience from language analyzer/compiler construction based on new and advance technology.

Prerequisites

formal languages and automata, principles of compiler construction, graph theory, complexity

Co-requisites

Not applicable.

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

Study evaluation is based on marks obtained for specified items. Minimimum number of marks to pass is 50.

Course curriculum

  1. Introduction - review, LL(1) languages and their analysis.
  2. LL(k) languages.
  3. Analysis of LL(k) languages.
  4. SLR languages.
  5. LR and LALR languages - I.
  6. LR and LALR languages - II.
  7. Semantically driven lexical analysis.
  8. Attributes - role and processing.
  9. Scattered context grammars, LL modification.
  10. Regulated pushdown automata.
  11. Context languages analysis.
  12. LL scattered context grammars analysis using regulated pushdown automata.
  13. Selected topics on optimization.

Work placements

Not applicable.

Aims

Ïn-depth study of new and complex methods for language analysis and compilation tightly coupled with practical development of programs exploiting such a 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).

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

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. Beneš, M., Češka, M., Hruška, T.: Překladače, Technical University of Brno, 1992. Meduna, A., Kolář, D.: Regulated Pushdown Automata, ActaCybernetica, Vol. 14, pp. 653-664, 2000. Kolář, D.: Pushdown Automata: Another Extensions and Transformations, Brno, CZ, FIT VUT, 2005, s. 76.

Recommended reading

Přednášky 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. 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, s. 33-48, ISBN 80-86840-09-3. Kolář, D.: Pushdown Automata: Another Extensions and Transformations, Brno, CZ, FIT VUT, 2005, s. 76

Classification of course in study plans

  • Programme CSE-PHD-4 Doctoral

    branch DVI4 , 0 year of study, winter semester, elective

  • Programme CSE-PHD-4 Doctoral

    branch DVI4 , 0 year of study, winter semester, elective

Type of course unit

 

Lecture

39 hod., optionally

Teacher / Lecturer

doc. Dr. Ing. Dušan Kolář

Syllabus

  1. Introduction - review, LL(1) languages and their analysis.
  2. LL(k) languages.
  3. Analysis of LL(k) languages.
  4. SLR languages.
  5. LR and LALR languages - I.
  6. LR and LALR languages - II.
  7. Semantically driven lexical analysis.
  8. Attributes - role and processing.
  9. Scattered context grammars, LL modification.
  10. Regulated pushdown automata.
  11. Context languages analysis.
  12. LL scattered context grammars analysis using regulated pushdown automata.
  13. Selected topics on optimization.

Project

13 hod., optionally

Teacher / Lecturer

doc. Dr. Ing. Dušan Kolář