編譯原理5自底向上的語法分析

1、Part5Part5語法分析語法分析授課：胡靜授課：胡靜自底向上的語法分析概述自底向上的語法分析概述目錄目錄自底向上語法分析是一個(gè)更加強(qiáng)大的分析技術(shù)。自底向上語法分析是一個(gè)更加強(qiáng)大的分析技術(shù)。LR文法文法比比LL描述能力更強(qiáng)描述能力更強(qiáng)構(gòu)造程序的最右推導(dǎo)構(gòu)造程序的最右推導(dǎo)幾乎所有的程序設(shè)計(jì)語言都是左遞歸的幾乎所有的程序設(shè)計(jì)語言都是左遞歸的更加容易描述程序設(shè)計(jì)語言的語法。更加容易描述程序設(shè)計(jì)語言的語法。移進(jìn)移進(jìn)-歸約分析歸約分析LR文法的語法分析器文法的語法分析器語法生成器的自動(dòng)生成器語法生成器的自動(dòng)生成器 (e.g., yacc)自頂向下自頂向下vsvs自底向上自底向上自底向上：只需要對當(dāng)前的

2、輸入給出足夠的語法樹的自底向上：只需要對當(dāng)前的輸入給出足夠的語法樹的部分就行部分就行自底向上的語法分析自底向上的語法分析較常用的自底向上語法分析法較常用的自底向上語法分析法移動(dòng)歸約分析法移動(dòng)歸約分析法用棧實(shí)現(xiàn)移動(dòng)歸約分析用棧實(shí)現(xiàn)移動(dòng)歸約分析最易于實(shí)現(xiàn)的移動(dòng)歸約分析法最易于實(shí)現(xiàn)的移動(dòng)歸約分析法算符優(yōu)先分析法算符優(yōu)先分析法算符優(yōu)先分析法定義、優(yōu)先分析表的確定、優(yōu)先函數(shù)的定義算符優(yōu)先分析法定義、優(yōu)先分析表的確定、優(yōu)先函數(shù)的定義使用算符優(yōu)先關(guān)系進(jìn)行分析使用算符優(yōu)先關(guān)系進(jìn)行分析算符優(yōu)先分析中的錯(cuò)誤恢復(fù)算符優(yōu)先分析中的錯(cuò)誤恢復(fù)最一般的移動(dòng)歸約分析方法最一般的移動(dòng)歸約分析方法LR分析法分析法自底向上語法分析

3、概述自底向上語法分析概述自底向上的語法分析方法，也稱為移動(dòng)歸約分析法。自底向上的語法分析方法，也稱為移動(dòng)歸約分析法。最易于實(shí)現(xiàn)的一種移動(dòng)歸約分析方法，叫做算符優(yōu)先分析法，最易于實(shí)現(xiàn)的一種移動(dòng)歸約分析方法，叫做算符優(yōu)先分析法，而更一般的移動(dòng)歸約分析方法叫做而更一般的移動(dòng)歸約分析方法叫做LR分析法，分析法，LR分析法可以用分析法可以用作許多自動(dòng)的語法分析器的生成器。作許多自動(dòng)的語法分析器的生成器。移動(dòng)歸約分析法為輸入串構(gòu)造分析數(shù)時(shí)是從葉結(jié)點(diǎn)（底端）移動(dòng)歸約分析法為輸入串構(gòu)造分析數(shù)時(shí)是從葉結(jié)點(diǎn)（底端）開始，向根結(jié)點(diǎn)（頂端）前進(jìn)。開始，向根結(jié)點(diǎn)（頂端）前進(jìn)。我們可以把該過程看成是把輸入串我們可以把該過

4、程看成是把輸入串“歸約歸約”成文法開始符號的成文法開始符號的過程。過程。在每一步歸約中，如果一個(gè)子串和某個(gè)產(chǎn)生式的右部匹配，則用在每一步歸約中，如果一個(gè)子串和某個(gè)產(chǎn)生式的右部匹配，則用該產(chǎn)生式的左部符號代替該子串。該產(chǎn)生式的左部符號代替該子串。如果每一步都能恰當(dāng)?shù)倪x擇子串，我們就可以得到最右推導(dǎo)的逆如果每一步都能恰當(dāng)?shù)倪x擇子串，我們就可以得到最右推導(dǎo)的逆過程。過程。 移進(jìn)移進(jìn)- -歸約分析歸約分析分析就是移進(jìn)和歸約動(dòng)作的序列分析就是移進(jìn)和歸約動(dòng)作的序列移進(jìn)：將當(dāng)前掃描的移進(jìn)：將當(dāng)前掃描的token移動(dòng)到堆棧中。移動(dòng)到堆棧中。歸約：將棧頂?shù)姆柎畾w約：將棧頂?shù)姆柎?移除，用非終結(jié)符移除，用非終

5、結(jié)符X代替，代替，這對應(yīng)著產(chǎn)生式這對應(yīng)著產(chǎn)生式A (pop , push A)短語、直接短語、句柄的定義：短語、直接短語、句柄的定義：文法文法GS，是文法是文法G的一個(gè)句型，的一個(gè)句型，S=*A且且A=+則稱則稱是句型是句型相對于非終結(jié)符相對于非終結(jié)符A的短語。若有的短語。若有A 則稱則稱是句型是句型相對于該規(guī)則相對于該規(guī)則A的直接短語。一個(gè)句型的最左直接短語稱為該句的直接短語。一個(gè)句型的最左直接短語稱為該句型的句柄。型的句柄。用子樹解釋短語，直接短語，句柄用子樹解釋短語，直接短語，句柄: :短語：一棵子樹的所有葉子自左至右排列起來形成一短語：一棵子樹的所有葉子自左至右排列起來形成一個(gè)相對于子

6、樹根的短語。個(gè)相對于子樹根的短語。直接短語：僅有父子兩代的一棵子樹，它的所有葉子直接短語：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號串。自左至右排列起來所形成的符號串。句柄：一個(gè)句型的分析樹中最左那棵只有父子兩代的句柄：一個(gè)句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。子樹的所有葉子的自左至右排列。例如，對表達(dá)式文法例如，對表達(dá)式文法GE和句子和句子a1+a2*a3，挑選出，挑選出推導(dǎo)過程中產(chǎn)生的句型中的短語，直接短語，句柄。推導(dǎo)過程中產(chǎn)生的句型中的短語，直接短語，句柄。EE+TE+T*FE+T*a3 E+F*a3 E+a2*a3 T+a2 *a3 F

7、+a2*a3E+T T*F,E+T*F a3,T*a3,E+T*a3 a3,F,F*a3,E+F*a3 a3,a2,a2*a3, E+a2*a3a3,a2,T, a2*a3, T+a2*a3a3,a2,F, a2*a3, F+a2*a3a1, a2, a3, a2 * a3 a1+ a2 *a3EE+TTFa1T*FFa2a3a1+a2 *a3短語短語 移動(dòng)歸約分析法相關(guān)概念移動(dòng)歸約分析法相關(guān)概念規(guī)范歸約規(guī)范歸約文法的最右推導(dǎo)為規(guī)范推導(dǎo)，自底向上分析是自頂向下最右推導(dǎo)的逆文法的最右推導(dǎo)為規(guī)范推導(dǎo)，自底向上分析是自頂向下最右推導(dǎo)的逆過程，叫規(guī)范歸約過程，叫規(guī)范歸約句柄句柄直觀來看：一個(gè)符號串的直

8、觀來看：一個(gè)符號串的“句柄句柄”是和一個(gè)產(chǎn)生式右部匹配的子串，是和一個(gè)產(chǎn)生式右部匹配的子串，而且把它歸約到該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)逆過程的一而且把它歸約到該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)逆過程的一步。步。形式定義：右句型（最右推導(dǎo)可得到的句型）形式定義：右句型（最右推導(dǎo)可得到的句型）的句柄是一個(gè)產(chǎn)生式的句柄是一個(gè)產(chǎn)生式A以及以及的一個(gè)位置，在該位置可以找到串的一個(gè)位置，在該位置可以找到串，而且用，而且用A代替代替可以得到可以得到的最右推導(dǎo)的前一個(gè)右句型的最右推導(dǎo)的前一個(gè)右句型對于有二義性的文法而言，由于最右推導(dǎo)不一定，則句柄不一定唯一。對于有二義性的文法而言，由于最右推導(dǎo)不一定

9、，則句柄不一定唯一。只有當(dāng)文法沒有二義性時(shí)，每個(gè)右句型才只有一個(gè)句柄。只有當(dāng)文法沒有二義性時(shí)，每個(gè)右句型才只有一個(gè)句柄。句柄剪裁句柄剪裁通過通過“剪裁句柄剪裁句柄”可以得到最右推導(dǎo)的逆過程可以得到最右推導(dǎo)的逆過程在歸約過程中用到的產(chǎn)生式序列的逆序就是輸入串的最右推導(dǎo)在歸約過程中用到的產(chǎn)生式序列的逆序就是輸入串的最右推導(dǎo)(1)S aABe (2)A b (3)A Abc (4)B dSaABeaAdeaAbcdeabbcde步驟步驟符號棧符號棧輸入符號串輸入符號串 動(dòng)作動(dòng)作1$abbcde$移動(dòng)移動(dòng)2$a bbcde$移動(dòng)移動(dòng)3$ab bcde$歸約歸約(2)4$aA bcde$移動(dòng)移動(dòng)5$aA

10、b cde$移動(dòng)移動(dòng)6$aAbc de$歸約（歸約（3）7$aA de$移動(dòng)移動(dòng)8$aAd e$歸約歸約(4)9$aAB e$移進(jìn)移進(jìn)10$aABe $歸約歸約(1)11$S $接受接受移動(dòng)歸約分析中需要解決的問題移動(dòng)歸約分析中需要解決的問題定位右句型中將要?dú)w約的子串（可歸約串）定位右句型中將要?dú)w約的子串（可歸約串）在用堆棧實(shí)現(xiàn)時(shí)，這個(gè)子串總是在棧頂。語法分析器在用堆棧實(shí)現(xiàn)時(shí)，這個(gè)子串總是在棧頂。語法分析器不需要深入到棧中去尋找句柄不需要深入到棧中去尋找句柄選擇產(chǎn)生式對選定的串進(jìn)行歸約選擇產(chǎn)生式對選定的串進(jìn)行歸約如果選定的子串是多個(gè)產(chǎn)生式的右部，要確定選擇哪如果選定的子串是多個(gè)產(chǎn)生式的右部，要

11、確定選擇哪個(gè)產(chǎn)生式進(jìn)行歸約個(gè)產(chǎn)生式進(jìn)行歸約移動(dòng)歸約分析過程中的沖突移動(dòng)歸約分析過程中的沖突根據(jù)棧中的內(nèi)容和下一個(gè)輸入符號不能決定是移動(dòng)還根據(jù)棧中的內(nèi)容和下一個(gè)輸入符號不能決定是移動(dòng)還是歸約（移動(dòng)是歸約（移動(dòng)-歸約沖突）歸約沖突）不能決定按哪一個(gè)產(chǎn)生式進(jìn)行歸約（歸約不能決定按哪一個(gè)產(chǎn)生式進(jìn)行歸約（歸約-歸約沖突）歸約沖突）算符優(yōu)先分析法算符優(yōu)先分析法 算符優(yōu)先分析法算符優(yōu)先分析法算符文法的定義：算符文法的定義：所有產(chǎn)生式的右部都不是所有產(chǎn)生式的右部都不是或兩個(gè)相鄰的非終結(jié)符或兩個(gè)相鄰的非終結(jié)符設(shè)有一個(gè)文法設(shè)有一個(gè)文法G，如果，如果G中沒有形如中沒有形如ABC的產(chǎn)生式，其中的產(chǎn)生式，其中B和和C為

12、非終結(jié)符，則稱為非終結(jié)符，則稱G為算符文法為算符文法(Operator Grammar)也稱也稱OG文法文法.算符優(yōu)先文法的特點(diǎn)：算符優(yōu)先文法的特點(diǎn)：一旦我們構(gòu)造了算符優(yōu)先語法分析器，就可以忽略原來的文法，一旦我們構(gòu)造了算符優(yōu)先語法分析器，就可以忽略原來的文法，棧中的非終結(jié)符僅僅作為與這些非終結(jié)符相關(guān)的屬性的占位符棧中的非終結(jié)符僅僅作為與這些非終結(jié)符相關(guān)的屬性的占位符難以處理像減號這樣有不同優(yōu)先級的符號難以處理像減號這樣有不同優(yōu)先級的符號由于分析的語言的文法和算符優(yōu)先語法分析器本身的關(guān)系不是很由于分析的語言的文法和算符優(yōu)先語法分析器本身的關(guān)系不是很緊密，所以不能肯定語法分析器接受的就是所期望的

13、語言緊密，所以不能肯定語法分析器接受的就是所期望的語言算符優(yōu)先關(guān)系的定義算符優(yōu)先關(guān)系的定義a的優(yōu)先級低于的優(yōu)先級低于ba b：文法中有形如：文法中有形如A ABbBb的產(chǎn)生式的產(chǎn)生式, ,而而B B+aa或或B B+aCaC算符的優(yōu)先關(guān)系是有序的算符的優(yōu)先關(guān)系是有序的如果如果a b，不能推出，不能推出b b，有可能，有可能b a如果如果a b， b c，不一定，不一定a c算符優(yōu)先關(guān)系定義（續(xù)算符優(yōu)先關(guān)系定義（續(xù)1 1）a b，則存在語法子樹如下，則存在語法子樹如下其中，其中，為為或者或者C C，a a和和b b不在同一個(gè)句柄中，不在同一個(gè)句柄中，a a先被歸約先被歸約A A B Bb b P

14、 Pa a最左素短語最左素短語一個(gè)算符優(yōu)先文法一個(gè)算符優(yōu)先文法G的任何句型的最左素短語是滿足的任何句型的最左素短語是滿足如下條件的最左子串如下條件的最左子串 NjajNiaiNi+1，aj-1ai+1使用算符優(yōu)先關(guān)系使用算符優(yōu)先關(guān)系算符優(yōu)先關(guān)系主要用于界定右句型的句柄算符優(yōu)先關(guān)系主要用于界定右句型的句柄標(biāo)記句柄標(biāo)記句柄的右端。的右端。發(fā)現(xiàn)句柄的過程：發(fā)現(xiàn)句柄的過程：從左端開始掃描串，直到遇到第一個(gè)從左端開始掃描串，直到遇到第一個(gè)為止。為止。向左掃描，跳過所有的向左掃描，跳過所有的=，直到遇到一個(gè)，直到遇到一個(gè)為止。為止。句柄包括從上一步遇到的句柄包括從上一步遇到的左部之間的所左部之間的所有符號

15、，包括介于期間或者兩邊的非終結(jié)符有符號，包括介于期間或者兩邊的非終結(jié)符非終結(jié)符的處理非終結(jié)符的處理因?yàn)榉墙K結(jié)符不能影響語法分析，所以不需要區(qū)分它因?yàn)榉墙K結(jié)符不能影響語法分析，所以不需要區(qū)分它們，于是只用一個(gè)占位符來代替它們們，于是只用一個(gè)占位符來代替它們算符優(yōu)先分析算法算符優(yōu)先分析算法算法的主體思想算法的主體思想用棧存儲已經(jīng)看到的輸入符號，用優(yōu)先關(guān)系指導(dǎo)移動(dòng)用棧存儲已經(jīng)看到的輸入符號，用優(yōu)先關(guān)系指導(dǎo)移動(dòng)歸約語法分析器的動(dòng)作歸約語法分析器的動(dòng)作如果棧頂?shù)慕K結(jié)符和下一個(gè)輸入符之間的優(yōu)先關(guān)系是如果棧頂?shù)慕K結(jié)符和下一個(gè)輸入符之間的優(yōu)先關(guān)系是關(guān)系，就調(diào)用歸約關(guān)系，就調(diào)用歸約算法描述算法描述輸入：輸入字符

16、串輸入：輸入字符串和優(yōu)先關(guān)系表和優(yōu)先關(guān)系表輸出：如果輸出：如果是語法產(chǎn)生的一個(gè)句子，則輸出其用來是語法產(chǎn)生的一個(gè)句子，則輸出其用來歸約的產(chǎn)生式；如果有錯(cuò)誤，則轉(zhuǎn)入錯(cuò)誤處理歸約的產(chǎn)生式；如果有錯(cuò)誤，則轉(zhuǎn)入錯(cuò)誤處理規(guī)范歸約和算符優(yōu)先歸約規(guī)范歸約和算符優(yōu)先歸約句型句型#i+i#的規(guī)范歸約過程的規(guī)范歸約過程步驟步驟符號棧符號棧剩余輸入串剩余輸入串 句柄句柄 歸約用產(chǎn)生式歸約用產(chǎn)生式1# i+i# 2#i +i# i Pi4#F +i# F TF5#T +i# T ET6#E +i#7#E+ i#8#E+i # i Pi10#E+F # F TF11#E+T # E+T EE+T12#E # 接受接受E

17、 = #E# = #E+T# = #E+F# = #E+P# = #E+i# = #T+i# = #F+i# = #P+i# = #i+i#3#P +i# P FP9#E+P # P FP規(guī)范歸約和算符優(yōu)先歸約規(guī)范歸約和算符優(yōu)先歸約句型句型#i+i#的算符優(yōu)先歸約過程的算符優(yōu)先歸約過程步驟步驟棧棧 優(yōu)先關(guān)系優(yōu)先關(guān)系 當(dāng)前符號當(dāng)前符號 剩余符號串剩余符號串 動(dòng)作動(dòng)作1 1# # i +i# + i# + i# 歸約歸約3 3#P#P + i# + i# 移進(jìn)移進(jìn)3 3#P+#P+ i # # # 歸約歸約4 4#P+P#P+P # # 歸約歸約4 4#E#E = # = # 接受接受算符優(yōu)先分析

18、法優(yōu)缺點(diǎn)算符優(yōu)先分析法優(yōu)缺點(diǎn)由于算符優(yōu)先分析并未對文法的非終結(jié)符定義優(yōu)先關(guān)由于算符優(yōu)先分析并未對文法的非終結(jié)符定義優(yōu)先關(guān)系，所以就無法發(fā)現(xiàn)由單個(gè)非終結(jié)符組成的系，所以就無法發(fā)現(xiàn)由單個(gè)非終結(jié)符組成的“可歸約可歸約串串”。也就是說，在算符優(yōu)先歸約過程中，我們無法用那些也就是說，在算符優(yōu)先歸約過程中，我們無法用那些右部僅含一個(gè)非終結(jié)符的產(chǎn)生式（稱為單非產(chǎn)生式，右部僅含一個(gè)非終結(jié)符的產(chǎn)生式（稱為單非產(chǎn)生式，如如PQ）進(jìn)行歸約。這樣，算符優(yōu)先分析比規(guī)范歸）進(jìn)行歸約。這樣，算符優(yōu)先分析比規(guī)范歸約要快很多。這既是算符優(yōu)先分析的優(yōu)點(diǎn)，也是它的約要快很多。這既是算符優(yōu)先分析的優(yōu)點(diǎn)，也是它的缺點(diǎn)。缺點(diǎn)。忽略非終結(jié)

19、符在歸約過程中的作用，存在某種危險(xiǎn)性，忽略非終結(jié)符在歸約過程中的作用，存在某種危險(xiǎn)性，可能導(dǎo)致把本來不成句子的輸入串誤認(rèn)為是句子。可能導(dǎo)致把本來不成句子的輸入串誤認(rèn)為是句子。 優(yōu)先函數(shù)優(yōu)先函數(shù)優(yōu)先函數(shù)的計(jì)算方法優(yōu)先函數(shù)的計(jì)算方法1.f(a) g(b)，如果，如果a g(b)，如果，如果a b優(yōu)先函數(shù)的問題優(yōu)先函數(shù)的問題使得優(yōu)先關(guān)系表中的空白項(xiàng)是模糊的使得優(yōu)先關(guān)系表中的空白項(xiàng)是模糊的使得錯(cuò)誤的發(fā)現(xiàn)被推遲使得錯(cuò)誤的發(fā)現(xiàn)被推遲優(yōu)先關(guān)系表的存儲方式優(yōu)先關(guān)系表的存儲方式矩陣表示：準(zhǔn)確直觀；需要大量內(nèi)存空間矩陣表示：準(zhǔn)確直觀；需要大量內(nèi)存空間(n+1)(n+1)2 2優(yōu)先函數(shù)：需要內(nèi)存空間小優(yōu)先函數(shù)：需要

20、內(nèi)存空間小2(n+1)2(n+1)；不利于出錯(cuò)處理；不利于出錯(cuò)處理優(yōu)先函數(shù)的構(gòu)造算法優(yōu)先函數(shù)的構(gòu)造算法輸入：算符優(yōu)先表輸入：算符優(yōu)先表輸出：表示輸入矩陣的優(yōu)先函數(shù)或指出它不存在輸出：表示輸入矩陣的優(yōu)先函數(shù)或指出它不存在方法：方法：為每個(gè)終結(jié)符（包括為每個(gè)終結(jié)符（包括#）創(chuàng)建）創(chuàng)建fa和和ga。并以其作為結(jié)點(diǎn)，畫出。并以其作為結(jié)點(diǎn)，畫出2n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)如果如果a b或者或者a = b，則畫一條從，則畫一條從fa到到gb的箭弧的箭弧如果如果a b或者或者a = b，則畫一條從，則畫一條從gb到到fa的箭弧的箭弧如果構(gòu)造的圖中有環(huán)路，則不存在優(yōu)先函數(shù)；如果沒有環(huán)路，則如果構(gòu)造的圖中有環(huán)路，則不存在優(yōu)

21、先函數(shù)；如果沒有環(huán)路，則將將f(a)設(shè)為從設(shè)為從fa開始的最長路徑的長度；開始的最長路徑的長度；g(a)為從為從ga開始的最長路開始的最長路徑的長度。徑的長度。檢查是否一致！檢查是否一致！實(shí)例說明實(shí)例說明i*+$i*+$=figig*f*f+g+g#f#i*+$fg45432100檢查是否一致！檢查是否一致！算符優(yōu)先分析中的錯(cuò)誤恢復(fù)算符優(yōu)先分析中的錯(cuò)誤恢復(fù)算符優(yōu)先分析器能發(fā)現(xiàn)的語法錯(cuò)誤算符優(yōu)先分析器能發(fā)現(xiàn)的語法錯(cuò)誤如果棧頂?shù)慕K結(jié)符和當(dāng)前輸入之間沒有優(yōu)先關(guān)系（如如果棧頂?shù)慕K結(jié)符和當(dāng)前輸入之間沒有優(yōu)先關(guān)系（如果用優(yōu)先函數(shù)存儲，這個(gè)錯(cuò)誤不能發(fā)現(xiàn)）果用優(yōu)先函數(shù)存儲，這個(gè)錯(cuò)誤不能發(fā)現(xiàn)）如果發(fā)現(xiàn)句柄，但句

22、柄不是任何產(chǎn)生式的右部如果發(fā)現(xiàn)句柄，但句柄不是任何產(chǎn)生式的右部歸約時(shí)的錯(cuò)誤處理歸約時(shí)的錯(cuò)誤處理給出相應(yīng)的具有描述性的出錯(cuò)信息給出相應(yīng)的具有描述性的出錯(cuò)信息試圖通過插入、刪除來獲得句柄試圖通過插入、刪除來獲得句柄一個(gè)加入了出錯(cuò)處理的優(yōu)先矩陣一個(gè)加入了出錯(cuò)處理的優(yōu)先矩陣E1：缺少整個(gè)表達(dá)式：缺少整個(gè)表達(dá)式把把id插入輸入字符串中插入輸入字符串中輸出診斷信息輸出診斷信息Missing operandE2：表達(dá)式以右括號開始：表達(dá)式以右括號開始從輸入中刪除從輸入中刪除 )輸出診斷信息輸出診斷信息Unbalanced right parenthesisE3：id/)后面跟后面跟id/(把把+插入輸入字符

23、串插入輸入字符串輸出診斷信息輸出診斷信息Missing operatorE4：表達(dá)式以左括號結(jié)束：表達(dá)式以左括號結(jié)束從棧中彈出從棧中彈出(輸出診斷信息輸出診斷信息Missing right parenthesisid()$idE3E3($aABeaAdeaAbcdeabbcde步驟步驟符號棧符號棧輸入符號串輸入符號串 動(dòng)作動(dòng)作1$abbcde$移動(dòng)移動(dòng)2$a bbcde$移動(dòng)移動(dòng)3$ab bcde$歸約歸約(2)4$aA bcde$移動(dòng)移動(dòng)5$aAb cde$移動(dòng)移動(dòng)6$aAbc de$歸約（歸約（3）7$aA de$移動(dòng)移動(dòng)8$aAd e$歸約歸約(4)9$aAB e$移進(jìn)移進(jìn)10$aABe

24、 $歸約歸約(1)11$S $接受接受LRLR語法分析算法語法分析算法 LR分析的基本思想是，在規(guī)范歸約過程中，一方面分析的基本思想是，在規(guī)范歸約過程中，一方面記住已移進(jìn)和歸約出的整個(gè)符號串，即記住記住已移進(jìn)和歸約出的整個(gè)符號串，即記住“歷史歷史”，另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入符號，即對未來進(jìn)行符號，即對未來進(jìn)行“展望展望”。當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧的頂端時(shí)，我當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧的頂端時(shí)，我們希望能夠根據(jù)所記載的們希望能夠根據(jù)所記載的“歷史歷史”和和“展望展望”以及以及“現(xiàn)實(shí)現(xiàn)實(shí)”的輸入符號等三方面的材料

25、，來確定棧頂?shù)牡妮斎敕柕热矫娴牟牧希瑏泶_定棧頂?shù)姆柎欠駱?gòu)成相對某一產(chǎn)生式的句柄。符號串是否構(gòu)成相對某一產(chǎn)生式的句柄。 LRLR語法分析器的結(jié)構(gòu)語法分析器的結(jié)構(gòu)一個(gè)一個(gè)LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲器（棧）的確定分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲器（棧）的確定有限狀態(tài)自動(dòng)機(jī)。有限狀態(tài)自動(dòng)機(jī)。棧棧LR分分析析程程序序actiongoto輸輸出出輸輸入入串串a(chǎn)1SmS1S0XmX1#aian#分分析析表表LRLR語法分析器的結(jié)構(gòu)語法分析器的結(jié)構(gòu)棧棧我們將把我們將把“歷史歷史”和和“展望展望”材料綜合的抽象成某些材料綜合的抽象成某些“狀狀態(tài)態(tài)”，存放在棧里。棧里的每個(gè)狀態(tài)概括了從分析開始直

26、到，存放在棧里。棧里的每個(gè)狀態(tài)概括了從分析開始直到某一歸約階段的全部某一歸約階段的全部“歷史歷史”和和“展望展望”資料。資料。 SmS1S0XmX1X0棧頂棧頂狀態(tài)狀態(tài)符號符號LRLR語法分析器的結(jié)構(gòu)語法分析器的結(jié)構(gòu)分析表分析表ACTIONs ,a規(guī)定了當(dāng)前狀態(tài)規(guī)定了當(dāng)前狀態(tài)s面臨輸入符號面臨輸入符號a時(shí)應(yīng)采時(shí)應(yīng)采取什么動(dòng)作。取什么動(dòng)作。GOTOs, X規(guī)定了狀態(tài)規(guī)定了狀態(tài)s面對文法符號面對文法符號X（終結(jié)符或（終結(jié)符或非終結(jié)符）時(shí)下一個(gè)狀態(tài)是什么。非終結(jié)符）時(shí)下一個(gè)狀態(tài)是什么。 LRLR語法分析器的結(jié)構(gòu)語法分析器的結(jié)構(gòu)ACTIONACTION表表每一項(xiàng)每一項(xiàng)ACTIONs,a所規(guī)定的動(dòng)作不外

27、是下述四種可所規(guī)定的動(dòng)作不外是下述四種可能之一。能之一。移進(jìn)：把移進(jìn)：把(s,a)的下一個(gè)狀態(tài)的下一個(gè)狀態(tài)s=GOTOs,a和輸入符號和輸入符號a推進(jìn)棧，下一個(gè)輸入符號變成現(xiàn)行輸入符號推進(jìn)棧，下一個(gè)輸入符號變成現(xiàn)行輸入符號歸約：指用某一個(gè)產(chǎn)生式歸約：指用某一個(gè)產(chǎn)生式A進(jìn)行歸約。假若進(jìn)行歸約。假若的長的長度為度為r，歸約的動(dòng)作是，歸約的動(dòng)作是A，去除棧頂?shù)?，去除棧頂?shù)膔個(gè)項(xiàng)，使?fàn)顟B(tài)個(gè)項(xiàng)，使?fàn)顟B(tài)Sm-r變成棧頂狀態(tài)，然后把（變成棧頂狀態(tài)，然后把（Sm-r, A）的下一個(gè)狀態(tài)）的下一個(gè)狀態(tài)s=GOTOSm-r, A和文法符號和文法符號A推進(jìn)棧。推進(jìn)棧。接受：宣布分析成功，停止分析器的工作。接受：宣布

28、分析成功，停止分析器的工作。報(bào)錯(cuò)：發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。報(bào)錯(cuò)：發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。 LRLR語法分析器分析過程舉例語法分析器分析過程舉例文法文法G：(1)E E+T (2)E T(3)T T*F (4)T F (5)F (E)(6)F i狀態(tài)狀態(tài)ACTIONGOTOi+*（）#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5對上述例子的分析對上述例子的分析LR語法分析器不需要掃描整個(gè)棧就可以知道什么時(shí)語法分析

29、器不需要掃描整個(gè)棧就可以知道什么時(shí)候句柄出現(xiàn)在棧頂。棧頂?shù)臓顟B(tài)符號包含了所需要的候句柄出現(xiàn)在棧頂。棧頂?shù)臓顟B(tài)符號包含了所需要的一切信息。一切信息。 請注意一個(gè)非常重要的事實(shí)：如果僅由棧的內(nèi)容和現(xiàn)請注意一個(gè)非常重要的事實(shí)：如果僅由棧的內(nèi)容和現(xiàn)實(shí)的輸入符號就可以識別一個(gè)句柄，那么就可以用一實(shí)的輸入符號就可以識別一個(gè)句柄，那么就可以用一個(gè)有限自動(dòng)機(jī)自底向上掃描棧的內(nèi)容和檢查現(xiàn)行輸入個(gè)有限自動(dòng)機(jī)自底向上掃描棧的內(nèi)容和檢查現(xiàn)行輸入符號來確定呈現(xiàn)于棧頂?shù)木浔鞘裁矗ó?dāng)棧頂呈現(xiàn)一符號來確定呈現(xiàn)于棧頂?shù)木浔鞘裁矗ó?dāng)棧頂呈現(xiàn)一個(gè)句柄時(shí)）。個(gè)句柄時(shí)）。 實(shí)際上，實(shí)際上，LR分析表的分析表的goto函數(shù)就是這樣一

30、個(gè)有限自函數(shù)就是這樣一個(gè)有限自動(dòng)機(jī)，只是它不需要每次移動(dòng)都讀棧。動(dòng)機(jī)，只是它不需要每次移動(dòng)都讀棧。 LRLR文法與文法與LLLL文法的區(qū)別文法的區(qū)別LL文法要求每個(gè)非終結(jié)符的所有候選首字符均不相文法要求每個(gè)非終結(jié)符的所有候選首字符均不相同，因?yàn)轭A(yù)測程序認(rèn)為，一旦看到首符之后就看準(zhǔn)了同，因?yàn)轭A(yù)測程序認(rèn)為，一旦看到首符之后就看準(zhǔn)了該用哪一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。該用哪一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。但但LR分析程序只有在看到整個(gè)右部所推導(dǎo)的東西之分析程序只有在看到整個(gè)右部所推導(dǎo)的東西之后才認(rèn)為是看準(zhǔn)了歸約方向。因此，后才認(rèn)為是看準(zhǔn)了歸約方向。因此，LR方法比方法比LL方方法更加一般化。法更加一般化。 LR(0)LR

31、(0)項(xiàng)目集族和項(xiàng)目集族和LR(0)LR(0)分析表的構(gòu)造分析表的構(gòu)造 相關(guān)概念：相關(guān)概念：前綴：字的前綴是指該字的任意首部。前綴：字的前綴是指該字的任意首部。字字abc的前綴有的前綴有、a、ab、abc?；钋熬Y：指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄活前綴：指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后任何符號。之所以稱為活前綴，是因?yàn)樵谟疫吿碇笕魏畏?。之所以稱為活前綴，是因?yàn)樵谟疫吿砑右恍┓栔?，就可以使它稱為一個(gè)規(guī)范句型。加一些符號之首，就可以使它稱為一個(gè)規(guī)范句型。在在LR分析工作過程中的任何時(shí)候，棧里的文法符號分析工作過程中的任何時(shí)候，棧里的文法符號（自棧底而上）（自棧底而上）X0

32、X1 Xm應(yīng)該構(gòu)成活前綴，把輸入應(yīng)該構(gòu)成活前綴，把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型。串的剩余部分配上之后即應(yīng)成為規(guī)范句型。只要輸入串的已掃描部分保持可歸約成一個(gè)活前綴，那只要輸入串的已掃描部分保持可歸約成一個(gè)活前綴，那就意味著所掃描過的部分沒有錯(cuò)誤。就意味著所掃描過的部分沒有錯(cuò)誤。 LR(0)LR(0)項(xiàng)目的定義項(xiàng)目的定義對于一個(gè)文法對于一個(gè)文法G，我們首先要構(gòu)造一個(gè)，我們首先要構(gòu)造一個(gè)NFA，它能識，它能識別別G的所有活前綴。這個(gè)的所有活前綴。這個(gè)NFA的每一個(gè)狀態(tài)是下面定的每一個(gè)狀態(tài)是下面定義的一個(gè)義的一個(gè)“項(xiàng)目項(xiàng)目”。 文法文法G的每一個(gè)產(chǎn)生式的右部添加一個(gè)圓點(diǎn)稱為的每一個(gè)產(chǎn)生式

33、的右部添加一個(gè)圓點(diǎn)稱為G的的一個(gè)一個(gè)LR(0)項(xiàng)目（簡稱項(xiàng)目）。例如產(chǎn)生式項(xiàng)目（簡稱項(xiàng)目）。例如產(chǎn)生式AXYZ對應(yīng)有四個(gè)項(xiàng)目：對應(yīng)有四個(gè)項(xiàng)目：AXYZAXYZAXYZAXYZ 產(chǎn)生式產(chǎn)生式A只對應(yīng)一個(gè)項(xiàng)目只對應(yīng)一個(gè)項(xiàng)目A。 LR(0)LR(0)項(xiàng)目的說明項(xiàng)目的說明直觀上說，一個(gè)項(xiàng)目指明了在分析過程的某時(shí)刻我們直觀上說，一個(gè)項(xiàng)目指明了在分析過程的某時(shí)刻我們看到產(chǎn)生式多大部分?？吹疆a(chǎn)生式多大部分。例如，例如， AXYZ這個(gè)項(xiàng)目意味著，我們希望能從后面這個(gè)項(xiàng)目意味著，我們希望能從后面輸入串中看到可以從輸入串中看到可以從XYZ推出的符號串。推出的符號串。AXYZ這個(gè)項(xiàng)目意味著，我們已經(jīng)從輸入串中看到這

34、個(gè)項(xiàng)目意味著，我們已經(jīng)從輸入串中看到能從能從X推出的符號串，我們希望能進(jìn)一步看到可以從推出的符號串，我們希望能進(jìn)一步看到可以從YZ推出的符號串。推出的符號串。 將每個(gè)項(xiàng)目看成將每個(gè)項(xiàng)目看成NFA的一個(gè)狀態(tài)，我們就可以構(gòu)造這的一個(gè)狀態(tài)，我們就可以構(gòu)造這樣一個(gè)樣一個(gè)NFA，用來識別文法所有的活前綴。，用來識別文法所有的活前綴。 LR(0)LR(0)項(xiàng)目間的轉(zhuǎn)換規(guī)則項(xiàng)目間的轉(zhuǎn)換規(guī)則如果狀態(tài)如果狀態(tài)i和和j來自同一個(gè)產(chǎn)生式，而且狀態(tài)來自同一個(gè)產(chǎn)生式，而且狀態(tài)j的圓點(diǎn)的圓點(diǎn)只落后于狀態(tài)只落后于狀態(tài)i的原點(diǎn)一個(gè)位置，的原點(diǎn)一個(gè)位置，如狀態(tài)如狀態(tài)i為為XX1 Xi-1 XiXn，狀態(tài)狀態(tài)j為為XX1 Xi

35、Xi+1Xn，那么就從狀態(tài)那么就從狀態(tài)i畫一條標(biāo)志為畫一條標(biāo)志為Xi的弧到狀態(tài)的弧到狀態(tài)j。假若狀態(tài)假若狀態(tài)i的圓點(diǎn)之后的那個(gè)符號為非終結(jié)符，的圓點(diǎn)之后的那個(gè)符號為非終結(jié)符，如如i為為XA，A為非終結(jié)符，為非終結(jié)符，就從狀態(tài)就從狀態(tài)i畫畫弧到所有弧到所有A狀態(tài)。狀態(tài)。NFA的接受狀態(tài)就是那些圓點(diǎn)出現(xiàn)在最右邊的項(xiàng)目。的接受狀態(tài)就是那些圓點(diǎn)出現(xiàn)在最右邊的項(xiàng)目。LR(0)LR(0)項(xiàng)目分類項(xiàng)目分類歸約項(xiàng)目歸約項(xiàng)目凡圓點(diǎn)在最右的項(xiàng)目，如凡圓點(diǎn)在最右的項(xiàng)目，如A稱為一個(gè)稱為一個(gè)“歸約項(xiàng)目歸約項(xiàng)目” 接受項(xiàng)目接受項(xiàng)目對文法的開始符號對文法的開始符號S的歸約項(xiàng)目，如的歸約項(xiàng)目，如S稱為稱為“接受接受”項(xiàng)目。

36、項(xiàng)目。 移進(jìn)項(xiàng)目移進(jìn)項(xiàng)目形如形如Aa的項(xiàng)目，其中的項(xiàng)目，其中a為終結(jié)符，稱為為終結(jié)符，稱為“移進(jìn)移進(jìn)”項(xiàng)目。項(xiàng)目。待約項(xiàng)目待約項(xiàng)目形如形如AB的項(xiàng)目，其中的項(xiàng)目，其中B為非終結(jié)符，稱為為非終結(jié)符，稱為“待約待約”項(xiàng)目。項(xiàng)目。 識別識別LR(0)LR(0)活前綴的活前綴的NFANFA舉例舉例文法文法G：S EE aA | bB A cA | dB cB | d文法的項(xiàng)目有：文法的項(xiàng)目有：14. B cB 15. B cB 16. B cB 3. E aA4. E aA5. E aA6. A cA7. A cA8. A cA11. E bB12. E bB13. E bB17. B d 18. B

37、 d1. S E2. S E 9. A d10. A d 識別識別LR(0)LR(0)活前綴的活前綴的NFANFA舉例（續(xù)）舉例（續(xù)）初態(tài)初態(tài)S E 1句柄識別態(tài)句柄識別態(tài)E aA5A cA8A d 10E bB13B cB 16B d18句子識別態(tài)句子識別態(tài)S E 214. B cB 15. B cB 16. B cB 3. E aA4. E aA5. E aA6. A cA7. A cA8. A cA11. E bB12. E bB13. E bB17. B d 18. B d1. S E2. S E 9. A d10. A d 1. S E2. S E 3. E aA4. E aA5.

38、E aA6. A cA7. A cA8. A cA9. A d10. A d 11. E bB12. E bB13. E bB16. B cB 15. B cB 14. B cB 18. B d17. B d EaAcAdbBcBd0. S E E aA E bB2. E aA A cA A d1. S E3. E bB B cB B d4. A cA A cA A d5. B cB B cB B d8. A cA10. A d6. E aA7. E bB11. B d9. B cBbEaccccABdAdddBLR(0)LR(0)項(xiàng)目集規(guī)范族的構(gòu)造項(xiàng)目集規(guī)范族的構(gòu)造用用-CLOSURE(閉包

39、閉包)的辦法來構(gòu)造一個(gè)文法的辦法來構(gòu)造一個(gè)文法G的的LR(0)項(xiàng)目集規(guī)范族。項(xiàng)目集規(guī)范族。準(zhǔn)備工作：準(zhǔn)備工作：假定文法假定文法G是一個(gè)以是一個(gè)以S為開始符號的文法，我們構(gòu)造一為開始符號的文法，我們構(gòu)造一個(gè)文法個(gè)文法G，它包含整個(gè)，它包含整個(gè)G，但它引進(jìn)了一個(gè)不出現(xiàn)在，但它引進(jìn)了一個(gè)不出現(xiàn)在G中的非終結(jié)符中的非終結(jié)符S，并加進(jìn)一個(gè)新產(chǎn)生式，并加進(jìn)一個(gè)新產(chǎn)生式SS，而這個(gè)，而這個(gè)S是是G的開始符號。那么我們稱的開始符號。那么我們稱G是是G的拓廣文法。的拓廣文法。 這樣，便會有一個(gè)僅含項(xiàng)目這樣，便會有一個(gè)僅含項(xiàng)目SS的狀態(tài)，這就是唯的狀態(tài)，這就是唯一的一的“接受接受”狀態(tài)。狀態(tài)。 LR(0)LR(0

40、)項(xiàng)目集規(guī)范族的構(gòu)造項(xiàng)目集規(guī)范族的構(gòu)造假定假定I是文法是文法G的任一項(xiàng)目集，定義和構(gòu)造的任一項(xiàng)目集，定義和構(gòu)造I的閉包的閉包CLOSURE(I)的辦法是：的辦法是： I的任何項(xiàng)目都屬于的任何項(xiàng)目都屬于CLOSURE(I)；若若AB屬于屬于CLOSURE(I)，那么，對任何關(guān)于，那么，對任何關(guān)于B的產(chǎn)生式的產(chǎn)生式B，項(xiàng)目，項(xiàng)目B也屬于也屬于CLOSURE(I)；重復(fù)執(zhí)行上述兩步驟直至重復(fù)執(zhí)行上述兩步驟直至CLOSURE(I)不再增大為止。不再增大為止。函數(shù)函數(shù)GO(I,X)是一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)。是一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)。第一個(gè)變元第一個(gè)變元I是一個(gè)項(xiàng)目集，是一個(gè)項(xiàng)目集，第二個(gè)變元第二個(gè)變元X是一個(gè)文法符

41、號。是一個(gè)文法符號。函數(shù)值函數(shù)值GO(I,X)定義為定義為GO(I,X)=CLOSURE(J)，其中其中J=任何形如任何形如AX的項(xiàng)目的項(xiàng)目 | AX屬于屬于I LR(0)LR(0)項(xiàng)目集規(guī)范族舉例項(xiàng)目集規(guī)范族舉例初始狀態(tài)初始狀態(tài)I0的項(xiàng)目集規(guī)范族：的項(xiàng)目集規(guī)范族：S EE aAE bBI1、I2、I3和分別是和分別是GO(I0,E)、 GO(I0,a)和和GO(I0,b)I1是是CLOSURE(SE)=SEI2是是CLOSURE(EaA)=EaA, AcA, AdI3是是CLOSURE(EbB)=EbB, BcB, Bd文法文法G：(0) S E(1) E aA (2) E bB (3) A

42、 cA(4) A d(5) B cB(6) B d0. S E E aA E bB2. E aA A cA A d1. S E3. E bB B cB B d4. A cA A cA A d5. B cB B cB B d8. A cA10. A d6. E aA7. E bB11. B d9. B cBbEaccccABdAdddBLR(0)LR(0)項(xiàng)目集規(guī)范族的討論項(xiàng)目集規(guī)范族的討論有效項(xiàng)目有效項(xiàng)目我們說項(xiàng)目我們說項(xiàng)目A12對活前綴對活前綴1是有效的，其條件是存在規(guī)范是有效的，其條件是存在規(guī)范推導(dǎo)推導(dǎo)S=*A=12。LR(0)項(xiàng)目集可能出現(xiàn)的沖突項(xiàng)目集可能出現(xiàn)的沖突同一項(xiàng)目可能對好幾個(gè)活

43、前綴都是有效的（當(dāng)一個(gè)項(xiàng)目出現(xiàn)在同一項(xiàng)目可能對好幾個(gè)活前綴都是有效的（當(dāng)一個(gè)項(xiàng)目出現(xiàn)在好幾個(gè)不同的集合中便是這種情況）。好幾個(gè)不同的集合中便是這種情況）。若歸約項(xiàng)目若歸約項(xiàng)目A1對活前綴對活前綴1是有效的，則它告訴我們應(yīng)該是有效的，則它告訴我們應(yīng)該把符號串把符號串1歸于為歸于為A。即把活前綴。即把活前綴1變成變成A。若移進(jìn)項(xiàng)目若移進(jìn)項(xiàng)目A12對活前綴對活前綴1是有效的，則它告訴我們，句是有效的，則它告訴我們，句柄尚未形成，因此，下一步動(dòng)作應(yīng)該是移進(jìn)。柄尚未形成，因此，下一步動(dòng)作應(yīng)該是移進(jìn)。但是，可能存在這樣的情形，對同一活前綴，存在若干項(xiàng)目對但是，可能存在這樣的情形，對同一活前綴，存在若干項(xiàng)目

44、對它都是有效的，而且告訴我們應(yīng)該做的事情各不相同，互相沖它都是有效的，而且告訴我們應(yīng)該做的事情各不相同，互相沖突。這種沖突通過向前多看幾個(gè)輸入符號，或許能夠解決，但突。這種沖突通過向前多看幾個(gè)輸入符號，或許能夠解決，但有些沖突卻是無法解決的。有些沖突卻是無法解決的。 LR(0)LR(0)分析表的構(gòu)造分析表的構(gòu)造假如一個(gè)文法假如一個(gè)文法G的拓廣文法的拓廣文法G的活前綴識別自動(dòng)機(jī)的的活前綴識別自動(dòng)機(jī)的每個(gè)狀態(tài)（項(xiàng)目集）不存在下述情況：每個(gè)狀態(tài)（項(xiàng)目集）不存在下述情況：既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目。既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目。含多個(gè)歸約項(xiàng)目。含多個(gè)歸約項(xiàng)目。則稱則稱G是一個(gè)是一個(gè)LR(0)文法。換言之，文

45、法。換言之，LR(0)文法規(guī)范族文法規(guī)范族的每個(gè)項(xiàng)目集不包含任何沖突項(xiàng)目。的每個(gè)項(xiàng)目集不包含任何沖突項(xiàng)目。 LR(0)LR(0)分析表的構(gòu)造分析表的構(gòu)造假定項(xiàng)目集規(guī)范族假定項(xiàng)目集規(guī)范族C=I0,I1,In。令每一個(gè)項(xiàng)目集。令每一個(gè)項(xiàng)目集Ik的下標(biāo)的下標(biāo)k作為分析器的狀態(tài)。分析表的作為分析器的狀態(tài)。分析表的ACTION子表和子表和GOTO子表可子表可按如下方法構(gòu)造按如下方法構(gòu)造令那個(gè)包含項(xiàng)目令那個(gè)包含項(xiàng)目SS的集合的集合Ik的下標(biāo)的下標(biāo)k為分析器的初態(tài)。為分析器的初態(tài)。 若項(xiàng)目若項(xiàng)目Aa屬于屬于Ik且且GO(Ik , a)= Ij,a為終結(jié)符，置為終結(jié)符，置ACTIONk,a為為“把把(j,a)

46、移進(jìn)棧移進(jìn)棧”，簡記為，簡記為“sj”。若項(xiàng)目若項(xiàng)目A屬于屬于Ik，對任何終結(jié)符，對任何終結(jié)符a(或結(jié)束符或結(jié)束符#)，置，置ACTIONk,a為為“用產(chǎn)生式用產(chǎn)生式A進(jìn)行歸約進(jìn)行歸約”，簡記為，簡記為“rj”（假定產(chǎn)生式（假定產(chǎn)生式A是文法是文法G的第的第j個(gè)產(chǎn)生式）。個(gè)產(chǎn)生式）。若項(xiàng)目若項(xiàng)目SS屬于屬于Ik，則置，則置ACTIONk,#為為“接受接受”，簡記為，簡記為“acc”。若若GO(Ik , A)= Ij，A為非終結(jié)符，則置為非終結(jié)符，則置GOTOk,A=j。分析表中凡不能用規(guī)則分析表中凡不能用規(guī)則1至至4填入信息的空白格均填上填入信息的空白格均填上“報(bào)錯(cuò)標(biāo)志報(bào)錯(cuò)標(biāo)志”。 0. S

47、E E aA E bB2. E aA A cA A d1. S E3. E bB B cB B d4. A cA A cA A d5. B cB B cB B d8. A cA10. A d6. E aA7. E bB11. B d9. B cBbEaccccABdAdddBSLRSLR分析表的構(gòu)造分析表的構(gòu)造SLRSLR語法分析概述語法分析概述LR(0)文法的活前綴識別自動(dòng)機(jī)的每一個(gè)狀態(tài)（項(xiàng)目文法的活前綴識別自動(dòng)機(jī)的每一個(gè)狀態(tài)（項(xiàng)目集）都不含沖突的項(xiàng)目。集）都不含沖突的項(xiàng)目。本節(jié)我們要研究一種有點(diǎn)簡單本節(jié)我們要研究一種有點(diǎn)簡單“展望展望”材料的材料的LR分分析法，即析法，即SLR文法。文法。

48、SLR文法構(gòu)造分析表的主要思想是：許多沖突性的動(dòng)文法構(gòu)造分析表的主要思想是：許多沖突性的動(dòng)作都可能通過考察有關(guān)非終結(jié)符的作都可能通過考察有關(guān)非終結(jié)符的FOLLOW集而獲集而獲解決。解決。 LR(0)LR(0)文法的局限性文法的局限性假定一個(gè)假定一個(gè)LR(0)規(guī)范族中含有如下的一個(gè)項(xiàng)目集（狀規(guī)范族中含有如下的一個(gè)項(xiàng)目集（狀態(tài)）態(tài)）I：I=Xb, A, B第一個(gè)項(xiàng)目是移進(jìn)項(xiàng)目，第二、三個(gè)項(xiàng)目是歸約項(xiàng)目。第一個(gè)項(xiàng)目是移進(jìn)項(xiàng)目，第二、三個(gè)項(xiàng)目是歸約項(xiàng)目。這三個(gè)項(xiàng)目告訴我們應(yīng)該做的動(dòng)作各不相同，互相沖這三個(gè)項(xiàng)目告訴我們應(yīng)該做的動(dòng)作各不相同，互相沖突：突：第一個(gè)項(xiàng)目告訴我們應(yīng)該把下一個(gè)符號第一個(gè)項(xiàng)目告訴我

49、們應(yīng)該把下一個(gè)符號b移進(jìn)；移進(jìn)；第二個(gè)項(xiàng)目告訴我們應(yīng)該把棧頂?shù)牡诙€(gè)項(xiàng)目告訴我們應(yīng)該把棧頂?shù)臍w約為歸約為A；第三個(gè)項(xiàng)目告訴我們應(yīng)該把棧頂?shù)牡谌齻€(gè)項(xiàng)目告訴我們應(yīng)該把棧頂?shù)臍w約為歸約為B。 SLRSLR基本算法基本算法解決沖突的方法是分析所有含解決沖突的方法是分析所有含A和和B的句型，考察集的句型，考察集合合FOLLOW(A)和和FOLLOW(B)，如果這兩個(gè)集合不，如果這兩個(gè)集合不相交，而且也不包含相交，而且也不包含b，那么當(dāng)狀態(tài)，那么當(dāng)狀態(tài)I面臨輸入符號面臨輸入符號a時(shí)，我們可以使用如下策略：時(shí)，我們可以使用如下策略：若若a=b，則移進(jìn)。，則移進(jìn)。若若aFOLLOW(A)，則用產(chǎn)生式，則用產(chǎn)生

50、式A進(jìn)行歸約；進(jìn)行歸約；若若aFOLLOW(B)，則用產(chǎn)生式，則用產(chǎn)生式B進(jìn)行歸約；進(jìn)行歸約；此外，報(bào)錯(cuò)此外，報(bào)錯(cuò)SLRSLR基本算法基本算法假定假定LR(0)規(guī)范族的一個(gè)項(xiàng)目集規(guī)范族的一個(gè)項(xiàng)目集I中含有中含有m個(gè)移進(jìn)項(xiàng)目個(gè)移進(jìn)項(xiàng)目A1a11，A2a22，Amamm；同時(shí)含有同時(shí)含有n個(gè)歸約項(xiàng)目個(gè)歸約項(xiàng)目B1，B2，B3，如果集合如果集合 a1, am，F(xiàn)OLLOW(B1)，F(xiàn)OLLOW(Bn)兩兩兩兩不相交（包括不得有兩個(gè)不相交（包括不得有兩個(gè)FOLLOW集合有集合有#），則隱含在），則隱含在I中中的動(dòng)作沖突可以通過檢查現(xiàn)行輸入符號的動(dòng)作沖突可以通過檢查現(xiàn)行輸入符號a屬于上述屬于上述n+1個(gè)

51、集合個(gè)集合中的哪個(gè)集合而活的解決：中的哪個(gè)集合而活的解決：若若a是某個(gè)是某個(gè)ai，i=1,2,m，則移進(jìn)。，則移進(jìn)。若若aFOLLOW(Bi)，i=1,2,m，則用產(chǎn)生式，則用產(chǎn)生式Bi進(jìn)行歸約；進(jìn)行歸約；此外，報(bào)錯(cuò)此外，報(bào)錯(cuò)這種沖突的解決方法叫做這種沖突的解決方法叫做SLR(1)解決辦法。解決辦法。 SLRSLR語法分析表的構(gòu)造算法語法分析表的構(gòu)造算法首先把首先把G拓廣為拓廣為G，對，對G構(gòu)造構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族C和活前綴和活前綴識別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)識別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)GO。函數(shù)。函數(shù)ACTION和和GOTO可按可按如下方法構(gòu)造：如下方法構(gòu)造：若項(xiàng)目若項(xiàng)目Ab屬于屬

52、于Ik，GO(Ik,a)= Ij,a為終結(jié)符，置為終結(jié)符，置ACTIONk,a為為“把狀態(tài)把狀態(tài)j和符號和符號a移進(jìn)棧移進(jìn)?！?，簡記為，簡記為“sj”；若項(xiàng)目若項(xiàng)目A屬于屬于Ik，那么，對任何非終結(jié)符，那么，對任何非終結(jié)符a，aFOLLOW(A)，置，置ACTIONk,a為為“用產(chǎn)生式用產(chǎn)生式A進(jìn)行歸約進(jìn)行歸約”，簡記為，簡記為“rj”；其中，假定；其中，假定A為文法為文法G的第的第j個(gè)產(chǎn)生式個(gè)產(chǎn)生式若項(xiàng)目若項(xiàng)目SS屬于屬于Ik，則置，則置ACTIONk,#為可為可“接受接受”，簡記為，簡記為“acc”；若若GO(Ik, A)= Ij，A為非終結(jié)符，則置為非終結(jié)符，則置GOTOk, A=j；分

53、析表中凡不能用規(guī)則分析表中凡不能用規(guī)則1至至4填入信息的空白格均填上填入信息的空白格均填上“出錯(cuò)標(biāo)出錯(cuò)標(biāo)志志”。 語法分析器的初始狀態(tài)是包含語法分析器的初始狀態(tài)是包含S S的項(xiàng)目集合的狀態(tài)的項(xiàng)目集合的狀態(tài)SLRSLR分析舉例分析舉例文法文法G：(0) S E(1) E E+T (2) E T (3) T T*F(4) T F(5) F (E)(6) F iI0:S E E E+T E T T T*F T F F (E) F iI1:S E E E+TI2:E T T T*FI3:T FI4:F (E) E E+T E T T T*F T F F (E) F iI5:F iI6:E E+T T

54、T*F T F F (E) F iI7:T T*F F (E) F iI8:F (E) E E+TI9:E E+T T T*FI11:F (E)I10:T T*FFOLLOW(S)#FOLLOW(E)#, ), +SLRSLR分析舉例分析舉例I1:S E E E+TI2:E T T T*FI9:E E+T T T*FFOLLOW(S)#FOLLOW(E)#, ), +狀狀態(tài)態(tài)ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5

55、r5r5r5構(gòu)造規(guī)范構(gòu)造規(guī)范LRLR語法分析表語法分析表SLRSLR文法中可能出現(xiàn)的沖突文法中可能出現(xiàn)的沖突文法文法G：(0) S S(1) S L=R(2) S R (3) L *R (4) L i(5) R LI0:S S S L=R S R L *R L i R LI1:S SI2:S L=R R LI3:S RI4:L *R R L L *R L iI5:L iI6:S L=R R L L *R L iI7:L *RI8:R LI9:S L=RSLRSLR語法分析的局限性語法分析的局限性所有的所有的SLR語法必須滿足如下條件語法必須滿足如下條件I = X b , A , B 若有：若有

56、：FOLLOW(A) FOLLOW(B) = FOLLOW(A) b = FOLLOW(B) b = 狀態(tài)狀態(tài)I面臨某輸入符號面臨某輸入符號a1) 若若a=b，則移進(jìn)，則移進(jìn)2) 若若a FOLLOW(A), 則用產(chǎn)生式則用產(chǎn)生式 A 進(jìn)行歸約進(jìn)行歸約3) 若若a FOLLOW(B), 則用產(chǎn)生式則用產(chǎn)生式 B 進(jìn)行歸約進(jìn)行歸約4) 此外，報(bào)錯(cuò)此外，報(bào)錯(cuò)構(gòu)造規(guī)范構(gòu)造規(guī)范LRLR語法分析表語法分析表針對針對SLR語法分析的局限性，我們給出如下解決方案：語法分析的局限性，我們給出如下解決方案：重新定義項(xiàng)目，使之包含一個(gè)終結(jié)符作為第二個(gè)分量，可以把更重新定義項(xiàng)目，使之包含一個(gè)終結(jié)符作為第二個(gè)分量，可

57、以把更多的信息并入狀態(tài)中。多的信息并入狀態(tài)中。項(xiàng)目的一般形式也就變成了項(xiàng)目的一般形式也就變成了A, a1a2ak ，其中，其中ALR(0)項(xiàng)目，每一個(gè)項(xiàng)目，每一個(gè)a都是終結(jié)符或者都是終結(jié)符或者#。LR(k)項(xiàng)目中的項(xiàng)目中的a1a2ak稱為它的向前搜索符串（或展望串）稱為它的向前搜索符串（或展望串）搜索符對搜索符對是非空的產(chǎn)生式?jīng)]有什么影響是非空的產(chǎn)生式?jīng)]有什么影響這樣的這樣的a的集合是的集合是FOLLOW(A)的子集，有可能是真子集的子集，有可能是真子集歸約項(xiàng)目歸約項(xiàng)目A, a1a2ak意味著：當(dāng)它所屬的狀態(tài)呈現(xiàn)在棧頂意味著：當(dāng)它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的且后續(xù)的k個(gè)輸入符號為個(gè)輸入符號為a

58、1a2ak時(shí)，才可以把棧頂?shù)臅r(shí)，才可以把棧頂?shù)臍w約為歸約為A。我們只對我們只對k1的情形感興趣的情形感興趣 LR(1)LR(1)LR(1)對活前綴有效的定義對活前綴有效的定義形式的，形式的，LR(1)的項(xiàng)目的項(xiàng)目A, a對活前綴對活前綴有效，如果存在推有效，如果存在推導(dǎo)導(dǎo)S=*A=，其中：，其中：=a是是的第一個(gè)符號，或者的第一個(gè)符號，或者是空串，是空串，a是是#。對于對于Closure運(yùn)算的新定義運(yùn)算的新定義考慮對考慮對對活前綴對活前綴有效的項(xiàng)目集中的項(xiàng)目有效的項(xiàng)目集中的項(xiàng)目AB,a必定存在一必定存在一個(gè)最右推導(dǎo)個(gè)最右推導(dǎo)S=*Aax=Bax，其中，其中=。假設(shè)假設(shè)ax能推導(dǎo)出終結(jié)符串能推導(dǎo)

59、出終結(jié)符串by，那么對每一個(gè)形如，那么對每一個(gè)形如B的產(chǎn)生的產(chǎn)生式，存在推導(dǎo)式，存在推導(dǎo)S=*Bby =by ，于是，于是B, b對對有效有效可以說，可以說，b是是FIRST(ax)中的任何終結(jié)符，根據(jù)中的任何終結(jié)符，根據(jù)FIRST的定義，的定義， FIRST(ax)= FIRST(a)。規(guī)范規(guī)范LRLR語法分析表的構(gòu)造語法分析表的構(gòu)造步驟步驟構(gòu)造拓廣文法構(gòu)造拓廣文法G的的LR(1)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族C=I0,I1,In從從Ii構(gòu)造語法分析器的狀態(tài)構(gòu)造語法分析器的狀態(tài)i，狀態(tài)，狀態(tài)i的分析動(dòng)作如下：的分析動(dòng)作如下：如果如果Aa, b在在Ii中，且中，且goto(Ii,a)= Ij，則置，

60、則置actioni,a為為sj ，即，即“移動(dòng)移動(dòng)j進(jìn)棧進(jìn)棧”，這里要求，這里要求a必須是終結(jié)符必須是終結(jié)符如果如果A, a在在Ii中，且中，且A$，則置，則置actioni,a為為rj ，即按照，即按照rj歸約，歸約，其中其中j是產(chǎn)生式是產(chǎn)生式A的序號的序號如果如果SS, $在在Ii中，則置中，則置actioni,$為為acc，表示接受，表示接受如果上述出現(xiàn)沖突，那么該文法不是如果上述出現(xiàn)沖突，那么該文法不是LR(1)文法文法狀態(tài)狀態(tài)i的轉(zhuǎn)移按照下面的方法確定：如果的轉(zhuǎn)移按照下面的方法確定：如果goto(Ii,A)= Ij,那么那么gotoi,a=j其余表項(xiàng)設(shè)為出錯(cuò)其余表項(xiàng)設(shè)為出錯(cuò)初始狀態(tài)是