Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MIF0003	Formal Languages and Compiler Design Methods	

Semester	Hours: C+S+L+P	Category	Status	
5	2+1+2+0	speciality	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
MOTOGNA Simona Claudia	Ph.D.	Assoc.Prof.	Computer Science	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
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, parsing and code generation.	

IV. Course contents
I. Grammars, languages, automata

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

II. Compilers

General problems of compiler construction
Lexical parsers
Syntactical analyzers - ascendant and descendant methods	

V. Bibliography
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. MOTOGNA, S. – Metode de proiectare a compilatoarelor, Ed. Albastra, 2006
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	

VI. Thematic of didactic activities per weeks
Course:
Week 1. General Structure of a compiler. Compiler phases
Week 2. Scanning (Lexical Analysis)
Week 3. Introductory notions of formal languages. Grammars
Week 4. Finite Automata
Week 5. Equivalence between finite automata and regular grammars
Week 6. Regular languages, regular expressions, equivalence with finite automata and regular grammars. Pumping lemma.
Week 7. Context-free grammars, syntax tree
Week 8. Push-down automata
Week 9. Parsing: general notions, classification
Week 10. Recursive-descendant parser
Week 11. LL(1) parser: First, Follow , construction of LL(1) table
Week 12. LR(k) Parsing method. LR(0) parser: closure, goto and canonical collection
Week 13. SLR, LR(1), LALR parser
Week 14. Reserved topic

Seminar:
Sem1: Specification of a programming language; BNF notation
Sem 2: Grammars; language generated by a grammar; grammar corresponding to a language
Sem 3: Finite automata: language generated by a FA; FA corresponding to a language
Sem 4: Transformations: regular expressions – regular grammars – finite automata
Sem 5: Context free grammars; descendent recursive parser
Sem 6: LL(1) parser
Sem 7: LR(k) parsers

Laboratory:
Week 1-4: Specify a mini-language and implement scanner
Week 5-6: regular grammars + finite automata + transformations
Week 7-8: context free grammars + equivalent transformations of cfg
Week 9-13: implement a parser (descendent recursive parser, LL(1), LL(0) or SLR)
Week 14: use tools for lexer and parser generator: lex, yacc	

VII. Didactic methods used

VIII. 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).

For academic year 2010-2011, see
http://www.cs.ubbcluj.ro/~motogna/FLandCD.htm	

IX. Additional references

	Dean,							Chair head,

	Date,							Course responsible,
							Assoc.Prof. MOTOGNA Simona Claudia, Ph.D.