Article
Full entry |
PDF
(3.2 MB)
Feedback
PDF
(3.2 MB)
Feedback
Keywords:
translation grammars; parsing
translation grammars; parsing
Summary:
The class of $LR$ translation grammars is introduced. This class is characterized by a possibility to implement a formal translation as an algorithm directed by $LR$ parsing. To perform a translation, the conventional $LR$ parser is extended by a facility to perform output operations within the parsing actions shift and reduce. The definitions of Kernel$(R)$- and $LR$-translation grammars are presented. The transformations shaking-down and postponing that enable to transform some translation grammars into Kernel$(R)$-translation grammars are described and used in the process of construction of the collection of sets of $LR(k)$ translation items. Different algorithms using these transformations are presented in an uniform way which makes it possible to compare them and to fix the hierarchy of the $LR$ translation grammars.
References:
[1] Aho A. V., Ullman J. D.: The Theory of Parsing, Translation and Compiling. Vol. 1: Parsing, Vol. 2: Compiling. Prentice–Hall, New York 1971, 1972 MR 0408321
[2] Aho A. V., Sethi, R., Ullman J. D.: Compiler–Principles, Techniques and Tools. Addison–Wesley, Reading, 1987
[3] Bac N. V.: $LR$ Translation Grammars. MSc Thesis. Department of Computer Science and Engineering, CTU, Prague 1994. In Czech
[4] Bac N. V., Melichar B.: Hierarchy of $LR(k)$ Translation Grammars. Research Report DC-96-09, Department of Computer Science and Engineering, CTU, Prague 1996
[5] Janoušek J.: One–pass formal translation directed by $LR$ parsing. In: WORKSHOP’97, CTU, Prague 1997, pp. 139–140
[6] Janoušek J., Melichar B.: Formal translations described by translation grammars with $LR(k)$ input grammars. In: Ninth International Symposium on Programming Languages, Implementations, Logics and Programs (Lecture Notes in Computer Science 1338), Springer–Verlag, Berlin 1997, pp. 421–422
[7] Janoušek J., Melichar B.: The output-store formal translator directed by LR parsing. In: SOFSEM’97: Theory and Practice of Informatics (Lecture Notes in Computer Science 1338), Springer–Verlag, Berlin 1997, pp. 432–439
[8] Lewis P. M., Stearns R. E.: Syntax directed transductions. J. Assoc. Comput. Mach. 15 (1967), 3, 465–488 DOI 10.1145/321466.321477
[9] Lewis P. M., Rosenkrantz D. J., Stearns R. E.: Compiler Design Theory. Addison–Wesley, London 1976 Zbl 0464.68004
[10] Melichar B.: Compilers. Publishing House of the Czech Technical University, Prague 1991. In Czech
[11] Melichar B.: $LR$ Translation Grammars. Reseach Report DC-92-03, Department of Computer Science and Engineering, CTU, Prague 1992
[12] Melichar B.: Formal translation directed by $LR$ parsing. Kybernetika 28 (1992), 1, 50–61 MR 1159874 | Zbl 0746.68056
[13] Melichar B.: Transformations of translation grammars. Kybernetika 30 (1994), 1, 53–62 MR 1267471 | Zbl 0820.68069
[14] Melichar B., Bac N. V.: Transformations of Grammars and Translation Directed by $LR$ Parsing. Research Report DC-96-02, Department of Computer Science and Engineering, CTU, Prague 1996
[15] Purdom P., Brown C. A.: Semantic routines and $LR(k)$ parsers. Acta Inform. 14 (1980), 4, 229–315 DOI 10.1007/BF00286489 | MR 0593927 | Zbl 0424.68052
Search
Partner of
