在创建抽象语法树的上下文中合成属性是什么? [英] What are synthesized attributes in the context of creating an abstract syntax tree?

查看:30
本文介绍了在创建抽象语法树的上下文中合成属性是什么?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

编译器解析源代码并构建抽象语法树.用于构造抽象语法树的函数返回构成综合属性的指针.它们是什么以及它们与继承的属性有何不同?

Compilers parse source code and build an abstract syntax tree. The functions used to construct an abstract syntax tree return pointers which constitute synthesized attributes. What are they and how do they differ from inherited attributes.?

我不知道这是否有帮助,但我最初在法语环境中听说过这些术语:Attributs synthétisés、attributs hérités.

edit: I don't know if this can help, but I originally heard of these terms in a French context: Attributs synthétisés, attributs hérités.

推荐答案

属性是与核心利益相关联的附加值.在 AST 的情况下,您可以将它们视为与每个 AST 节点相关联的对 (attribute_name, attribute_value),其中属性名称对应于一些有趣的事实类型,而属性值对应于该事实的实际状态(例如, "(constants_in_subtree_count,12)").

Attributes are additional values associated with something of central interest. In the case of ASTs, you can think of them as pairs (attribute_name, attribute_value) associated with each AST node, where the attribute name corresponds to some interesting fact-type, and the attribute value corresponds to the actual state of that fact (e.g., "(constants_in_subtree_count,12)").

继承综合是描述如何为每个 AST 节点计算属性值的术语,通常与使用其子节点生成 AST 节点的语法规则相关联.

Inherited and synthesized are terms for describing how the attribute values are computed for each AST node, usually associated with the grammar rule that produces the AST node using its children.

综合属性是那些值是从子节点的属性值计算出来的,并被向上传递到树中.通常,合成属性的值被组合以产生父节点的属性.如果一个 AST 节点有两个子节点,每个子节点都有自己的属性 (constants_in_subtree_count,5) 和 (constants_in_subtree_count,7),那么通过向上传递这些属性,父节点可以计算出其对应的属性 (constants_in_subtree_count,12).

Synthesized attributes are those whose value is computed from attribute values from children nodes, and are being passed up the tree. Often, values of synthesized attributes are combined to produce an attribute for the parent node. If an AST node has two children, each of which have their own attributes (constants_in_subtree_count,5) and (constants_in_subtree_count,7), then by passing those attributes up, the parent can compute his corresponding attribute (constants_in_subtree_count,12).

继承属性是从父级向下传递到子级的属性.如果函数 AST 的根知道"函数返回类型是 (return_type,integer) 作为属性,它可以将返回类型传递给函数根的子级,例如到函数体.在那棵树的深处有一个实际的 return 语句;如果它接收到继承的属性 (return_type,X),它可以检查它计算的结果是否是正确的类型.

Inherited attributes are those passed from the parent down to the child. If the root of a function AST "knows" the function return type is (return_type,integer) as an attribute, it can pass the return type to the children of the function root, e.g. to the function body. Someplace deep down in that tree is an actual return statement; if it receives the inherited attribute (return_type,X), it can check that the result it is computing is the correct type.

在实践中,您希望能够为节点定义任意属性集,并出于处理 AST 所需的多种目的(构建符号表、构建控制流图、进行类型检查、计算指标,...).属性语法生成器是一种解析器生成器,它将采用语法规则、属性集定义,以及关于如何计算每个规则中涉及的节点的合成和继承属性的规则,并生成一个解析器和一个计算所有属性的 AST walker.

In practice, you want to be able to define arbitrary sets of attributes for nodes, and pass them up and down the tree for the multiple purposes required to process ASTs (building symbol tables, constructing control flow graphs, doing type checking, computing metrics, ...). An attribute grammar generator is a kind of parser generator that will take grammar rules, sets of attribute definitions, and rules about how to compute synthesized and inherited attributes for the nodes involved in each rule, and generates both a parser and an AST walker that computes all the attributes.

这个想法的价值在于它提供了一个由自动化支持的组织原则,可以用来以常规方式计算关于 AST 的许多有趣的事情.否则,您可以使用临时代码编写所有这些内容.

The value of this idea is it provides an organizing principle supported by automation, that can be used to compute many interesting things about ASTs in a regular way. Otherwise you get to code all that stuff using ad hoc code.

我们的DMS Software Reengineering Toolkit 是一个 AST 操作系统(实际上是源到源程序转换) 大量使用并行属性评估来计算对 AST 的各种有用分析:常规指标、符号表、类型检查(如我上面描述的返回类型检查)、从代码中提取控制和数据流,以及其他不太容易描述但在子树上计算的有用结果(此表达式中的副作用分配列表").为什么平行?嗯,子树中的属性计算本质上是独立的,所以并行性已经存在,当你处理真正的大树时,性能很重要.DMS 经常处理数千个编译单元,每个编译单元产生一个(可能很大)AST.

Our DMS Software Reengineering Toolkit is an AST manipulation system (actually source-to-source program transformations) that heavily uses parallel attribute evaluation to compute all kinds of useful analyses over ASTs: conventional metrics, symbol tables, type checks (like the return type check I described above), control and data flow extraction from code, as well as other not-so-easily described but useful results computed over subtrees ("list of side effecting assignments in this expression"). Why parallel? Well, attribute computations in subtrees are essentially independent, so the parallelism is already there, and when you deal with really big trees performance matters. DMS often deals with thousands of compilation units, each producing a (possibly big) AST.

这篇关于在创建抽象语法树的上下文中合成属性是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆