Fülöp Zoltán

Formális nyelvek és szintaktikus elemzésük

Tartalom
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
    4.6. Automaták minimalizálása 36
5. Környezetfüggetlen nyelvek 47
    5.1. Bal és jobb oldali derivációk, derivációs fák 47
    5.2. Veremautomaták 53
    5.3. A környezetfüggetlen nyelvtanok és a veremautomaták ekvivalenciája 58
    5.4. Környezetfüggetlen nyelvtanok átalakításai 62
        5.4.1. \lambda-mentesítés 62
        5.4.2. A felesleges szimbólumok elhagyása 64
        5.4.3. A balrekurzió megszüntetése 68
    5.5. Bar--Hillel lemma 74
    5.6. Környezetfüggetlen nyelvek zártsági tulajdonságai 76
    5.7. Determinisztikus veremautomaták 78
6. Az elemzés alapfeladatáról 79
    7. Felülről lefelé haladó elemzési algoritmusok 81
    7.1. Általános felülről lefelé elemzés 81
    7.2. LL(k) nyelvtanok és elemzésük 86
    7.3. Erősen LL(k) nyelvtanok és elemzésük 96
    7.4. LL(1) nyelvtanok és elemzésük 103
8. Alulról felfelé haladó elemzési algoritmusok 107
    8.1. Általános alulról felfelé elemzés 107
    8.2. LR(k) nyelvtanok és elemzésük 111
    8.3. LALR(k) nyelvtanok és elemzésük 125
    8.4. Precedencia nyelvtanok és elemzésük 126
Irodalomjegyzék 133
Tárgymutató 135

Ajánlott könyvek