Theory of compilation (1)


Aim of the course

The lecture is intended to provide students with theoretical and practical foundations of building compilers construction. The approach based on context-free grammars and syntax oriented translation is used to introduce the design and operation of the front-end of the compiler.

Lecture programme

Translators, compilers, interpreters. Main components of translator. Lexical analysis. Scanner. Specification, identification symbols on the basis of lexical nondeterministic joint finite automaton and deterministic finite automaton, the implementation of scanner.The Lex generator lof exical analyzers. Syntactic analysis. Parser. Grammars LL (k). Design and implementation of parser LL (1) using recursive procedures. Grammars LR (k). Parser LR (1). Parser SLR (1), design of reducing parser based on ambiguous grammars. Parser LALR(1). Generator of syntactic analyzers Yacc. Parser based on grammars using the priorities of operators. Semantic analysis. Attributed grammars. Syntax-driven translation. S-attributed grammars, ascending calculations of S-attributed definitions. L- attributed grammars, descending and ascending calculations of the definitions of L-attributed definitions. Recursive calculations L-attributed definitions. The analysis of syntax-driven definitions. Recursive calculations for tree analysis.

Overview of the course elements

The laboratory classes are mainly devoted to the implementation of lexical and syntactic analyzers, with elements of syntax-driven translation, using generators Lex and Yacc. The course comprises also several meetings of a audytorium type, to explain details of lexical analysis algorithms, and to present the design and exploration of attributed grammars.

Reading list

1. Aho A. V., Sethi R., Ullman J. D.: Kompilatory. Reguły, metody i narzędzia, WNT, 2002
2. Waite W., Goos G.: Konstrukcja kompilatorów, WNT, 1989.
3. Hopcroft J. E., Motwani R., Ullman J. D.: Wprowadzenie do teorii automatów, języków i obliczeń, PWN, 2005
4. Hopgood F.R.A. – Metody kompilacji. 1982.

Copyright © 2010 Department of Computer Science   |   AGH University of Science and Technology   |   Created by Creative Bastards