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

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

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

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

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

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