【7A文】上下文無關(guān)文法及其語法樹.ppt

《【7A文】上下文無關(guān)文法及其語法樹.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、軟件教研室　徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載上下文無關(guān)文法及其語法樹文法和語言一、語法樹（推導(dǎo)樹）直觀定義：用圖表示上下文無關(guān)文法句型的推導(dǎo)的直觀方法。語法樹有助于理解一個句子的語法層結(jié)構(gòu)的層次，語法樹通常表示成一棵倒立的樹，根在上，枝葉在下。2.形式定義對文法G=(VN,VT,P,S)相關(guān)聯(lián)的語法樹滿足以下4個條件：（1）根結(jié)點由開始符號S所標(biāo)記；（2）每個結(jié)點都有一個標(biāo)記，此標(biāo)記是V(即VN∪VT)的一個符號；（3）非終結(jié)符VN中的結(jié)點至少有一個除它自己以外的子孫結(jié)點；（4）對產(chǎn)生式A

2、→A1A2…Ak，結(jié)點A1,A2,…,Ak是結(jié)點A的直接子孫，順序與產(chǎn)生式相同。軟件教研室　徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載從根結(jié)點S開始推導(dǎo)，當(dāng)非終結(jié)符被它的某個候選式所替換時，這個非終結(jié)符的相應(yīng)結(jié)就產(chǎn)生出下一代新結(jié)，候選式中自左向右的每個符號對應(yīng)一個新結(jié)，并用這些符號標(biāo)記其相應(yīng)的新結(jié)。每個新結(jié)與其父結(jié)點間都有一條連線。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的端末結(jié)自左向右排列起來就是一個句型。語法樹構(gòu)造的過程例1文法G=({E},{+,*,i,(,)},P,E)，其中P為：

3、E→E+E

4、E*E

5、(E)

6、i對該文法關(guān)于(i*i+i)的推導(dǎo)的語法樹如下所示：文法和語言軟件教研室　徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載接語法樹構(gòu)造舉例文法和語言E(根)（E）E++EE*Eiii代次12345軟件教研室　徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載文法和語言語法樹的問題分析（1）允許產(chǎn)生同名結(jié)點（反映遞歸性）；（2）沒有后代的結(jié)點為端末結(jié)；（3）語法樹不能反映生養(yǎng)后代的先后；（4）一棵語法樹表示了一個句型種種可能的（但未必是所有的）不同推導(dǎo)過程。軟件教研室　

7、徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載文法和語言最左推導(dǎo)/最右推導(dǎo)/規(guī)范句型最左推導(dǎo)是指：任何一步α=>β都是對α中的最左非終結(jié)符進(jìn)行替換。同樣，可定義最右推導(dǎo)（又稱規(guī)范推導(dǎo)）：任何一步α=>β都是對α中的最右非終結(jié)符進(jìn)行替換。由規(guī)范推導(dǎo)所得到的句型稱為規(guī)范句型。注意：從一個句型到另一個句型的推導(dǎo)過程往往是不唯一的。例如E+E(i+i)：（a）E+E=>E+i=>i+i——最右推導(dǎo)（b）E+E=>i+E=>i+i——最左推導(dǎo)軟件教研室　徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載

8、語法樹的特點文法和語言一棵語法樹是這些不同推導(dǎo)過程的共性抽象，是它們的代表。一棵語法樹完全等價于一個最左（右）推導(dǎo)，這種等價性包括樹的步步生長和推導(dǎo)的步步展開是完全一致的。例:推導(dǎo)(i*i+i)最左推導(dǎo)：E=>(E)=>(E+E)=>(E*E+E)=>(i*E+E)=>(i*i+E)=>(i*i+i)最右推導(dǎo)：E=>(E)=>(E+E)=>(E+i)=>(E*E+i)=>(E*i+i)=>(i*i+i)但兩種推導(dǎo)的語法樹相同。軟件教研室　徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載文法和語言一個句型是

9、否只對應(yīng)唯一的一棵語法樹？例如對于文法G[E]：E→E+E

10、E*E

11、(E)

12、i，關(guān)于(i*i+i)存在一個與前面不同的最左推導(dǎo)：E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)它所對應(yīng)的語法樹如右圖：E(根)（E）E*EE+Eiii軟件教研室　徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載文法和語言1.定義：一個文法的某個句子對應(yīng)兩棵不同的語法樹，則這個文法是二義的。或一個文法的某個句子有兩個不同的最左（右）推導(dǎo)，則這個文法是二義的。二、二義性(1/2)2.區(qū)別文法的二義性：存在兩

13、個不同文法G(二義)、G’(無二義)，卻有L(G)=L(G’)，即產(chǎn)生語言相同。語言的二義性軟件教研室　徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載二義性其它問題文法和語言人們已證明，二義性問題是不可判定的，即不存在一個算法，它能在有限步驟內(nèi)，確切地判斷一個文法是否是二義的。我們所能做的就是為無二義性尋找一些充分條件，例如對文法G[E]：E→E+E

14、E*E

15、(E)

16、i修改，規(guī)定運算符“+”與“*”的優(yōu)先關(guān)系和結(jié)合規(guī)則，設(shè)“*”的優(yōu)先性高于“+”，且服從左結(jié)合。G’:E→T

17、E+TT→F

18、T*FF→(E

19、)

20、i軟件教研室　徐慧英　呂振洪來自www.3722.cn中國最大的資料庫下載文法和語言3.6句型的分析句型分析的任務(wù)就是按文法的產(chǎn)生式，識別輸入的符號是否是該文法的句型。語法樹——是句型推導(dǎo)過程的幾何表示，可以十分直觀的顯示某句型的結(jié)構(gòu)。因此在句型時，對輸入符號串構(gòu)造語法樹，以此識別它是否是該文法的一個句型（或句子）。因此，語法樹又可稱為語法