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

Tematika:

• Chomsky nyelvtanok: Definíciója, levezetés, generált nyelv fogalma. A Chomsky nyelvosztályok és nyelv hierarchia ismertetése.
• Reguláris nyelvek: Véges automata definíciója, a determinisztikus és nemdeterminisztikus automaták ekvivalenciája. Reguláris kifejezések, általuk meghatározott nyelvek osztálya. A 3 típusú nyelvtanok, az automaták és a reguláris kifejezések ekvivalenciája. Pumpáló lemma reguláris nyelvekre. Reguláris nyelvek reguláris műveletekre és Boole műveletekre vonatkozó zártsági tulajdonságai.
• Környezetfüggetlen nyelvek: Bal oldali, jobb oldali és korlátozás nélküli derivációk, ezek kapcsolata. Derivációs fa fogalma, levezetések és derivációs fák közötti kapcsolatok. Bar Hillel lemma. Veremautomata definíciója, felismerés végállapottal és felismerés üres veremmel. Ezen felismerési módok ekvivalenciája (nemdeterminisztikus esetben). Környezetfüggetlen nyelvtanok és veremautomaták ekvivalenciája. Determinisztikus veremautomata fogalma. Környezetfüggetlen nyelvek reguláris műveletekre és Boole műveletekre vonatkozó zártsági tulajdonságai.
• Felülről lefelé haladó elemzési módszerek: Általános felülről lefelé elemzési algoritmus. LL(k) és erősen LL(k) nyelvtanok: definíciók, FIRSTk és FOLLOWk kiszámítása, az LL(k) és az erősen LL(k) feltétel eldöntése, az elemzőtáblák elkészítése, az elemzési algoritmus megadása. Az LL(1) eset.
• Alulról felfelé haladó elemzési módszerek: Általános alulról felfelé elemzés, shiftelés-redukálás és redukálás-redukálás konfliktusok. LR(k) nyelvtanok: definíció, LR(k) táblák kiszámítása, LR(k) tétel, az LR(k) feltétel eldöntése és az elemzési algoritmus megadása. LALR(k) nyelvtanok és elemzésük.
• Egyszerű precedencia nyelvtanok: definíció, az egyszerű precedencia feltétel eldöntése és az elemzési algoritmus megadása.

Ajánlott irodalom:

• A. V. Aho, J. D. Ullman, Principles of Compiler Design, Addison Wesley, 1977.
• A. V. Aho, S. C. Johnson, LR parsing, Computing Surveys, 6 (1974) 99-124.
• A. V. Aho, J. D. Ullman, The Theory of Parsing, Translation and Compiling I., II., Prentice Hall, Englewood Clifs, New Jersey, 1972.
• A. V. Aho, R. Sethi, J. D. Ullman, Compilers - Principles, Techniques, and Tools, Addison Wesley, 1986.
• R. C. Backhouse, Syntax of Programming Languages - Theory and Practice, Prentice Hall International, London, 1979.
• Bánkfalvi Judit, Bánkfalvi Zsolt, Bolgár Gábor, Formális nyelvek szintaktikus elemzése, Közgazdasági és Jogi Könyvkiadó, Budapest, 1978
• J. G. Brookshear, Theory of Computation - Formal Languages, Automata, and Complexity, The Benjamin-Cummings Publishing Company, 1989.
• J. Carroll, D. Long, Theory of Finite Automata, Prentice Hall, Englewood Cliffs, New Jersey, 1989.
• Csörnyei László, Bevezetés a fordítóprogramok elméletébe I., II., Nemzeti Tankönyvkiadó, Budapest, 1996.
• Demetrovics János, Jordan Denev, Anton Pavlov, A számítástudomány matematikai alapjai, Tankönyvkiadó, Budapest, 1985.
• Fülöp Zoltán, Formális nyelvek és szintaktikus elemzésük, JATE TTK, kézirat, 1998.
• M. A. Harrison, Introduction to Formal Language Theory, Addison Wesley, 1978.
• J. E. Hopcroft, A. V. Aho, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979.
• D. Kelley, Automata and Formal Languages, Prentice Hall, Englewood Cliffs, 1995.
• R. N. Moll, M. A. Arbib, A. J. Kfoury, An Introduction to Formal Language Theory, Springer Publishing Company, 1988.
• Peák István, Bevezetés az automaták elméletébe I.-III., Tankönyvkiadó, Budapest, 1977-78, 1980.
• Révész György, Bevezetés a formális nyelvek elméletébe, Akadémiai Kiadó, 1979.
• S.Sippu, Parsing Theory I., II., Springer Publishing Company, 1988.
• A.Salomaa, Formal Languages, Academic Press, 1973.
• A.Salomaa, G. Rozenberg (Editors), The Handbook of Formal Languages, I., II., Springer Publishing Company, 1997.