Abstract:

The notion of the syntax-directed translation was a highly influential idea in theory of the formal translation. Models for the description of the formal translations are syntax-directed translation schemes. The special case of syntax-directed translation schemes are simple syntax-directed translation schemes, which can be written in the form of translation grammars. It is possible for an arbitrary translation described by a translation grammar with LL(k) input grammar to create one-pass translation algorithm by a simple extension of the algorithm of a syntax analysis for LL(k) grammars. Similar approach for an LR(k) grammar led to the result that it is possible to perform an one-pass formal translation during LR(k) analysis only in that case when the translation grammar has a postfix property. In this paper the construction of the algorithm is studied, which can, for a particular class of translation grammars (called LR(k) R-translation grammars), perform one pass formal translation. The basic idea discussed in this paper is the following: It is possible to make an extension of the algorithm of the syntax analysis for LR(k) grammars in such a way, that the output of output symbols can be performed not only as a part of the operation reduction but also as a part of the operation shift.