第五章 語法分析 自下而上 4.0

1、第五章第五章 語法分析語法分析自下而上分析自下而上分析本章內(nèi)容本章內(nèi)容l自下而上分析基本問題自下而上分析基本問題l直觀算符優(yōu)先分析法直觀算符優(yōu)先分析法l算符優(yōu)先分析算符優(yōu)先分析l LRLR分析法分析法- 核心問題：句型分析核心問題：句型分析 對(duì)任意對(duì)任意上下文無關(guān)文法上下文無關(guān)文法G G = ( = (V V ，T T ，P P，S S ) ) 和任意和任意w w T T * *，是否有，是否有w w L(G)L(G)？ 若成立，若成立， 則給出分析樹或（最左）推導(dǎo)步驟；否則，則給出分析樹或（最左）推導(dǎo)步驟；否則， 進(jìn)行報(bào)錯(cuò)處理。進(jìn)行報(bào)錯(cuò)處理。 語法分析語法分析自下而上分析法自下而上分析法從輸

2、入串開始，逐步進(jìn)行從輸入串開始，逐步進(jìn)行“歸約歸約”，直至，直至歸約到文法的開始符號(hào)。歸約到文法的開始符號(hào)。例例5.1 5.1 文法文法G2:G2:S-aAcBe S-aAcBe （1 1） A-b A-b （2 2） A-Ab A-Ab （3 3） B-d B-d （4 4）輸入串：輸入串：abbcdeabbcdel abbcde abbcde 數(shù)目數(shù)目=3=3，選擇（，選擇（2 2）l aAbcde aAbcde 數(shù)目數(shù)目=3=3，選擇（，選擇（3 3）l aAcde aAcde 數(shù)目數(shù)目=1=1， 選擇（選擇（4 4）l aAcBe aAcBe 數(shù)目數(shù)目=1=1， 選擇（選擇（1 1）l

3、 S S 得解得解l abbcde abbcde 數(shù)目數(shù)目=3=3，選擇（，選擇（4 4）l abbcBe abbcBe 數(shù)目數(shù)目=2=2，選擇（，選擇（2 2）l abAcBe abAcBe 數(shù)目數(shù)目=1=1， 選擇（選擇（2 2）l aAAcBe aAAcBe 數(shù)目數(shù)目=0=0，失敗，失敗自下而上，進(jìn)行規(guī)約，自下而上，進(jìn)行規(guī)約，如何進(jìn)行？如何進(jìn)行？自左向右掃描初始串或句型，根據(jù)產(chǎn)生式找到能自左向右掃描初始串或句型，根據(jù)產(chǎn)生式找到能規(guī)約的規(guī)約的候選串候選串如果候選串如果候選串?dāng)?shù)目數(shù)目=0=0，無法規(guī)約，無法規(guī)約如果候選串如果候選串?dāng)?shù)目數(shù)目=1=1，進(jìn)行唯一規(guī)約，進(jìn)行唯一規(guī)約如果候選串如果候選

4、串?dāng)?shù)目數(shù)目11，且只有一個(gè)最左候選串，選擇該，且只有一個(gè)最左候選串，選擇該串進(jìn)行規(guī)約串進(jìn)行規(guī)約如果候選串如果候選串?dāng)?shù)目數(shù)目11，且有多個(gè)最左候選串，選擇較長，且有多個(gè)最左候選串，選擇較長串進(jìn)行規(guī)約串進(jìn)行規(guī)約一、自下而上分析基本問題一、自下而上分析基本問題1 1 、歸約、歸約利用棧，輸入符號(hào)移進(jìn)棧，當(dāng)棧頂形成利用棧，輸入符號(hào)移進(jìn)棧，當(dāng)棧頂形成P P的的候選式時(shí)，就歸約為它的左候選式時(shí)，就歸約為它的左P P符號(hào)符號(hào)例例5.1 5.1 文法文法G2:G2:S-aAcBe A-bS-aAcBe A-bA-Ab B-dA-Ab B-d輸入串：輸入串：abbcdeabbcde自下而上法，即自下而上法，即“

5、移進(jìn)移進(jìn)- -歸約歸約”法法最右推導(dǎo)：最右推導(dǎo)：a aa ab ba aA Aa aA Ab ba aA Aa aA Ac ca aA Ac cd da aA Ac cB Ba aA Ac cB Be eS S1 12 23 34 45 56 67 78 89 91010棧棧S S= aAc= aAcB Be e = aAc= aAcd de e =a=aAbAbcdecde= a b b c d e= a b b c d eS-aAcBeS-aAcBe輸入串：輸入串：abbcdeabbcdeA-AbA-AbB-dB-dA-bA-b注意注意b b及及AbAb都可以規(guī)約都可以規(guī)約SaAcBeAb

6、db分分 析析 樹樹最左歸約：最左歸約：= S= S= aAc= aAcB Be e= a= aA Acdecde= a= aA Abcdebcdea a b b b c d e b c d e S-aAcBeS-aAcBe輸入串：輸入串：abbcdeabbcdeA-AbA-AbB-dB-dA-bA-b- 從所要分析的終結(jié)符串開始從所要分析的終結(jié)符串開始進(jìn)行歸約；進(jìn)行歸約；- 每一步歸約每一步歸約是在當(dāng)前串中找到與某個(gè)產(chǎn)生式的右部相是在當(dāng)前串中找到與某個(gè)產(chǎn)生式的右部相匹配的子串，然后將該子串用這一產(chǎn)生式的左部非終結(jié)匹配的子串，然后將該子串用這一產(chǎn)生式的左部非終結(jié)符進(jìn)行替換；符進(jìn)行替換；-如果找

7、不到這樣的子串，則回退到上一步歸約前的狀如果找不到這樣的子串，則回退到上一步歸約前的狀 態(tài)，選擇不同的子串或不同的產(chǎn)生式重試；態(tài)，選擇不同的子串或不同的產(chǎn)生式重試；- 重復(fù)上一步驟，直到重復(fù)上一步驟，直到歸約至文法開始符號(hào)歸約至文法開始符號(hào)；- 如果不存在任何一個(gè)這樣的歸約，則表明該終結(jié)符串如果不存在任何一個(gè)這樣的歸約，則表明該終結(jié)符串存在語法錯(cuò)誤存在語法錯(cuò)誤 自底向上分析的一般過程自底向上分析的一般過程u 在每一步歸約中，選擇哪一個(gè)產(chǎn)生式以及匹配在每一步歸約中，選擇哪一個(gè)產(chǎn)生式以及匹配 哪一個(gè)位置上的子串都可能是非確定的哪一個(gè)位置上的子串都可能是非確定的u這些非確定性導(dǎo)致分析過程會(huì)有很高的復(fù)

8、雜性這些非確定性導(dǎo)致分析過程會(huì)有很高的復(fù)雜性 自底向上分析中的非確定性？自底向上分析中的非確定性？ 改進(jìn)的方法？改進(jìn)的方法？- 選擇選擇“可歸約串可歸約串”進(jìn)行歸約進(jìn)行歸約 在實(shí)用的自底向上分析中，總是選擇某個(gè)在實(shí)用的自底向上分析中，總是選擇某個(gè)“可可 歸約串歸約串”進(jìn)行歸約，可大大減少回溯進(jìn)行歸約，可大大減少回溯 觀 察v當(dāng)前棧頂部分與多個(gè)產(chǎn)生式右部匹配；v移進(jìn)歸約沖突反映了文法有二義性；v通過消除文法二義性可以避免某些移進(jìn)歸約沖突；v通過向前查看一個(gè)Token可以避免某些移進(jìn)歸約沖突；2 2 規(guī)范歸約規(guī)范歸約短語短語: :令令G G是一個(gè)文法，是一個(gè)文法，S S是文法的開始符是文法的開始符

9、號(hào)，若號(hào)，若是文法是文法G G的一個(gè)句型，的一個(gè)句型，如果有如果有S S A A且且 A A ，則稱，則稱是句型是句型相對(duì)于相對(duì)于非終結(jié)符非終結(jié)符A A的的短語。短語。句柄：句柄：一個(gè)句型的一個(gè)句型的最左直接短語最左直接短語稱為該句型稱為該句型的句柄。的句柄。直接短語：直接短語：如果有如果有A A =，則稱，則稱是句型是句型相對(duì)于規(guī)則相對(duì)于規(guī)則A A 的的直接短語直接短語例例5.25.2 文法文法G G E T | E +T T F | T * F F i |（E）的一個(gè)句型的一個(gè)句型 i i1 1* *i i2 2+i+i3 3語語 法法 樹樹TFEEFF+T*iiiTTFEEFF+T*i1

10、i2i3T i i1 ,1 ,i i2 ,2 ,i i3 , 3 , i i1 1* *i i2 , 2 , i i1 1* *i i2 2+i+i3 3i i1 ,1 ,i i2 ,2 ,i i3 3 i i1 1 l短語短語: :l直接短語直接短語: :l句柄句柄: : i2+i3不是該句型的一個(gè)短語，為什么？不是該句型的一個(gè)短語，為什么？盡管有盡管有E推到出推到出i2+i3，但不存在從開始但不存在從開始符號(hào)符號(hào)E到到i1*E的推到的推到子樹和短語：子樹和短語： 語法樹的某個(gè)結(jié)點(diǎn)連同它的所有后代組成了一棵子樹，語法樹的某個(gè)結(jié)點(diǎn)連同它的所有后代組成了一棵子樹，只含有單層分支的子樹稱為只含有單

11、層分支的子樹稱為簡單子樹簡單子樹。 子樹與短語的關(guān)系十分密切，根據(jù)子樹的概念，句型的子樹與短語的關(guān)系十分密切，根據(jù)子樹的概念，句型的短語、直接短語、句柄的直觀解釋如下：短語、直接短語、句柄的直觀解釋如下：(1)短語：子樹的末端結(jié)點(diǎn)短語：子樹的末端結(jié)點(diǎn)(即樹葉即樹葉)組成的符號(hào)串是相對(duì)于組成的符號(hào)串是相對(duì)于子子樹的根樹的根的短語。的短語。(2)直接短語：簡單子樹的末端結(jié)點(diǎn)組成的符號(hào)串是相對(duì)于直接短語：簡單子樹的末端結(jié)點(diǎn)組成的符號(hào)串是相對(duì)于簡簡單子樹的根單子樹的根的直接短語。的直接短語。(3)句柄：最左簡單子樹的末端結(jié)點(diǎn)組成的符號(hào)串是句柄。句柄：最左簡單子樹的末端結(jié)點(diǎn)組成的符號(hào)串是句柄。 例：短語

12、、直接短語SEEE+T|ET|TTT*i|T/i|i-ESETT4*32T 2-3*42是句型是句型2-3*4相對(duì)于相對(duì)于T和和E的短語，是相對(duì)于的短語，是相對(duì)于Ti的直接短語的直接短語3是句型是句型2-3*4相對(duì)于相對(duì)于T的的短語，是相對(duì)于短語，是相對(duì)于Ti的的直接短語直接短語3*4是句型是句型2-3*4相對(duì)于相對(duì)于T的短語，不是直接短語的短語，不是直接短語2-3*4是句型是句型2-3*4相對(duì)于相對(duì)于E和和S的短語，不是直接的短語，不是直接短語短語SEEE+T|ET|TTT*i|T/i|i2*3+42是句型是句型2*3+4相對(duì)于相對(duì)于T的短語，是相對(duì)于的短語，是相對(duì)于Ti的直接短語的直接短語

13、4是句型是句型2*3+4相對(duì)于相對(duì)于T的短語，是相對(duì)于的短語，是相對(duì)于Ti的直接短語的直接短語2*3是句型是句型2*3+4相對(duì)于相對(duì)于T和和E的短語的短語,不是直接短語不是直接短語2-3*4是句型是句型2*3+4相對(duì)相對(duì)于于E和和S的短語，不是直的短語，不是直接短語接短語+ESTTT3*24E例：短語、直接短語例：SEEE+T|ET|TTT*i|T/i|i-ESETT4*32T句型句型: 2-3*42是句型是句型2-3*4相對(duì)于相對(duì)于T和和E的短語，是相對(duì)于的短語，是相對(duì)于Ti的直接短語，的直接短語，是句柄是句柄3是句型是句型2-3*4相對(duì)于相對(duì)于T的的短語，是相對(duì)于短語，是相對(duì)于Ti的的直接

14、短語直接短語3*4是句型是句型2-3*4相對(duì)于相對(duì)于T的短語，不是直接短語的短語，不是直接短語2-3*4是句型是句型2-3*4相對(duì)于相對(duì)于E和和S的短語，不是直接的短語，不是直接短語短語例：SEEE+T|ET|TTT*i|T/i|i+ESTTT3*24句型句型: 2*3+42是句型是句型2*3+4相對(duì)于相對(duì)于T的短語，是相對(duì)于的短語，是相對(duì)于Ti的直接短語，的直接短語，是句柄是句柄4是句型是句型2*3+4相對(duì)于相對(duì)于T的短語，是相對(duì)于的短語，是相對(duì)于Ti的直接短語的直接短語2*3是句型是句型2*3+4相對(duì)于相對(duì)于T和和E的短語的短語,不是直接短語不是直接短語2-3*4是句型是句型2*3+4相對(duì)

15、相對(duì)于于E和和S的短語，不是直的短語，不是直接短語接短語Ev定義：假定定義：假定 是文法是文法G G的一個(gè)句子，我們稱序的一個(gè)句子，我們稱序列列 n n， n-1n-1， ， 0 0 是的一個(gè)是的一個(gè)規(guī)范歸約規(guī)范歸約，如果此序列滿足：，如果此序列滿足： 1 1 n n= = 2 2 0 0為文法的開始符號(hào)，即為文法的開始符號(hào)，即 0 0=S=S 3 3 對(duì)任何對(duì)任何i i，0 0 i i n n， i-1i-1是從是從 i i經(jīng)把句柄替換經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號(hào)而得到的。成為相應(yīng)產(chǎn)生式左部符號(hào)而得到的。句柄：句柄：可歸約串可歸約串規(guī)范推導(dǎo)：規(guī)范推導(dǎo)：即即最右推導(dǎo)最右推導(dǎo)；規(guī)范句型：規(guī)

16、范句型：由規(guī)范推導(dǎo)所得的句型稱為規(guī)范由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型；句型；規(guī)范歸約：規(guī)范歸約：是關(guān)于句型是關(guān)于句型的一個(gè)的一個(gè)最右推導(dǎo)最右推導(dǎo)的的逆過程，也稱逆過程，也稱最左歸約最左歸約。v可用句柄來對(duì)句子進(jìn)行歸約可用句柄來對(duì)句子進(jìn)行歸約句型句型 歸約規(guī)則歸約規(guī)則a ab bbcde bcde (2) A (2) A b ba aAbAbcde cde (3) A (3) A Ab AbaAcaAcd de e (4) B (4) B d daAcBeaAcBe (1) S (1) S aAcBe aAcBe S SbdbaceSABAdbaceSABAdaceSABaceSABSa ab

17、bbcde bcde a aAbAbcdecdeaAcaAcd de e aAcBeaAcBe 在一個(gè)句型對(duì)應(yīng)的語法樹在一個(gè)句型對(duì)應(yīng)的語法樹中，以某非終結(jié)符為根的中，以某非終結(jié)符為根的兩代以上的子樹的所有末兩代以上的子樹的所有末端結(jié)點(diǎn)從左到右排列就是端結(jié)點(diǎn)從左到右排列就是相對(duì)于該非終結(jié)符的一個(gè)相對(duì)于該非終結(jié)符的一個(gè)短語，如果子樹只有兩代，短語，如果子樹只有兩代，則該短語就是直接短語。則該短語就是直接短語。一個(gè)句型的最左直接短語一個(gè)句型的最左直接短語稱為該句型的句柄。稱為該句型的句柄。3 3 符號(hào)棧的使用符號(hào)棧的使用規(guī)范歸約用來作語法分析需要解決的規(guī)范歸約用來作語法分析需要解決的問題：問題：如何

18、在句型中找出句柄如何在句型中找出句柄? ?在相同的右部有不止一個(gè)產(chǎn)生式時(shí)在相同的右部有不止一個(gè)產(chǎn)生式時(shí), ,選哪一個(gè)選哪一個(gè)? ?實(shí)現(xiàn)移進(jìn)實(shí)現(xiàn)移進(jìn)- -歸約分析的一個(gè)方便途徑是用一個(gè)棧和一個(gè)輸歸約分析的一個(gè)方便途徑是用一個(gè)棧和一個(gè)輸 入緩沖區(qū)入緩沖區(qū), ,用用# #表示棧底和輸入的結(jié)束表示棧底和輸入的結(jié)束棧棧輸輸 入入#w# 分析程序的動(dòng)作分析程序的動(dòng)作l移進(jìn)移進(jìn): : 下一輸入符號(hào)移進(jìn)棧頂下一輸入符號(hào)移進(jìn)棧頂l歸約歸約: : 把句柄按產(chǎn)生式的左部進(jìn)行歸約把句柄按產(chǎn)生式的左部進(jìn)行歸約l接收接收: : 分析程序報(bào)告成功分析程序報(bào)告成功l出錯(cuò)出錯(cuò): : 發(fā)現(xiàn)了一個(gè)語法錯(cuò)發(fā)現(xiàn)了一個(gè)語法錯(cuò), ,調(diào)用出

19、錯(cuò)處理程序調(diào)用出錯(cuò)處理程序注意注意: : 可歸約的串在棧頂可歸約的串在棧頂, ,不會(huì)在內(nèi)部不會(huì)在內(nèi)部文法文法G G E T | E +T T F | T * F F i |（E）在移進(jìn)-規(guī)約過程中如何生成語法分析樹？穿線表穿線表語法樹的實(shí)際表示方法：穿線表語法樹的實(shí)際表示方法：穿線表(1)(1) 從輸入串移一個(gè)符號(hào)入棧時(shí)，建立代表端末結(jié)從輸入串移一個(gè)符號(hào)入棧時(shí)，建立代表端末結(jié)a a（葉結(jié)點(diǎn)、（葉結(jié)點(diǎn)、終結(jié)符）的數(shù)據(jù)結(jié)構(gòu)：終結(jié)符）的數(shù)據(jù)結(jié)構(gòu)：(a.) (a.) 兒子的個(gè)數(shù)：兒子的個(gè)數(shù)：0 0 ；(b.) (b.) 關(guān)于關(guān)于a a自身信息（如單詞內(nèi)部值）；自身信息（如單詞內(nèi)部值）；將此數(shù)據(jù)結(jié)構(gòu)地址

20、（指示器值）連同將此數(shù)據(jù)結(jié)構(gòu)地址（指示器值）連同a a本身一起進(jìn)棧。本身一起進(jìn)棧。(2)(2)棧頂棧頂n n個(gè)符號(hào)如個(gè)符號(hào)如X X1 1X X2 2X Xn n歸約為歸約為A A時(shí)，建立新結(jié)時(shí)，建立新結(jié)A A的數(shù)據(jù)結(jié)構(gòu)：的數(shù)據(jù)結(jié)構(gòu)：(a.) (a.) 兒子個(gè)數(shù)：兒子個(gè)數(shù)：n n；(b.) (b.) 指向兒子結(jié)點(diǎn)的指向兒子結(jié)點(diǎn)的n n個(gè)指示器值；個(gè)指示器值；(c.) (c.) 關(guān)于關(guān)于A A自身信息（如語義信息）；自身信息（如語義信息）；將此數(shù)據(jù)結(jié)構(gòu)地址連同將此數(shù)據(jù)結(jié)構(gòu)地址連同A A本身一起進(jìn)棧。本身一起進(jìn)棧。二二 直觀算符優(yōu)先分析法直觀算符優(yōu)先分析法 1 1 定義定義: : 任二個(gè)相繼出現(xiàn)的終

21、結(jié)符任二個(gè)相繼出現(xiàn)的終結(jié)符a a與與b(b(可能中間有可能中間有V VNN), ),可能有以可能有以下優(yōu)先關(guān)系下優(yōu)先關(guān)系: :a b a的優(yōu)先性的優(yōu)先性低于低于ba b a的優(yōu)先性的優(yōu)先性等于等于ba b a的優(yōu)先性的優(yōu)先性高于高于b2 例例5.3 文法文法G:E E + E | E * E | EE | ( E ) | i的終結(jié)符的優(yōu)先關(guān)系見下表。的終結(jié)符的優(yōu)先關(guān)系見下表。 + * i （ ） # + * i（ ） #優(yōu)優(yōu) 先先 表表E E E+E | E E+E | E* *E | EE |( E )| iE | EE |( E )| i3 3 使用如上分析表，構(gòu)造分析算法（直觀算符使用如

22、上分析表，構(gòu)造分析算法（直觀算符優(yōu)先分析法）優(yōu)先分析法）記號(hào)使用說明：記號(hào)使用說明： #：語句括號(hào)（棧底：語句括號(hào)（棧底 w后）后）：現(xiàn)行棧頂符：現(xiàn)行棧頂符 a：剛讀入字符：剛讀入字符OPTR：運(yùn)算符棧：運(yùn)算符棧OPND：操作符棧：操作符棧分析算法步驟：分析算法步驟：下一個(gè)輸入符號(hào)讀至下一個(gè)輸入符號(hào)讀至a a中；中；若若a a為為i i，則，則a aOPNDOPND，轉(zhuǎn)第一步；，轉(zhuǎn)第一步；若若 a a，則調(diào)用關(guān)于，則調(diào)用關(guān)于的處理程序（語義程序），處理子的處理程序（語義程序），處理子表達(dá)式表達(dá)式 : : E E（1 1）EE（2 2） ；然后重新進(jìn)入第；然后重新進(jìn)入第3 3步；（其中，步；（其

23、中， E E（1 1） 、E E（2 2）分分別為別為OPNDOPND棧的次棧頂和棧頂）棧的次棧頂和棧頂）aOPTROPND#E （1） E （2）E（3）=若若 a a，則，則若若=( (,a=,a=) ), ,則逐出則逐出OPTROPTR棧頂?shù)臈ｍ數(shù)? (, ,放棄放棄a a中的中的 ) ), ,轉(zhuǎn)第轉(zhuǎn)第 1 1步步; ;若若=a=a=# #, ,分析成功結(jié)束；分析成功結(jié)束；若若 a a，a aOPTROPTR棧，轉(zhuǎn)第棧，轉(zhuǎn)第1 1步；步；與與a a不存在優(yōu)先關(guān)系不存在優(yōu)先關(guān)系，則輸入串錯(cuò)誤，調(diào)出錯(cuò)處理，則輸入串錯(cuò)誤，調(diào)出錯(cuò)處理)OPTROPND#(E （1） E （2）a#成功！成功！2

24、 例例5.4 由文法由文法G: E E + E | E * E | EE | ( E ) | i的終結(jié)符的優(yōu)先關(guān)系表及上述分析算法的終結(jié)符的優(yōu)先關(guān)系表及上述分析算法分析算術(shù)表達(dá)式分析算術(shù)表達(dá)式 i1 + i2 i1 + i2 * * i3 # i3 # 的過程。的過程。OPTROPTROPNDOPND分析過程分析過程 OPND OPND棧為空，棧為空， # # -OPTR-OPTR棧棧 i1-OPND i1-OPND # # OPTROPTR i2-OPND i2-OPND# #+ +i1 i1i2i2i3i3* *t te e輸入串輸入串 : :i1 + i2 i1 + i2 * * i3

25、# i3 #+ + OPTR-OPTR i3-OPND i3-OPND* * # # ， * *彈出彈出OPTROPTR棧；棧； i2 i2 * * i3 = t -OPND i3 = t -OPND + + # # ， + +彈出彈出OPTROPTR棧；棧； t + i1 = e -OPNDt + i1 = e -OPND # # = =# # ， 分析成功；分析成功； e e 為整個(gè)表達(dá)式的結(jié)為整個(gè)表達(dá)式的結(jié)果果a a1 1 算符優(yōu)先文法算符優(yōu)先文法定義一定義一 如果一個(gè)文法的任何產(chǎn)生式右部都不含兩如果一個(gè)文法的任何產(chǎn)生式右部都不含兩個(gè)相繼（并列）的非終結(jié)符，即不含有如下形式個(gè)相繼（并列）

26、的非終結(jié)符，即不含有如下形式的產(chǎn)生式右部：的產(chǎn)生式右部：QRQR則我們稱該文法為則我們稱該文法為算符文法。算符文法。三三 算符優(yōu)先分析算符優(yōu)先分析定義二定義二 假定假定G G是一個(gè)不含是一個(gè)不含- -產(chǎn)生式的算符文法。對(duì)于任產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符何一對(duì)終結(jié)符a a、b b，我們說：，我們說：la a b b， 當(dāng)且僅當(dāng)文法當(dāng)且僅當(dāng)文法G G中含有形如中含有形如P-P-abab 或或P-P-aQbaQb的產(chǎn)生式；的產(chǎn)生式； （如：（如：（E E），則（），則（ ）la ba b， 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G G中含有形如中含有形如P-P-aRaR的產(chǎn)生的產(chǎn)生式，而式，而R bR b 或或

27、R QbR Qb；la ba b， 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G G中含有形如中含有形如P-P-RbRb的產(chǎn)生的產(chǎn)生式，而式，而R R a a 或或 R R aQaQ。 定義三定義三 如果一個(gè)算符文法如果一個(gè)算符文法G G中的任何終結(jié)符對(duì)（中的任何終結(jié)符對(duì)（a a，b b）至多只滿足下述三種關(guān)系之一：至多只滿足下述三種關(guān)系之一：a ba b，a ba b，a ba b則稱則稱G G是一個(gè)是一個(gè)算符優(yōu)先文法。算符優(yōu)先文法。2 2 從算符優(yōu)先文法構(gòu)造優(yōu)先關(guān)系表從算符優(yōu)先文法構(gòu)造優(yōu)先關(guān)系表v例例: :考慮下面的文法考慮下面的文法G(E)G(E)： (1) EE+T | T(1) EE+T | T (2) TT

28、 (2) TT* *F | FF | F (3) FP (3) FP F | P F | P (4) P(E) | i (4) P(E) | iv由第由第(4)(4)條規(guī)則，有條規(guī)則，有 (=)(=)；v由規(guī)則由規(guī)則(1)EE(1)EET T和和(2)T(2)TT T* *F F， 有有 * *；v由由(2) (2) TTTT* *F F 和和(3) (3) FP FP F F ，可得，可得* *+；v由由(3)FP(3)FP F F和和F F P P F F，可得，可得。v由由(4)P(E)(4)P(E)和和 E EE+TE+TT+TT+TT T* *F+TF+TF F* *F+TF+TPF

29、PF* *F+TF+TiFiF* *F+TF+T 有有 (+(+、(* *、(和和(i(aP-a或或P-Qa,P-Qa,則則aFIRSTVT(P)aFIRSTVT(P)；若若aFIRSTVT(Q),aFIRSTVT(Q),且有產(chǎn)生式且有產(chǎn)生式P-QP-Q，則，則aFIRSTVT(P)aFIRSTVT(P)FIRSTVT Pa PaPQaaVQVTN() |,或而 3 3 構(gòu)造集合構(gòu)造集合FIRSTVT(P)FIRSTVT(P)的算法的算法v數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：布爾數(shù)組布爾數(shù)組FPFP，aa，使得，使得FPFP，aa為真的條件是，當(dāng)且僅為真的條件是，當(dāng)且僅當(dāng)當(dāng)a a FIRSTVT(P)FIRS

30、TVT(P)。開始時(shí)，按上述的規(guī)則。開始時(shí)，按上述的規(guī)則(1)(1)對(duì)每個(gè)數(shù)對(duì)每個(gè)數(shù)組元素組元素FPFP，aa賦初值。賦初值。棧棧STACKSTACK，把所有初值為真的數(shù)組元素，把所有初值為真的數(shù)組元素FPFP，aa的符號(hào)的符號(hào)對(duì)對(duì)(P(P，a)a)全都放在全都放在STACKSTACK之中。之中。v運(yùn)算：運(yùn)算：如果棧如果棧STACKSTACK不空，就將頂項(xiàng)逐出，記此項(xiàng)為不空，就將頂項(xiàng)逐出，記此項(xiàng)為(Q(Q，a)a)。對(duì)于每個(gè)形如對(duì)于每個(gè)形如PQPQ 的產(chǎn)生式，若的產(chǎn)生式，若FPFP，aa為假，則變其值為真且將為假，則變其值為真且將(P(P，a)a)推推進(jìn)進(jìn)STACKSTACK棧。棧。上述過程必

31、須一直重復(fù)，直至棧上述過程必須一直重復(fù)，直至棧STACKSTACK拆空為止。拆空為止。lFIRSTVT(P)FIRSTVT(P)的自動(dòng)構(gòu)造的自動(dòng)構(gòu)造過程過程INSERTINSERT： PROCEDURE INSERT(P,a)PROCEDURE INSERT(P,a) IF NOT FP,a THEN IF NOT FP,a THENBEGIN BEGIN FP,a := TRUE FP,a := TRUE； 把把(P,a)(P,a)下推進(jìn)下推進(jìn)STACKSTACK棧棧 END;END;主程序：主程序：BEGINBEGIN FOR FOR 每個(gè)非終結(jié)符每個(gè)非終結(jié)符P P和終結(jié)符和終結(jié)符a DO

32、 FP,a := FALSE;a DO FP,a := FALSE; FOR FOR 每個(gè)形如每個(gè)形如P-a P-a 或或P-QaP-Qa的產(chǎn)生式的產(chǎn)生式 DO DO INSERT(P,a);INSERT(P,a); WHILE STACK WHILE STACK 非空非空 DODO BEGIN BEGIN把把STACKSTACK的頂項(xiàng)，記為的頂項(xiàng)，記為(Q,a)(Q,a)，彈出去，彈出去FOR FOR 每條形如每條形如P-QP-Q的產(chǎn)生式的產(chǎn)生式 DODO INSERT(P,a) INSERT(P,a) END OF WHILE; END OF WHILE;ENDEND這個(gè)算法的工作結(jié)果得到

33、一個(gè)二維數(shù)組這個(gè)算法的工作結(jié)果得到一個(gè)二維數(shù)組F F，從它可得任何非終結(jié)符，從它可得任何非終結(jié)符P P的的FIRSTVTFIRSTVT。 FIRSTVT(P) FIRSTVT(P)a | FPa | FP，a=TRUEa=TRUE4 4 構(gòu)造集合構(gòu)造集合LASTSTVT(P)LASTSTVT(P)的算法的算法,|)(NTVQVaaQPaPaPLASTVT而或 P-a P-a 或或 P-aQ,P-aQ,則則aLASTVT(P)aLASTVT(P)；若若aLASTVT(Q),aLASTVT(Q),且有產(chǎn)生式且有產(chǎn)生式P-QP-Q，則，則aLASTVT(P)aLASTVT(P)lLASTVT(P)L

34、ASTVT(P)的自動(dòng)構(gòu)造的自動(dòng)構(gòu)造過程過程INSERTINSERT： PROCEDURE INSERT(P,a)PROCEDURE INSERT(P,a)IF NOT LP,a THENIF NOT LP,a THEN BEGIN BEGIN LP,a := TRUELP,a := TRUE；把把(P,a)(P,a)下推進(jìn)下推進(jìn)STACKSTACK棧棧 END;END;主程序：主程序：BEGINBEGIN FOR FOR 每個(gè)非終結(jié)符每個(gè)非終結(jié)符P P和終結(jié)符和終結(jié)符a DO LP,a := FALSE;a DO LP,a := FALSE; FOR FOR 每個(gè)形如每個(gè)形如P- P- a

35、a 或或P- P- aQ aQ的產(chǎn)生式的產(chǎn)生式 DO DO INSERT(P,a);INSERT(P,a); WHILE STACK WHILE STACK 非空非空 DODO BEGIN BEGIN把把STACKSTACK的頂項(xiàng)，記為的頂項(xiàng)，記為(Q,a)(Q,a)，彈出去，彈出去FOR FOR 每條形如每條形如P- P- Q Q的產(chǎn)生式的產(chǎn)生式 DODO INSERT(P,a) INSERT(P,a) END OF WHILE; END OF WHILE;ENDEND5 5 構(gòu)造優(yōu)先表方法構(gòu)造優(yōu)先表方法 對(duì)文法適當(dāng)改造（增廣文法）之后：對(duì)文法適當(dāng)改造（增廣文法）之后： 對(duì)形如對(duì)形如 P-a

36、bP-ab和形如和形如P-aQbP-aQb，有，有a a b b；對(duì)形如對(duì)形如 P-aRP-aR，而，而bFIRSTVT(R)bFIRSTVT(R)，有，有a a b b；對(duì)形如對(duì)形如 P-RbP-Rb，而，而aLASTVT(R)aLASTVT(R)，有，有a a b b；優(yōu)先表中對(duì)#的處理(增廣文法)vS是文法G的開始符號(hào)，給G中添加一個(gè)產(chǎn)生式S#S#顯然：M#,#:= ;foreach aFIRSTVT(S) M#, a:= ;foreach b LASTVT(S ) Mb, #:= ; MXi , a FOR FOR 每條產(chǎn)生式每條產(chǎn)生式P-X1X2P-X1X2Xn DOXn DO FO

37、R i := 1 TO n-1 DO FOR i := 1 TO n-1 DOBEGINBEGIN IF Xi IF Xi和和Xi+1Xi+1均為終結(jié)符均為終結(jié)符 THEN THEN 置置Xi Xi+1Xi Xi+1 IF in IF in2 2且且XiXi和和Xi+2Xi+2都為終結(jié)符都為終結(jié)符但但Xi+1Xi+1為非終結(jié)符為非終結(jié)符 THEN THEN 置置Xi Xi+2;Xi Xi+2; IF Xi IF Xi為終結(jié)符而為終結(jié)符而Xi+1Xi+1為非終結(jié)符為非終結(jié)符THENTHENFOR FIRSTVT(Xi+1)FOR FIRSTVT(Xi+1)中的每個(gè)中的每個(gè)a DOa DO置置 X

38、i a;Xi a; IF Xi IF Xi為非終結(jié)符而為非終結(jié)符而Xi+1Xi+1為終結(jié)符為終結(jié)符 THENTHENFOR LASTVT(Xi)FOR LASTVT(Xi)中的每個(gè)中的每個(gè)a DOa DO置置 a Xi+1a Xi+1ENDEND例1 設(shè)有表達(dá)式的文法GE：E E + T | TT T * F | FF (E) | id構(gòu)造該文法的算符優(yōu)先關(guān)系表。首先S#E#計(jì)算每個(gè)非終結(jié)符的FIRSTVT和LASTVT FIRSTVT LASTVT E *, +, (, id *, +, ), id T *, (, id *, ), id F (, id ), id P-aP-a或或P-Qa

39、,P-Qa,則則aFIRSTVT(P)aFIRSTVT(P)；若若aFIRSTVT(Q),aFIRSTVT(Q),且有產(chǎn)生式且有產(chǎn)生式P-QP-Q，則，則aFIRSTVT(P)aFIRSTVT(P) P-a P-a 或或 P-aQ,P-aQ,則則aLASTVT(P)aLASTVT(P)；若若aLASTVT(Q),aLASTVT(Q),且有產(chǎn)生式且有產(chǎn)生式P-QP-Q，則，則aLASTVT(P)aLASTVT(P)+ T 尋找終結(jié)符在左邊，非終結(jié)符在右邊的符號(hào)對(duì)有尋找終結(jié)符在左邊，非終結(jié)符在右邊的符號(hào)對(duì)有 則則+ FIRSTVT(T).* * F則則* * FIRSTVT(F)則則( FIRST

40、VT(E)( E * *, (, id (, id * *, +, (, id 逐條掃描文法規(guī)則，因有逐條掃描文法規(guī)則，因有E(E)的規(guī)則，則有的規(guī)則，則有( ) 尋找非終結(jié)符在左邊，終結(jié)在右邊的符號(hào)對(duì)有尋找非終結(jié)符在左邊，終結(jié)在右邊的符號(hào)對(duì)有 E +E +則則LASTVT(E) LASTVT(E) + +則則LASTVT(T) LASTVT(T) * *T T * *則則LASTVT(E) LASTVT(E) ) )E )E )補(bǔ)充：補(bǔ)充：# # # # # # FIRSTVT(E) LASTVT(E) FIRSTVT(E) LASTVT(E) # # * *, ), id , ), id

41、* *, +, ), id , +, ), id 例EE+T|T TT*F|F S#E#FPF|P P(E)|i+*i()#+ * i ( ) # a b 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中有中有Pab或或PaQba b 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中有中有PaR且且b FIRSTVT(R)a b 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中有中有PRb且且a LASTVT(R)6 6 算符優(yōu)先分析算法的設(shè)計(jì)算符優(yōu)先分析算法的設(shè)計(jì)l定義定義 1 1）文法文法G G，開始符號(hào)，開始符號(hào)S S，若，若S S ，如果，如果S S 且且 A A ，則稱則稱是句型是句型的一個(gè)的一個(gè)短語短語。2 2）所謂素短語是指這樣一個(gè)短語所謂素短語是指這樣一個(gè)短語

42、, ,它至少含有一個(gè)它至少含有一個(gè)終終結(jié)符結(jié)符, ,并且并且, ,除自身之外除自身之外, ,不再含任何更小的不再含任何更小的素短語素短語。3 3）句型最左邊的那個(gè)素短語叫句型最左邊的那個(gè)素短語叫最左素短語最左素短語。v考慮下面的文法考慮下面的文法G(E)G(E)： (1) EE+T | T(1) EE+T | T (2) TT (2) TT* *F | FF | F (3) FP (3) FP F | P F | P (4) P(E) | i (4) P(E) | iE EE EF F+ +* *T Ti iF FT TF FT TP P+ +E ET TP P句型：句型：T+FT+F* *P

43、+iP+i短語：短語：直接短語：直接短語：句柄：句柄：素短語：素短語：最左素短語：最左素短語：, T+F, T+F* *P+iP+iT T, F, F, P, P, F, F* *P,P, i, iT+FT+F* *P PT T, F, F, P, P, i, iT TF F* *P P , i, iF F* *P Pl定理定理: :一個(gè)算符優(yōu)先文法一個(gè)算符優(yōu)先文法G G的任何句型的最左素短語是滿的任何句型的最左素短語是滿足以下條件的最左子串足以下條件的最左子串 NNj ja aj j N Ni ia ai iNNi+1i+1， a aj-1j-1 a aj ja aj j a aj+1 j+

44、1 , , , a , ai-1 i-1 a ai i a ai i a ai+1i+1算符優(yōu)先文法的句型一般形式：算符優(yōu)先文法的句型一般形式：#N#N1 1a a1 1NN2 2a a2 2NNn na an nNNn+1n+1# # 其中，其中，a ai i V VT T，NNi i V VNN| | 任何兩個(gè)終結(jié)符間任何兩個(gè)終結(jié)符間頂多頂多只有一個(gè)非終結(jié)符只有一個(gè)非終結(jié)符.l也即：也即： a aj-1j-1 a ai+1i+1 NNj j a aj j a ai i NNi+1i+12 例例5.5 i1 i1 * *( i2 + i3) # ( i2 + i3) # # # i1 i1

45、* * ( ( i2 i2 + + i3i3 ) ) # #i1i1，i2i2，i3i3是素短語；是素短語；i1 i1是最左素短語。是最左素短語。對(duì)定理的解釋句型 #N1a1N2a2NnanNn+1#記為 NjajNiaiNi+1由由a aj-1j-1 a aj j可知有規(guī)范推導(dǎo)（最右推導(dǎo)）：可知有規(guī)范推導(dǎo)（最右推導(dǎo)）： R R NNj ja aj jNNi ia ai iNNi+1i+1 由由a ai i a ai+1i+1 可知有規(guī)范推導(dǎo)：可知有規(guī)范推導(dǎo)： R R NNj ja aj jNNi ia ai iNNi+1i+1 由由 a aj j a aj+1 j+1 , a, ai-1i-

46、1 a ai i 可知可知NNj ja aj jNNi ia ai iNNi+1 i+1 是某個(gè)產(chǎn)生式規(guī)則是某個(gè)產(chǎn)生式規(guī)則( (其左部設(shè)為其左部設(shè)為R R）的候選式）的候選式; ;根據(jù)根據(jù)最左素短語最左素短語的定理，最左素短語中的終結(jié)符的定理，最左素短語中的終結(jié)符號(hào)具有相同的優(yōu)先關(guān)系，并且，由于最左素短語號(hào)具有相同的優(yōu)先關(guān)系，并且，由于最左素短語中的符號(hào)是當(dāng)時(shí)中的符號(hào)是當(dāng)時(shí)最先要?dú)w約的串最先要?dú)w約的串，其優(yōu)先關(guān)系先，其優(yōu)先關(guān)系先于最左素短語之外的符號(hào)，所以我們使用一個(gè)用于最左素短語之外的符號(hào)，所以我們使用一個(gè)用于存放文法符號(hào)的于存放文法符號(hào)的先進(jìn)后出棧先進(jìn)后出棧，并利用優(yōu)先關(guān)系，并利用優(yōu)先關(guān)系

47、表，可以確定最左素短語是否已形成來決定分析表，可以確定最左素短語是否已形成來決定分析器的動(dòng)作。器的動(dòng)作。 l算法分析：算法分析：# #t t1 1t t3 3t tj+1j+1t t2 2t tj jt ti+1i+1t tn n# #符號(hào)棧符號(hào)棧t ti i 尾尾頭頭最左素短語最左素短語算符優(yōu)先分析程序的基本思想算符優(yōu)先分析程序的基本思想: : . .S j a ? 或或 S j a ?N.=.YS j Q?.N說明說明:算法中算法中K為符號(hào)棧為符號(hào)棧S的指針，的指針，a用來存放當(dāng)用來存放當(dāng)前輸入符號(hào)，前輸入符號(hào)，j是棧的是棧的查找指針，查找指針，Q是工作是工作單元。單元。117算符優(yōu)先分析

48、舉例算符優(yōu)先分析舉例+ +* * i i( () )# #+ +* *i i( () )# # 步步驟驟分析棧分析棧剩余輸入串剩余輸入串所用產(chǎn)所用產(chǎn)生式生式/Q 1 #1 # i+i i+i* *ii #ii # 2 #i2 #i +i +i* *iiii # # Q=iQ=i 3 #P +i3 #P +i* *iiii # # 4 #P+4 #P+ i i* *iiii # # 5 #P+i5 #P+i * *iiii # # Q=iQ=i 6 #P+P6 #P+P * *iiii # # 7 #P+P7 #P+P* * ii ii # # 8 #P+P 8 #P+P* *i i i i #

49、 # Q=iQ=i 9 #P+P 9 #P+P* *P P i i # # G G：(1)E(1)EE+T|TE+T|T (2)T (2)TT T* *F|FF|F (3)F (3)FPF|PPF|P (4)P (4)P(E)|i(E)|i1185.2 5.2 算符優(yōu)先分析算符優(yōu)先分析+ +* * i i( () )# #+ +* *i i( () )# # 步驟分析棧剩余輸入串所用產(chǎn)生式 9 #P+P9 #P+P* *P i #P i #Q=iQ=i 10 #P+P10 #P+P* *P P i # i # 11 #P+P11 #P+P* *P Pi #i # 12 #P+P12 #P+P*

50、 *P PP #P #Q=Q= 13 #P+P13 #P+P* *F F # #Q=Q=* * 14 #P+14 #P+T T # #Q=+ Q=+ 15 #15 #E E # #G G：(1)E(1)EE+T|TE+T|T (2)T (2)TT T* *F|FF|F (3)F (3)FPF|PPF|P (4)P (4)P(E)|i(E)|iv對(duì)于算符優(yōu)先分析法，它雖然是一種自下對(duì)于算符優(yōu)先分析法，它雖然是一種自下而上的語法分析方法，但它并不是一種而上的語法分析方法，但它并不是一種規(guī)規(guī)范歸約范歸約的分析方法。的分析方法。WHY?WHY?v這是因?yàn)樵谒惴麅?yōu)先文法中，僅在終結(jié)符這是因?yàn)樵谒惴麅?yōu)先文

51、法中，僅在終結(jié)符號(hào)之間定義優(yōu)先關(guān)系而未對(duì)非終結(jié)符定義號(hào)之間定義優(yōu)先關(guān)系而未對(duì)非終結(jié)符定義優(yōu)先關(guān)系，從而無法使用優(yōu)先關(guān)系表去識(shí)優(yōu)先關(guān)系，從而無法使用優(yōu)先關(guān)系表去識(shí)別由別由單個(gè)非終結(jié)符單個(gè)非終結(jié)符組成的組成的可歸約串可歸約串v算符優(yōu)先分析法不是用算符優(yōu)先分析法不是用句柄句柄來刻畫可歸約來刻畫可歸約串，而是用串，而是用最左素短語最左素短語來刻畫可歸約串的。來刻畫可歸約串的。v算符優(yōu)先分析一般并不等價(jià)于規(guī)范歸約。算符優(yōu)先分析一般并不等價(jià)于規(guī)范歸約。EE+*iTP+iPiPiPEEF+*TiFTFTP+ETiFPiPiPn考慮下面的文法考慮下面的文法G(E)G(E)： (1) EE+T | T(1) E

52、E+T | T (2) TT (2) TT* *F | FF | F (3) FP (3) FP F | P F | P (4) P(E) | I (4) P(E) | I 的句子的句子i+ii+i* *i+ii+iv算符優(yōu)先分析法特點(diǎn)：算符優(yōu)先分析法特點(diǎn)：優(yōu)點(diǎn)優(yōu)點(diǎn): : 簡單，快速簡單，快速缺點(diǎn)缺點(diǎn): : 可能錯(cuò)誤接受非法句子，能力有限可能錯(cuò)誤接受非法句子，能力有限. .v算符優(yōu)先分析法是一種廣為應(yīng)用、行之算符優(yōu)先分析法是一種廣為應(yīng)用、行之有效的方法。有效的方法。用于分析各類表達(dá)式用于分析各類表達(dá)式ALGOL 60ALGOL 607 7 優(yōu)先函數(shù)優(yōu)先函數(shù) l定義：定義： 我們把每個(gè)終結(jié)符我們

53、把每個(gè)終結(jié)符與兩個(gè)自然數(shù)與兩個(gè)自然數(shù)f( f() ) 和和g(g() )相對(duì)相對(duì)應(yīng)，使得：應(yīng)，使得： 若若1 1 2 2，則，則f( f(1 1)g()g()g(2 2) )函數(shù)函數(shù) f f 稱為稱為入棧優(yōu)先函數(shù)入棧優(yōu)先函數(shù)，g g 稱為稱為比較優(yōu)先函數(shù)比較優(yōu)先函數(shù)。l使用優(yōu)先函數(shù)的優(yōu)缺點(diǎn)：使用優(yōu)先函數(shù)的優(yōu)缺點(diǎn)：優(yōu)：便于比較運(yùn)算；節(jié)省存儲(chǔ)空間。優(yōu)：便于比較運(yùn)算；節(jié)省存儲(chǔ)空間。缺：對(duì)不存在優(yōu)先關(guān)系的兩個(gè)終結(jié)符，由于與自然數(shù)相缺：對(duì)不存在優(yōu)先關(guān)系的兩個(gè)終結(jié)符，由于與自然數(shù)相 對(duì)應(yīng)，變成可比較對(duì)應(yīng)，變成可比較。l優(yōu)先函數(shù)的性質(zhì)：優(yōu)先函數(shù)的性質(zhì)：1）正確性：）正確性：優(yōu)先函數(shù)掩蓋了矩陣中出錯(cuò)元素對(duì)，若

54、優(yōu)先函數(shù)掩蓋了矩陣中出錯(cuò)元素對(duì)，若f(id) g(b) f(a) g(b) f(b) = g(a) f(b) = g(a) f(b) = g(b) f(b) = g(b)那么，那么，f(a)g(b)=f(b)=g(a)=f(a)f(a)g(b)=f(b)=g(a)=f(a)，矛盾。，矛盾。baba g(x)f(x)3）唯一性：）唯一性：存在一個(gè)優(yōu)先函數(shù)，就有無數(shù)多對(duì)，加一常數(shù)，不等存在一個(gè)優(yōu)先函數(shù)，就有無數(shù)多對(duì)，加一常數(shù)，不等式也成立。式也成立。l構(gòu)造優(yōu)先函數(shù)的方法構(gòu)造優(yōu)先函數(shù)的方法（如果優(yōu)先函數(shù)存在的話）（如果優(yōu)先函數(shù)存在的話）構(gòu)造優(yōu)先函數(shù)的方法v已知優(yōu)先關(guān)系表，構(gòu)造一個(gè)有向圖H=(V,E)

55、，foreach (aVT ) 置fa V;置ga V 結(jié)點(diǎn)為終結(jié)符a對(duì)應(yīng)的符號(hào)fa和ga;if (a b)置(fa , gb)E 畫結(jié)點(diǎn)fa到結(jié)點(diǎn)gb一條?。籭f (a b)置(gb , fa)E 畫結(jié)點(diǎn)gb到結(jié)點(diǎn)fa一條?。籿定義優(yōu)先函數(shù)f和g,令f(a)為從fa出發(fā)所能達(dá)到的結(jié)點(diǎn)個(gè)數(shù)+1;令g(a)為從ga出發(fā)所能達(dá)到的結(jié)點(diǎn)個(gè)數(shù)+1;v檢查f和g有無矛盾，若有則不存在優(yōu)先函數(shù)否則成功v對(duì)每個(gè)對(duì)每個(gè)a a（包括）（包括）V VT T，對(duì)應(yīng)兩個(gè)符號(hào)，對(duì)應(yīng)兩個(gè)符號(hào)f fa a，g ga a。v把所建立的符號(hào)盡可能劃分為許多組：把所建立的符號(hào)盡可能劃分為許多組：若若a ba b，則，則f fa

56、a和和g gb b就在一組；就在一組；若若a ba b，c bc b，則，則f fa a和和f fc c同組；同組；v建立一個(gè)有向圖，其結(jié)點(diǎn)是上一步中找出的組。建立一個(gè)有向圖，其結(jié)點(diǎn)是上一步中找出的組。對(duì)于任何對(duì)于任何a a和和b b，若，若 a ba b，畫，畫 f fa aggb b 弧，意味著弧，意味著f(a)g(b)f(a)g(b)； 若若 a ba b，畫，畫 g gb bffa a 弧，意味著弧，意味著f(a)g(b)f(a) E+E | E*E | EE | ( E ) | i的終結(jié)符的優(yōu)先關(guān)系表，構(gòu)造優(yōu)先函數(shù)。的終結(jié)符的優(yōu)先關(guān)系表，構(gòu)造優(yōu)先函數(shù)。f+f*ff)f(g)g(gg*

57、g+由優(yōu)先關(guān)系表，得：由優(yōu)先關(guān)系表，得： + ) ( * + *其余類同其余類同4662935882算符優(yōu)先-最左素短語規(guī)范歸約-句柄自下而上(自動(dòng)生成)遞歸下降-消除左遞歸預(yù)測分析法- 預(yù)測分析表 自上而下(手動(dòng)，自動(dòng)生成)語法分析4 4 LR LR分析法分析法lLRLR分析程序分析程序( (器器) )：自左向右自左向右掃描，識(shí)別句柄，掃描，識(shí)別句柄，自下而上自下而上歸約的歸約的 語法分析程序語法分析程序。lLRLR分析程序生成器：自動(dòng)生成分析程序生成器：自動(dòng)生成LRLR分析程序的程分析程序的程序。序。- “L”, “L”, 代表從代表從左左（LeftLeft）向右掃描輸入單詞序列）向右掃描

58、輸入單詞序列- “R R”, ,代表產(chǎn)生的是代表產(chǎn)生的是最右最右（RightmostRightmost）推導(dǎo)）推導(dǎo) 主要學(xué)習(xí)四種主要學(xué)習(xí)四種 LRLR 分析技術(shù)分析技術(shù)- LRLR（0 0）分析）分析 適用于適用于 LRLR（0 0）文法）文法- SLRSLR（1 1）分析）分析 適用于適用于 SLRSLR（1 1）文法）文法- LRLR（1 1）分析）分析 適用于適用于 LRLR（1 1）文法）文法- LALRLALR（1 1）分析）分析 適用于適用于 LALRLALR（1 1）文法）文法S Simpleimple LR(1) LR(1)L LookookA Aheadhead LR(1)

59、LR(1)“0” “0” - - 向前查看向前查看 0 0 個(gè)符號(hào)個(gè)符號(hào)“1” “1” - - 向前查看向前查看 1 1 個(gè)符號(hào)個(gè)符號(hào)分析表分析表產(chǎn)生器產(chǎn)生器文法文法分析表分析表總控總控程序程序輸入輸入輸出輸出分析表分析表l分析表的構(gòu)造方法分析表的構(gòu)造方法LR(0)表構(gòu)造法SLR表構(gòu)造法規(guī)范LR表構(gòu)造法LALR（向前LR）表構(gòu)造法分析表的構(gòu)造方法最簡單最簡單, ,局限性大局限性大( (絕大多數(shù)高級(jí)語言絕大多數(shù)高級(jí)語言的語法分析器均不適用的語法分析器均不適用),),但卻是建立但卻是建立其它較一般的其它較一般的 LRLR分析法的基礎(chǔ)分析法的基礎(chǔ). .一種較易實(shí)現(xiàn)又極有使用價(jià)值的方法一種較易實(shí)現(xiàn)又極

60、有使用價(jià)值的方法, ,對(duì)某些文法不適用對(duì)某些文法不適用. .能力最強(qiáng)能力最強(qiáng), ,能適用一大類文法能適用一大類文法, ,但實(shí)現(xiàn)但實(shí)現(xiàn)代價(jià)過高代價(jià)過高( (分析表體積太大分析表體積太大).).能力介于能力介于SLRSLR和規(guī)范和規(guī)范LRLR之間之間, ,稍加努力稍加努力, ,即可高效實(shí)現(xiàn)即可高效實(shí)現(xiàn). .l規(guī)范歸約規(guī)范歸約的關(guān)鍵問題是尋的關(guān)鍵問題是尋找找句柄句柄. .l“歷史歷史”：已移入符號(hào)棧的：已移入符號(hào)棧的內(nèi)容內(nèi)容l“展望展望”：根據(jù)產(chǎn)生式推測：根據(jù)產(chǎn)生式推測未來可能遇到的輸入符號(hào)未來可能遇到的輸入符號(hào)l“現(xiàn)實(shí)現(xiàn)實(shí)”：當(dāng)前的輸入符號(hào)：當(dāng)前的輸入符號(hào)l把把“歷史歷史”及及“展望展望”綜合抽象