Kybernetika 30 no. 1, 53-62, 1994

Transformations of translation grammars

Bořivoj Melichar


A one-pass translation algorithm may be constructed by an extension of $LR(k)$ parser for some $R$-translation grammars. An $LR$ parser is possible to extend in such a way that output of output symbols is performed during both basic operations of the parser - shift and reduce. Some transformations are studied which enable to transform some class of translation grammars on $R$-translation grammars. The most important transformations that can be used for this purpose are those called shaking down and postponing.


68Q42, 68Q45, 68N20, 68Q50