The complexity of Languages Generated by Attribute Grammars
The complexity of Languages Generated by Attribute Grammars
复制标题
属性文法生成语言的复杂性
DOI：
10.1137/0215005
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
J. Engelfriet
中科院分区：
文献类型：
--
作者：
J. Engelfriet
字符串值属性文法（SAG）具有字符串在某个字母表上的语义域，并以连接作为基本操作。它表明输出语言（即，翻译的范围）的SAG是对数空间可约化为上下文无关的语言。关键词，理论，编译器，属性文法，交替，复杂性，由文法定义的语言类，由资源有界自动机CR类别。D3.4、F1.2、F2、F4.3简介。属性语法（AG）是一种将上下文无关语法的派生树翻译成某个语义域的值的机制[26]。一个特殊的，非常有限的，感兴趣的领域是字符串的集合在一些字母表与连接作为基本操作。这样的“字符串值”属性语法（SAG），参见[10]，由于两个原因是重要的。第一个原因是每个属性语法都可以被看作是一个SAG。事实上，将AG的语义规则的右侧视为字符串而不是有意义的表达式，可以获得SAG，其属性评估对应于AG属性的符号评估：SAG将上下文无关语法的派生树转换为字符串（通常是表达式），最终可以再次解释为AG计算的值。字符串值属性文法重要的第二个原因是它们可以用作语言生成机制：SAG G的翻译范围，记为OUT（G），是一种形式语言。如果G描述了一个将高级程序翻译成汇编程序的编译器，那么OUT（G）是“编译器所说的汇编语言”，即，所有汇编程序的集合，这些程序是某个高级程序的翻译。对于自上而下的树转换器的更受限制的形式主义，这种“树转换语言”首先在[32]中进行了研究。本文证明了对每个SAG G，OUT（G）在可约化为上下文无关语言的对数空间语言类-因此，这些输出语言在多项式时间或对数平方空间（在确定性图灵机上）是可识别的。这个结果的证明是作为[2]中IO_CF（CF）证明的推广而获得的，其中IO是由内而外的宏语言类[19]。事实上，IO等于所有OUT（G）的类，其中G是具有一个合成属性（和任意数量的继承属性）的SAG，参见[10]。为了证明语言L在CF中，可以使用[36]中介绍的技术（并在[2]中使用）在多项式时间内通过非确定性多头下推自动机（MPDA）接受L：多项式时间MPDA和CF的等价性在[36]中显示。为了证明OUT（G）在CF中，我们将使用这种技术的一个变体，它涉及交替多头有限自动机（AMFA）而不是MPDA。众所周知，AMFA和MPDA接受同一类语言（即PTIME，一类确定性多项式时间图灵机语言，* 1982年12月27日由编辑接收，并于1984年4月15日最终修订。“荷兰恩斯赫德7500 AE特文特理工大学计算机科学系。现住址：莱顿大学数学和计算机科学系，
A string-valued attribute grammar (SAG) has a semantic domain of strings over some alphabet, with concatenation as basic operation. It is shown that the output language (i.e., the range ofthe translation) of a SAG is log-space reducible to a context-free language. Key words, theory, compilers, attribute grammars, alternation, complexity, classes of languages defined by grammars, by resource-bounded automata CR categories. D3.4, F1.2, F2, F4.3 Introduction. Attribute grammars (AG) are a mechanism for translating the derivation trees of a context-free grammar into values of some semantic domain [26]. A particular, very restricted, domain of interest is the set of strings over some alphabet with concatenation as basic operation. Such "string-valued" attribute grammars (SAG), see [10], are of importance for two reasons. The first reason is that every attribute grammar can be viewed as a SAG. In fact, viewing the right-hand sides of semantic rules of an AG as strings rather than meaningful expressions, a SAG is obtained whose attribute evaluation corresponds to the symbolic evaluation of the attributes of the AG: the SAG translates the derivation trees of the context-free grammar into strings (usually expressions) which eventually may be interpreted again as the values computed by the AG. The second reason that string-valued attribute grammars are important is that they can be used as a language generating mechanism: the range of the translation of a SAG G, denoted OUT (G), is a formal language. If G describes a compiler that translates high-level programs into assembler programs, then OUT (G) is the "assembler dialect spoken by the compiler," i.e., the set of all assembler programs that are the translation of some high-level program. For the more restricted formalism of top-down tree transducers, such "tree transformation languages" were first studied in [32]. In this paper we prove that for every SAG G, OUT (G) is in LOG (CF): the class of languages log-space reducible to context-free languages.. Hence these output languages are recognizable in polynomial time or log square space (on a deterministic Turing machine). The proof of this result was obtained as a generalization of the proof of IO_ LOG (CF) in [2], where IO is the class of inside-out macro languages 19]. In fact, IO is equal to the class of all OUT (G), where G is a SAG with one synthesized attribute (and an arbitrary number of inherited attributes), see [10]. To show that a language L is in LOG (CF), one can use the technique introduced in [36] (and used in [2]) to accept L by a nondeterministic multihead pushdown automaton (MPDA) in polynomial time: the equivalence of polynomial time MPDA and LOG (CF) is shown in [36]. To show that OUT (G) is in LOG (CF) we will use a variation of this technique that concerns alternating multihead finite automata (AMFA) rather than MPDA. It is well-known that AMFA and MPDA accept the same class of languages (viz. PTIME, the class of deterministic polynomial time Turing machine languages, * Received by the editors December 27, 1982, and in final revised form April 15, 1984. " Department of Computer Science, Twente University of Technology, 7500 AE Enschede, the Netherlands. Present address, Department of Mathematics and Computer Science, University of Leiden, Leiden,