Course details

Formal Languages and Compilers

IFJ Acad. year 2006/2007 Winter semester 5 credits

Current academic year

This course discusses formal languages and their models. Based on these models, it explains the construction of compilers. The lectures are organized as follows: (I) Basic notions: formal languages and their models, grammars, automata; compilers. (II) Regular languages and lexical analysis: regular languages and expressions, finite automata and transducers, lexical analyzer; Lex; symbol table. (III) Context-free languages and syntax analysis: context-free grammars, pushdown automata and transducers, deterministic top-down syntax analysis (recursive descent), the essence of deterministic bottom-up syntax analysis; Yacc. (IV) Semantic analysis and code generation: intermediate code generation, optimization, code generation.

Guarantor

Meduna Alexandr, prof. RNDr., CSc. (DIFS)

Language of instruction

Czech, English

Completion

Credit+Examination

Time span

  • 39 hrs lectures
  • 13 hrs projects

Department

Department of Information Systems (UIFS)

Subject specific learning outcomes and competences

Fundamental familiarity with the theory of formal languages. Ability of a compiler construction.

Learning objectives

Familiarity with formal languages and their models. Grasp of compiler construction.

Prerequisite knowledge and skills

There are no prerequisites

Study literature

  • kopie přednášek (elektronické i papírové)
  • Meduna, A.: Automata and Languages. London, Springer, 2000.
  • Meduna, A.: Elements of Compiler Design. New York, US, Tailor & Francis, 2008.

Fundamental literature

  • Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992.

Syllabus of lectures

  • Formal languages.
  • Chomsky hierarchy and the corresponding models.
  • Translation of languages and the structure of a compiler.
  • Regular languages and their models: regular expressions and finite automata.
  • Lexical analysis: lexical analyzer; Lex; symbol table.
  • Context-free languages and their models: context-free grammars and pushdown automata.
  • Syntax analysis: deterministic syntax analysis, FIRST and FOLLOW, LL and LR grammars.
  • Deterministic top-down syntax analysis: recursive descent.
  • Deterministic bottom-up syntax analysis: simple precedence analysis, LR analysis; Yacc.
  • Semantic analysis and intermediate form generation.
  • Optimazation.
  • Code generation.
  • Remarks and summary. Preliminary discussion of the VYP contents.

Progress assessment

To be allowed to take the final written exam, the student has to obtain 20 points during the semesterů; out of these 20 points, at least five points has to be obtained for the programming part of the project.

 

Controlled instruction

There are no checked study.

Back to top