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

1、第五章第五章 語法分析語法分析自下而上分析自下而上分析本章內(nèi)容本章內(nèi)容l自下而上分析基本問題自下而上分析基本問題l直觀算符優(yōu)先分析法直觀算符優(yōu)先分析法l算符優(yōu)先分析算符優(yōu)先分析l LRLR分析法分析法- 核心問題：句型分析核心問題：句型分析 對任意對任意上下文無關(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)行報錯處理。進(jìn)行報錯處理。 語法分析語法分析自下而上分析法自下而上分析法從輸

2、入串開始，逐步進(jìn)行從輸入串開始，逐步進(jìn)行“歸約歸約”，直至，直至歸約到文法的開始符號。歸約到文法的開始符號。例例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，且只有一個最左候選串，選擇該，且只有一個最左候選串，選擇該串進(jìn)行規(guī)約串進(jìn)行規(guī)約如果候選串如果候選串?dāng)?shù)目數(shù)目11，且有多個最左候選串，選擇較長，且有多個最左候選串，選擇較長串進(jìn)行規(guī)約串進(jìn)行規(guī)約一、自下而上分析基本問題一、自下而上分析基本問題1 1 、歸約、歸約利用棧，輸入符號移進(jìn)棧，當(dāng)棧頂形成利用棧，輸入符號移進(jìn)棧，當(dāng)棧頂形成P P的的候選式時，就歸約為它的左候選式時，就歸約為它的左P P符號符號例例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)前串中找到與某個產(chǎn)生式的右部相是在當(dāng)前串中找到與某個產(chǎn)生式的右部相匹配的子串，然后將該子串用這一產(chǎn)生式的左部非終結(jié)匹配的子串，然后將該子串用這一產(chǎn)生式的左部非終結(jié)符進(jìn)行替換；符進(jìn)行替換；-如果找

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

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

9、號，若號，若是文法是文法G G的一個句型，的一個句型，如果有如果有S S A A且且 A A ，則稱，則稱是句型是句型相對于相對于非終結(jié)符非終結(jié)符A A的的短語。短語。句柄：句柄：一個句型的一個句型的最左直接短語最左直接短語稱為該句型稱為該句型的句柄。的句柄。直接短語：直接短語：如果有如果有A A =，則稱，則稱是句型是句型相對于規(guī)則相對于規(guī)則A A 的的直接短語直接短語例例5.25.2 文法文法G G E T | E +T T F | T * F F i |（E）的一個句型的一個句型 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不是該句型的一個短語，為什么？不是該句型的一個短語，為什么？盡管有盡管有E推到出推到出i2+i3，但不存在從開始但不存在從開始符號符號E到到i1*E的推到的推到子樹和短語：子樹和短語： 語法樹的某個結(jié)點連同它的所有后代組成了一棵子樹，語法樹的某個結(jié)點連同它的所有后代組成了一棵子樹，只含有單層分支的子樹稱為只含有單

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

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

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

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

15、相對于于E和和S的短語，不是直的短語，不是直接短語接短語Ev定義：假定定義：假定 是文法是文法G G的一個句子，我們稱序的一個句子，我們稱序列列 n n， n-1n-1， ， 0 0 是的一個是的一個規(guī)范歸約規(guī)范歸約，如果此序列滿足：，如果此序列滿足： 1 1 n n= = 2 2 0 0為文法的開始符號，即為文法的開始符號，即 0 0=S=S 3 3 對任何對任何i i，0 0 i i n n， i-1i-1是從是從 i i經(jīng)把句柄替換經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號而得到的。成為相應(yīng)產(chǎn)生式左部符號而得到的。句柄：句柄：可歸約串可歸約串規(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)于句型的一個的一個最右推導(dǎo)最右推導(dǎo)的的逆過程，也稱逆過程，也稱最左歸約最左歸約。v可用句柄來對句子進(jìn)行歸約可用句柄來對句子進(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 在一個句型對應(yīng)的語法樹在一個句型對應(yīng)的語法樹中，以某非終結(jié)符為根的中，以某非終結(jié)符為根的兩代以上的子樹的所有末兩代以上的子樹的所有末端結(jié)點從左到右排列就是端結(jié)點從左到右排列就是相對于該非終結(jié)符的一個相對于該非終結(jié)符的一個短語，如果子樹只有兩代，短語，如果子樹只有兩代，則該短語就是直接短語。則該短語就是直接短語。一個句型的最左直接短語一個句型的最左直接短語稱為該句型的句柄。稱為該句型的句柄。3 3 符號棧的使用符號棧的使用規(guī)范歸約用來作語法分析需要解決的規(guī)范歸約用來作語法分析需要解決的問題：問題：如何

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

19、錯處理程序調(diào)用出錯處理程序注意注意: : 可歸約的串在棧頂可歸約的串在棧頂, ,不會在內(nèi)部不會在內(nèi)部文法文法G G E T | E +T T F | T * F F i |（E）在移進(jìn)-規(guī)約過程中如何生成語法分析樹？穿線表穿線表語法樹的實際表示方法：穿線表語法樹的實際表示方法：穿線表(1)(1) 從輸入串移一個符號入棧時，建立代表端末結(jié)從輸入串移一個符號入棧時，建立代表端末結(jié)a a（葉結(jié)點、（葉結(jié)點、終結(jié)符）的數(shù)據(jù)結(jié)構(gòu)：終結(jié)符）的數(shù)據(jù)結(jié)構(gòu)：(a.) (a.) 兒子的個數(shù)：兒子的個數(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個符號如個符號如X X1 1X X2 2X Xn n歸約為歸約為A A時，建立新結(jié)時，建立新結(jié)A A的數(shù)據(jù)結(jié)構(gòu)：的數(shù)據(jù)結(jié)構(gòu)：(a.) (a.) 兒子個數(shù)：兒子個數(shù)：n n；(b.) (b.) 指向兒子結(jié)點的指向兒子結(jié)點的n n個指示器值；個指示器值；(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 定義定義: : 任二個相繼出現(xiàn)的終

21、結(jié)符任二個相繼出現(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)先分析法）記號使用說明：記號使用說明： #：語句括號（棧底：語句括號（棧底 w后）后）：現(xiàn)行棧頂符：現(xiàn)行棧頂符 a：剛讀入字符：剛讀入字符OPTR：運算符棧：運算符棧OPND：操作符棧：操作符棧分析算法步驟：分析算法步驟：下一個輸入符號讀至下一個輸入符號讀至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)系，則輸入串錯誤，調(diào)出錯處理，則輸入串錯誤，調(diào)出錯處理)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 為整個表達(dá)式的結(jié)為整個表達(dá)式的結(jié)果果a a1 1 算符優(yōu)先文法算符優(yōu)先文法定義一定義一 如果一個文法的任何產(chǎn)生式右部都不含兩如果一個文法的任何產(chǎn)生式右部都不含兩個相繼（并列）的非終結(jié)符，即不含有如下形式個相繼（并列）

26、的非終結(jié)符，即不含有如下形式的產(chǎn)生式右部：的產(chǎn)生式右部：QRQR則我們稱該文法為則我們稱該文法為算符文法。算符文法。三三 算符優(yōu)先分析算符優(yōu)先分析定義二定義二 假定假定G G是一個不含是一個不含- -產(chǎn)生式的算符文法。對于任產(chǎn)生式的算符文法。對于任何一對終結(jié)符何一對終結(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中的任何終結(jié)符對（中的任何終結(jié)符對（a a，b b）至多只滿足下述三種關(guān)系之一：至多只滿足下述三種關(guān)系之一：a ba b，a ba b，a ba b則稱則稱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)。開始時，按上述的規(guī)則。開始時，按上述的規(guī)則(1)(1)對每個數(shù)對每個數(shù)組元素組元素FPFP，aa賦初值。賦初值。棧棧STACKSTACK，把所有初值為真的數(shù)組元素，把所有初值為真的數(shù)組元素FPFP，aa的符號的符號對對(P(P，a)a)全都放在全都放在STACKSTACK之中。之中。v運算：運算：如果棧如果棧STACKSTACK不空，就將頂項逐出，記此項為不空，就將頂項逐出，記此項為(Q(Q，a)a)。對于每個形如對于每個形如PQPQ 的產(chǎn)生式，若的產(chǎn)生式，若FPFP，aa為假，則變其值為真且將為假，則變其值為真且將(P(P，a)a)推推進(jìn)進(jìn)STACKSTACK棧。棧。上述過程必

31、須一直重復(fù)，直至棧上述過程必須一直重復(fù)，直至棧STACKSTACK拆空為止。拆空為止。lFIRSTVT(P)FIRSTVT(P)的自動構(gòu)造的自動構(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 每個非終結(jié)符每個非終結(jié)符P P和終結(jié)符和終結(jié)符a DO

32、 FP,a := FALSE;a DO FP,a := FALSE; FOR FOR 每個形如每個形如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的頂項，記為的頂項，記為(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這個算法的工作結(jié)果得到

33、一個二維數(shù)組這個算法的工作結(jié)果得到一個二維數(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)的自動構(gòu)造的自動構(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 每個非終結(jié)符每個非終結(jié)符P P和終結(jié)符和終結(jié)符a DO LP,a := FALSE;a DO LP,a := FALSE; FOR FOR 每個形如每個形如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的頂項，記為的頂項，記為(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)先表方法 對文法適當(dāng)改造（增廣文法）之后：對文法適當(dāng)改造（增廣文法）之后： 對形如對形如 P-a

36、bP-ab和形如和形如P-aQbP-aQb，有，有a a b b；對形如對形如 P-aRP-aR，而，而bFIRSTVT(R)bFIRSTVT(R)，有，有a a b b；對形如對形如 P-RbP-Rb，而，而aLASTVT(R)aLASTVT(R)，有，有a a b b；優(yōu)先表中對#的處理(增廣文法)vS是文法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)中的每個中的每個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)中的每個中的每個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#計算每個非終結(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é)符在右邊的符號對有尋找終結(jié)符在左邊，非終結(jié)符在右邊的符號對有 則則+ FIRSTVT(T).* * F則則* * FIRSTVT(F)則則( FIRST

40、VT(E)( E * *, (, id (, id * *, +, (, id 逐條掃描文法規(guī)則，因有逐條掃描文法規(guī)則，因有E(E)的規(guī)則，則有的規(guī)則，則有( ) 尋找非終結(jié)符在左邊，終結(jié)在右邊的符號對有尋找非終結(jié)符在左邊，終結(jié)在右邊的符號對有 E +E +則則LASTVT(E) LASTVT(E) + +則則LASTVT(T) LASTVT(T) * *T T * *則則LASTVT(E) LASTVT(E) ) )E )E )補充：補充：# # # # # # 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è)計算符優(yōu)先分析算法的設(shè)計l定義定義 1 1）文法文法G G，開始符號，開始符號S S，若，若S S ，如果，如果S S 且且 A A ，則稱則稱是句型是句型的一個的一個短語短語。2 2）所謂素短語是指這樣一個短語所謂素短語是指這樣一個短語

42、, ,它至少含有一個它至少含有一個終終結(jié)符結(jié)符, ,并且并且, ,除自身之外除自身之外, ,不再含任何更小的不再含任何更小的素短語素短語。3 3）句型最左邊的那個素短語叫句型最左邊的那個素短語叫最左素短語最左素短語。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定理定理: :一個算符優(yōu)先文法一個算符優(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| | 任何兩個終結(jié)符間任何兩個終結(jié)符間頂多頂多只有一個非終結(jié)符只有一個非終結(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是最左素短語。是最左素短語。對定理的解釋句型 #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 是某個產(chǎn)生式規(guī)則是某個產(chǎn)生式規(guī)則( (其左部設(shè)為其左部設(shè)為R R）的候選式）的候選式; ;根據(jù)根據(jù)最左素短語最左素短語的定理，最左素短語中的終結(jié)符的定理，最左素短語中的終結(jié)符號具有相同的優(yōu)先關(guān)系，并且，由于最左素短語號具有相同的優(yōu)先關(guān)系，并且，由于最左素短語中的符號是當(dāng)時中的符號是當(dāng)時最先要歸約的串最先要歸約的串，其優(yōu)先關(guān)系先，其優(yōu)先關(guān)系先于最左素短語之外的符號，所以我們使用一個用于最左素短語之外的符號，所以我們使用一個用于存放文法符號的于存放文法符號的先進(jìn)后出棧先進(jìn)后出棧，并利用優(yōu)先關(guān)系，并利用優(yōu)先關(guān)系

47、表，可以確定最左素短語是否已形成來決定分析表，可以確定最左素短語是否已形成來決定分析器的動作。器的動作。 l算法分析：算法分析：# #t t1 1t t3 3t tj+1j+1t t2 2t tj jt ti+1i+1t tn n# #符號棧符號棧t ti i 尾尾頭頭最左素短語最左素短語算符優(yōu)先分析程序的基本思想算符優(yōu)先分析程序的基本思想: : . .S j a ? 或或 S j a ?N.=.YS j Q?.N說明說明:算法中算法中K為符號棧為符號棧S的指針，的指針，a用來存放當(dāng)用來存放當(dāng)前輸入符號，前輸入符號，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對于算符優(yōu)先分析法，它雖然是一種自下對于算符優(yōu)先分析法，它雖然是一種自下而上的語法分析方法，但它并不是一種而上的語法分析方法，但它并不是一種規(guī)規(guī)范歸約范歸約的分析方法。的分析方法。WHY?WHY?v這是因為在算符優(yōu)先文法中，僅在終結(jié)符這是因為在算符優(yōu)先文

51、法中，僅在終結(jié)符號之間定義優(yōu)先關(guān)系而未對非終結(jié)符定義號之間定義優(yōu)先關(guān)系而未對非終結(jié)符定義優(yōu)先關(guān)系，從而無法使用優(yōu)先關(guān)系表去識優(yōu)先關(guān)系，從而無法使用優(yōu)先關(guān)系表去識別由別由單個非終結(jié)符單個非終結(jié)符組成的組成的可歸約串可歸約串v算符優(yōu)先分析法不是用算符優(yōu)先分析法不是用句柄句柄來刻畫可歸約來刻畫可歸約串，而是用串，而是用最左素短語最左素短語來刻畫可歸約串的。來刻畫可歸約串的。v算符優(yōu)先分析一般并不等價于規(guī)范歸約。算符優(yōu)先分析一般并不等價于規(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)先分析法特點：算符優(yōu)先分析法特點：優(yōu)點優(yōu)點: : 簡單，快速簡單，快速缺點缺點: : 可能錯誤接受非法句子，能力有限可能錯誤接受非法句子，能力有限. .v算符優(yōu)先分析法是一種廣為應(yīng)用、行之算符優(yōu)先分析法是一種廣為應(yīng)用、行之有效的方法。有效的方法。用于分析各類表達(dá)式用于分析各類表達(dá)式ALGOL 60ALGOL 607 7 優(yōu)先函數(shù)優(yōu)先函數(shù) l定義：定義： 我們把每個終結(jié)符我們

53、把每個終結(jié)符與兩個自然數(shù)與兩個自然數(shù)f( f() ) 和和g(g() )相對相對應(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)缺點：使用優(yōu)先函數(shù)的優(yōu)缺點：優(yōu)：便于比較運算；節(jié)省存儲空間。優(yōu)：便于比較運算；節(jié)省存儲空間。缺：對不存在優(yōu)先關(guān)系的兩個終結(jié)符，由于與自然數(shù)相缺：對不存在優(yōu)先關(guān)系的兩個終結(jié)符，由于與自然數(shù)相 對應(yīng)，變成可比較對應(yīng)，變成可比較。l優(yōu)先函數(shù)的性質(zhì)：優(yōu)先函數(shù)的性質(zhì)：1）正確性：）正確性：優(yōu)先函數(shù)掩蓋了矩陣中出錯元素對，若

54、優(yōu)先函數(shù)掩蓋了矩陣中出錯元素對，若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）唯一性：）唯一性：存在一個優(yōu)先函數(shù)，就有無數(shù)多對，加一常數(shù)，不等存在一個優(yōu)先函數(shù)，就有無數(shù)多對，加一常數(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)造一個有向圖H=(V,E)

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

56、a和和g gb b就在一組；就在一組；若若a ba b，c bc b，則，則f fa a和和f fc c同組；同組；v建立一個有向圖，其結(jié)點是上一步中找出的組。建立一個有向圖，其結(jié)點是上一步中找出的組。對于任何對于任何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ī)范歸約-句柄自下而上(自動生成)遞歸下降-消除左遞歸預(yù)測分析法- 預(yù)測分析表 自上而下(手動，自動生成)語法分析4 4 LR LR分析法分析法lLRLR分析程序分析程序( (器器) )：自左向右自左向右掃描，識別句柄，掃描，識別句柄，自下而上自下而上歸約的歸約的 語法分析程序語法分析程序。lLRLR分析程序生成器：自動生成分析程序生成器：自動生成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 個符號個符號“1” “1” - - 向前查看向前查看 1 1 個符號個符號分析表分析表產(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ù)高級語言絕大多數(shù)高級語言的語法分析器均不適用的語法分析器均不適用),),但卻是建立但卻是建立其它較一般的其它較一般的 LRLR分析法的基礎(chǔ)分析法的基礎(chǔ). .一種較易實現(xiàn)又極有使用價值的方法一種較易實現(xiàn)又極

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