編譯原理 2016小測(cè)驗(yàn)2-解析

1、2016年 編譯原理小測(cè)驗(yàn)（2）之解析1. 文法 G1 的開(kāi)始符號(hào)是 ，非終結(jié)符包括 ，終結(jié)符包括 。 該文法表明運(yùn)算=比+的優(yōu)先級(jí) ，M M + A | AA V = A | V (G1)V x | y | z 運(yùn)算=的結(jié)合性是 結(jié)合的。答： M M, A, V +, =, x, y, z 高 右。解析：本題考察的第一個(gè)知識(shí)點(diǎn)：上下文無(wú)關(guān)文法（CFG）的基本概念。在任何正確的CFG定義中，只有非終結(jié)符才需要、必須用產(chǎn)生式來(lái)定義其所代表的語(yǔ)法結(jié)構(gòu)，所以可按以下規(guī)律來(lái)判別文法的終結(jié)符和非終結(jié)符：(1) 非終結(jié)符絕對(duì)會(huì)出現(xiàn)在產(chǎn)生式左邊：因此，上述文法G1的非終結(jié)符包括 M, A, V 。(2) 終

2、結(jié)符只能出現(xiàn)在產(chǎn)生式右邊（絕不會(huì)出現(xiàn)在產(chǎn)生式左邊）。還有一個(gè)約定：第一個(gè)產(chǎn)生式左部非終結(jié)符就是文法開(kāi)始符號(hào)。本題考察的第二個(gè)知識(shí)點(diǎn)：文法符號(hào)（只考慮終結(jié)符）的優(yōu)先級(jí)。在學(xué)習(xí)消除文法二義性的第一種方法時(shí)曾提到：“越接近文法開(kāi)始符號(hào)S的文法符號(hào)的優(yōu)先級(jí)越低”。這個(gè)陳述中涉及一個(gè)基礎(chǔ)性概念：某文法符號(hào) X 與開(kāi)始符號(hào) S 的距離。該距離指：從S推導(dǎo)出包含 X 的文法符號(hào)序列所需的最少直接推導(dǎo)步驟數(shù)。如文法G1中，M 與 開(kāi)始符號(hào)M 的距離為0，因?yàn)?M 可推導(dǎo)出其自身；+ 與 M 的距離為1，因?yàn)?M => M+A，需要最少一步直接推導(dǎo)；= 與 M 的距離為2，因?yàn)?M => A =&g

3、t; V=A，需要最少兩步直接推導(dǎo)；因此，文法表明了 = 的優(yōu)先級(jí)高于 +。本題考察的第三個(gè)知識(shí)點(diǎn)：文法符號(hào)（只考慮終結(jié)符）的結(jié)合性。在學(xué)習(xí)消除文法二義性的第一種方法時(shí)曾提到：“對(duì)于AA，其右部中，若A在終結(jié)符a左邊出現(xiàn)（即中包含a），則終結(jié)符a具有左結(jié)合性質(zhì)；”。這句話除了強(qiáng)調(diào)“結(jié)合性”必須通過(guò)“遞歸定義非終結(jié)符A”之外，還強(qiáng)調(diào) a 和 A在產(chǎn)生式右部中的相對(duì)位置。為便于理解，可將A的產(chǎn)生式簡(jiǎn)單地寫成兩種情況：Case 1： A à A a ，且 a 右邊無(wú) A該產(chǎn)生式表明終結(jié)符 a 是左結(jié)合的，如課堂例子中 E à E + T；Case 2： A à a A

4、，且 a 左邊無(wú) A該產(chǎn)生式表明終結(jié)符 a 是右結(jié)合的，如課堂例子中 F à - F；不滿足上述任何條件者，則表明不了a的結(jié)合性，或者表明 a 無(wú)結(jié)合性，如 A à a A a A à A a A 等。2. 對(duì)于文法 G1 產(chǎn)生的句子 z + x = y ，畫(huà)出該句子的 (a) 分析樹(shù)、 (b)語(yǔ)法樹(shù)。M M + A | AA V = A | V (G1)V x | y | z解析： 本題考察推導(dǎo)、兩種樹(shù)的基本概念。（即使你不知道 + 和 = 的優(yōu)先級(jí)、結(jié)合性，也不影響本題的解答，除非你連樹(shù)的概念都不知道或未理解）分析樹(shù)：可（用構(gòu)造過(guò)程）直觀地表示推導(dǎo)過(guò)程，也可（

5、用樹(shù)形）表示句型結(jié)構(gòu)。本題給定句子的最右推導(dǎo)過(guò)程為：M => M + A => M + V=A => M+V= V => M+V= y => M+ x =y => A +x=y => V +x=y => z + x = y注：下滑線標(biāo)記了各右句型中將被展開(kāi)的非終結(jié)符，矩形邊框包圍了前一句型最右邊的非終結(jié)符被展開(kāi)的結(jié)果。據(jù)此，分析樹(shù)的構(gòu)造過(guò)程如下列各圖所示（注意句型與分析樹(shù)的對(duì)應(yīng)關(guān)系）。 也可用最左推導(dǎo)構(gòu)造分析樹(shù) 語(yǔ)法樹(shù)：可表示句子結(jié)構(gòu)，但表示不了推導(dǎo)過(guò)程。這類樹(shù)有多種構(gòu)造過(guò)程。無(wú)論如何構(gòu)造，牢記語(yǔ)法樹(shù)的根本：父節(jié)點(diǎn)表示運(yùn)算、兒子節(jié)點(diǎn)表示相應(yīng)的操作

6、數(shù)。構(gòu)造方法1：若你根據(jù)文法確定出了優(yōu)先級(jí)和結(jié)合性，則可據(jù)此 (遞歸地) 分解句子結(jié)構(gòu)。并將分解結(jié)果（直觀地）表示為語(yǔ)法樹(shù)即可。根據(jù)題目1的答案，文法G1表明了 = 的優(yōu)先級(jí)高于+，所以句子 z +x=y 的最后一個(gè)運(yùn)算是 +， 第一個(gè)運(yùn)算是 =，即整個(gè)句子結(jié)構(gòu)就是：z + (x=y)。這樣最終語(yǔ)法樹(shù)的樹(shù)根就是 +，其左孩子（操作數(shù)）就是z，右孩子（操作數(shù)）就是 x=y。構(gòu)造方法2： 觀察分析樹(shù)表示的句子結(jié)構(gòu)（因?yàn)閮煞N樹(shù)都表示了句子結(jié)構(gòu)，所以可采用“句子結(jié)構(gòu)”為橋梁）對(duì)于最終的分析樹(shù)，采用“從上往下”看 (第2層) ，可知句子整體結(jié)構(gòu)是二元加，這必然是句子中最后一個(gè)計(jì)算，所以語(yǔ)法樹(shù)的樹(shù)根用 +

7、 標(biāo)記，其操作數(shù)為：(a) 左操作數(shù)為 z（分析（子）樹(shù) M-A-V-z的葉子）;(b) 右操作數(shù)是一個(gè)賦值表達(dá)式，因此該子樹(shù)的樹(shù)根為 =，其操作數(shù)為：(I) 左操作樹(shù)為 x（分析樹(shù) V-x 的葉子）；(II) 右操作樹(shù)為 y（分析樹(shù) A-V-y 的葉子）綜上即可得到完整語(yǔ)法樹(shù)。構(gòu)造方法3：借助最終分析樹(shù)，執(zhí)行LR 分析的驅(qū)動(dòng)器算法，并且： “歸約”時(shí)，構(gòu)造產(chǎn)生式右部對(duì)應(yīng)的語(yǔ)法樹(shù)（子樹(shù)），須遵守操作符為父親節(jié)點(diǎn)，操作數(shù)為兒子節(jié)點(diǎn)?！揪唧w過(guò)程請(qǐng)閱讀P170171給出的樹(shù)的語(yǔ)法制導(dǎo)翻譯】如本題中的句子 z + x =y，其分析過(guò)程中的幾個(gè)格局之分析棧及樹(shù)節(jié)點(diǎn)如下：(a) 移進(jìn)z并歸約為M，移進(jìn) +

8、 x，x歸約為V，再移進(jìn) =y，y歸約為A之后的分析棧： (棧底) M + V = A (棧頂，下同)語(yǔ)法樹(shù)的節(jié)點(diǎn)：(z) (+) (x) (=) (y) 括弧表示節(jié)點(diǎn)或子樹(shù)，此時(shí)樹(shù)高均為1。(z歸約得到的) M 的屬性就是 z 對(duì)應(yīng)的語(yǔ)法樹(shù)節(jié)點(diǎn)，其他類似。 (b) V=A歸約為A后的分析棧： M + A語(yǔ)法樹(shù)的節(jié)點(diǎn)：(z) (+) ( (=) (x) (y) ) 此時(shí) (=) 為子樹(shù)的根，(x) 和 (y) 為其兒子(c) M+A歸約后的分析棧： M語(yǔ)法樹(shù)的節(jié)點(diǎn)：( (+) (z) ( (=) (x) (y) ) ) 此時(shí) (+) 為樹(shù)根，(z)為左兒子， (=)為右兒子實(shí)際上，利用擴(kuò)充了語(yǔ)

9、義分析的LR分析器的話，語(yǔ)法樹(shù)節(jié)點(diǎn)就是“語(yǔ)義”，用“屬性”表示，并存儲(chǔ)在語(yǔ)義棧中! 如右側(cè)三個(gè)圖所示。 解答：【根據(jù)題目陳述可知：解答中無(wú)需上述各步驟，只需給出最終的樹(shù)即可】 分析樹(shù) 語(yǔ)法樹(shù)3.右圖的分析樹(shù)使用了某文法 G2 的全部產(chǎn)生式， (a) 請(qǐng)寫出完整文法 G2（注意：D1 與 D2 對(duì)應(yīng)同一個(gè)文法符號(hào) D，其他類似）； (b) 寫出分析樹(shù)表示的句型； (c) 給出該句型的所有短語(yǔ)、直接短語(yǔ)、句柄； (d) G2 是否為 LL(1) 文法？請(qǐng)給出理由； (e) 若 G2 不是 LL(1) 文法，請(qǐng)給出等價(jià)的LL(1)文法。解析： 本題考察分析樹(shù)與文法的關(guān)系、短語(yǔ)（直接短語(yǔ)/句柄）、LL

10、(1)文法的概念。問(wèn)題(a): 根據(jù)分析樹(shù)的概念可知，只有父子關(guān)系（樹(shù)高為2）的任何一顆子分析樹(shù)，對(duì)應(yīng)一個(gè)產(chǎn)生式，且父節(jié)點(diǎn)就是產(chǎn)生式左部，其所有兒子節(jié)點(diǎn)從左到右依次排列就構(gòu)成了產(chǎn)生式右部。據(jù)此，對(duì)整個(gè)分析樹(shù)掃一遍，將每個(gè)樹(shù)高為2的子樹(shù)都寫成對(duì)應(yīng)的產(chǎn)生式，去掉重復(fù)的產(chǎn)生式，就可得到對(duì)應(yīng)的文法 G2 如下： S à a D B D à D d | dB à b B | b另外，題干中指明這個(gè)樹(shù)使用了G2的“全部”產(chǎn)生式，所以G2的全部產(chǎn)生式如上。注意：因?yàn)榭捎卯a(chǎn)生式集合表示CFG，所以非終結(jié)符集合、終結(jié)符集合、開(kāi)始符號(hào)無(wú)需另外專門指出。問(wèn)題(b):每一顆完整的分析樹(shù)均

11、對(duì)應(yīng)（表示）一個(gè)句型 及其結(jié)構(gòu)，其中：Ø （從上往下看）樹(shù)的形狀表示了結(jié)構(gòu)，Ø 所有葉子節(jié)點(diǎn)（從左到右依次寫出來(lái)）就是句型（的文法符號(hào)序列）。如果均為終結(jié)符，則該句型就是句子(如本題就是)。n 回憶 句型 的概念！所以這顆樹(shù)表示的句型為：addbb （攜帶下標(biāo) ad1d2b2b1也可）。有同學(xué)將句型寫成 ad*b*，ad+b+，此為何物 L，從何處來(lái)？問(wèn)題(c): 考察短語(yǔ)們?cè)诜治鰳?shù)上的表現(xiàn)形式。短語(yǔ)：以非終結(jié)符為根的某個(gè)子樹(shù)（含整顆樹(shù)）的所有葉子，從左到右依次寫出來(lái)所得的符號(hào)序列；觀察后，可找到的短語(yǔ)有：注意：短語(yǔ)不能寫成產(chǎn)生式ad1d2b2b1 相對(duì)于樹(shù)根S 的短語(yǔ)d1

12、 相對(duì)于D2 的短語(yǔ)d1d2 相對(duì)于 D1 的短語(yǔ)b2b1 相對(duì)于 B1 的短語(yǔ)b1 相對(duì)于 B2 的短語(yǔ)直接短語(yǔ)：所有短語(yǔ)中，位于分析樹(shù)末端、且只有父子關(guān)系的那些子樹(shù)（樹(shù)高為2）的所有葉子，從左到右依次寫出來(lái)所得的符號(hào)序列；觀察后，可找到上述短語(yǔ)中的直接短語(yǔ)有：d1 相對(duì)于產(chǎn)生式Dàd 的直接短語(yǔ)b1 相對(duì)于產(chǎn)生式 Bà b 的直接短語(yǔ)句柄：最左邊的直接短語(yǔ)，在樹(shù)上表現(xiàn)為 深度優(yōu)先遍歷過(guò)程中，第一個(gè)遇到的直接短語(yǔ)。 據(jù)此，句柄為 d1。應(yīng)注意的概念問(wèn)題：Ø 直接短語(yǔ) 一定 是短語(yǔ)， 但短語(yǔ) 不一定 是直接短語(yǔ)!Ø 句柄 一定 是直接短語(yǔ)，但直接短語(yǔ) 不

13、一定 是句柄!Ø 每個(gè)句型的句柄是唯一的，但直接短語(yǔ)、短語(yǔ)至少有一個(gè)!問(wèn)題(d)： 考察 LL(1)文法的定義和判別方法.判別方法1：構(gòu)造文法的預(yù)測(cè)分析表，看看是否存在多重定義（即填寫了兩個(gè)或以上的產(chǎn)生式右部）的條目（單元格）。* 這是基本方法，但必須構(gòu)造出預(yù)測(cè)分析表，計(jì)算量大，麻煩。判別方法2：根據(jù)推論3.2判斷，但只需考察那些有 兩個(gè) 或更多個(gè)候選項(xiàng)的產(chǎn)生式即可。若每個(gè)此類產(chǎn)生式均滿足推論3.2的三個(gè)條件，則文件是LL(1)的，否則不是。對(duì)于文法G2，D和B的產(chǎn)生式右部各存在2個(gè)候選項(xiàng)，先考察D的兩個(gè)候選項(xiàng)，存在以下兩個(gè)推導(dǎo)：D => Dd => dd （先用候選項(xiàng)1

14、推導(dǎo)，再用候選項(xiàng)2推導(dǎo)）D => d （用候選項(xiàng)2推導(dǎo)）二者都推導(dǎo)出了 d 開(kāi)始的序列，不滿足推論3.2的條件1。所以：G2不是LL(1)文法。提示1：既然已經(jīng)得出了結(jié)論，就無(wú)需再B的產(chǎn)生式推導(dǎo)+判斷了。提示2：推論3.2的前兩個(gè)條件的本質(zhì)：確定同一非終結(jié)符的任意兩個(gè)候選項(xiàng)的 First 集合是否相交？若相交，則文法不是LL(1)。判別方法3：還有幾類特殊文法，一定不是 LL(1) 文法，包括：Ø 二義文法Ø 有左遞歸的文法Ø 有左因子的文法考慮文法 G2 的 D 產(chǎn)生式右部，存在（直接）左遞歸，而B(niǎo)的產(chǎn)生式右部存在左因子，所以 G2 不是 LL(1) 文法

15、。自己思考：若一個(gè)文法不是二義的、沒(méi)有左遞歸、沒(méi)有左因子的話，它是LL(1)文法嗎？問(wèn)題(e)： 文法 G2 不是二義文法，所以改寫的內(nèi)容就是消除左遞歸、提取左因子。當(dāng)這兩種現(xiàn)象同時(shí)存在時(shí)，一般先消除左遞歸。當(dāng)然也可以先提取左因子，但所得文法（可能）會(huì)有不同，改寫過(guò)程也稍啰嗦。對(duì)于文法G2，消除 D 產(chǎn)生式中的直接左遞歸，提取B產(chǎn)生式的左因子，可得左下文法。該文法中，D、B的產(chǎn)生式也可以寫為右邊的形式。D的產(chǎn)生式也可寫成：D à d D D à D | S à a D BD à d DD à d D | B à b BB à

16、 B | B的產(chǎn)生式也可寫成：B à b B B à bB | 實(shí)際上，D描述的是“至少一個(gè)d構(gòu)成的d串”，B描述的是“至少一個(gè)b構(gòu)成的b串”，因此 D 和 B 的產(chǎn)生式形式一致，均有多種寫法。比如還可以寫成：D à dD | dB à bB | b【小測(cè)驗(yàn)的解析結(jié)束】【下面給出學(xué)習(xí)、做題過(guò)程中值得注意的若干問(wèn)題，務(wù)必關(guān)注并理解】附錄：一些值得注意的問(wèn)題/錯(cuò)誤Ø 表示推導(dǎo)的符號(hào) 是 =>，不是箭頭 ->Ø 分析樹(shù)/語(yǔ)法樹(shù)上的父子關(guān)系用線段連接，不是箭頭Ø 文法的開(kāi)始符號(hào)也是一個(gè)非終結(jié)符Ø 運(yùn)算符是終結(jié)符Ø 產(chǎn)生式右部的候選項(xiàng)之間的豎線不是文法符號(hào)Ø