Kybernetika 38 no. 1, 13-44, 2002

Transformations of grammars and translation directed by LR parsing

Bořivoj Melichar and Nguyen van Bac


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 {\sl Kernel}$(R)$- and $LR$-translation grammars are presented. The transformations shaking-down and postponing that enable to transform some translation grammars into {\sl 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.