Elõszó i
1. A generatív nyelvtanok gyakorlati jelentõsége
1
2. Fogalmak, jelölések 7
2.1. Halmazok, relációk 7
2.2. Formális nyelvek 8
3. Generatív nyelvtanok 11
3.1. A generatív nyelvtan definíciója
11
3.2. Chomsky nyelvosztályok 13
4. Reguláris nyelvek 17
4.1. Véges automaták 17
4.2. Reguláris kifejezések 22
4.3. A reguláris nyelvek osztályának
jellemzései 24
4.4. Pumpáló lemma reguláris nyelvekre
31
4.5. Reguláris nyelvek zártsági
tulajdonságai 34
5. Környezetfüggetlen nyelvek 37
5.1. Bal és jobb oldali derivációk,
derivációs fák 37
5.2. Veremautomaták 43
5.3. A környezetfüggetlen nyelvtanok és
a veremautomaták ekvivalenciája 48
5.4. Környezetfüggetlen nyelvtanok
átalakításai 52
5.4.1. lambda -mentesítés
52
5.4.2. A felesleges szimbólumok
elhagyása 54
5.4.3. A balrekurzió
megszüntetése 58
5.5. Bar--Hillel lemma 64
5.6. Környezetfüggetlen nyelvek
zártsági tulajdonságai 66
5.7. Determinisztikus veremautomaták 68
6. Az elemzés alapfeladatáról 69
7. Felülrõl lefelé haladó elemzési
algoritmusok 71
7.1. Általános felülrõl
lefelé elemzés 71
7.2. LL(k) nyelvtanok és
elemzésük} 76
7.3. Erõsen LL(k) nyelvtanok és
elemzésük 86
7.4. LL(1) nyelvtanok és elemzésük
93
8. Alulról felfelé haladó elemzési algoritmusok
97
8.1. Általános alulról felfelé
elemzés 97
8.2. LR(k) nyelvtanok és
elemzésük 101
8.3. LALR(k) nyelvtanok és
elemzésük 115
8.4. Precedencia nyelvtanok és elemzésük
116
Irodalomjegyzék 123
Tárgymutató 125