Generátor kompilátorů založený na restartovacích automatech

• Thesis title in Czech: Generátor kompilátorů založený na restartovacích automatech
• Thesis title in English: Compiler generator based on restarting automata
• Academic year of topic announcement: 2008/2009
• Type of assignment: diploma thesis
• Thesis language: čeština
• Department: Department of Software and Computer Science Education (32-KSVI)
• Supervisor: RNDr. František Mráz, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 14.11.2008
• Date of assignment: 14.11.2008
• Date and time of defence: 31.05.2010 00:00
• Date of electronic submission: 31.05.2010
• Date of proceeded defence: 31.05.2010
• Reviewers: Martin Plátek, CSc.

Guidelines

Cílem práce je navrhnout generátor kompilátorů založený na modelu restartovacího automatu. Kompilátory kompilátorů (compiler compilers) jako yacc, bison a jim podobné nabízejí možnost generování syntaktického analyzátoru přímo ze zápisu bezkontextové gramatiky s vhodnými vlastnostmi. Navíc lze ke každému pravidlu gramatiky přidat příkazy, které se mají vykonat při uplatnění daného pravidla při analýze vstupního řetězce.

Podobně lze pro popis syntaxe jazyka použít restartovací automat (např. ve formě tzv. metainstrukcí). Diplomant ve své práci navrhne vhodné rozšíření pro metainstrukce restartovacího automatu tak, aby bylo možné s pomocí takového automatu nejenom zjišťovat syntaktickou správnost vstupního řetězce, ale navíc i vykonávat sémantické akce, aby při přijetí vstupního slova analyzátor vydal také "překlad slova".

Diplomant ověří funkčnost svého návrhu na umělých příkladech, případně na reálné úloze rozpoznávání názvů sloučenin organické chemie zapsaných v českém jazyce.

References

[1] H. Messerschmidt, F. Mráz, F. Otto, and M. Plátek: Correctness preservation and complexity of simple RL-automata. In O. Ibarra and H.-C. Yen, editors, Proceedings CIAA 2006, volume 4094 of LNCS, Berlin, 2006. Springer-Verlag, pages 162-172.

[2] F. Otto: Restarting automata. In Z. Ésik, C. Martin-Vide, and V. Mitrana (eds.): Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence 25, Springer-Verlag, Berlin, 2006, 269-303.

[3] Donnelly, C., Stallman, R.M.: Bison: the YACC-compatible Parser Generator, Bison Version 1.28. Free Software Foundation, 1999.

[4] S. McPeak and G. C. Necula: Elkhound: A Fast, Practical GLR Parser Generator. In Norman Ramsey (ed.): Compiler Construction,
13th International Conference, CC 2004, Springer, 2004