Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu maghiară
Limba de predare: Maghiară

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MIF0003	Formális nyelvek és fordítóprogramok	

Félév	Órák: C+S+L+P	Kategória	Típus	
5	2+1+2+0	szaktárgy	kötelező	

II. Foállásban az  Egyetem  oktatói
Név	Tudományos	Oktatói	Tanszék	Tevékenység	
	fokozat	státus		E	Sz	L	
BODÓ Zalán Péter	Dr. 	Lect.	Magyar Matematika és Informatika	*	*	*	

Társult oktatók
Név	Tudományos	Intézmény	Állás	Tevékenység 	
	fokozat		típusa	E	Sz	L	

III. A tantárgy célkitűzései
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.
A szemináriumokon az elméleti tudást gyakorlati feladatokon mélyítjük el. A gyakorlati órákon a hallgatók konkrét algoritmusokat programoznak.	

IV. A tantárgy tartalma
Formális nyelvek
•	Formális nyelvtanok, nyelvek, alapfogalmak
•	Chomsky-féle nyelvosztályok, kiterjesztett nyelvtanok
•	Véges automaták és reguláris nyelvek, pumpáló lemma reguláris nyelvekre, reguláris kifejezések
•	Veremautomaták és környezetfüggetlen nyelvek, pumpáló lemma környezetfüggetlen nyelvekre
Fordítóprogramok
•	Fordítóprogramok szerkezete
•	Lexikális elemzés
•	Szintaktikai elemzések. Felülről lefelé és alulról felfelé történő elemzések. LL(1), LR(1) és LALR(1) elemzések
•	Szimbólumtábla, szemantikai elemzés, kódgenerálás és kódoptimalizálás	

V. 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.	

VI. Az oktatói tevékenység heti tematikája
Előadások (E)
1–2. Nyelvek és nyelvtanok
•	Alapfogalmak
•	Műveletek nyelvekkel
•	Nyelvek definiálása
•	Chomsky-féle nyelvosztályok
•	Kiterjesztett nyelvtanok
3–6. Véges automaták és reguláris nyelvek
•	Véges automaták értelmezése
•	Nemproduktív, 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. Fejlett kiértékelési módszerek
7. Veremautomaták és környezetfüggetlen nyelvek
•	Veremautomaták
•	Környezetfüggetlen nyelvek
•	Átalakítások
•	Pumpáló lemma környezetfüggetlen nyelvekre
8. Fordítóprogramok. Lexikális elemzés
9. A flex és a bison
•	A flex felépítése
•	Reguláris kifejezések
•	Illeszkedés-vizsgálat
•	Műveletek, 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
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
13. Szimbólumtábla, szemantikai elemzés, kódgenerálás, kódoptimalizálás
14. Összefoglalás, ismétlés

Szemináriumi feladatok (Sz)
A szemináriumi feladatok az előadások tematikáját követi.
1. Nyelvek és nyelvtanok
2. Véges automaták és reguláris nyelvek
3. Véges automaták és reguláris nyelvek
4. Veremautomaták és környezetfüggetlen nyelvek
5. Veremautomaták és környezetfüggetlen nyelvek
6. Lexikális és LL(1) szintaktikai elemzések
7. LR(1) és LALR(1) szintaktikai elemzések

Laborfeladatok (L)
1–3. feladatok:
•	Elérhetetlen és nem produktív állapotok kizárása
•	Automaták ekvivalenciájának vizsgálata
•	Nemdeterminisztikus automata szimulációja
•	Reguláris kifejezés átalakítása nemdeterminisztikus automatává
•	Véges automata grafikus megjelenítése
•	Veremautomata szimulációja
•	Reguláris grammatika átalakítása véges automatává
4. Listázóprogram, lexikális elemző (flex)
5. Szintaktikai elemző, a grammatika megírása (flex + bison)
6. Szimbólumtábla készítése (flex + bison)
7. Kódgenerálás (flex + bison)
(Mindegyik feladat megoldására körülbelül 2 hét áll a hallgatók rendelkezésére.)	

VII. Alkalmazott didaktikai módszerek
Alkalmazott módszerek: tanári magyarázat, munkáltatás, individuális feladatok.
Az előadásokon vetítőt használunk a jegyzetek kivetítéséhez.
A szemináriumokon legfőképp a táblát használjuk a feladatok leírásához/megoldásához, szemináriumi példa/bemutató esetén pedig vetítőt.
A laborgyakorlatokon mesterséges és valós adatokkal dolgozunk számítógépeken, meghatározott programozási nyelveket használva.
Az előadások tematikája, a laborfeladatok és a kötelező olvasmányok letölthető anyaga közös gyűjtőhelye:
http://canvas.infooktatas.ro/courses/16	

VIII. Értékelés
A hallgatók tevékenységét a szemináriumokon és a gyakorlati órákon állandóan ellenőrizzük. A végleges jegyben:
•	50% súllyal szerepel az írásbeli vizsga, 
•	25% súllyal a szemináriumi és 
•	25% súllyal a laboratóriumi tevékenység.
A végső jegybe 10%-ban beleszámít egy evközi parciális vizsgán szerzett pontszám is, viszont ezzel csak növelhető a szerzett jegy.	

IX. Kiegészítő könyvészet
[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.	

	Dékán,						Tanszékvezető,

	Dátum,						Előadás felelőse,
	2011.12.17.						Lect. Dr.  BODÓ Zalán Péter