Title:

Selected Topics on Language Parsing and Translation

Code:APD
Ac.Year:2017/2018
Term:Winter
Curriculums:
ProgrammeBranchYearDuty
CSE-PHD-4DVI4-Elective
Language:Czech
Completion:examination (verbal)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:3900013
 ExaminationTestsExercisesLaboratoriesOther
Points:6000040
Guarantee:Kolář Dušan, doc. Dr. Ing., DIFS
Lecturer:Kolář Dušan, doc. Dr. Ing., DIFS
Faculty:Faculty of Information Technology BUT
Department:Department of Information Systems FIT BUT
 
Learning objectives:
  n-depth study of new and complex methods for language analysis and compilation tightly coupled with practical development of programs exploiting such a methods.
Description:
  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.
Knowledge and skills required for the course:
  formal languages and automata, principles of compiler construction, graph theory, complexity
Learning outcomes and competences:
  Both theoretical and practical knowledge and experience from language analyzer/compiler construction based on new and advance technology.
Syllabus of lectures:
 
  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.
Syllabus - others, projects and individual work of students:
 
  1. An essay based on language analysis related to student's dissertation.
  2. A program based advanced compiler technology presented during lectures.
Fundamental 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.
  • 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, s. 76.
Study literature:
 
  • A copy of lectures
  • 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
Controlled instruction:
  Several papers on a given topic, program construction-compiler/analyzer construction using specific techniques).