Geodesic
Transformations of grammars and translation directed by $LR$ parsing
Kybernetika, Tome 38 (2002) no. 1, pp. 13-44 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 68N20, 68Q42, 68Q45
Keywords: translation grammars; parsing 
@article{KYB_2002_38_1_a1,
     author = {Melichar, Bo\v{r}ivoj and Bac, Nguyen van},
     title = {Transformations of grammars and translation directed by $LR$ parsing},
     journal = {Kybernetika},
     pages = {13--44},
     year = {2002},
     volume = {38},
     number = {1},
     mrnumber = {1899845},
     zbl = {1265.68088},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2002_38_1_a1/}
}
TY  - JOUR
AU  - Melichar, Bořivoj
AU  - Bac, Nguyen van
TI  - Transformations of grammars and translation directed by $LR$ parsing
JO  - Kybernetika
PY  - 2002
SP  - 13
EP  - 44
VL  - 38
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/KYB_2002_38_1_a1/
LA  - en
ID  - KYB_2002_38_1_a1
ER  - 
%0 Journal Article
%A Melichar, Bořivoj
%A Bac, Nguyen van
%T Transformations of grammars and translation directed by $LR$ parsing
%J Kybernetika
%D 2002
%P 13-44
%V 38
%N 1
%U http://geodesic.mathdoc.fr/item/KYB_2002_38_1_a1/
%G en
%F KYB_2002_38_1_a1
Melichar, Bořivoj; Bac, Nguyen van. Transformations of grammars and translation directed by $LR$ parsing. Kybernetika, Tome 38 (2002) no. 1, pp. 13-44. http://geodesic.mathdoc.fr/item/KYB_2002_38_1_a1/

[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

[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

[9] Lewis P. M., Rosenkrantz D. J., Stearns R. E.: Compiler Design Theory. Addison–Wesley, London 1976 | Zbl

[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 | Zbl

[13] Melichar B.: Transformations of translation grammars. Kybernetika 30 (1994), 1, 53–62 | MR | Zbl

[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 | MR | Zbl