| Title:
|
Transformations of grammars and translation directed by $LR$ parsing (English) |
| Author:
|
Melichar, Bořivoj |
| Author:
|
Bac, Nguyen van |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
38 |
| Issue:
|
1 |
| Year:
|
2002 |
| Pages:
|
[13]-44 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
translation grammars |
| Keyword:
|
parsing |
| MSC:
|
68N20 |
| MSC:
|
68Q42 |
| MSC:
|
68Q45 |
| idZBL:
|
Zbl 1265.68088 |
| idMR:
|
MR1899845 |
| . |
| Date available:
|
2009-09-24T19:43:37Z |
| Last updated:
|
2015-03-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135444 |
| . |
| Reference:
|
[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 |
| Reference:
|
[2] Aho A. V., Sethi, R., Ullman J. D.: Compiler–Principles, Techniques and Tools.Addison–Wesley, Reading, 1987 |
| Reference:
|
[3] Bac N. V.: $LR$ Translation Grammars.MSc Thesis. Department of Computer Science and Engineering, CTU, Prague 1994. In Czech |
| Reference:
|
[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 |
| Reference:
|
[5] Janoušek J.: One–pass formal translation directed by $LR$ parsing.In: WORKSHOP’97, CTU, Prague 1997, pp. 139–140 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[8] Lewis P. M., Stearns R. E.: Syntax directed transductions.J. Assoc. Comput. Mach. 15 (1967), 3, 465–488 10.1145/321466.321477 |
| Reference:
|
[9] Lewis P. M., Rosenkrantz D. J., Stearns R. E.: Compiler Design Theory.Addison–Wesley, London 1976 Zbl 0464.68004 |
| Reference:
|
[10] Melichar B.: Compilers.Publishing House of the Czech Technical University, Prague 1991. In Czech |
| Reference:
|
[11] Melichar B.: $LR$ Translation Grammars.Reseach Report DC-92-03, Department of Computer Science and Engineering, CTU, Prague 1992 |
| Reference:
|
[12] Melichar B.: Formal translation directed by $LR$ parsing.Kybernetika 28 (1992), 1, 50–61 Zbl 0746.68056, MR 1159874 |
| Reference:
|
[13] Melichar B.: Transformations of translation grammars.Kybernetika 30 (1994), 1, 53–62 Zbl 0820.68069, MR 1267471 |
| Reference:
|
[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 |
| Reference:
|
[15] Purdom P., Brown C. A.: Semantic routines and $LR(k)$ parsers.Acta Inform. 14 (1980), 4, 229–315 Zbl 0424.68052, MR 0593927, 10.1007/BF00286489 |
| . |
