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	Category	Status	
5	2+2+2	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.	Programming  Languages and Methods	*			

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, persing and code generation.	

IV. Course contents
I. Grammars, languages, automata

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

II. Compilers

Genaral problems of compiler contruction
Lexical parsers
Syntactical analyzers - ascendent and descendent 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. CSÖRNYEI ZOLTÁN, Bevezetés a fordítóprogramok elméletébe, I, II., ELTE, Budapest, 1996
4. CSÖRNYEI ZOLTÁN, Fordítási algoritmusok, Erdélyi Tankönyvtanács, Kolozsvár, 2000.
5. DEMETROVICS JÁNOS-DENEV, J.-PAVLOV, R., A számítástudomány matematikai alapjai, Nemzeti Tankönyvkiadó, Budapest, 1999.
6. D. GRIES - Compiler construction for digital computers,, John Wiley, New York, 1971.
7. D. GRUNE, H.BAL,C.JACOBS, K. LANGENDOEN – Modern Copiler Design, John Wiley, 2000
8. 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
9. S. MOTOGNA – Metode de proiectare a compilatoarelor, Ed. Albastra, 2006
10. L.D. SERBANATI - Limbaje de programare si compilatoare, Ed. Academiei RSR, 1987.

VI. Thematic of didactic activities per weeks
Course 1. What is a compiler, general structure and compilation phases [6,9]
Course 2. Scanning [9,7,10]
Course 3. Formal languages - Basic notions: language, grammar, Chomsky hierarchy [2]
Course 4. Regular Grammars (RG) and Finite Automata (FA). [2]
-	Definitions
-	Equivalence betweend RG and FA 
Course 5. Regular expressions [2]
-	Equivalence between regular languages, RG and FA;
-	Closure properties; 
-	Pumping lemma 
Course 6. Context-free grammars (CFG) [2]
-	Definition, pumping lemma
-	Syntax tree
-	Equivalent transformations
Course 7. Push-down  Automata (PDA)[2]
-	Definition
-	Equivalence to CFG
Course 8. Parsing [1,9]
-	Basic notions. Representation of the syntax tree
-	Classification of parsers
-	Descending recursive parsing
Course 9. LL(1) Parsing [1,9,10]
-	LL(k) grammars
-	Functions FIRST and FOLLOW
-	Constructing an LL(1) parser
Course 10. LR Parsing [1,9,10]
-	Shift-reduce parsing
-	Basic principles for LR(k) parsing; LR(k) grammars
-	LR(0) canonical collection
Course 11. LR Parsing – cont. [1,9,10]
-	Constructing an LR(0) parser
Course 12. LR Parsing – cont. [1,9,10]
-	SLR parser
-	LR(1) parser
-	LALR parser
Course 13. Scanning and parsing generators [7,9]
-	Scanning generator (lex)
-	Parsing generators (yacc, lgen)
Course 14. Turing  Machines[1]	

VII. Didactic methods used
Exposure: desacription, explanation, presentation with proofs, introductive presentations
Conversation: Heuristic conversation, debate, dialog, introductive conversations, for consolidating information, for synthesis
Didactical Proof: proofs at the blackboard, with logical steps .
Modeling: using models and patterns. 
Algorithmization: algorithmic description. 
Problematization: QA session, problems and practical situations 
Othert methods: case study, individual study, exercise.	

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 (icluding semnianr work too).	

IX. Additional references
***[lex & yacc] - http://dinosaur.compilertools.net/	

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