blocks|key|998855|text|据我所知，AST更侧重于源代码组件之间的抽象关系，而解析树侧重于语言所使用的语法的实际实现，包括挑剔的细节。它们肯定是不同的，因为“解析树”的另一个术语是“具体语法树”。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|998856|我找到了这个page，它试图解决这个问题。|offset|length|998857|entityMap|0|LINK|mutability|MUTABLE|url|http://www.jguru.com/faq/view.jsp?EID=814505^0|0|6|4|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

From what I understand, the AST focuses more on the abstract relationships between the components of source code, while the parse tree focuses on the actual implementation of the grammar utilized by the language, including the nitpicky details. They are definitely not the same, since another term for "parse tree" is "concrete syntax tree".

I found this <a href="http://www.jguru.com/faq/view.jsp?EID=814505" rel="nofollow noreferrer">page</a> which attempts to resolve this exact question.

blocks|key|998938|text|马丁·福勒的DSL+book很好地解释了这一点。AST只包含用于进一步处理的所有“有用”元素，而解析树包含所有工件(空格、方括号等)。从您解析的原始文档|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|998939|entityMap|0|LINK|mutability|MUTABLE|url|https://martinfowler.com/books/dsl.html^0|6|8|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

The <a href="https://martinfowler.com/books/dsl.html" rel="nofollow noreferrer">DSL book</a> from Martin Fowler explains this nicely. The AST only contains all 'useful' elements that will be used for further processing, while the parse tree contains all the artifacts (spaces, brackets, ...) from the original document you parse

blocks|key|784814|text|这是基于Terrence的Expression+Evaluator语法的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|784815|此示例的语法如下：|784816|grammar+Expr002;

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

prog++++:+++(+stat+)%2B+;

stat++++:+++expr+NEWLINE++++++++->+expr
++++++++%7C+++ID+'='+expr+NEWLINE+->+%5E('='+ID+expr)
++++++++%7C+++NEWLINE+++++++++++++->
++++++++;

expr++++:+++multExpr+((+'%2B'%5E+%7C+'-'%5E+)+multExpr)*
++++++++;+

multExpr
++++++++:+++atom+('*'%5E+atom)*
++++++++;+

atom++++:+++INT+
++++++++%7C+++ID
++++++++%7C+++'('!+expr+')'!
++++++++;

ID++++++:+('a'..'z'+%7C+'A'..'Z'+)%2B+;
INT+++++:+'0'..'9'%2B+;
NEWLINE+:+'\r'?+'\n'+;
WS++++++:+(+'+'+%7C+'\t'+)%2B+{+skip();+}+;|code-block|syntax|javascript|784817|输入|784818|x=1
y=2
3*(x%2By)|784819|解析树|784820|解析树是输入的具体表示。解析树保留了输入的所有信息。空框表示空格，即行尾。|784821|​|784822|📷|atomic|784823|784824|天冬氨酸|784825|AST是输入的抽象表示。请注意，在AST中不存在父项，因为可以从树结构派生关联。|784826|784827|784828|784829|有关更详细的解释，请参阅Compilers+and+Compiler+Generators+pg。23|784830|或者pg上的Abstract+Syntax+Trees。在Syntax+and+Semantics+of+Programming+Languages中为21|784831|entityMap|0|LINK|mutability|MUTABLE|url|http://www.antlr3.org/works/help/tutorial/calculator.html|1|IMAGE|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/535e1a199e20033c08d67be41f3628fb.png|imageAlt|2|https://ask.qcloudimg.com/http-save/yehe-900000/2698576b8e1b4e88d7237560285efbb8.png|3|http://www.cs.ru.ac.za/compilers/pdfvers.pdf|4|http://homepage.divms.uiowa.edu/~slonnegr/plf/Book/Chapter1.pdf|5|http://homepage.divms.uiowa.edu/~slonnegr/plf/Book/^0|D|K|0|0|0|0|0|0|0|0|0|0|1|1|0|0|0|0|0|0|1|2|0|0|C|X|3|0|6|L|4|T|19|5|0^^$0|@$1|2|3|4|5|6|7|1V|8|@]|9|@$A|1W|B|1X|1|1Y]]|C|$]]|$1|D|3|E|5|6|7|1Z|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|20|8|@]|9|@]|C|$I|J]]|$1|K|3|L|5|6|7|21|8|@]|9|@]|C|$]]|$1|M|3|N|5|H|7|22|8|@]|9|@]|C|$I|J]]|$1|O|3|P|5|6|7|23|8|@]|9|@]|C|$]]|$1|Q|3|R|5|6|7|24|8|@]|9|@]|C|$]]|$1|S|3|T|5|6|7|25|8|@]|9|@]|C|$]]|$1|U|3|V|5|W|7|26|8|@]|9|@$A|27|B|28|1|29]]|C|$]]|$1|X|3|T|5|6|7|2A|8|@]|9|@]|C|$]]|$1|Y|3|Z|5|6|7|2B|8|@]|9|@]|C|$]]|$1|10|3|11|5|6|7|2C|8|@]|9|@]|C|$]]|$1|12|3|T|5|6|7|2D|8|@]|9|@]|C|$]]|$1|13|3|V|5|W|7|2E|8|@]|9|@$A|2F|B|2G|1|2H]]|C|$]]|$1|14|3|T|5|6|7|2I|8|@]|9|@]|C|$]]|$1|15|3|16|5|6|7|2J|8|@]|9|@$A|2K|B|2L|1|2M]]|C|$]]|$1|17|3|18|5|6|7|2N|8|@]|9|@$A|2O|B|2P|1|2Q]|$A|2R|B|2S|1|2T]]|C|$]]|$1|19|3|-4|5|6|7|2U|8|@]|9|@]|C|$]]]|1A|$1B|$5|1C|1D|1E|C|$1F|1G]]|1H|$5|1I|1D|1J|C|$1K|1L|1M|-4]]|1N|$5|1I|1D|1J|C|$1K|1O|1M|-4]]|1P|$5|1C|1D|1E|C|$1F|1Q]]|1R|$5|1C|1D|1E|C|$1F|1S]]|1T|$5|1C|1D|1E|C|$1F|1U]]]]

This is based on the <a href="http://www.antlr3.org/works/help/tutorial/calculator.html" rel="noreferrer">Expression Evaluator</a> grammar by Terrence Parr.

The grammar for this example:

<pre><code>grammar Expr002;

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

prog : ( stat )+ ;

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

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

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

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

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

Input

<pre><code>x=1
y=2
3*(x+y)
</code></pre>

Parse Tree

The parse tree is a concrete representation of the input. The parse tree retains all of the information of the input. The empty boxes represent whitespace, i.e. end of line.

<img src="https://i.stack.imgur.com/SyonV.png" alt="Parse Tree">

AST

The AST is an abstract representation of the input. Notice that parens are not present in the AST because the associations are derivable from the tree structure. 

<img src="https://i.stack.imgur.com/dhd3v.png" alt="AST">

For a more through explanation see <a href="http://www.cs.ru.ac.za/compilers/pdfvers.pdf" rel="noreferrer">Compilers and Compiler Generators</a> pg. 23 
or <a href="http://homepage.divms.uiowa.edu/~slonnegr/plf/Book/Chapter1.pdf" rel="noreferrer">Abstract Syntax Trees</a> on pg. 21 in <a href="http://homepage.divms.uiowa.edu/~slonnegr/plf/Book/" rel="noreferrer">Syntax and Semantics of Programming Languages</a>

blocks|key|999161|text|在解析树中，内部节点是非终结点，叶是终结点。在语法树中，内部节点是运算符，叶是操作数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|999162|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In parse tree interior nodes are non terminal, leaves are terminal.
In syntax tree interior nodes are operator, leaves are operands.

blocks|key|784968|text|以pascal赋值Age:=+42为例；|type|unstyled|depth|inlineStyleRanges|entityRanges|data|784969|语法树看起来就像源代码一样。下面我用括号将节点括起来。Age42|784970|一棵抽象的树应该看起来像这样=42|784971|赋值将成为一个包含2个元素的节点:+Age和42。这个想法是你可以执行赋值。|784972|还要注意的是，pascal语法消失了。因此，可以让多个语言生成相同的AST。这对于跨语言脚本引擎很有用。|784973|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

Take the pascal assignment
Age:= 42;

The syntax tree would look just like the source code. Below I am putting brackets around the nodes.
[Age][:=][42][;]

An abstract tree would look like this
[=][Age][42]

The assignment becomes a node with 2 elements, Age and 42. The idea is that you can execute the assignment.

Also note that the pascal syntax disappears. Thus it is possible to have more than one language generate the same AST. This is useful for cross language script engines.

Are they generated by different phases of a compiling process? Or are they just different names for the same thing?

What's the difference between parse trees and abstract syntax trees (ASTs)?

它们是由编译过程的不同阶段生成的吗？或者它们只是同一个东西的不同名称？

问语法分析树和抽象语法树(AST)有什么不同？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问语法分析树和抽象语法树(AST)有什么不同？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问语法分析树和抽象语法树(AST)有什么不同？
EN