Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate

SUBJECT

Code
Subject
MIF0003 Formal Languages and Compiler Design Methods
Section
Semester
Hours: C+S+L
Category
Type
Computer Science
5
2+1+2
speciality
compulsory
Mathematics and Computer Science
3
2+1+1
speciality
compulsory
Information engineering
5
2+1+1
speciality
compulsory
Teaching Staff in Charge
Assoc.Prof. MOTOGNA Simona Claudia, Ph.D.,  motognacs.ubbcluj.ro
Prof. KASA Zoltan, Ph.D.,  kasacs.ubbcluj.ro
Lect. EGRI Edith,  egrieditcs.ubbcluj.ro
Aims
Grammars and languages; Chomsky hierarchy; regular grammars, finite automata and the equivalence between them; context-free grammars, push-down automata and their equivalence.
Compiler construction fundamentals: compiling phases, scanning, persing and code generation.
Content
I. Grammars, languages, automata

Regular gramars and languages. Finite automata.
Context free grammars and languages. Pushdown automata.
Turing automata
Special grammars - LR(k), LL(k) and precedence grammars

II. Compilers

General problems of compiler construction
Lexical parsers
Syntactical analyzers - ascendant and descendant methods
References
1. A.V. AHO, D.J. ULLMAN - Principles of computer design, Addison-Wesley, 1978.
2. A.V. AHO, D.J. ULLMAN - The theory of parsing, translation and compiling, Prentice-Hall, Engl. Cliffs., N.J., 1972, 1973.
3. D. GRIES - Compiler construction for digital computers,, John Wiley, New York, 1971.
4. SIPSER, M., Introduction to the theory of computation, PWS Pulb. Co., 1997.
5. G. MOLDOVAN, V. CIOBAN, M. LUPEA - Limbaje formale si automate. Culegere de probleme, Univ. Babes-Bolyai, Cluj-Napoca, 1996.,l http://math.ubbcluj.ro/~infodist/alf/INDEX.HTM
6. CSÖRNYEI ZOLTÁN, Bevezetés a fordítóprogramok elméletébe, I, II., ELTE, Budapest, 1996
7. L.D. SERBANATI - Limbaje de programare si compilatoare, Ed. Academiei RSR, 1987.
8. CSÖRNYEI ZOLTÁN, Fordítási algoritmusok, Erdélyi Tankönyvtanács, Kolozsvár, 2000.
9. DEMETROVICS JÁNOS-DENEV, J.-PAVLOV, R., A számítástudomány matematikai alapjai, Nemzeti Tankönyvkiadó, Budapest, 1999.
Assessment
The final grade will reflect the seminar and lab activity and the knowledge obtained by the students.
The final mark will be compute from: 25% lab_mark + 75% exam_mark (including seminar work too).
Details for academic year 2009-2010, at:
http://www.cs.ubbcluj.ro/~motogna/FLandCD.htm
Links: Syllabus for all subjects
Romanian version for this subject
Rtf format for this subject