關於抽象語法樹（AST）的問題

Question

我很難理解

1）AST匹配，兩個AST如何相似？包含在比較/匹配中的類型還是隻包含像+， - ，++，...等操作的類型？

2）兩個語句在語法上是相似的（這個術語我在某篇論文中讀過），我們可以說下面的例子是兩個語句在語法上是相似的嗎？

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

Java - Eclipse現在正在使用，並試圖瞭解AST。

此致

Answer 1

什麼AST的是：

的AST是表示程序源文本的數據結構由包含一個節點類型，以及可能的一個文字值的節點，和一個兒童節點的列表。節點類型對應於OP所稱的「操作」（+， - ，...），還包括語言命令（do，if，assignment，call，...），聲明（int，struct，...）和文字（數字，字符串，布爾）。 [目前還不清楚「類型」是什麼意思）。 （AST通常在每個節點中都有附加信息，指向源文本文件中的起點）。

什麼AST的是：

OP似乎被AST的Eclipse中存在的困惑。

AST被用來表示比原始文本更容易解釋的形式的程序文本。他們提供了一種方法來推理程序結構或內容;有時它們通過修改程序的AST，然後從AST中重新生成文本來修改程序（「重構」）。

比較AST的相似性是不是我的經驗，除了在克隆檢測和/或模式匹配除外的真正常用。

比較的AST：

的相等比較AST的很簡單：比較是否相等根節點類型/字面值;如果不相等，則比較完成，否則（遞歸地）比較子節點）。

比較AST的相似性比較困難，因爲您必須決定如何放寬等式比較。 尤其是，您必須決定相似度的精確定義。有很多方法來定義這個，一些語法上比較淺，一些語義更復雜。

我的論文Clone Detection Using Abstract Syntax Trees描述了一種方法來做到這一點，使用相似性定義爲共享節點數量除以兩棵樹中總節點數量的比率。共享節點是通過比較樹頂部到某個孩子不同的點來計算的。 （實際比較是計算一個反統一）。這種相似的測量方法很簡單，但它在大型軟件系統中查找代碼克隆方面非常有效。

從這個角度看，有機磷農藥的例子：

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

有寫爲S-表達式樹：

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

這些都不是非常相似的;它們只共享類型爲「帶分配的聲明」和+子樹頂部的根節點。 （這裏的節點數是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，取決於您是否希望將它們定義爲「相等」或不相似，相似度爲4/12。

如果將其中一棵樹更改爲模式樹，其中某些「葉」是模式變量，則可以使用此類模式樹來查找具有特定結構的代碼。

表面語法圖案：

?type ?variable = 1 + ?expression 

與S-表達

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

匹配的第一個的OP的例子，但不是第二。

據我所知，Eclipse不提供任何基於模式的匹配功能。但這些在程序分析和/或程序轉換工具中非常有用。對於一些特定的例子，這裏包含的時間太長，請參閱DMS Rewrite Rules

（完全披露：DMS是我公司的產品，我是架構師）。