(0) 阅读 (1136)

抽象语法树 编辑

词条创建者 匿名用户

抽象语法树

编辑

计算机科学中,抽象语法树(AST),或只是语法树,是用一种形式语言编写的文本(通常是源代码)的抽象语法结构的树状表示。树上的每个节点都表示文本中出现的一个结构。语法是抽象的,因为它并不代表真实语法中出现的每一个细节,而只是代表结构或内容相关的细节。例如,分组括号在树状结构中是隐含的,所以这些括号不需要作为单独的节点来表示。同样地,像if-condition-then语句这样的语法结构可以用一个有三个分支的节点来表示。这就把抽象的语法树与具体的语法树(传统上称为解析树)区分开来。在源代码翻译和编译过程中,解析树通常由解析器构建。一旦建成,通过后续处理,例如上下文分析,额外的信息被添加到AST中。抽象语法树也被用于程序分析和程序转换系统中。

在编译器中的应用

编辑

抽象语法树是编译器中广泛使用的数据结构,用来表示程序代码的结构。语法树通常是一个编译器的语法分析阶段的结果。它经常作为程序的中间表示,通过编译器需要的几个阶段,对编译器的最终输出有很大影响。

抽象语法树的动机

编辑

一个AST有几个特性,可以帮助编译过程的后续步骤。一个AST可以被编辑和增强,它包含的每个元素都有属性和注释等信息。与源代码相比,AST不包括不必要的标点和定界符(大括号、分号、小括号等)。由于编译器的连续分析阶段,AST通常包含关于程序的额外信息。例如,它可以存储每个元素在源代码中的位置,允许编译器打印有用的错误信息。由于编程语言及其文档的固有性质,需要AST。语言在本质上往往是含糊不清的。为了避免这种模糊性,编程语言通常被指定为无语境语法(CFG)。然而,编程语言的某些方面往往是CFG所不能表达的,但却是语言的一部分,并被记录在其规范中。这些细节需要一个上下文来确定其有效性和行为。

抽象语法树

例如,如果一种语言允许声明新的类型,CFG不能预测这种类型的名称,也不能预测它们的使用方式。即使一种语言有一套预定义的类型,强制执行正确的使用通常也需要一些上下文。另一个例子是鸭子类型,其中一个元素的类型可以根据上下文而改变。运算符重载是另一种情况,正确的用法和最终的功能都取决于上下文。

抽象语法树的设计

编辑

一个AST的设计通常与编译器的设计和它的预期功能密切相关。核心要求包括以下几点。变量类型必须被保留,以及每个声明在源代码中的位置。可执行语句的顺序必须被明确表示和很好地定义。二进制操作的左和右组件必须被存储和正确识别。对于赋值语句必须存储标识符和它们的赋值。这些要求可以用来设计AST的数据结构。有些操作总是需要两个元素,例如加法的两个项。然而,有些语言结构需要任意多的子元素,例如从命令外壳传递给程序的参数列表。因此,用于表示用这种语言编写的代码的AST也必须足够灵活,以允许快速增加未知数量的子元素。为了支持编译器的验证,应该可以将AST解读为源代码的形式。在重新编译时,产生的源代码应该与原始代码在外观上有足够的相似性,并且在执行上也是相同的。AST在语义分析中被大量使用,编译器检查程序和语言元素的正确用法。在语义分析期间,编译器还根据AST生成符号表。对树的完整遍历可以验证程序的正确性。在验证了正确性之后,AST作为代码生成的基础。AST经常被用来生成一个中间表示法(IR),有时被称为中间语言,用于代码生成。

其他用途AST差分

编辑

AST差分,或简称树差分,包括计算


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/163750/

发表评论

登录后才能评论

词条目录
  1. 抽象语法树
  2. 在编译器中的应用
  3. 抽象语法树的动机
  4. 抽象语法树的设计
  5. 其他用途AST差分

轻触这里

关闭目录

目录