語法樹

語法樹是句子結(jié)構(gòu)的圖形表示，它代表了句子的推導結(jié)果，有利于理解句子語法結(jié)構(gòu)的層次。簡單說，語法樹就是按照某一規(guī)則進行推導時所形成的樹。
中文名 語法樹 外文名 Parse Tree 文 ? ?法 G=(Vn,Vt,P,S) 性 ? ?質(zhì) 計算機語言 釋 ? ?義 一個句型的所有可能的推導過程
目錄
1 簡介
2 詳細信息
簡介
給定文法G=(Vn,Vt,P,S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導樹)。樹中的每一個節(jié)點都有一個標記，此標記是V= Vn∪Vt中的一個符號。語法樹是句子結(jié)構(gòu)的圖形表示，它代表了句子的推導結(jié)果，有利于理解句子語法結(jié)構(gòu)的層次。簡單說，語法樹就是按照某一規(guī)則進行推導時所形成的樹。
對應(yīng)關(guān)系
對應(yīng)關(guān)系
一棵語法樹包括了一個句型的所有可能的推導過程。
詳細信息
這個語法樹滿足：
(1) 樹中每一個結(jié)點都有一個標記，此標記是V= VN∪VT中的一個符號。
(2) 根的標記是S。
(3) 若樹的一結(jié)點A至少有一個子女，則A∈VN。
(4) 如結(jié)點A的子女結(jié)點從左到右次序為B1，B2...Bn，則必有產(chǎn)生式A→B1B2...Bn。
例：G[S]： S→aAS | a
A→SbA |SS |ba
對句型aabbaa的推導過程可表示為下圖所示語法樹。
語法樹
語法樹
下面兩個推導過程均可由右圖表示。
(1) SÞaASÞaSbASÞaabASÞaabbaSÞaabbaa
(2) SÞaASÞaAaÞaSbAaÞaSbbaaÞaabbaa
這說明同一語法樹可以表示對同一句型不同的推導過程。
========

編譯原理學習周入門教程--（5）上下文無關(guān)文法，及其語法樹

?
? ? ? ? ?首先我們回顧一下上篇的內(nèi)容，上篇講述了四種類型的文法，0型1型2型3型，他們要求的規(guī)則越來越嚴格。
?
? ? ? ? ?開始教程：
?
? ? ? ? ?本篇著重講解上下文無關(guān)文法及其語法樹，因為對于計算機程序來講，上下文無關(guān)文法表達能力足夠強，來表達大多數(shù)程序語言的語法。
?
? ? ? ? ?描述一種上下文無關(guān)的推導工具：句型的推導和語法樹（推導樹）
?
? ? ? ? ? 給定文法G（VN,VT,P ,S）,對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹滿足下面四個條件：
?
? ? ? ? ? ?① 每個結(jié)點都有一個標記，此標記是V的 一個符號。（說的是節(jié)點一定是終結(jié)符或非終結(jié)符）


? ? ? ? ? ?② 根的標記是S。（說的是樹根的標記是開始符號S）


? ? ? ? ? ?③ 若一結(jié)點標記A,至少有一個從它出發(fā)的分枝，則A肯定在VN中（說的是如果一個節(jié)點有分支的話，這個節(jié)點一定是非終結(jié)符）


? ? ? ? ? ?④ 如果標記為A，有n個從它出發(fā)的分枝，并且這些分枝的結(jié)點的標記（從左到右）為B1, B2，…，Bn，那么A→B1B2，…，Bn一定是P中的一個產(chǎn)生式。（說的是從A出發(fā)的葉子節(jié)點從左到右排列，一定是P中規(guī)則的一個產(chǎn)生式）
?
? ? ? ? ?例1: 文法G[S]:


? ? ? ? ? S→aAS
? ? ? ? ? A→SbA
? ? ? ? ? A→SS
? ? ? ? ? S→a
? ? ? ? ? A→ba


　　寫出aabbaa句型的推導過程：
　　（１）Ｓ＝＞aAS=>aAa=>aSbAa=>aSbbaa=>aabbaa(最右推導）（最右推導，就是從最右側(cè)的非終結(jié)符開始）
　　（２）Ｓ＝＞aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa(最左推導）（最左推導，就是從最左側(cè)的非終結(jié)符開始） ? ? ? ?


? ? ? ? ? 例2： G[E]： ? ? ? ?E→E+T|T
? ? ? ? ? ? ? ? ? ? ? T→T*F|F
? ? ? ? ? ? ? ? ? ? ? F→(E)|a
? ? ? ? ? ? ? ? ? ? ? 判斷a+a*a ? ? ? ? 是否是合法的句子,采用最左推導和最右推導
?
　　　　Ｅ＝＞Ｅ＋Ｔ＝＞Ｔ＋Ｔ＝＞Ｆ＋Ｔ＝＞a＋Ｔ＝＞a+Ｔ*Ｆ
? ? ? ? ? ? ? ? ?＝＞a＋Ｆ＊Ｆ＝＞a＋a＊Ｆ=>a＋a*a(最左推導）
?
　　　　Ｅ＝＞Ｅ+Ｔ＝＞Ｅ＋Ｔ＊Ｆ＝＞Ｅ＋Ｔ＊a＝＞Ｅ＋Ｆ＊a
? ? ? ? ? ? ? ? ?=>Ｅ＋a*a＝＞Ｔ＋a*a＝＞Ｆ＋a*a＝＞a+a*a(最右推導）
?
? ? ? ? ? ? ? ?書上規(guī)定，最右推導又稱為規(guī)范推導，規(guī)范推導推導出的句型又稱為規(guī)范句型。
?
? ? ? ? ? ? ? ?構(gòu)造上述句型的語法樹：
?
? ? ? ? ? ? ? ? 畫出a+a*a句型的語法樹 ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? E→E+T|T?
? ? ? ? ? ? ? ? ? T→T*F|F
? ? ? ? ? ? ? ? ? F→(E)|a ? ? ? ? ? ? ? ??
?
? ? ? ? ? ? ? ? 注:上面的例子來自網(wǎng)絡(luò)。
?
? ? ? ? 而一個語法樹可以表示可能的不同推導過程，包括最右推導和最左推導。但是一個句型是否對應(yīng)唯一的一顆語法樹呢？一個句型是否只有唯一的一個最左推導（最右推導）？答案是否定的，下面我們講述二義文法。
?
? ? ? ? ? ? ? ? 看看下面的文法推導樹： ? ? ? ? ? ? ? ??
?
? ? ? ? ? ? ? ? ? ? ? 二義文法的定義：
?
? ? ? ? ? ? ? ? ? ? ? 若一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的，或一個文法有兩個不同的最左推導，則稱這個文法是二義的。
?
? ? ? ? ? ? ? ? ? ? ?當然我們不希望程序的某些文法是二義的，希望對程序的每個句子的分析是唯一的。
??
本篇到此結(jié)束，下篇講述句型的簡單分析。
========

Redy語法分析－－抽象語法樹簡介

抽象語法樹簡介


(一)簡介


抽象語法樹（abstract syntax code，AST）是源代碼的抽象語法結(jié)構(gòu)的樹狀表示，樹上的每個節(jié)點都表示源代碼中的一種結(jié)構(gòu)，這所以說是抽象的，是因為抽象語法樹并不會表示出真實語法出現(xiàn)的每一個細節(jié)，比如說，嵌套括號被隱含在樹的結(jié)構(gòu)中，并沒有以節(jié)點的形式呈現(xiàn)。抽象語法樹并不依賴于源語言的語法，也就是說語法分析階段所采用的上下文無文文法，因為在寫文法時，經(jīng)常會對文法進行等價的轉(zhuǎn)換（消除左遞歸，回溯，二義性等），這樣會給文法分析引入一些多余的成分，對后續(xù)階段造成不利影響，甚至會使合個階段變得混亂。因些，很多編譯器經(jīng)常要獨立地構(gòu)造語法分析樹，為前端，后端建立一個清晰的接口。


抽象語法樹在很多領(lǐng)域有廣泛的應(yīng)用，比如瀏覽器，智能編輯器，編譯器。


(二)抽象語法樹實例


(1)四則運算表達式


表達式: 1+3*(4-1)+2


抽象語法樹為：


(2)xml


代碼2.1：


<letter>
? <address>
? ? <city>ShiChuang</city>
? </address>
? <people>
? ? <id>12478</id>
? ? <name>Nosic</name>
? </people>
</letter>
抽象語法樹


(3)程序1


代碼2.2


while b != 0
{
? ? if a > b
? ? ? ? a = a-b
? ? else
? ? ? ? b = b-a
}
return a
抽象語法樹


(4)程序2


代碼2.3


sum=0
for i in range(0,100)
? ? sum=sum+i
end
抽象語法樹


(三)為什么需要抽象語法樹


當在源程序語法分析工作時，是在相應(yīng)程序設(shè)計語言的語法規(guī)則指導下進行的。語法規(guī)則描述了該語言的各種語法成分的組成結(jié)構(gòu)，通常可以用所謂的前后文無關(guān)文法或與之等價的Backus-Naur范式(BNF)將一個程序設(shè)計語言的語法規(guī)則確切的描述出來。前后文無關(guān)文法有分為這么幾類：LL(1)，LR(0)，LR(1)， LR(k) ,LALR(1)等。每一種文法都有不同的要求，如LL(1)要求文法無二義性和不存在左遞歸。當把一個文法改為LL(1)文法時，需要引入一些隔外的文法符號與產(chǎn)生式。


例如，四則運算表達式的文法為：


文法1.1


E->T|EAT
T->F|TMF
F->(E)|i
A->+|-
M->*|/
改為LL(1)后為：


文法1.2


E->TE'
E'->ATE'|e_symbol
T->FT'
T'->MFT'|e_symbol
F->(E)|i
A->+|-
M->*|/
例如，當在開發(fā)語言時，可能在開始的時候，選擇LL(1)文法來描述語言的語法規(guī)則，編譯器前端生成LL(1)語法樹，編譯器后端對LL(1)語法樹進行處理，生成字節(jié)碼或者是匯編代碼。但是隨著工程的開發(fā)，在語言中加入了更多的特性，用LL(1)文法描述時，感覺限制很大，并且編寫文法時很吃力，所以這個時候決定采用LR(1)文法來描述語言的語法規(guī)則，把編譯器前端改生成LR(1)語法樹，但在這個時候，你會發(fā)現(xiàn)很糟糕，因為以前編譯器后端是對LL(1)語樹進行處理，不得不同時也修改后端的代碼。


抽象語法樹的第一個特點為:不依賴于具體的文法。無論是LL(1)文法，還是LR(1)，或者還是其它的方法，都要求在語法分析時候，構(gòu)造出相同的語法樹，這樣可以給編譯器后端提供了清晰，統(tǒng)一的接口。即使是前端采用了不同的文法，都只需要改變前端代碼，而不用連累到后端。即減少了工作量，也提高的編譯器的可維護性。


抽象語法樹的第二個特點為:不依賴于語言的細節(jié)。在編譯器家族中，大名鼎鼎的gcc算得上是一個老大哥了，它可以編譯多種語言，例如c，c＋＋，java，ADA，Object C， FORTRAN， PASCAL， COBOL等等。在前端gcc對不同的語言進行詞法，語法分析和語義分析后，產(chǎn)生抽象語法樹形成中間代碼作為輸出，供后端處理。要做到這一點，就必須在構(gòu)造語法樹時，不依賴于語言的細節(jié)，例如在不同的語言中，類似于if－condition－then這樣的語句有不同的表示方法


在c中為：


if(condition)
{
? ? do_something();
}
? ? ?在fortran中為：


If condition then
? ? do_somthing()
end if
在構(gòu)造if－condition－then語句的抽象語法樹時，只需要用兩個分支節(jié)點來表于，一個為condition，一個為if_body。如下圖：


在源程序中出現(xiàn)的括號，或者是關(guān)鍵字，都會被丟掉。
========

總結(jié)

以上是生活随笔為你收集整理的语法树学习总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。