我在一本編譯器設計書中找到了這兩個術語，我想知道它們各自代表什麼，以及它們有何不同。解析樹和抽象語法樹有什麼區別？

我在網上搜索，發現解析樹也被稱爲具體語法樹（CST）。

2011-05-11 Shashi Bhushan

查看此SO問題的答案：http://stackoverflow.com/questions/1888854/what-is-the-difference-between-an-abstract-syntax-tree-and-a-concrete-syntax-樹 – 2011-05-14 09:57:15

這是基於Terrence Parr的Expression Evaluator語法。

此示例的語法：

grammar Expr002; 

options 
{ 
    output=AST; 
    ASTLabelType=CommonTree; // type of $stat.tree ref etc... 
} 

prog : (stat)+ ; 

stat : expr NEWLINE  -> expr 
     | ID '=' expr NEWLINE -> ^('=' ID expr) 
     | NEWLINE    -> 
     ; 

expr : multExpr (('+'^ | '-'^) multExpr)* 
     ; 

multExpr 
     : atom ('*'^ atom)* 
     ; 

atom : INT 
     | ID 
     | '('! expr ')'! 
     ; 

ID  : ('a'..'z' | 'A'..'Z')+ ; 
INT  : '0'..'9'+ ; 
NEWLINE : '\r'? '\n' ; 
WS  : (' ' | '\t')+ { skip(); } ;

輸入

x=1 
y=2 
3*(x+y)

解析樹

的語法分析樹是輸入的具體表示。分析樹保留了輸入的所有信息。空框表示空白，即行尾。

Parse Tree

AST

AST是輸入的抽象表示。請注意，parens不存在於AST中，因爲這些關聯可以從樹結構中推導出來。

AST

編輯

對於通過解釋更見Compilers and Compiler Generators通過P.D.特里pg。 23.另請參閱作者home page瞭解更多項目，例如源代碼。

來源

2012-04-16 15:47:17

給定的URL「編譯器和編譯器生成器」需要認證。這個資源是否有不同的URL或者是否有某種匿名訪問？ – rexford 2016-01-05 14:11:06

@rexford當我第一次發佈它時，鏈接是免費的。顯然這已經改變了。你有具體的問題嗎？ – 2016-01-05 14:30:45

本書可在本書作者的主頁上找到，截至2017年11月。http://www.cs.ru.ac.za/compilers/index.html – uxp 2017-11-08 23:25:29

AST從概念上描述了源代碼，它不需要包含解析某些源代碼（花括號，關鍵字，括號等）所需的所有語法元素。

解析樹更接近地表示源代碼。

在AST爲IF語句的節點可以只包含三個孩子：

條件
如果案例
否則案例

對於類似C語言的解析樹需要包含'if'關鍵字，圓括號和花括號的節點。

來源

2011-05-11 17:54:57 jjwchoy

這裏是解析樹（具體語法樹，國家支助組）和抽象語法樹（AST的）的解釋，在編譯器構造的情況下。它們是相似的數據結構，但它們構造不同，並用於不同的任務。

解析樹

解析樹通常爲詞法分析之後的下一步驟（其轉動源代碼轉換成一系列令牌可以被看作是有意義的單位，而不是僅僅一個字符的序列）產生的。

它們是樹型數據結構，它顯示了輸入的終端字符串（源代碼標記）是如何由相關語言的語法生成的。解析樹的根是語法的最一般符號 - 起始符號（例如，語句），並且內部節點表示開始符號擴展到的非終止符號（可以包括開始符號本身），例如as expression，statement，term，函數調用。葉子是語法的終端，在語言/輸入字符串中顯示爲標識符，關鍵字和常量的實際符號，例如爲，，如果等

在解析編譯器還執行各種檢查，以確保語法的正確性 - 和和語法錯誤報告可以嵌入到解析器代碼。

對於簡單的任務（如將中綴表達式轉換爲後綴表達式），它們可以用於通過語法指導的定義或轉換方案進行語法指導的轉換。

這裏的一個分析樹的用於表達9 - 5 + 2的圖形表示（注意在樹的端子和從表達式串的實際的符號的位置）：

enter image description here

抽象語法樹

AST表示一些代碼的句法結構。編程樹的結構，如表達式，流控制語句等 - 分組成運算符（內部節點）和操作數（葉）。例如，表達式i + 9的語法樹將以運算符+爲根，變量i作爲操作員的左孩子，編號9作爲右孩子。

這裏的區別在於非終端和終端不起作用，因爲AST不處理語法和字符串生成，而是編程構造，因此它們表示這些構造之間的關係，而不是它們的方式由語法生成。

請注意，操作符本身是給定語言的程序設計結構，並不一定是實際的計算操作符（如+就是）：for循環也將以這種方式處理。例如，可以有一個語法樹，如for [ expr, expr, expr, stmnt ]（內聯），其中for是運算符，方括號內的元素是它的子元素（表示C的for語法） - 也由操作員等組成。

AST通常由語法分析（解析）階段的編譯器生成，稍後用於語義分析，中間表示，代碼生成等。

下面是一個AST的圖形表示：

來源

2014-10-12 22:23:53 corazza

我希望你的答案是可以接受的。它更詳細，更好地解釋。 – Salil 2017-09-05 04:00:26

@Salil謝謝！:)我在博客上也寫過關於這些內容的內容：http://flowing.systems/tag/mcd – corazza 2017-09-05 12:56:51

我發現這個在網絡上，也許有幫助：

解析樹是規則（和令牌）的紀錄用於匹配一些輸入文本，而語法樹記錄輸入的結構，並且對產生它的文法不敏感。請注意，對於任何單一語言都是無限數量的語法，因此對於給定的輸入句子，每個語法都會導致不同的語法樹形式，因爲所有不同的中間規則都是如此。一個抽象語法樹是一個非常優越的中間形式，正是因爲這種不敏感性，並且因爲它強調了語言而不是語法的結構。

來源

2015-01-30 13:51:53 Khatri

解析樹和抽象語法樹有什麼區別？

回答

解析樹

抽象語法樹

相關問題