1、語(yǔ)法分析樹(shù)語(yǔ)法分析樹(shù) 主講：李繼偉學(xué)號(hào)：2015112648指導(dǎo)老師：楊青老師什么是語(yǔ)法分析樹(shù)什么是語(yǔ)法分析樹(shù) 設(shè)G是一個(gè)上下文無(wú)關(guān)文法，字符wL(G)在G中可能有很多推導(dǎo)。例如：如果G是生成平衡括號(hào)語(yǔ)言的上下文無(wú)關(guān)文法，則字符串()()至少可以用兩個(gè)不同的推導(dǎo)從S得到：這兩個(gè)推導(dǎo)的過(guò)程中我們會(huì)發(fā)現(xiàn)這樣的特點(diǎn)： （1）使用的規(guī)則相同（2）在中間字符串使用的它們的地點(diǎn)也相同（3）唯一不同的區(qū)別是使用規(guī)則的次序兩個(gè)推導(dǎo)都可以用右邊圖來(lái)表示。語(yǔ)法分析樹(shù)的概念語(yǔ)法分析樹(shù)的概念（1）語(yǔ)法分析樹(shù)語(yǔ)法分析樹(shù)（如右圖）（2）圖中的點(diǎn)叫做頂點(diǎn)頂點(diǎn)。每一個(gè)頂點(diǎn)有一個(gè)標(biāo)記，標(biāo)記是V中的一個(gè)符號(hào)（3）最上面的頂點(diǎn)叫做

2、根根，最底層的頂點(diǎn)叫做樹(shù)葉樹(shù)葉。樹(shù)葉都標(biāo)記終點(diǎn)符終點(diǎn)符,也可能標(biāo)記空串e.（4）從左到右鏈接樹(shù)葉的標(biāo)記得到推導(dǎo)出來(lái)的終結(jié)符串，稱為語(yǔ)法分析樹(shù)的結(jié)果語(yǔ)法分析樹(shù)的結(jié)果語(yǔ)法分析樹(shù)語(yǔ)法分析樹(shù)的形式語(yǔ)法分析樹(shù)的形式對(duì)于任一上下文無(wú)關(guān)文法G=(V, ,R,S),定義它的語(yǔ)法分析樹(shù)及根，樹(shù)葉和結(jié)果如下：（1） . a對(duì)于每一個(gè)a,這是一個(gè)語(yǔ)法分析樹(shù)。它的唯一的一個(gè)頂點(diǎn)既是根也是樹(shù)葉，它的結(jié)果是a。（2）如果Ae是R中的一個(gè)規(guī)則，則是一顆語(yǔ)法分析樹(shù)。它的根是標(biāo)記A的頂點(diǎn)，它的唯一一片樹(shù)葉是標(biāo)記e的頂點(diǎn)，它的結(jié)果是e。（3）如果AA1An 是R的一個(gè)規(guī)則,是n課語(yǔ)法樹(shù)，它們的根分別標(biāo)記A1An ，結(jié)果分別為y1

3、 y2,這是n=1,則是一顆語(yǔ)法分析樹(shù)，它的根是標(biāo)記A的新節(jié)點(diǎn)，樹(shù)葉是構(gòu)成語(yǔ)法分析樹(shù)的所以樹(shù)葉，結(jié)果為y1 y2 。（4）除此之外沒(méi)有別的語(yǔ)法分析樹(shù)。例3.2.1：結(jié)果為id*(id+id)的語(yǔ)法分析樹(shù)推導(dǎo)直觀上直觀上，語(yǔ)法分析樹(shù)是表示L(G)中字符串的推導(dǎo)方法，它隱蔽了由于用不同的順序使用規(guī)則而造成的推導(dǎo)的人為差異。換句話說(shuō)，語(yǔ)法分析樹(shù)表示推導(dǎo)的等價(jià)類(lèi)推導(dǎo)的等價(jià)類(lèi)。例例3.2.2考慮生成所以平衡括號(hào)的字符串的文法G中下述三個(gè)推導(dǎo)D1.D2.D3有D1D2和D2 D3。但是，沒(méi)有D1D3，因?yàn)檫@兩個(gè)推導(dǎo)有一個(gè)以因?yàn)檫@兩個(gè)推導(dǎo)有一個(gè)以上的不同字符串上的不同字符串。注意，這三個(gè)推導(dǎo)的語(yǔ)法分析樹(shù)相同

4、語(yǔ)法分析樹(shù)相同（如圖）如果有序?qū)?D,D)屬于的自反對(duì)稱傳遞閉包自反對(duì)稱傳遞閉包，則稱這兩個(gè)推導(dǎo)D,D是相似相似的。自反相似傳遞閉包自反的對(duì)稱的傳遞的等價(jià)關(guān)系相似性換句話說(shuō)換句話說(shuō)，如果進(jìn)過(guò)一系列的變化，使用規(guī)則的次序能夠把兩個(gè)推導(dǎo)中的一個(gè)變成另一個(gè)，則這兩個(gè)推導(dǎo)是相似的，這樣的變換能夠把一個(gè)推導(dǎo)替換成一個(gè)先于它或它先于的推導(dǎo)。例：例：3.2.2(續(xù)續(xù)) 語(yǔ)法分析樹(shù)通過(guò)自然同態(tài)自然同態(tài)正好體現(xiàn)了上面定義的字符串推導(dǎo)之間的相似性的等價(jià)關(guān)系的等價(jià)類(lèi)相似性的等價(jià)關(guān)系的等價(jià)類(lèi)。所以以下推導(dǎo)：這十個(gè)推導(dǎo)之間的關(guān)系如圖：以上十個(gè)推導(dǎo)都是相似的。（1）非形式地）非形式地：它們表示在字符串的同樣位置應(yīng)用同樣的

5、規(guī)則，唯一的區(qū)別是區(qū)別是這些應(yīng)用的相對(duì)次序。（2）等價(jià)地：）等價(jià)地：重復(fù)使用或的逆可以把它們中的任一關(guān)聯(lián)到另一個(gè)。再?zèng)]有別的推導(dǎo)與它們相似。對(duì)比以下兩種：語(yǔ)法分析樹(shù)有何區(qū)別呢？不相似最左最左.右推導(dǎo)右推導(dǎo) 每一個(gè)在相似性下的等價(jià)類(lèi)，即每一棵語(yǔ)法分析樹(shù)，每一棵語(yǔ)法分析樹(shù)，有一個(gè)推導(dǎo)在下是極大的，極大的，即沒(méi)有先于它的其他推導(dǎo)沒(méi)有先于它的其他推導(dǎo)。這個(gè)推導(dǎo)叫做最左推導(dǎo)最左推導(dǎo)（1）最左推導(dǎo)最左推導(dǎo)：每一個(gè)語(yǔ)法分析樹(shù)中都有一個(gè)最左推導(dǎo)。它可以如下得到：從根的標(biāo)記A開(kāi)始，按照這棵語(yǔ)法分析樹(shù)提供的規(guī)則反復(fù)替換當(dāng)前字符串最左邊最左邊的非終結(jié)符。（2）最右推導(dǎo)：最右推導(dǎo)：不先于與任何其他推導(dǎo)的推導(dǎo)，不先于與

6、任何其他推導(dǎo)的推導(dǎo)，它是從語(yǔ)法分析樹(shù)經(jīng)過(guò)總是替換當(dāng)前字符串中的最右邊的非終結(jié)符得到。（3）每一個(gè)語(yǔ)法分析樹(shù)恰好有一個(gè)最左推導(dǎo)和一個(gè)最右推導(dǎo)，這是因?yàn)橐豢谜Z(yǔ)法分析樹(shù)的最左推導(dǎo)是唯一的每一步只有一個(gè)要替換的非終結(jié)符。即最左邊的終結(jié)符。例如：D1為最左推導(dǎo)，D10為最右推導(dǎo)定理定理3.2.1 設(shè)G=(V, ,R,S)是一個(gè)上下文無(wú)關(guān)文法，AV-及w*,則下述命題是等價(jià)的：（a）Aw（b）有一棵根為A結(jié)果為w的語(yǔ)法分析樹(shù)。（c）有最左推導(dǎo)Aw（d）有最右推導(dǎo)AwL*R*歧義性歧義性 能夠生產(chǎn)有兩棵或兩棵以上不同語(yǔ)法分析樹(shù)的字符串的文法叫做歧義的。歧義的。消去歧義消去歧義 固有歧義固有歧義歧義性有兩個(gè)不同的左推導(dǎo)有兩個(gè)不同的右推導(dǎo)有兩棵不同的語(yǔ)法分析樹(shù)或A為起始符w為結(jié)果課后習(xí)題課后習(xí)題3.2.3習(xí)題習(xí)題3.2.3的推導(dǎo)過(guò)程：的推導(dǎo)過(guò)程：最左推導(dǎo)： 沒(méi)有先于它的其他推導(dǎo) EE+T E+id T+id T*F+id T*id+id F*id+id id*