Syntax Directed Translation of Context Free Languages

摘要

The report presents a new general class of syntax directed translations defined on a context free grammar. The class is called VGSDT. For each nonterminal symbol X in the grammar, one or more 'translations' of X are defined. These 'translations' are in general defined in terms of the translations of (1) the direct descendants of X and (2) the direct ancestor of X. As a result, translations of a given node in a parse tree can be a function of any part of the parse tree, both above and below the node. An intra-language grammatical transformation is a grammatical transformation which preserves the language generated by the original grammar. Suppose a translation is defined on a grammar G1, and G1 is then modified according to an intra-language grammatical transformation to give another grammar G2. It is shown that a translation defined on G1 using VGSDT can always be converted to one defined on G2. If the original translation is defined using one of the less general translation schemes, this is not always true. Consequently, while translations in the VGSDT class are actually defined on a specific context-free grammar, it would be more accurate to say that they are defined on the language itself, since the particular form of the underlying grammar is arbitrary. (Author)