編譯原理課件：Chapter-4 語(yǔ)法分析

1、第四章 語(yǔ)法分析4.1 語(yǔ)法分析的功能、基本任務(wù)4.2 自頂向下分析法4.3 自底向上分析法4.1 語(yǔ)法分析概述 功能：根據(jù)文法規(guī)則，從源程序單詞符號(hào)串中識(shí)別出語(yǔ)法成分，并進(jìn)行語(yǔ)法檢查。 基本任務(wù)：識(shí)別符號(hào)串S是否為某語(yǔ)法成分。 兩大類分析方法：自頂向下分析自底向上分析 存在主要問題: 左遞歸問題 回溯問題若Z S 則 S L(GZ) 否則 S L(GZ) +GS 主要方法: 遞歸子程序法 LL分析法自頂向下分析算法的基本思想為：自底向上分析算法的基本思想為：+若Z S 則 S L(GZ) 否則 S L(GZ) GS存在主要問題: 句柄的識(shí)別問題 若兩個(gè)以上規(guī)則的右部有 相同的符號(hào)串且構(gòu)成句柄

2、， 選哪個(gè)候選式？主要方法: 算符優(yōu)先分析法 LR分析法4.2 自頂向下分析4.2.1 自頂向下分析的一般過程 我們可以通過一例子來說明語(yǔ)法分析過程 給定符號(hào)串S，若預(yù)測(cè)它是某一語(yǔ)法成分，那么可根據(jù)該語(yǔ)法成分的文法，設(shè)法為S構(gòu)造一棵語(yǔ)法樹。若成功，則S最終被識(shí)別為某一語(yǔ)法成分。即 SL(GZ) 其中GZ為某語(yǔ)言成分的文法。若不成功，則 SL(GZ) 。例S = c a dG Z : Z= c A d A= a b | a求解 S L(GZ) ？ 分析過程是設(shè)法建立一棵語(yǔ)法樹，使語(yǔ)法樹的末端結(jié)點(diǎn)與給定符號(hào)串相匹配。cAdZ2.用Z的右部符號(hào)串去匹配輸入串完成一步推導(dǎo) Z c A d 檢查 c -

3、 c匹配 A是非終結(jié)符，將匹配任務(wù)交給A2型文法！上下文無關(guān)文法1.開始：令Z為根結(jié)點(diǎn)。Z3.選用A的右部符號(hào)串匹配輸入串 A有兩個(gè)右部，選第一個(gè)。 cAdabZ完成進(jìn)一步推導(dǎo)A a b檢查：a - a匹配，b - d不匹配(失敗)但是還不能貿(mào)然宣布SL(GZ) 4.回溯：即砍掉A的子樹 改選A的第二右部ZcAdaA a 檢查 a - a匹配 d - d匹配 語(yǔ)法樹末端結(jié)點(diǎn)為c a d與輸入c a d相匹配，建立了推導(dǎo)序列 Z c A d c a d。c a d L(G(Z)S = c a d GZ: Z= c A d A= a b | a自頂向下分析方法的特點(diǎn) 1. 分析過程是帶有預(yù)測(cè)的。即

4、要根據(jù)輸入符號(hào)串中下一個(gè)單詞，來預(yù)測(cè)之后的內(nèi)容屬于什么語(yǔ)法成分，然后用相應(yīng)語(yǔ)法成分的文法建立語(yǔ)法樹。2. 分析過程是一種試探過程，是盡一切辦法（選用不同規(guī)則）設(shè)法建立語(yǔ)法樹的過程。由于是試探過程，故難免有失敗，所以分析過程需進(jìn)行回溯，因此我們也稱這種方法是帶回溯的自頂向下分析方法。3. 最左推導(dǎo)可以編出程序來實(shí)現(xiàn)，但在實(shí)際上價(jià)值不大，效率低，代價(jià)高。4.2.2 自頂向下分析存在的問題及解決方法 1 、 左遞歸文法： 該方法的基本缺點(diǎn)是不能處理具有左遞歸性的文法。這個(gè)規(guī)則文法是左遞歸的。有如下文法： 令U是文法的任一非終結(jié)符，文法中有規(guī)則 U= U 或者 U U+自頂向下分析為什么不能處理左遞歸

5、文法？如果我們?cè)谄ヅ漭斎氪^程中，假定正好輪到要用非終結(jié)符U直接匹配輸入串，即要用U的右部符號(hào)串U去匹配，為了用U去匹配，又得用U去匹配，這樣無限地循環(huán)下去，過程將無法終止。如果文法具有間接左遞歸，則也將發(fā)生上述問題，只不過兜的圈子更大。要實(shí)行自頂向下分析，必須要消除文法的左遞歸，下面我們將介紹直接左遞歸的消除方法。在此基礎(chǔ)上再介紹一般左遞歸的消除方法。消除直接左遞歸方法一：使用擴(kuò)充的BNF表示來改寫文法例：(1) E= E + T | T E= T + T (2) T= T * F | T / F | F T= F * F | / F a. 改寫以后的文法消除了左遞歸。b. 可以證明，改寫前

6、后的文法是等價(jià)的，表現(xiàn)在 L(G改前) = L(G改后)如何改寫文法能消除左遞歸，又前后等價(jià)？現(xiàn)在我們可以給出兩條規(guī)則。規(guī)則一（提因子）若：U= x y | x w |.| x z則可改寫為：U= x ( y | w |.| z )其中再若：y = y1 y2, w = y1 w2 則 U= x ( y1 ( y2 | w2 ) |.| z )若有規(guī)則：U= x | x y則可以改寫為：U= x ( y |)注意：不應(yīng)寫成U= x (| y) 總把安置成最后的選擇！使用提因子法，不僅有助于消除直接左遞歸，而且有助于壓縮文法的長(zhǎng)度，使我們更加有效地分析句子。注意若是 y x | w x |.|

7、z x則x不是公因子！規(guī)則二U Uv Uv v Uv vv 可以改寫為U= ( x | y | z ) v 其特點(diǎn)是：具有一個(gè)直接左遞歸的右部并位于最后，這表明該語(yǔ)法類U是由 x 或 y或 z打頭，其后跟隨零個(gè)或多個(gè) v 組成。通過以上兩條規(guī)則，就能消除文法的直接左遞歸，并且保證文法的等價(jià)性。 若有文法規(guī)則：U= x | y | z | U v下面有兩個(gè)例題：方法二：將左遞歸規(guī)則改為右遞歸規(guī)則規(guī)則三若：P= P | 則可改寫為：P = P P = P | 例1 E= E + T | T產(chǎn)生式右部無公因子，所以不能用規(guī)則一。為了使用規(guī)則二，我們令E= T | E + T由規(guī)則二我們可以得到 E=

8、 T + T 例2 T= T * F | T / F | F T= F | T * F | T / F T= F | T ( * F | / F ) 規(guī)則一 T= F ( * F | / F ) 規(guī)則二 即T= F * F | / F 右遞歸： T := F T T := * F T | / F T | 規(guī)則三消除一般左遞歸一般左遞歸也可以通過改寫法予以消除。消除所有左遞歸的算法：1.把G的非終結(jié)符整理成某種順序A1，A2，An ，使得 A1 := 1 |2 |k A2 := A1 r A3 := A2 u | A1 v. . 2. for i:=1 to n do begin for j :

9、=1 to i-1 do 把每個(gè)形如Ai= Aj r的規(guī)則替換成 Ai = (1 |2 |k ) r 其中Aj =1 |2 |k是當(dāng)前Aj 的全部規(guī)則 消除Ai 規(guī)則中的直接左遞歸 end 3. 化簡(jiǎn)由 2 得到的文法，即去掉那些多余的規(guī)則。例：文法G S 為 S = Q c | c Q = R b | b R = S a | a 非終結(jié)符順序重新排列R= S a | aQ= R b | bS= Q c | c該文法無直接左遞歸，但有間接左遞歸 S Q c R b c S a b c S S a b c+1.檢查規(guī)則R是否存在直接左遞歸 R= S a | a2.把R代入Q的有關(guān)選擇，改寫規(guī)則Q

10、 Q= S a b | a b | b3.檢查Q是否直接左遞歸4.把Q代入S的右部選擇 S= S a b c | a b c | b c | c5.消除S的直接左遞歸 S= ( a b c | b c | c ) a b c R= S a | aQ= R b | bS= Q c | c最后得到文法為:S= ( a b c | b c | c ) a b c Q= S a b | a b | bR= S a | a可以看出其中關(guān)于Q和R的規(guī)則是多余的規(guī)則經(jīng)過壓縮后S= ( a b c | b c | c ) a b c 可以證明改寫前后的文法是等價(jià)的應(yīng)該指出，由于對(duì)非終結(jié)符的排序不同，最后得到的

11、文法在形式上可能是不一樣的，但是不難證明它們的等價(jià)性。 2 、 回溯問題 什么是回溯? 分析工作要部分地或全部地退回去重做叫回溯。造成回溯的條件： 文法中，對(duì)于某個(gè)非終結(jié)符號(hào)的規(guī)則其右部有多個(gè)選擇，并根據(jù)所面臨的輸入符號(hào)不能準(zhǔn)確地確定所要的產(chǎn)生式，就可能出現(xiàn)回溯?；厮輲淼膯栴}：效率嚴(yán)重低下，只有在理論上的意義而無實(shí)際意義。U:= 1 | 2 | 3 效率低的原因1) 語(yǔ)法分析要重做2) 語(yǔ)法處理工作要推倒重來怎么樣才能避免回溯？為避免回溯，對(duì)文法的要求是: FIRST(i ) FIRST(j ) = (i j)定義 設(shè)文法G（不具左遞歸性），U Vn U:= 1 | 2 | 3 FIRST(

12、i) = a | i a, a Vt 消除回溯的途徑：1.改寫文法對(duì)具有多個(gè)右部的規(guī)則反復(fù)提取左因子例1 U= x V | x W U, V, WVn, xVt改寫為U= x ( V | W )更清楚表示 U= x Z Z= V | W注意：?jiǎn)栴}到此并沒有結(jié)束，還需要進(jìn)一步檢查V和W的首符號(hào)是否相交若V= a b | c d FIRST(V) = a , c W= d e | f g FIRST(W) = d , f 只要不相交就可以根據(jù)輸入符號(hào)確定目標(biāo)；若相交，則要代入，并再次提取左因子。如：V:= a b W:= a c 則：Z:= a ( b | c )例2：文法G = | = begi

13、n； end = begin endFIRST() = begin FIRST() = begin 改寫文法： = begin （； end | end）引入 = begin = ； end | end = begin = ； end | end 對(duì)于： FIRST( ； end) = real, integer, boolean, array, function, procedure FIRST( end ) = 標(biāo)識(shí)符，goto, begin, if, for不相交。2. 超前掃描當(dāng)文法不滿足避免回溯的條件時(shí)，即各選擇的首符號(hào)相交時(shí)，可以采用超前掃描的方法，即向前偵察各輸入符號(hào)串的第二個(gè)、

14、第三個(gè)符號(hào)來確定要選擇的目標(biāo)。這種方法是通過向前多看幾個(gè)符號(hào)來確定所選擇的目標(biāo)，從本質(zhì)上來講也有回溯的味道，因此比第一種方法費(fèi)時(shí)，但是讀的僅僅是向前偵察情況，不作任何語(yǔ)義處理工作。例 = | = begin ； end= begin end這兩個(gè)選擇的首符號(hào)是相交，因此讀到begin時(shí)并不能確定該用哪個(gè)選擇。這時(shí)可采用向前假讀進(jìn)行偵察，此例題只需假讀一次就可以確定目標(biāo)。因?yàn)榈氖追癁閞eal，integer，procedure；而的首符集為標(biāo)識(shí)符，if ，for，begin。只要超前假讀得到的是“說明串”的首符，便是第一個(gè)選擇。若是“語(yǔ)句串”的首符，就是第二個(gè)選擇。為了在不采取超前掃描的前提下

15、實(shí)現(xiàn)不帶回溯的自頂向下分析，對(duì)文法需要滿足兩個(gè)條件：文法的兩個(gè)條件 2、對(duì)文法的任一非終結(jié)符，若其規(guī)則右部有多個(gè)選擇時(shí)，各選擇所推出的終結(jié)符號(hào)串的首符號(hào)集合要兩兩不相交。 1、文法是非左遞歸的；在上述條件下，就可以根據(jù)文法構(gòu)造有效的、不帶回溯的自頂向下分析器。4.2.3 遞歸子程序法（遞歸下降分析法） 具體做法：對(duì)語(yǔ)法的每一個(gè)非終結(jié)符都編一個(gè)分析程序。當(dāng)根據(jù)文法和當(dāng)時(shí)的輸入符號(hào)預(yù)測(cè)到要用某個(gè)非終結(jié)符去匹配輸入串時(shí)，就調(diào)用該非終結(jié)符的分析程序。下面我們可以通過舉例說明如何根據(jù)文法構(gòu)造該文法的語(yǔ)法分析程序。 如文法GE: E := U VU := . V := .E的分析程序 U的分析程序V的分析

16、程序UV注：消除左遞歸后，可有其它遞歸（如右遞歸或自嵌入遞歸）： U := U U := W W:= U例：文法GZZ= ( U ) | a U bU= d Z | U d | e1.檢查并改寫文法Z= ( U ) | a U bU= ( d Z | e ) d 改寫后無左遞歸且首符集不相交： ( a = d e =2.檢查文法的遞歸性因此，Z和U的分析程序可以編成遞歸子程序Z UZ Z ZU ZU U U+注意：這兩個(gè)式子中的圓括號(hào)不同！Z中的括號(hào)是終結(jié)符號(hào)之一。U中的括號(hào)則是元語(yǔ)言的括號(hào)。Z= ( U ) | a U b3. 算法框圖讀符號(hào) UerrorYN(sym)=(入口YN(sym)

17、=a讀符號(hào) UNY(sym)=bN讀符號(hào)errorY(sym)=)出口讀符號(hào) Z讀符號(hào)U= (d Z | e) d YY入口errorNN(sym)=d(sym)=eN Y出口讀符號(hào)(sym)=d說明：要注意子程序之間的接口。在程序編制時(shí)，進(jìn)入某個(gè)非終結(jié)符的分析程序前，其所要分析的語(yǔ)法成分的第一個(gè)符號(hào)已讀入sym中了。遞歸子程序法對(duì)應(yīng)的是最左推導(dǎo)過程！在上面的分析過程中，我們強(qiáng)調(diào)一定要消除左遞歸，但允許存在右遞歸或自嵌入遞歸。正是由于在子程序的調(diào)用過程中允許（直接或間接的）遞歸調(diào)用，這種方法才得名遞歸子程序法。非終結(jié)符號(hào)的分析子程序功能，是用規(guī)則右部符號(hào)串去匹配輸入串。4.2.4 用遞歸子程序

18、法構(gòu)造語(yǔ)法分析程序的例子 改寫文法: = := | IF THEN ELSE = i = + = * = | ()文法: = := | IF THEN | IF THEN ELSE = i | i = | + = | * = | ()用單引號(hào)括起來的符號(hào)表示終結(jié)符號(hào)語(yǔ)法分析程序所要調(diào)用的子程序：nextsym: 詞法分析程序，每調(diào)用一次讀進(jìn)一個(gè)單詞， 單詞的類別碼放在sym中。error: 出錯(cuò)處理程序。PROCEDURE state; /*語(yǔ)句*/ IF sym =IF THEN BEGIN nextsym; expr; IF symTHEN THEN error ELSE BEGIN ne

19、xtsym; state; END IF sym= ELSE THEN BEGIN nextsym; state; END END ELSE BEGIN var; IF sym= THEN error ELSE BEGIN nextsym; expr; END END = = | IF THEN ELSE PROCEDURE var; /*變量*/ IF sym i THEN error ELSE BEGIN nextsym; IF sym = THEN BEGIN nextsym; expr; IF sym THEN error ELSE nextsym; END END = i PROCE

20、DURE expr; /*表達(dá)式*/ BEGIN term; WHILE sym = + DO BEGIN nextsym; term; END END = + PROCEDURE term; /*項(xiàng)*/ BEGIN factor; WHILE sym = * DO BEGIN nextsym; factor; END END PROCEDURE factor; /*因子*/ BEGIN IF sym=( THEN BEGIN nextsym; expr; IF sym ) THEN error ELSE nextsym END ELSE var; END= * = | ( )舉例分析 if

21、( i + i ) then i := i * i + i else i i := i + i i * i * ( i + i )作業(yè)： p90: 1-3 （注意：第3題第3個(gè)產(chǎn)生式應(yīng)為B:=aB|a而不是B:=aA|a ）4.2.5 LL分析法 LL自左向右掃描、自左向右地分析和匹配輸入串。 分析過程表現(xiàn)為最左推導(dǎo)的性質(zhì)。1、LL分析程序構(gòu)造及分析過程此過程有三部分組成：分析表 執(zhí)行程序 (總控程序） 符號(hào)棧 （分析棧）執(zhí)行程序分析表#符號(hào)棧#輸入串（1）分析表：二維矩陣M A=i MA, a = 或 其中iV*, AVn, aVt or # error 在實(shí)際語(yǔ)言中，每一種語(yǔ)法成分都有確定

22、的左右界符，為了研究問題方便，統(tǒng)一用表示。執(zhí)行程序分析表#符號(hào)棧#輸入串MA, a A=i 表示當(dāng)要用A去匹配輸入串時(shí)，且當(dāng)前輸入符號(hào)為 a 時(shí)，可用A的第 i 個(gè)選擇去匹配。 即 當(dāng)i時(shí)，有i a ; 當(dāng)i時(shí)，則 a 為A 的后繼符號(hào)。*MA, a error 表示當(dāng)用A去匹配輸入串時(shí)，若當(dāng)前輸入符號(hào)為 a，則不能匹配，表示無 A a，或 a 不是A的后繼符號(hào)。*（2）符號(hào)棧: 有四種情況#E符號(hào)棧 開始狀態(tài) E#xxxxxx#.X 工作狀態(tài)符號(hào)棧 X.#查分析表得：XVn， M X , a = X=i X a XVt， X = a+a#a# 出錯(cuò)狀態(tài)#.X符號(hào)棧 X.#查分析表得：XVn，

23、 M X , a = error 無X a XVt， X a+ 結(jié)束狀態(tài)#符號(hào)棧 #把 # 和文法識(shí)別符號(hào) E 推進(jìn)棧，并讀入輸入串的第一個(gè)符號(hào) a，重復(fù)下述過程直到正常結(jié)束或出錯(cuò)。2. 根據(jù)棧頂符號(hào) X 和當(dāng)前輸入符號(hào)a，執(zhí)行如下操作：若X (Vt ) = a = #，分析成功，停止。E匹配輸入串成功。若X (Vt ) = a#，把 X 退出棧，再讀入下一個(gè)符號(hào)。若X (Vt )a，轉(zhuǎn)出錯(cuò)處理。若XVn，查分析表 M。（3）執(zhí)行程序執(zhí)行程序主要實(shí)現(xiàn)如下操作:a#.X符號(hào)棧 X.#若XVn，查分析表M。 a) M X , a = X= U V W 則將 X 彈出棧，將 U V W逆序入棧 注：

24、U在棧頂 （最左推導(dǎo)） b) M X , a = error 轉(zhuǎn)出錯(cuò)處理 c) M X , a = X: = a為X的后繼符號(hào)，則將X彈出棧 （不讀下一符號(hào)）繼續(xù)分析。#.X#.WVU X.# UVW.#例：文法G E E := E + T | TT := T * F | FF := ( E ) | iE := T EE := + T E |T := F TT:= * F T |F := ( E ) | i消除左遞歸分析表注：矩陣元素空白表示Error輸入串為: i + i * i #步驟 符號(hào)棧 讀入符號(hào)剩余符號(hào)串 使用規(guī)則1. EE # i + i * i # E := T E2. E T

25、T E # i + i * i # T := F T3. E T FF T E # i + i * i # F := i4. E T ii T E # i + i * i # (出棧，讀下一個(gè)符號(hào)）5. E TT E # + i * i # T := 6. EE # + i * i # E := + T E7. E T + T E # + i * i # (出棧，讀下一個(gè)符號(hào)）i+*()#EE := T EE := T EEE := + T EE := E := TT := F TT := F TTT := T := * F TT := T := FF := iF := ( E )步驟 符號(hào)棧

26、 讀入符號(hào)剩余符號(hào)串 使用規(guī)則8.E T i * i # T := F T 9.E T F i * i # F := i10.E T i i * i # (出棧，讀下一個(gè)符號(hào)）11.E T * i # T := * F T12.E T F * * i # (出棧，讀下一個(gè)符號(hào)）13.E T F i # F := i14.E T i i # (出棧，讀下一個(gè)符號(hào)）15.E T # T := 16.E # E := 17. # accept (分析成功）i+*()#EE := T EE := T EEE := + T EE := E := TT := F TT := F TTT := T := *

27、 F TT := T := FF := iF := ( E )最左推導(dǎo)！ 已識(shí)別出來的終結(jié)符號(hào)和符號(hào)棧內(nèi)的現(xiàn)有符號(hào)排列（從棧頂?shù)綏５祝脴?gòu)成該推導(dǎo)過程！推導(dǎo)過程：E T E F T E i T E i E i + T E i + F T E i + i T E i + i * F T E i + i * i T E i + i * i E i + i * i2、分析表的構(gòu)造 定義：FIRST() = a | a，aVt V* , 若，則FIRST()該集合稱為的頭符號(hào)集合。*定義：FOLLOW() = a | Z a，aVt Vn , Z為識(shí)別符號(hào)該集合稱為的后繼符號(hào)集合。 特殊地：若Z

28、. 則 #FOLLOW()*設(shè)有文法G Z :設(shè)=X1 X2 . Xn , XiVn Vt求FIRST()=? 首先求出組成的每一個(gè)符號(hào)Xi 的FIRST集合。若XiVt，則 FIRST( Xi ) = Xi (2) 若XiVn 且 Xi = a|， aVt 則 FIRST( Xi ) = a , 構(gòu)造集合FIRST的算法(3) 若Xi Vn 且Xi= y1 y2 yk，則按如下順序計(jì)算FIRST(Xi) 若FIRST(y1) 則將FIRST(y1) 加入 FIRST(Xi) ； 若FIRST(y1) 則將FIRST(y2) 加入FIRST(Xi) 且若FIRST(y2) 則將FIRST(y3

29、) 加入FIRST(Xi) . FIRST(yk-1) 則將FIRST(yk) 加入FIRST(Xi) 若FIRST(y1) FIRST(yk) 則將加入FIRST(Xi) 注意：要順序往下做，一旦不滿足條件，過程就要中斷進(jìn)行得到FIRST(Xi)，即可求出FIRST()。 構(gòu)造集合FOLLOW的算法若S為識(shí)別符號(hào)，則把“ # ”加入FOLLOW(S)中； (2) 若A=B()，則把FIRST()-加入FOLLOW(B)； (3) 若A=B 或A=B， 且則把FOLLOW(A)加 入FOLLOW(B) 中去。*注意：FOLLOW集合中不能有! 設(shè)S, A, BVn ,算法：連續(xù)使用以下規(guī)則，直

30、至FOLLOW集合不再擴(kuò)大。FIRST(F) = ( , i FIRST(T) = * , FIRST(T) = FIRST( F ) - = ( , i FIRST(E) = + ,FIRST(E) = FIRST( T ) - = ( , i FIRST(TE) = FIRST( T ) - = ( , i FIRST(+TE) = + FIRST() = FIRST(FT) = FIRST( F ) - = ( , i FIRST(E) = ( FIRST( i ) = i 例：G E 分析表的構(gòu)造 E= T E E= + T E | T= F T T= * F T | F= ( E )

31、 | i求FIRST集 FOLLOW(E) = # , ) FOLLOW(E) = # , ) FOLLOW(T) = + , ) , # FOLLOW(T) = FOLLOW(T) = + , ) , # FOLLOW(F) = * , + , ) , # E= T E E= + T E |T= F T T= * F T | F= ( E ) | i求FOLLOW 集FIRST(F) = ( , i FIRST(T) = * , FIRST(T) = ( , i FIRST(E) = + ,FIRST(E) = ( , i E 是識(shí)別符號(hào) #FOLLOW(E)又F= ( E ) )FOLLO

32、W(E)E= TE FOLLOW(E)加入FOLLOW(E)E= + T E FIRST(E)-加入FOLLOW(T)又E， FOLLOW(E)加入FOLLOW(T) T= F T FOLLOW(T)加入FOLLOW(T) T= F T FOLLOW(F) = FIRST(T)- 又T FOLLOW(T)加入FOLLOW(F) 構(gòu)造分析表 基本思想: 當(dāng)文法中某一非終結(jié)符呈現(xiàn)在棧頂時(shí)，根據(jù)當(dāng)前的輸入符號(hào)，分析表應(yīng)指示要用該非終結(jié)符里的哪一條規(guī)則去匹配輸入串（即進(jìn)行下一步最左推導(dǎo)）。 根據(jù)這個(gè)思想，我們不難把構(gòu)造分析表算法構(gòu)造出來! 終結(jié)符號(hào) + #非終結(jié)符號(hào)2、若i =或i ，而且a FOLL

33、OW (i)，則A:=i (即)放入M A , a ，表示 A 已匹配輸入串成功，其后繼符號(hào)終結(jié)符 a 由 A 后面的語(yǔ)法成分去匹配。+3、把所有無定義的M A , a 都標(biāo)上error。算法：設(shè)A=i為文法中的任意一條規(guī)則，a為任一終結(jié)符或#。1、若a FIRST(i )，則將 A :=i 放入 M A , a 。 表示：A在棧頂，輸入符號(hào)是 a，應(yīng)選擇i 去匹配。注意：用上述算法可以構(gòu)造出任意給定文法的分析表，但不是所有文法都能構(gòu)造出上述那種形狀的分析表。即M A , a 只對(duì)應(yīng)一條規(guī)則或Error。對(duì)于能用上述算法構(gòu)造分析表的文法我們稱為L(zhǎng)L(1)文法。 構(gòu)造分析表 i+*()#EE:=

34、TEE:=TEEE:=+TEE:=E:=TT:=FTT:=FTTT:=T:=*FTT:=T:=FF:= iF:= (E)FOLLOW(E) = # , ) FOLLOW(E) = # , ) FOLLOW(T) = + , ) , # FOLLOW(T) = + , ) , # FOLLOW(F) = * , + , ) , # E= T E E= + T E |T= F T T= * F T | F= ( E ) | iFIRST(TE) = ( , i FIRST(+TE) = + FIRST(FT) = ( , i FIRST(E) = ( 2、若= , 則FIRST() FOLLOW(

35、A) = *3、LL(1)文法 定義：一個(gè)文法G，其分析表M不含多重定義入口（即分析表中無兩條以上規(guī)則），則稱它是一個(gè)LL(1)文法。定理：文法G是LL(1)文法的充分必要條件是：對(duì)于G的每個(gè)非終結(jié)符A的任意兩條規(guī)則A:=|,下列條件成立： 1、FIRST() FIRST() = 用上述分析表的構(gòu)造算法可以構(gòu)造任何文法的分析表。但對(duì)于某些文法，有些MA,a中可能有若干條規(guī)則，這稱為分析表的多重定義或者多重入口。 可以證明：如果G是左遞歸或二義的，那么M至少含有一個(gè)多重定義入口。因此，消除左遞歸和提取左因子將有助于獲得無多重定義的分析表M。 反之，一個(gè)文法G的預(yù)測(cè)分析表M不含多重定義入口，當(dāng)且僅

36、當(dāng)該文法為L(zhǎng)L(1)的。左遞歸：U=U| a 則有：FIRST(U)FIRST(a) MU,a = U=U, U= a二義文法：對(duì)文法所定義的某些句子存在著兩(多)個(gè)最左推導(dǎo)，即在推導(dǎo)的某些步上存在多重定義，有兩(多)條規(guī)則可用，所以分析表是多重定義的。有些文法可以從非LL(1)文法改寫為L(zhǎng)L(1)文法。但并不是所有的非LL(1)文法都能改寫為L(zhǎng)L(1)文法。習(xí)題：p97頁(yè)1, 2, 6（不需證明） (注：第3題題目本身錯(cuò)誤！)選作題：有文法G S S := i C t S S | aS:= e S |C := b (1) 證明該文法是二義性文法。 (2) 求FIRST集和FOLLOW集 (3

37、) 構(gòu)造LL分析表，證明該文法是非LL(1)文法。4、LL分析的錯(cuò)誤恢復(fù)-補(bǔ)充 當(dāng)符號(hào)棧頂?shù)慕K結(jié)符和下一個(gè)輸入符號(hào)不匹配，或棧頂是非終結(jié)符A，輸入符號(hào)a，而M A , a 為空白（即error）時(shí)，則分析發(fā)現(xiàn)錯(cuò)誤。 錯(cuò)誤恢復(fù)的基本思想是：跳過一些輸入符號(hào)，直到期望的同步符號(hào)之一出現(xiàn)為止。 同步符號(hào)（可重新開始繼續(xù)分析的輸入符號(hào)）集合通?？砂匆韵路椒ù_定：把FOLLOW(A)的所有符號(hào)加入A的同步符號(hào)集。如果我們跳讀一些輸入符號(hào)直到出現(xiàn)FOLLOW(A)的符號(hào)，之后把 A 從棧中彈出，繼續(xù)往下分析即可。2) 只用FOLLOW(A)作為非終結(jié)符A的同步符號(hào)集是不夠的(容易造成跳讀過多，如輸入串中缺

38、少語(yǔ)句結(jié)束符分號(hào)時(shí))。此時(shí)可將作為語(yǔ)句開頭的關(guān)鍵字加入它的同步符號(hào)集，從而避免這種情況的發(fā)生。3) 把FIRST(A)的符號(hào)加入非終結(jié)符A的同步符號(hào)集中。4) 如果非終結(jié)符A可以產(chǎn)生空串，那么推導(dǎo)的產(chǎn)生式可以作為缺省的情況。這樣做可以推遲某些錯(cuò)誤檢查，但不會(huì)漏過錯(cuò)誤。5) 如果終結(jié)符在棧頂而不能匹配，則可彈出該終結(jié)符并發(fā)出一條信息后繼續(xù)分析。這好比把所有其他符號(hào)均作為該符號(hào)的同步集合元素。4.3 自底向上分析基本算法思想: 若采用自左向右地掃描和分析輸入串，那么自底向上的基本算法是： 從輸入符號(hào)串開始，通過反復(fù)查找當(dāng)前句型的句柄（最左簡(jiǎn)單短語(yǔ)），并利用有關(guān)規(guī)則進(jìn)行規(guī)約。若能規(guī)約為文法的識(shí)別符號(hào)

39、，則表示分析成功，輸入符號(hào)串是文法的合法句子；否則有語(yǔ)法錯(cuò)誤。分析過程是重復(fù)以下步驟 ：1、找出當(dāng)前句型的句柄 x （或句柄的變形）； 2、找出以 x 為右部的規(guī)則 X:= x ； 3、把 x 規(guī)約為X，產(chǎn)生語(yǔ)法樹的一枝。 關(guān)鍵：找出當(dāng)前句型的句柄 x (或其變形），這不是很容易的。 本節(jié)內(nèi)容介紹（全書的重點(diǎn)?。┳缘紫蛏戏治龅囊话氵^程（移進(jìn)-歸約分析）算符優(yōu)先分析法LR分析法LR(0)分析法SLR(1)分析法規(guī)范LR(1)分析法LALR(1)分析法4.3.1 移進(jìn)規(guī)約分析（Shift-reduce parsing ) 要點(diǎn)：設(shè)置符號(hào)棧，用來紀(jì)錄分析的歷史和現(xiàn)狀 ， 并根據(jù)所面臨的狀態(tài)，確定下一

40、步動(dòng)作是移 進(jìn)還是規(guī)約。#S.R.P#符號(hào)棧輸入串分析過程：把輸入符號(hào)串按順序一個(gè)一個(gè)地移進(jìn)符號(hào)棧（一次移一個(gè)）；檢查棧中符號(hào)，當(dāng)在棧頂?shù)娜舾煞?hào)形成當(dāng)前句型的句柄時(shí)，就根據(jù)規(guī)則進(jìn)行規(guī)約將句柄從符號(hào)棧中彈出，并將相應(yīng)的非終結(jié)符號(hào)壓入棧內(nèi)（即規(guī)則的左部符號(hào)），然后再檢查棧內(nèi)符號(hào)串是否形成新的句柄，若有就再進(jìn)行規(guī)約，否則移進(jìn)符號(hào)；分析一直進(jìn)行到讀到輸入串的右界符為止。最后，若棧中僅含有左界符號(hào)和識(shí)別符號(hào)，則表示分析成功，否則失敗。#S.R.P#符號(hào)棧輸入串例：G S : 輸入串為： a b b c d e S= a A c B e A= b A= A b B= d 檢查輸入串a(chǎn)bbcde是否是該文

41、法的合法句子。 若采用自底向上分析，即能否一步步規(guī)約當(dāng)前句型的句柄，最終規(guī)約到識(shí)別符號(hào)S。先設(shè)立一個(gè)符號(hào)棧，我們?nèi)匀唤y(tǒng)一用符號(hào)“ # ”作為待分析符號(hào)串的左右分界符。 作為初始狀態(tài)，先將符號(hào)串的左分界符推進(jìn)符號(hào)棧作為棧底符號(hào)。 分析過程如下表:步驟符號(hào)棧輸入符號(hào)串動(dòng)作1#abbcde#準(zhǔn)備。初始化2#abbcde#移進(jìn)3#abbcde#移進(jìn)4#aAbcde#規(guī)約(A=b)5#aAbcde#移進(jìn)6#aAcde#規(guī)約(A=Ab)7#aAcde#移進(jìn)8#aAcde#移進(jìn)9#aAcBe#規(guī)約(B=d)10#aAcBe#移進(jìn)11#S#規(guī)約(S=aAcBe)12#S#成功例：GS: S= a A c B

42、e A= b A= A b B= d 這一方法簡(jiǎn)單明了，不斷地進(jìn)行移進(jìn)規(guī)約。關(guān)鍵是確定當(dāng)前句型的句柄。說明：1) 例子的分析過程是一步步地規(guī)約當(dāng)前句型的句柄。該句子的唯一語(yǔ)法樹為：SbabcdeAAB 注意兩點(diǎn)： 棧內(nèi)符號(hào)串 + 未處理輸入符號(hào)串 = 當(dāng)前句型 句柄都在棧頂 實(shí)際上，以上分析過程并未真正解決句柄的識(shí)別問題。 2) 未真正解決句柄的識(shí)別問題 上述分析過程中識(shí)別句柄的過程，主要看棧頂符號(hào)串是否形成規(guī)則的右部。 這種做法形式上是正確的，但在實(shí)際上不一定正確。舉例的分析過程可以說是一種巧合。 因?yàn)椴荒苷J(rèn)為：對(duì)句型 xuy 而言，若有U= u，即U u 就斷定u是簡(jiǎn)單短語(yǔ)，u 就是句柄，

43、而是要同時(shí)滿足Z xUy。*步驟符號(hào)棧輸入符號(hào)串當(dāng)前句型5#aAbcde#aAbcdeA= b A = bA= Ab A = Ab若用A= b 歸約， 得aAAcde若用A= Ab歸約，得aAcdeS =aAAcde S =aAcde*2) 稱為算符優(yōu)先分析是因?yàn)檫@種方法是仿效算術(shù)式的四則運(yùn)算而建立起來的。做算術(shù)式的四則運(yùn)算時(shí)，為了保證計(jì)算結(jié)果和過程的唯一性，規(guī)定了一個(gè)統(tǒng)一的四則運(yùn)算法則，規(guī)定運(yùn)算符之間的優(yōu)先關(guān)系。4.3.2 算符優(yōu)先分析(Operator-Precedence Parsing)1) 這是一種經(jīng)典的自底向上分析法，簡(jiǎn)單直觀，并被廣泛使 用。開始主要是對(duì)表達(dá)式的分析，現(xiàn)在已不限于

44、此，可以用于一大類上下文無關(guān)文法。運(yùn)算法則:1.乘除的優(yōu)先級(jí)大于加減；2.同優(yōu)先級(jí)的運(yùn)算符左大于右；3.括號(hào)內(nèi)的優(yōu)先級(jí)大于括號(hào)外。于是： 4 + 8 6 / 2 * 3 運(yùn)算過程和結(jié)果唯一。 3) 算符優(yōu)先分析的特點(diǎn):仿效四則運(yùn)算過程，預(yù)先規(guī)定相鄰終結(jié)符之間的優(yōu)先關(guān)系，然后利用這種優(yōu)先關(guān)系來確定句型的“句柄” ，并進(jìn)行規(guī)約。4) 分析器結(jié)構(gòu):#分析程序優(yōu)先關(guān)系矩陣 #符號(hào)棧輸入串例: G E E= E + E | E * E | ( E ) | i Vt = + , * , ( , ) , i 這是一個(gè)二義文法，要用算符優(yōu)先法分析由該文法所確定的語(yǔ)言句子。 如：i + i * i(1) 先確定

45、終結(jié)符之間的優(yōu)先關(guān)系1) 優(yōu)先關(guān)系的定義： 設(shè) a，b 為可能相鄰的終結(jié)符定義： a = b a的優(yōu)先級(jí)等于b a b a的優(yōu)先級(jí)大于b. .優(yōu)先關(guān)系矩陣 ) = i * + # ) ( i * +ba. . . . . . . . .2) 矩陣元素空白處表示這兩個(gè)終結(jié)符不能相鄰，故沒有優(yōu)先關(guān)系。(2) 分析過程 i + i * i算法： 當(dāng)棧頂項(xiàng)（或次棧頂項(xiàng)）終結(jié)符的優(yōu)先級(jí)大 于棧外的終結(jié)符的優(yōu)先級(jí)則進(jìn)行規(guī)約，否則 移進(jìn)。步驟符號(hào)棧輸入串優(yōu)先關(guān)系 動(dòng)作1i + i * i # i移進(jìn)#7# E + E *i #* #規(guī)約3# E+ i * i # +移進(jìn)4# E +i * i #+ i移進(jìn)6

46、# E + E* i #+ +規(guī)約5# E + i* i #i *規(guī)約8# E + E * i#i #規(guī)約10# E + E#+ #規(guī)約11# E#接受 ) = i * + # ) ( i * +ba. . . . . . . . .E= E + E | E * E | ( E ) | i 分析過程是從符號(hào)串開始，根據(jù)相鄰終結(jié)符之間的優(yōu)先關(guān)系確定句型的“句柄”并進(jìn)行規(guī)約，直到識(shí)別符號(hào)E。最后分析成功: i + i * i L ( G E )出錯(cuò)情況： 1. 相鄰終結(jié)符之間無優(yōu)先關(guān)系。 2. 對(duì)雙目運(yùn)算符進(jìn)行規(guī)約時(shí)，符號(hào)棧中無足夠項(xiàng)。 3. 非正常結(jié)束狀態(tài)。重要說明 上述分析過程不一定是嚴(yán)格的最

47、左規(guī)約（即不一定是 規(guī)范規(guī)約）。也就是每次規(guī)約不一定是規(guī)約當(dāng)前句型 的句柄，而是句柄的變形，但也是短語(yǔ)。(2) 實(shí)際應(yīng)用中，文法終結(jié)符間優(yōu)先關(guān)系一般不用矩陣表示，而是采用兩個(gè)優(yōu)先函數(shù)來表示： f 棧內(nèi)優(yōu)先函數(shù) g 棧外優(yōu)先函數(shù) 若 a b 則令 f ( a ) b f ( a ) g ( b ) .根據(jù)這些原則，構(gòu)造出上述文法的優(yōu)先函數(shù)：算符優(yōu)先函數(shù)值的確定方法 由定義直接構(gòu)造優(yōu)先函數(shù) 用關(guān)系圖構(gòu)造優(yōu)先函數(shù)具體方法不要求！ + * ( ) i #f (棧內(nèi)) 2 4 0 5 50g (棧外) 1 3 6 0 60根據(jù)這些原則，構(gòu)造出上述文法的優(yōu)先函數(shù)：算符優(yōu)先函數(shù)值的確定方法 把各算符優(yōu)先級(jí)按

48、小到大定為j = 0n # （ + * ） i 0 0 1 2 3 對(duì)于各算符的優(yōu)先順序 若為左結(jié)合，則 f (op) = 2 j g (op) = 2 j - 1 若為右結(jié)合，則 f (op) = 2 j g (op) = 2 j 設(shè)m 2 n, 則 f ( j ) = f ( i ) = m + 1 g ( j ) = g ( i ) = m，其他為0 f ( # ) = f ( ( ) = g ( # ) = g ( ) ) = 0 + * ( ) i #f (棧內(nèi)) 2 4 0 5 5 0g (棧外) 1 3 6 0 6 0 + * ( ) i #f (棧內(nèi)) 2 4 0 5 5 0g

49、 (棧外) 1 3 6 0 6 0f ( + ) g ( + ) 左結(jié)合f ( + ) g ( * ) 先乘后加f ( + ) g ( ( ) 先括號(hào)內(nèi)后括號(hào)外 ： ： 特點(diǎn)： 優(yōu)先函數(shù)值不唯一。 優(yōu)點(diǎn)： 節(jié)省內(nèi)存空間。 若文法有n個(gè)終結(jié)符，則關(guān)系矩陣為n2 ，而優(yōu)先函數(shù)為2n。 易于比較：算法上容易實(shí)現(xiàn)。數(shù)與數(shù)比，不必查矩陣。 缺點(diǎn)：可能掩蓋錯(cuò)誤。(3) 可以設(shè)立兩個(gè)棧來代替一個(gè)棧 運(yùn)算對(duì)象棧 (OPND)運(yùn)算符棧 (OPTR)好處是：便于比較，只需將輸入符號(hào)與運(yùn)算符棧的棧頂 符號(hào)相比較。(4) 使用算符優(yōu)先分析方法可以分析二義性文法所產(chǎn)生的語(yǔ)言例: G E E= E + E | E * E

50、 | ( E ) | i Vt = + , * , ( , ) , i 二義性文法若按規(guī)范分析，其句柄不唯一。這是一個(gè)二義性文法，i + i * i 有兩棵語(yǔ)法樹。 E E * E E + i i i E如對(duì)句型E + E * i ，規(guī)范規(guī)約時(shí)句柄不唯一，所以整個(gè)規(guī)約過程就不唯一，編譯所得的結(jié)果也將不唯一。 E E + E E E * i i i4.3.3 算符優(yōu)先分析法的進(jìn)一步討論 三個(gè)問題: (1) 算符優(yōu)先文法(OPG) (2) 構(gòu)造優(yōu)先關(guān)系矩陣 (3) 算符優(yōu)先分析算法的設(shè)計(jì)（1）算符優(yōu)先文法（OPGOperator Precedence Grammar）算符文法（OG）的定義 若文法

51、中無形如U= VW的規(guī)則，這里V, WVn則稱G為OG文法，也就是算符文法。算符文法不允許兩個(gè)非終結(jié)符相鄰！優(yōu)先關(guān)系的定義 若G是一個(gè)OG文法，a, bVt , U, V, WVn分別有以下三種情況:1) a=b iff 文法中有形如 U=ab或U=aVb 的規(guī)則。2) ab iff 文法中有形如 U=Wb的規(guī)則，其中 Wa或WaV 。+.+.例：文法G E E := E + T | TT := T * F | FF := ( E ) | i1) a=b iff 文法中有形如 U=ab或U=aVb 的規(guī)則。2) ab iff 文法中有形如 U=Wb的規(guī)則, 其中 Wa或WaV 。+ . .+對(duì)

52、于E:= E + T E = E + T + + T = T * F + F = ( E ) + F = i + E + T + ) ( = ) ( +. . . . . .對(duì)于OG算法的幾點(diǎn)說明： 運(yùn)算是以中綴形式出現(xiàn)的。 算法語(yǔ)言中的表達(dá)式以及大部分語(yǔ)言成分的文法均是OG文法。 可以證明，若文法為OG文法，則不會(huì)出現(xiàn)兩個(gè)非終結(jié)符相鄰的句型。算符優(yōu)先文法（OPGOperator Precedence Grammar）的定義 設(shè)有一OG文法，如果在任意兩個(gè)終結(jié)符之間，至多只有上述關(guān)系中的一種，則稱該文法為算符優(yōu)先文法(OPG)。（2）構(gòu)造優(yōu)先關(guān)系矩陣FIRSTVT( U ) = b | U b

53、或U Vb, bVt , VVn+LASTVT( U ) = a | U a 或U aV, aVt , VVn+求“ = ” 檢查每一條規(guī)則，若有U:=ab 或 U:=aVb, 則 a=b。.求“ ”復(fù)雜一些，需定義兩個(gè)集合：. .求“ ”:. .若文法有規(guī)則 W= . a U. ，對(duì)任何b, bFIRSTVT( U ) 則有：a b .構(gòu)造FIRSTVT(U)的算法1)若有規(guī)則U= b或U= V b 則bFIRSTVT(U)（FIRSTVT的定義中一步推導(dǎo)）2)若有規(guī)則U= V且 bFIRSTVT(V), 則bFIRSTVT(U) （FIRSTVT的定義中多步推導(dǎo)）說明：因?yàn)閂 b 或 V

54、W b， 所以有U V b 或 U V W b+設(shè)一個(gè)棧S和一個(gè)二維布爾數(shù)組FFU, b = TRUE iff bFIRSTVT(U)具體程序如下:PROCEDURE INSERT(U, b) IF NOT FU, b THEN BEGIN FU, b := TRUE; 把(U, b)推進(jìn)S棧 /* bFIRSTVT(U) */ ENDmain( )BEGIN FOR 每個(gè)非終結(jié)符號(hào)U和終結(jié)符b DO FU, b := FALSE; /*賦初值*/ FOR 每個(gè)形如 U := b或U := Vb 的規(guī)則 DO INSERT(U, b); /*完成算法的第1條*/ WHILE S棧非空 DO B

55、EGIN 把S棧的頂項(xiàng)彈出，記為 (V, b) /* bFIRSTVT(V)*/ FOR 每個(gè)形如U := V的規(guī)則 DO INSERT (U, b); /* bFIRSTVT(U)*/ END OF WHILE /*完成算法的第2條*/END 上述算法的工作結(jié)果是得到一個(gè)二維的布爾數(shù)組F，從F可以得到任何非終結(jié)符號(hào) U 的FIRSTVT： FIRSTVT( U ) = b | FU, b = TRUE 構(gòu)造LASTVT(U)的算法1.若有規(guī)則U:=a 或 U:=aV，則aLASTVT(U)2.若有規(guī)則U:=V，且aLASTVT(V) 則 aLASTVT(U)設(shè)一個(gè)棧 ST 和一個(gè)布爾數(shù)組 B

56、PROCEDURE INSERT(U, a) IF NOT BU, a THEN BEGIN BU, a := TRUE； 把(U, a)推進(jìn)ST棧； END主程序：BEGIN FOR 每個(gè)非終結(jié)符號(hào)U和終結(jié)符號(hào)a DO BU, a := FALSE; FOR 每個(gè)形如U:=a 或 U:=aV 的規(guī)則 DO INSERT (U, a); WHILE ST棧非空 DO BEGIN 把ST棧的棧頂彈出，記為(V, a); FOR 每條形如U:=V的規(guī)則 DO INSERT(U, a); END OF WHILEEND構(gòu)造優(yōu)先關(guān)系矩陣的算法FOR 每條規(guī)則U:= x1 x2xn DO FOR i:=

57、1 TO n-1 DO BEGIN IF xi和xi+1均為終結(jié)符, THEN 置 xi=xi+1 IF in-2，且xi和xi+2都為終結(jié)符號(hào)但 xi+1為非終結(jié)符號(hào) THEN 置 xi=xi+2 IF xi為終結(jié)符號(hào)xi+1為非終結(jié)符號(hào) THEN FOR FIRSTVT(xi+1)中的每個(gè)b DO 置xixi+1 END .（3）算符優(yōu)先分析算法的實(shí)現(xiàn) 先定義優(yōu)先級(jí)，在分析過程中通過比較相鄰運(yùn)算符之間的優(yōu)先級(jí)來確定句型的“句柄”并進(jìn)行歸約。定義 素短語(yǔ)：文法G的句型的素短語(yǔ)是一個(gè)短語(yǔ)，它至少包含有一個(gè)終結(jié)符號(hào)，并且除它自身以外不再包含其它素短語(yǔ)。？ 最左素短語(yǔ)從文法的語(yǔ)法樹中可以找出以下短

58、語(yǔ)：T * F 為最左素短語(yǔ)！而該句型的句柄為T。例: 文法G E E := E + T | T T := T * F | F F := ( E ) | i求句型 T + T * F + i 的最左素短語(yǔ)。 T + T * F + i T + T * F T T * F i 包含其它短語(yǔ) 包含其它短語(yǔ) 不包含終結(jié)符 是素短語(yǔ) 是素短語(yǔ)文法的語(yǔ)法樹 T E + T + T F* F i E E T更進(jìn)一步，對(duì)句型：T + T + i 短語(yǔ)：T + T + iT + TT i句柄：T素短語(yǔ)：T + T ，i最左素短語(yǔ)：T + T E + T + T F i E E T對(duì)于算符優(yōu)先分析法：如何確定當(dāng)

59、前句型的最左素短語(yǔ)？設(shè)有OPG文法句型為: # N1 a1 N2 a2 Nn an Nn+1 #其中Ni 為非終結(jié)符(可以為空)，ai 為終結(jié)符。定理：一個(gè)OPG句型的最左素短語(yǔ)是滿足下列條件的最左子串：aj-1 Nj aj Ni ai Ni+1 ai+1其中 aj-1 ai+1. . . . 根據(jù)該定理，要找句型的最左素短語(yǔ)就是要找滿足上述條件的最左子串。 注意：出現(xiàn)在 aj 左端和 ai 右端的非終結(jié)符號(hào)一定屬于這個(gè)素短語(yǔ)，因?yàn)槲覀兊倪\(yùn)算是中綴形式給出的（OPG文法的特點(diǎn)）N a N a N a N N a W a N例: 文法G E E := E + T | T T := T * F |

60、 F F := ( E ) | i分析文法的句型 T + T * F + iNj aj Ni ai Ni+12#T+T+i#+#T+TE. . . .可以看出：1. 每次規(guī)約的最左子串，確實(shí)是當(dāng)前句型的最左素短語(yǔ)(從語(yǔ)法樹可以看出來)2. 規(guī)約的不都是真正的句柄(僅 i 規(guī)約為 F 是句柄，但它同時(shí)也是最左素短語(yǔ))3. 沒有完全按規(guī)則進(jìn)行規(guī)約，因?yàn)樗囟陶Z(yǔ)不一定是簡(jiǎn)單短語(yǔ)步驟句型關(guān)系最左子串規(guī)約符號(hào)1#T+T*F+i#+#T*FT. . . . .3#E+i#+#iF. . .4#E+F#E+FE. . T E + T + TF* F i E E T# + + # E + T + T F i E