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

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

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

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

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

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

6、樹根的短語。個相對于子樹根的短語。直接短語：僅有父子兩代的一棵子樹，它的所有葉子直接短語：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號串。自左至右排列起來所形成的符號串。句柄：一個句型的分析樹中最左那棵只有父子兩代的句柄：一個句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。子樹的所有葉子的自左至右排列。例如，對表達式文法例如，對表達式文法GE和句子和句子a1+a2*a3，挑選出，挑選出推導過程中產生的句型中的短語，直接短語，句柄。推導過程中產生的句型中的短語，直接短語，句柄。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短語短語 移動歸約分析法相關概念移動歸約分析法相關概念規(guī)范歸約規(guī)范歸約文法的最右推導為規(guī)范推導，自底向上分析是自頂向下最右推導的逆文法的最右推導為規(guī)范推導，自底向上分析是自頂向下最右推導的逆過程，叫規(guī)范歸約過程，叫規(guī)范歸約句柄句柄直觀來看：一個符號串的直

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

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

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

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

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

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

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

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

16、串輸入：輸入字符串和優(yōu)先關系表和優(yōu)先關系表輸出：如果輸出：如果是語法產生的一個句子，則輸出其用來是語法產生的一個句子，則輸出其用來歸約的產生式；如果有錯誤，則轉入錯誤處理歸約的產生式；如果有錯誤，則轉入錯誤處理規(guī)范歸約和算符優(yōu)先歸約規(guī)范歸約和算符優(yōu)先歸約句型句型#i+i#的規(guī)范歸約過程的規(guī)范歸約過程步驟步驟符號棧符號棧剩余輸入串剩余輸入串 句柄句柄 歸約用產生式歸約用產生式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)先關系優(yōu)先關系 當前符號當前符號 剩余符號串剩余符號串 動作動作1 1# # i +i# + i# + i# 歸約歸約3 3#P#P + i# + i# 移進移進3 3#P+#P+ i # # # 歸約歸約4 4#P+P#P+P # # 歸約歸約4 4#E#E = # = # 接受接受算符優(yōu)先分析

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

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

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

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

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

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

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

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

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

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

28、分析成功，停止分析器的工作。報錯：發(fā)現(xiàn)源程序含有錯誤，調用出錯處理程序。報錯：發(fā)現(xiàn)源程序含有錯誤，調用出錯處理程序。 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語法分析器不需要掃描整個棧就可以知道什么時語法分析

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

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

31、(0)項目集族和項目集族和LR(0)LR(0)分析表的構造分析表的構造 相關概念：相關概念：前綴：字的前綴是指該字的任意首部。前綴：字的前綴是指該字的任意首部。字字abc的前綴有的前綴有、a、ab、abc?；钋熬Y：指規(guī)范句型的一個前綴，這種前綴不含句柄活前綴：指規(guī)范句型的一個前綴，這種前綴不含句柄之后任何符號。之所以稱為活前綴，是因為在右邊添之后任何符號。之所以稱為活前綴，是因為在右邊添加一些符號之首，就可以使它稱為一個規(guī)范句型。加一些符號之首，就可以使它稱為一個規(guī)范句型。在在LR分析工作過程中的任何時候，棧里的文法符號分析工作過程中的任何時候，棧里的文法符號（自棧底而上）（自棧底而上）X0

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

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

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

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

36、項目。 移進項目移進項目形如形如Aa的項目，其中的項目，其中a為終結符，稱為為終結符，稱為“移進移進”項目。項目。待約項目待約項目形如形如AB的項目，其中的項目，其中B為非終結符，稱為為非終結符，稱為“待約待約”項目。項目。 識別識別LR(0)LR(0)活前綴的活前綴的NFANFA舉例舉例文法文法G：S EE aA | bB A cA | dB cB | d文法的項目有：文法的項目有：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)項目集規(guī)范族的構造項目集規(guī)范族的構造用用-CLOSURE(閉包

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

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

41、號。是一個文法符號。函數(shù)值函數(shù)值GO(I,X)定義為定義為GO(I,X)=CLOSURE(J)，其中其中J=任何形如任何形如AX的項目的項目 | AX屬于屬于I LR(0)LR(0)項目集規(guī)范族舉例項目集規(guī)范族舉例初始狀態(tài)初始狀態(tài)I0的項目集規(guī)范族：的項目集規(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)項目集規(guī)范族的討論項目集規(guī)范族的討論有效項目有效項目我們說項目我們說項目A12對活前綴對活前綴1是有效的，其條件是存在規(guī)范是有效的，其條件是存在規(guī)范推導推導S=*A=12。LR(0)項目集可能出現(xiàn)的沖突項目集可能出現(xiàn)的沖突同一項目可能對好幾個活

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

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

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

46、移進棧移進棧”，簡記為，簡記為“sj”。若項目若項目A屬于屬于Ik，對任何終結符，對任何終結符a(或結束符或結束符#)，置，置ACTIONk,a為為“用產生式用產生式A進行歸約進行歸約”，簡記為，簡記為“rj”（假定產生式（假定產生式A是文法是文法G的第的第j個產生式）。個產生式）。若項目若項目SS屬于屬于Ik，則置，則置ACTIONk,#為為“接受接受”，簡記為，簡記為“acc”。若若GO(Ik , A)= Ij，A為非終結符，則置為非終結符，則置GOTOk,A=j。分析表中凡不能用規(guī)則分析表中凡不能用規(guī)則1至至4填入信息的空白格均填上填入信息的空白格均填上“報錯標志報錯標志”。 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分析表的構造分析表的構造SLRSLR語法分析概述語法分析概述LR(0)文法的活前綴識別自動機的每一個狀態(tài)（項目文法的活前綴識別自動機的每一個狀態(tài)（項目集）都不含沖突的項目。集）都不含沖突的項目。本節(jié)我們要研究一種有點簡單本節(jié)我們要研究一種有點簡單“展望展望”材料的材料的LR分分析法，即析法，即SLR文法。文法。

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

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

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

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

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

53、析表中凡不能用規(guī)則分析表中凡不能用規(guī)則1至至4填入信息的空白格均填上填入信息的空白格均填上“出錯標出錯標志志”。 語法分析器的初始狀態(tài)是包含語法分析器的初始狀態(tài)是包含S S的項目集合的狀態(tài)的項目集合的狀態(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構造規(guī)范構造規(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，則移進，則移進2) 若若a FOLLOW(A), 則用產生式則用產生式 A 進行歸約進行歸約3) 若若a FOLLOW(B), 則用產生式則用產生式 B 進行歸約進行歸約4) 此外，報錯此外，報錯構造規(guī)范構造規(guī)范LRLR語法分析表語法分析表針對針對SLR語法分析的局限性，我們給出如下解決方案：語法分析的局限性，我們給出如下解決方案：重新定義項目，使之包含一個終結符作為第二個分量，可以把更重新定義項目，使之包含一個終結符作為第二個分量，可

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

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

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

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