Fordítóprogramok

Tematika:

• Elméleti tematika:
  • Lexikális elemzés. Reguláris kifejezések, véges automaták, determinisztikus automata megszerkesztése reguláris kifejezés alapján. Lexikális elemző készítése a Lex program segítségével.
  • Szintaktikus elemzés. Környezetfüggetlen nyelvek és nyelvtanok, derivációs fák, bal- és jobboldali levezetések, FIRSTk és FOLLOWk halmazok.
  • Felülről lefelé történő elemzés.LL(k) és erősen LL(k) nyelvek és nyelvtanok. Rekurzív elemzőprogram írása erősen LL(k) nyelvtan esetén. Táblavezérelt elemzőprogram írása erősen LL(k) nyelvtan esetén.
  • Alulról felfelé történő elemzés. LR(k) nyelvek és nyelvtanok, járható prefix fogalma, LR(k) elemek és táblák. Táblavezérelt LR(k) elemzés. Fordítóprogram írása a Yacc program segítségével.
• Gyakorlati tematika
  • Lambda-átmenetes nemdeterminisztikus automata megszerkesztése reguláris kifejezés alapján.
  • Determinisztikus automata megszerkesztése lambda-átmenetes nemdeterminisztikus automata alapján.
  • Környezetfüggetlen nyelvtan balrekurzivitásának megszüntetése.
  • FIRSTk és FOLLOWk halmazok számítása.
  • Az erősen LL(k) feltétel eldöntése, elemző tábla elkészítése erősen LL(k)
  • nyelvtan esetén.
  • LR(k) táblák számítása, az LR(k) feltétel eldöntése.

Ajánlott irodalom:

• Thomas W. Parsons: Compiler Construction, W. H. Freeman and Company, 1992
• Alfred V. Aho, Jeffrey D. Ullman: The theory of parsing, translation and compiling, Volume I: Parsing, Prentice-Hall, 1972
• Alfred V. Aho, Jeffrey D. Ullman: The theory of parsing, translation and compiling, Volume II: Compiling, Prentice-Hall, 1973
• Salomaa: Formal languages, Academic Press, 1973