Transformations of grammars and translation directed by L R parsing

Bořivoj Melichar; Nguyen van Bac

Kybernetika (2002)

  • Volume: 38, Issue: 1, page [13]-44
  • ISSN: 0023-5954

Abstract

top
The class of L R translation grammars is introduced. This class is characterized by a possibility to implement a formal translation as an algorithm directed by L R parsing. To perform a translation, the conventional L R parser is extended by a facility to perform output operations within the parsing actions shift and reduce. The definitions of Kernel ( R ) - and L R -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 L R ( 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 L R translation grammars.

How to cite

top

Melichar, Bořivoj, and Bac, Nguyen van. "Transformations of grammars and translation directed by $LR$ parsing." Kybernetika 38.1 (2002): [13]-44. <http://eudml.org/doc/33565>.

@article{Melichar2002,
abstract = {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.},
author = {Melichar, Bořivoj, Bac, Nguyen van},
journal = {Kybernetika},
keywords = {translation grammars; parsing; translation grammars; parsing},
language = {eng},
number = {1},
pages = {[13]-44},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Transformations of grammars and translation directed by $LR$ parsing},
url = {http://eudml.org/doc/33565},
volume = {38},
year = {2002},
}

TY - JOUR
AU - Melichar, Bořivoj
AU - Bac, Nguyen van
TI - Transformations of grammars and translation directed by $LR$ parsing
JO - Kybernetika
PY - 2002
PB - Institute of Information Theory and Automation AS CR
VL - 38
IS - 1
SP - [13]
EP - 44
AB - 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.
LA - eng
KW - translation grammars; parsing; translation grammars; parsing
UR - http://eudml.org/doc/33565
ER -

References

top
  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 (1971) MR0408321
  2. Aho A. V., Sethi, R., Ullman J. D., Compiler–Principles, Techniques and Tools, Addison–Wesley, Reading, 1987 
  3. Bac N. V., L R Translation Grammars, MSc Thesis. Department of Computer Science and Engineering, CTU, Prague 1994. In Czech (1994) 
  4. Bac N. V., Melichar B., Hierarchy of L R ( 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 L R parsing, In: WORKSHOP’97, CTU, Prague 1997, pp. 139–140 (1997) 
  6. Janoušek J., Melichar B., Formal translations described by translation grammars with L R ( 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 (1997) 
  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 (1997) 
  8. Lewis P. M., Stearns R. E., 10.1145/321466.321477, J. Assoc. Comput. Mach. 15 (1967), 3, 465–488 (1967) DOI10.1145/321466.321477
  9. Lewis P. M., Rosenkrantz D. J., Stearns R. E., Compiler Design Theory, Addison–Wesley, London 1976 Zbl0464.68004
  10. Melichar B., Compilers, Publishing House of the Czech Technical University, Prague 1991. In Czech (1991) 
  11. Melichar B., L R Translation Grammars, Reseach Report DC-92-03, Department of Computer Science and Engineering, CTU, Prague 1992 
  12. Melichar B., Formal translation directed by L R parsing, Kybernetika 28 (1992), 1, 50–61 (1992) Zbl0746.68056MR1159874
  13. Melichar B., Transformations of translation grammars, Kybernetika 30 (1994), 1, 53–62 (1994) Zbl0820.68069MR1267471
  14. Melichar B., Bac N. V., Transformations of Grammars and Translation Directed by L R Parsing, Research Report DC-96-02, Department of Computer Science and Engineering, CTU, Prague 1996 
  15. Purdom P., Brown C. A., 10.1007/BF00286489, Acta Inform. 14 (1980), 4, 229–315 (1980) Zbl0424.68052MR0593927DOI10.1007/BF00286489

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.