关于抽象语法树（AST）的问题

Question

我很难理解

1) AST匹配，两个AST怎么相似？ comparison/matching 中包含类型还是仅包含 +、-、++、...等操作？

2) 两条语句在句法上相似（这个词我在一篇论文的某处读到过），下面的例子是否可以说这两条语句在句法上相似？

int x = 1 + 2
String y = "1" + "2"

Java - Eclipse 是我现在正在使用并试图理解 AST 的东西。

此致，

Answer 1

什么是 AST：

AST 是一种表示程序源文本的数据结构，它由包含 node 类型的节点组成，可能还有文字值，以及子节点列表。节点类型对应于 OP 调用的内容 "operations" (+, -, ...) 但也包括语言命令 (do, if, assignment, call, ...) ，声明 (int, struct, ... ) 和文字（数字、字符串、布尔值）。 [不清楚 OP 的 "type"] 是什么意思。（AST 通常在每个节点中都有附加信息，指向源文本文件中的原点）。

AST 的用途：

OP 似乎对 Eclipse 中 AST 的存在感到困惑。

AST 用于以比原始文本更容易解释的形式表示程序文本。它们提供了一种推理程序结构或内容的方法；有时它们用于通过修改程序的 AST 然后从 AST 重新生成文本来启用程序修改 ("refactoring")。

根据我的经验，比较 AST 的相似性并不是一个真正常见的用途，除了克隆检测 and/or 模式匹配。

比较 AST：

比较 AST 是否相等很容易：比较根节点 type/literal 值是否相等；如果不相等，则比较完成，否则（递归地）比较子节点）。

比较相似性的 AST 比较困难，因为您必须决定如何放宽相等性比较。 特别是，您必须决定相似性的精确定义。有很多方法可以定义它，一些在句法上相当浅显，一些在语义上更复杂。

我的论文 Clone Detection Using Abstract Syntax Trees 描述了一种方法，使用相似性定义为共享节点数除以两棵树中节点总数的比率。共享节点是通过自上而下比较树到某些子节点不同的点来计算的。（实际的比较是计算一个反统一器）。这种相似性度量相当肤浅，但在大型软件系统中查找代码克隆方面效果非常好。

从这个角度来看，OP 的示例：

     int x = 1 + 2
     String y = "1" + "2"

将树写成 S 表达式：

     (declaration_with_assignment (int x) (+ 1 2))
     (declaration_with_assignment (String y) (+ "1" "2"))

这些不是很相似；它们只共享一个类型为 "declaration-with-assignment" 的根节点和 + 子树的顶部。（此处节点数为 12，只有 2 个匹配节点，相似度为 2/12）。

这些会更相似：

     int x = 1 + 2
     float x = 1.0 + 2

（S 表达式）

     (declaration_with_assignment (int x) (+ 1 2))
     (declaration_with_assignment (float x) (+ 1.0 2))

与赋值、添加节点、文字叶节点 2 以及可以说是整数 1 和浮点数 1.0 的文字节点共享声明，具体取决于您是否希望将它们定义为 "equal" , 相似度为 4/12.

如果你把其中一棵树改成模式树，其中一些 "leaves" 是模式变量，你就可以使用这种模式树来找到具有一定结构的代码。

表面语法模式：

  ?type ?variable = 1 + ?expression

S 表达式

  ((declaration_with_assignment (?type ?varaible)) (+ 1 ?expression))

匹配 OP 的第一个示例，但不匹配第二个示例。

据我所知，Eclipse 不提供任何基于模式的匹配功能。不过这些都是非常有用的程序分析and/or程序改造工具。对于一些具体示例，由于太长而无法包含在此处，请参阅 DMS Rewrite Rules

（完全披露：DMS 是我公司的产品。我是架构师）。

关于抽象语法树（AST）的问题

Questions about Abstract Syntax Tree (AST)

abstract-syntax-tree