A tantárgy adatlapja
1. A képzési program adatai
1.1 Felsőoktatási intézmény	Babeș–Bolyai Tudományegyetem	
1.2 Kar 	Matematika és Informatika Kar	
1.3  Intézet	Magyar Matematika és Informatika Intézet	
1.4 Szakterület	informatika	
1.5 Képzési szint	alapképzés	
1.6 Szak / Képesítés	informatikai matematika	

2. A tantárgy adatai
2.1 A tantárgy neve	Formális nyelvek és fordítóprogramok	
2.2 Az előadásért felelős tanár neve	Bodó Zalán-Péter	
2.3 A szemináriumért felelős tanár neve	Bodó Zalán-Péter	
2.4 Tanulmányi év	3	2.5 Félév	1	2.6. Értékelés módja	vizsga	2.7 Tantárgy típusa	kötelező – szak	

3. Teljes becsült idő (az oktatási tevékenység féléves óraszáma)
3.1 Heti óraszám	4	melyből: 3.2 előadás	2	3.3 szeminárium/labor	1/1	
3.4 Tantervben szereplő össz-óraszám	56	melyből: 3.5 előadás	28	3.6 szeminárium/labor	14/14	
A tanulmányi idő elosztása:	óra	
A tankönyv, a jegyzet, a szakirodalom vagy saját jegyzetek tanulmányozása	28	
Könyvtárban, elektronikus adatbázisokban vagy terepen való további tájékozódás	20	
Szemináriumok / laborok, házi feladatok, portofóliók, referátumok, esszék kidolgozása	30	
Egyéni készségfejlesztés (tutorálás)	8	
Vizsgák	8	
Más tevékenységek: ..................	0	
3.7 Egyéni munka össz-óraszáma	94	
3.8 A félév össz-óraszáma	150	
3.9 Kreditszám	6	

4. Előfeltételek (ha vannak)
4.1 Tantervi	•	Nincs	
4.2 Kompetenciabeli	•	Algoritmika, gráfelmélet; C/C++, Assembly programozás	

5. Feltételek (ha vannak)
5.1 Az előadás lebonyolításának feltételei	•	Az elődásokhoz videoprojektor szükségeltetik.
•	A példák kifejtéséhez tábla szükséges.	
5.2 A szeminárium / labor lebonyolításának feltételei	•	A szemináriumi feladatmegoldáshoz tábla szükséges.
•	A laborfeladatokhoz és laborgyakorlatokhoz a szükséges szoftverekkel felszerelt gépek szükségesek.	

6. Elsajátítandó jellemző kompetenciák
Szakmai kompetenciák	•	Formális nyelvek és automaták alapfogalmainak, algoritmusainak ismerete.
•	Fordítóprogramok tervezésének és megvalósításának ismerete.
•	A flex és bison eszközök használatának elsajátítása.	
Transzverzális kompetenciák 	•	Önálló tanulás
•	Munkamódszerek, módszertani kompetenciák
•	Kritikus gondolkodás és reflexió	

7. A tantárgy célkitűzései (az elsajátítandó jellemző kompetenciák alapján)
7.1 A tantárgy általános célkitűzése	•	A tantárgy célja megismertetni a hallgatókkal a formális nyelvek és automaták alapfogalmait, algoritmusait, amelyek használatosak a fordítóprogramok esetében, bevezetni őket a fordítóprogramok tervezésének és megvalósításának tudományába.	
7.2 A tantárgy sajátos célkitűzései

	•	A használt reprezentációk, adatszerkezetek ismerete és alkalmazása.
•	A flex és bison eszközök használatának ismerete.
•	A tanultak alkalmazása nem kifejezetten formális nyelvekkel vagy fordítóprogramokkal kapcsolatos problémák megoldásában.	

8. A tantárgy tartalma
8.1 Előadás	Didaktikai módszerek	Megjegyzések	
1–2. Nyelvek és nyelvtanok: Alapfogalmak; Műveletek nyelvekkel; Nyelvek definiálása; Chomsky-féle nyelvosztályok; Kiterjesztett nyelvtanok	tanári magyarázat, munkáltatás		
3–6. Véges automaták és reguláris nyelvek: Véges automaták értelmezése; Nemproduktív és elérhetetlen állapotok; NDVA átalakítása DVA-vá; Automaták ekvivalenciája; Véges automaták és reguláris grammatikák ekvivalenciája; Epszilon-lépéses automaták; Automaták minimalizálása; Pumpáló lemma reguláris nyelvekre; Reguláris kifejezések	tanári magyarázat, munkáltatás		
7.  Veremautomaták és környezetfüggetlen nyelvek: Veremautomaták; Környezetfüggetlen nyelvek; Átalakítások; Pumpáló lemma környezetfüggetlen nyelvekre	tanári magyarázat, munkáltatás		
8. Fordítóprogramok és a lexikális elemzés	tanári magyarázat, munkáltatás		
9. A flex és a bison: A flex felépítése; Reguláris kifejezések; Illeszkedés-vizsgálat; Műveletek és speciális direktívák; Az yylex szkenner; Startfeltételek; A bison felépítése; Szabályok, szemantikus értékek, szemantikus műveletek; Terminálisok, nemterminálisok, tokenek; Rekurzív szabályok; Operátorok precedenciája; A bison és flex kapcsolata; A bison algoritmusa; Léptetés/redukció és redukció/redukció konfliktusok; Hibaelfedés; Debuggolás	tanári magyarázat, munkáltatás		
10–12. Szintaktikai elemzések: Alapfogalmak; LL(1) elemzés: táblázatos elemzés, a rekurzív leszállás módszere; LR(1) elemzés; LALR(1) elemzés	tanári magyarázat, munkáltatás		
13. Szimbólumtábla, szemantikai elemzés, kódgenerálás, kódoptimalizálás	tanári magyarázat, munkáltatás		
14. Összefoglalás, ismétlés	tanári magyarázat, munkáltatás		
Könyvészet
[1] Aho, Sethi, Ullman. Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986.
[2] Kása Zoltán. Automaták és formális nyelvek. In A. Iványi (szerk.). Informatikai algoritmusok 2. Eötvös ELTE Kiadó, Budapest, 2005, 19. fejezet.
[3] Kása Zoltán. Formális nyelvek és automaták. Farkas Gyula Egyesület, 2004.
[4] Csörnyei Zoltán, Kása Zoltán. Formális nyelvek és fordítóprogramok. Kolozsvári Egyetemi Kiadó, 2007.
[5] Csörnyei Zoltán. Fordítási algoritmusok. Erdélyi Tankönyvtanács, Kolozsvár, 2000.
[6] Csörnyei Zoltán. Fordítóprogramok. Typotex, Budapest, 2006.	
8.2 Szeminárium / Labor	Didaktikai módszerek	Megjegyzések	
Szeminárium:			
1. Nyelvek és nyelvtanok	munkáltatás, individuális feladatok		
2. Véges automaták és reguláris nyelvek	munkáltatás, individuális feladatok		
3. Véges automaták és reguláris nyelvek	munkáltatás, individuális feladatok		
4. Veremautomaták és környezetfüggetlen nyelvek	munkáltatás, individuális feladatok		
5. Veremautomaták és környezetfüggetlen nyelvek	munkáltatás, individuális feladatok		
6. Lexikális és LL(1) szintaktikai elemzések	munkáltatás, individuális feladatok		
7. LR(1) és LALR(1) szintaktikai elemzések	munkáltatás, individuális feladatok		
Labor:			
1–3. feladatok: (1) Elérhetetlen és nem produktív állapotok kizárása; (2) Automaták ekvivalenciájának vizsgálata; (3) Nemdeterminisztikus automata szimulációja; (4) Reguláris kifejezés átalakítása nemdeterminisztikus automatává; (5) Véges automata grafikus megjelenítése; (6) Veremautomata szimulációja; (7) Reguláris grammatika átalakítása véges automatává	individuális feladatok	A hét feladatból tetszőlegesen hármat kell választania a diáknak.	
4. Listázóprogram, lexikális elemző (flex)	individuális feladatok		
5. Szintaktikai elemző, a grammatika megírása (flex + bison)	individuális feladatok		
6. Szimbólumtábla készítése (flex + bison)	individuális feladatok		
7. Kódgenerálás (flex + bison)	individuális feladatok	opcionális	
Könyvészet	
[1]–[6] +
[7] Aho, Lam, Sethi, Ullman. Compilers: Principles, Techniques, and Tools. 2nd edition, Prentice Hall, 2006.
[8] Bach Iván. Formális nyelvek. Typotex, Budapest, 2002.
[9] Charles Donnelly, Richard Stallman. Bison. The YACC-compatible Parser Generator. 14 May 2011, Bison Version 2.5.
[10] Vern Paxson, Will Estes, John Millaway. Lexical Analysis With Flex. Edition 2.5.35, 25 February 2010.
[11] Anthony A. Aaby. Compiler Construction using Flex and Bison. 2005.
[12] Emden Gansner, Eleftherios Koutsofios, Stephen North. Drawing graphs with dot. 2006.	

9. Az episztemikus közösségek képviselői, a szakmai egyesületek és a szakterület reprezentatív munkáltatói elvárásainak összhangba hozása a tantárgy tartalmával.
•	Mivel a tantárgy alapterve a [4] alapján készült, ezért nagy az átfedés a Kása Zoltán által a Sapientia Tudománegyetemen oktatott Formális nyelvek és fordítóprogramok kurzussal (http://www.ms.sapientia.ro/~kasa/formalis.htm).
•	A Stanford University-n oktatott Compilers tantárgy 1–8. előadásának anyaga is benne foglaltatik e kurzus anyagában (http://www.stanford.edu/class/cs143/).
•	Az előadás formális nyelvek és automaták része nagy átfedésben van az ELTE-n oktatott Formális nyelvek és automaták I. tantárggyal (http://aszt.inf.elte.hu/~hunlaci/forautem2012t.htm).
•	A tantárgy tematikája nagyrészt egyezik a Csörnyei Zoltán Fordítóprogramok című, a Typotex kiadónál megjelent könyvének tartalmával (http://www.typotex.hu/konyv/csornyei_zoltan_forditoprogramok).
•	A flex és bison két széles körben alkalmazott eszköz, melyek segítségével gyorsan és könnyedén készíthetők nyelveket elemző programok. 	

10. Értékelés
Tevékenység típusa	10.1 Értékelési kritériumok	10.2 Értékelési módszerek	10.3 Aránya a végső jegyben	
10.4 Előadás 	Vizsgafeladatok	Írásbeli vizsga	50%	
				
10.5 Szeminárium / Labor	Feladatok megoldása szemináriumon	A megoldások pontozása	25%	
	Laborfeladatok határidőre való személyes bemutatása	Laborfeladatok értékelése	25%	
10.6 A teljesítmény minimumkövetelményei	
Az elvárt minimális tudás:
•	Formális nyelvek és automaták fogalmainak és problémainak ismerete.
•	A fordítóprogramokkal kapcsolatos fogalmak és problémák ismerete.
•	A kapcsolódó alapvető problémákat érintő feladatok megoldása.
Az átmenő jegy feltételei:
•	A laborfeladatokra kapott átlag legkevesebb 5-ös lehet (kizáró jellegű).
•	A szemináriumokon 50%+1 jelenlét.
•	A vizsgán a minimális átmenő jegy az 5-ös (kizáró jellegű).
•	A végső jegy minimálisan 5-ös kell legyen (kizáró jellegű).	

Kitöltés dátuma			Előadás felelőse			Szeminárium felelőse
2012.09.21				Bodó Zalán-Péter			Bodó Zalán-Péter

Az intézeti jóváhagyás dátuma				Intézetigazgató	
..........................						Szenkovits Ferenc