編譯原理：第4章 自頂向下的語(yǔ)法分析

1、第四章 自頂向下的語(yǔ)法分析School of Computer Science & Technology Harbin Institute of Technology重點(diǎn)：自頂向下分析的基本思想，預(yù)測(cè)分析器總體結(jié)構(gòu)，預(yù)測(cè)分析表的構(gòu)造，遞歸下降分析法基本思想，簡(jiǎn)單算術(shù)表達(dá)式的遞歸下降分析器。難點(diǎn)：FIRST 和 FOLLOW 集的求法，對(duì)它們的理解以及在構(gòu)造LL(1)分析表時(shí)的使用。遞歸子程序法中如何體現(xiàn)分析的結(jié)果。2022/7/172第4章 自頂向下的語(yǔ)法分析4.1 語(yǔ)法分析概述 4.2 自頂向下的語(yǔ)法分析面臨的問(wèn)題 與文法的改造 4.3 預(yù)測(cè)分析法 4.4 遞歸下降分析法 4.5 本章小結(jié)2

2、022/7/173語(yǔ)法分析的功能和位置語(yǔ)法分析(syntax analysis)是編譯程序的核心部分，其任務(wù)是檢查詞法分析器輸出的單詞序列是否是源語(yǔ)言中的句子，亦即是否符合源語(yǔ)言的語(yǔ)法規(guī)則。 圖4.1語(yǔ)法分析器在編譯器中的位置2022/7/1744.1 語(yǔ)法分析概述 遞歸子程序法自頂向下 預(yù)測(cè)分析法(LL(1) 算符優(yōu)先分析法自底向上 LR(0)、SLR(1)、LR(1)、LALR(1)Top DownBottom Up從文法產(chǎn)生語(yǔ)言的角度從自動(dòng)機(jī)識(shí)別語(yǔ)言的角度從根開(kāi)始，逐步為某語(yǔ)句構(gòu)造一棵語(yǔ)法樹(shù)相反，將一句子歸約為開(kāi)始符號(hào)問(wèn)題：解決確定性問(wèn)題！假定文法是壓縮的：即刪除了單位產(chǎn)生式和無(wú)用產(chǎn)生式

3、。2022/7/1754.2 自頂向下的語(yǔ)法分析面臨的問(wèn)題與文法的改造自頂向下語(yǔ)法分析的基本思想從文法的開(kāi)始符號(hào)出發(fā)，尋求所給的輸入符號(hào)串的一個(gè)最左推導(dǎo)。從樹(shù)根S開(kāi)始，構(gòu)造所給輸入符號(hào)串的語(yǔ)法樹(shù)例:設(shè)有G：SxAy A*|*，輸入串：x*ySxAy x*ySxAy*2022/7/1764.2.1 自頂向下分析面臨的問(wèn)題1.二義性問(wèn)題對(duì)于文法G，如果L(G)中存在一個(gè)具有兩棵或兩棵以上分析樹(shù)的句子，則稱G是二義性的。也可以等價(jià)地說(shuō)：如果L(G)中存在一個(gè)具有兩個(gè)或兩個(gè)以上最左(或最右)推導(dǎo)的句子，則G是二義性文法。如果一個(gè)文法G是二義性的，假設(shè)wL(G)且w存在兩個(gè)最左推導(dǎo)，則在對(duì)w進(jìn)行自頂向下

4、的語(yǔ)法分析時(shí)，語(yǔ)法分析程序?qū)o(wú)法確定采用w的哪個(gè)最左推導(dǎo)。Gexp：EE+T | E-T| TTT*F | T/F | FFFP | P Pc | id | (E) 解決辦法：改造文法，引入新的文法變量2022/7/1774.2.1 自頂向下分析面臨的問(wèn)題2.回溯問(wèn)題文法中每個(gè)語(yǔ)法變量A的產(chǎn)生式右部稱為A的候選式，如果A有多個(gè)候選式存在公共前綴，則自頂向下的語(yǔ)法分析程序?qū)o(wú)法根據(jù)當(dāng)前輸入符號(hào)準(zhǔn)確地選擇用于推導(dǎo)的產(chǎn)生式，只能試探。當(dāng)試探不成功時(shí)就需要退回到上一步推導(dǎo)，看A是否還有其它的候選式，這就是回溯(backtracking)。Ge：ET EE+T EE-T TF TT*F TT/F F(E

5、) Fid 例如：考慮為輸入串id+id*id建立最左推導(dǎo) 2022/7/1784.2.1 自頂向下分析面臨的問(wèn)題2.回溯問(wèn)題ET (4.1)ETF (4.2)ETF(E) (4.3)ETFid (4.4)ETT*F (4.5). 4.2.2節(jié)我們將采用提取左因子的方法來(lái)改造文法，以便減少推導(dǎo)過(guò)程中回溯現(xiàn)象的發(fā)生，當(dāng)然，單純通過(guò)提取左因子無(wú)法徹底避免回溯現(xiàn)象的發(fā)生。 2022/7/1794.2.1 自頂向下分析面臨的問(wèn)題3.左遞歸引起的無(wú)窮推導(dǎo)問(wèn)題假設(shè)A是文法G的某個(gè)語(yǔ)法變量，如果存在推導(dǎo)A A，則稱文法G是遞歸的，當(dāng)=時(shí)稱之為左遞歸；如果A A至少需要兩步推導(dǎo)，則稱文法G是間接遞歸的，當(dāng)=時(shí)

6、稱之為間接左遞歸；如果文法G中存在形如AA的產(chǎn)生式，則稱文法G是直接遞歸的，當(dāng)=時(shí)稱之為直接左遞歸。Ger：ET EE+T EE-T TF TT*F TT/F F(E) Fid 考慮為輸入串id+id*id建立一個(gè)最左推導(dǎo) EE+TE+T+TE+T+T+T 2022/7/17104.2.2 對(duì)上下文無(wú)關(guān)文法的改造 1.消除二義性改造的方法就是通過(guò)引入新的語(yǔ)法變量等，使文法含有更多的信息。其實(shí)，許多二義性文法是由于概念不清，即語(yǔ)法變量的定義不明確導(dǎo)致的，此時(shí)通過(guò)引入新的語(yǔ)法變量即可消除文法的二義性。 if then | if then else | other (4.7)根據(jù)if語(yǔ)句中else與

7、then配對(duì)情況將其分為配對(duì)的語(yǔ)句和不配對(duì)的語(yǔ)句兩類。上述if語(yǔ)句的文法沒(méi)有對(duì)這兩個(gè)不同的概念加以區(qū)分，只是簡(jiǎn)單地將它們都定義為，從而導(dǎo)致該文法是二義性的。 2022/7/17114.2.2 對(duì)上下文無(wú)關(guān)文法的改造 引入語(yǔ)法變量來(lái)表示不配對(duì)語(yǔ)句，表示配對(duì)語(yǔ)句 | if then else | other if then | if then else 2022/7/17124.2.2 對(duì)上下文無(wú)關(guān)文法的改造 2.消除左遞歸直接左遞歸的消除(轉(zhuǎn)換為右遞歸)引入新的變量A ，將左遞歸產(chǎn)生式AA|替換為AA A A | EE+T|T TT*F|F F(E)|id替換為：ETE E+TE| TFT T*

8、FT | F(E)|id 一般地，假設(shè)文法G中的語(yǔ)法變量A的所有產(chǎn)生式如下：AA1|A2|An|1|2|m其中，i(i=1,2,m)不以A打頭。則用如下的產(chǎn)生式代替A的所有產(chǎn)生式即可消除其直接左遞歸：A1A|2A|mA A1A|2A|nA| 2022/7/17134.2.2 對(duì)上下文無(wú)關(guān)文法的改造 算法4.1 消除左遞歸。輸入：不含循環(huán)推導(dǎo)和-產(chǎn)生式的文法G;輸出：與G等價(jià)的無(wú)左遞歸文法;步驟：1將G的所有語(yǔ)法變量排序(編號(hào))，假設(shè)排序后的語(yǔ)法變量記為A1，A2，An；2for i1 to n 3for j1 to i-1 4用產(chǎn)生式Ai1|2|k代替每個(gè)形如AiAj的產(chǎn)生式，其中，Aj1|2

9、|k是所有的當(dāng)前Aj產(chǎn)生式；5 6 消除Ai產(chǎn)生式中的所有直接左遞歸7 2022/7/17144.2.2 對(duì)上下文無(wú)關(guān)文法的改造3.提取左因子對(duì)每個(gè)語(yǔ)法變量A，找出它的兩個(gè)或更多候選式的最長(zhǎng)公共前綴。如果，則用下面的產(chǎn)生式替換所有的A產(chǎn)生式A1|2|n|1|2|n，其中1，2，n表示所有不以開(kāi)頭的候選式：AA|1|2|nA1|2|n其中，A是新引入的語(yǔ)法變量。反復(fù)應(yīng)用上述變換，直到任意語(yǔ)法變量都沒(méi)有兩個(gè)候選式具有公共前綴為止。請(qǐng)讀者自行給出這個(gè)變換的算法。 2022/7/17154.2.3 LL(1)文法問(wèn)題：什么樣的文法對(duì)其句子才能進(jìn)行確定的自頂向下分析？確定的自頂向下分析首先從文法的開(kāi)始符

10、號(hào)出發(fā)，每一步推導(dǎo)都根據(jù)當(dāng)前句型的最左語(yǔ)法變量A和當(dāng)前輸入符號(hào)a，選擇A的某個(gè)候選式來(lái)替換A，并使得從推導(dǎo)出的第一個(gè)終結(jié)符恰好是a。當(dāng)A有多個(gè)候選式時(shí)，當(dāng)前選中的候選式必須是惟一的。第一個(gè)終結(jié)符是指符號(hào)串的第一個(gè)符號(hào)，并且是終結(jié)符號(hào)，可以稱為首終結(jié)符號(hào)。在自頂向下的分析中，它對(duì)選取候選式具有重要的作用。為此引入首符號(hào)集的概念。2022/7/17164.2.3 LL(1)文法1. 假設(shè)是文法G=(V，T，P，S)的符號(hào)串，即(VT)*，從推導(dǎo)出的串的首符號(hào)集記作FIRST()：FIRST()=a| a，aT，(VT)*。2. 如果 ，則FIRST()。3. 如果文法G中的所有A產(chǎn)生式為A1|2|

11、m，且FIRST(1)FIRST(2)FIRST(n) 且對(duì)i，j，1i，jm；ij，均有FIRST(i)FIRST(j)=成立，則可以對(duì)G的句子進(jìn)行確定的自頂向下分析2022/7/17174.2.3 LL(1)文法如果存在A這樣的產(chǎn)生式，則需定義FOLLOW(A)A定義A的后續(xù)符號(hào)集為： 1. FOLLOW(A)=a|S Aa, aT, ,(VT)*2. 如果A是某個(gè)句型的最右符號(hào)，則將結(jié)束符#添加到FOLLOW(A)中3. 如果j ，則如果對(duì)i(1im；ij)，F(xiàn)IRST(i)FOLLOW(A)=均成立，則可以對(duì)G的句子進(jìn)行確定的自頂向下分析2022/7/17184.2.3 LL(1)文法

12、如果G的任意兩個(gè)具有相同左部的產(chǎn)生式A|滿足下列條件：1. 如果、均不能推導(dǎo)出，則FIRST()FIRST()=；2. 和至多有一個(gè)能推導(dǎo)出；3. 如果 ，則FIRST()FOLLOW(A) =則稱G為L(zhǎng)L(1)文法。第一個(gè)L代表從左向右掃描輸入符號(hào)串，第二個(gè)L代表產(chǎn)生最左推導(dǎo)，1代表在分析過(guò)程中執(zhí)行每步推導(dǎo)都要向前查看一個(gè)輸入符號(hào) 2022/7/1719LL(1)文法的判定算法4.2 計(jì)算FIRST(X)。輸入：文法G=(V，T，P，S)，X(VT);輸出：FIRST(X);步驟：1FIRST(X)= ;2if (XT) then FIRST(X):= X ;3if XV then begi

13、n4if (XP) then FIRST(X):= FIRST(X)a|XaP;5if (XP) then FIRST(X):= FIRST(X)a|XaPend6對(duì)X，重復(fù)如下的過(guò)程7-10，直到所有FIRST集不變?yōu)橹埂?if (XYP and YV) then FIRST(X):= FIRST(X)(FIRST(Y)-)；8if (XY1YnP and Y1.Yi-1 ) then 9for k=2 to i do FIRST(X):= FIRST(X)(FIRST(Yk)-);10if Y1.Yn then FIRST(X):=FIRST(X); 2022/7/1720LL(1)文法的

14、判定算法4.3 計(jì)算FIRST()。輸入：文法G=(V，T，P，S)，(VT)*，= X1Xn;輸出：FIRST();步驟：1計(jì)算FIRST(X1);2FIRST():= FIRST(X1)-;3k:=1;4while (FIRST(Xk) and kn) do begin5 FIRST():= FIRST()(FIRST(Xk+1)-);6 k:=k+1 end7if (k=n and FIRST(Xk) then FIRST():=FIRST(); 2022/7/1721例 表達(dá)式文法的語(yǔ)法符號(hào)的FIRST 集FIRST(F)=（, idFIRST(T)=FIRST(F)=（, id FI

15、RST(E)=FIRST(T)=（, id FIRST(E)=+，F(xiàn)IRST(T)=*, FIRST(+)=+, FIRST(*)=*FIRST(（)=（FIRST(）)=）FIRST(id)=idETE E+TE| TFT T*FT| F(E)|id2022/7/1722LL(1)文法的判定算法4.4 計(jì)算FOLLOW集。輸入：文法G=(V，T，P，S)，AV;輸出：FOLLOW(A);步驟：1對(duì)XV，F(xiàn)OLLOW(X) := ;2FOLLOW(S) := #，#為句子的結(jié)束符;3對(duì)XV，重復(fù)下面的第4步到第5步，直到所有FOLLOW集不變?yōu)橹埂?若ABP，則FOLLOW(B):=FOLLO

16、W(B)FIRST();5若AB或ABP，且 ，AB，則FOLLOW(B):=FOLLOW(B)FOLLOW(A); 2022/7/1723例 表達(dá)式文法的語(yǔ)法變量的 FOLLOW 集FOLLOW(E) = #, ) FOLLOW(E)= FOLLOW( E ) = #, ) FOLLOW(T) = FIRST(E)-FOLLOW(E)FOLLOW(E)= +,),#FOLLOW(T)= FOLLOW(T)= +,),#FOLLOW(F) = FIRST(T)FOLLOW(T)FOLLOW(T) =*,+,),# ETE E+TE|TFT T*FT|F(E)|idFIRST(F)=（,idFI

17、RST(T)=FIRST(F)=（,id FIRST(E)=FIRST(T)=（,id FIRST(E)=+，F(xiàn)IRST(T)=*,2022/7/1724表達(dá)式文法是 LL(1) 文法E T E E + T E T F T T * F T F ( E )id考察E : + 不在 FOLLOW( E ) = ), # T : * 不在 FOLLOW( T ) = +, ), # F: ( 和 id 不同2022/7/1725非 LL(1)文法的不確定性例 對(duì)文法ScAdAab|a 輸入 cad 的分析SdcAbaSdcAa2022/7/1726不確定性的解決方法1) 采用回溯算法過(guò)于復(fù)雜，效率低

18、下2）改寫文法將非LL(1)文法改寫為等價(jià)的LL(1)文法無(wú)法改寫時(shí)：增加其它的判別因素文法過(guò)于復(fù)雜，無(wú)法用自頂向下方法處理2022/7/17274.3 預(yù)測(cè)分析法系統(tǒng)維持一個(gè)分析表和一個(gè)分析棧，根據(jù)當(dāng)前掃描到的符號(hào)，選擇當(dāng)前語(yǔ)法變量（處于棧頂）的候選式進(jìn)行推導(dǎo)希望找到相應(yīng)輸入符號(hào)串的最左推導(dǎo)。一個(gè)通用的控制算法一個(gè)分析棧，#為棧底符號(hào)一個(gè)輸入緩沖區(qū)，#為輸入串結(jié)束符一個(gè)統(tǒng)一形式的分析表M不同語(yǔ)言使用內(nèi)容不同的分析表2022/7/17284.3.1 預(yù)測(cè)分析器的構(gòu)成 輸入緩沖區(qū)(符號(hào)序列)棧預(yù)測(cè)分析程序預(yù)測(cè)分析表M輸出的產(chǎn)生式序列2022/7/1729系統(tǒng)的執(zhí)行與特點(diǎn)在系統(tǒng)啟動(dòng)時(shí)，輸入指針指向

19、輸入串的第一個(gè)字符，分析棧中存放著棧底符號(hào)#和文法的開(kāi)始符號(hào)。根據(jù)棧頂符號(hào)A和讀入的符號(hào)a，查看分析表M,以決定相應(yīng)的動(dòng)作。優(yōu)點(diǎn)：1）效率高2）便于維護(hù)、自動(dòng)生成關(guān)鍵分析表M的構(gòu)造2022/7/1730預(yù)測(cè)分析程序的總控程序 算法4.5 預(yù)測(cè)分析程序的總控程序。輸入：輸入串w和文法G=(V, T, P, S)的分析表M;輸出：如果w屬于L(G)，則輸出w的最左推導(dǎo)，否則報(bào)告錯(cuò)誤;步驟：1將棧底符號(hào)#和文法開(kāi)始符號(hào)S壓入棧中;2repeat3X:=當(dāng)前棧頂符號(hào);4a:=當(dāng)前輸入符號(hào);5if XT# then6if X=a then7 if X# then begin8將X彈出棧;9前移輸入指針1

20、0end 2022/7/1731預(yù)測(cè)分析程序的總控程序 11else error12else 13if MX, a=Y1Y2Yk then begin14 將X彈出棧;15依次將Yk，Y2，Y1壓入棧;16輸出產(chǎn)生式XY1Y2Yk17end18else error19until X=# 2022/7/1732FOLLOW( E)= ), # FOLLOW( T)= +, ), # FIRST(TE)=(,id FIRST(+TE)=+FIRST(FT)=(,id FIRST(*FT)=*FIRST(E)=( FIRST(id)=idETE E+TE| TFT T*FT| F(E)|id例4.1

21、0 考慮簡(jiǎn)單算術(shù)表達(dá)式文法的實(shí)現(xiàn)2022/7/1733簡(jiǎn)單算術(shù)表達(dá)式文法的預(yù)測(cè)分析表2022/7/1734對(duì)輸入串id+id*id進(jìn)行分析的過(guò)程（在黑板上同時(shí)畫(huà)出語(yǔ)法樹(shù)）棧 輸入緩沖區(qū) 輸出#E id+id*id# #ET id+id*id# ETE#ETF id+id*id# TFT#ETid id+id*id# Fid#ET +id*id# #E +id*id# T#ET+ +id*id# E+TE#ET id*id# 2022/7/1735#ETF id*id# TFT#ETid id*id# Fid#ET *id# #ETF* *id# T*FT#ETF id#ETid id# Fid

22、#ET #E # T# # E輸出的產(chǎn)生式序列形成了最左推導(dǎo)對(duì)應(yīng)的分析樹(shù)#ET id*id#2022/7/17364.3.2 預(yù)測(cè)分析表的構(gòu)造算法算法4.6 預(yù)測(cè)分析表(LL(1)分析表)的構(gòu)造算法。輸入：文法G;輸出：分析表M;步驟：1對(duì)G中的任意一個(gè)產(chǎn)生式A, 執(zhí)行第2步和第3步;2 for aFIRST(), 將A填入MA, a;3 if FIRST() then aFOLLOW(A),將A填入MA, a; if FIRST()4將所有無(wú)定義的MA, b標(biāo)上出錯(cuò)標(biāo)志。2022/7/1737預(yù)測(cè)分析法的實(shí)現(xiàn)步驟1. 構(gòu)造文法2. 改造文法：消除二義性、消除左遞歸、提取左因子3. 求每個(gè)候選

23、式的FIRST集和變量的FOLLOW集4. 檢查是不是 LL(1) 文法 若不是 LL(1),說(shuō)明文法的復(fù)雜性超過(guò)自頂向下方法的分析能力，需要附加新的“信息”5. 構(gòu)造預(yù)測(cè)分析表6. 實(shí)現(xiàn)預(yù)測(cè)分析器2022/7/17384.3.3 預(yù)測(cè)分析中錯(cuò)誤的處理 對(duì)語(yǔ)法變量A，如果MA,a無(wú)定義，并且a屬于FOLLOW(A)，則增加MA,a為“同步點(diǎn)”(synch), 同步記號(hào)選擇方法如下：把FOLLOW(A)的所有符號(hào)放入語(yǔ)法變量A的同步記號(hào)集合中。把高層結(jié)構(gòu)的開(kāi)始符號(hào)加到低層結(jié)構(gòu)的同步記號(hào)集合中。把FIRST(A)的符號(hào)加入A的同步記號(hào)集合。如果語(yǔ)法變量可以產(chǎn)生空串，若出錯(cuò)時(shí)棧頂是這樣的語(yǔ)法變量，則

24、可以使用產(chǎn)生空串的產(chǎn)生式。如果符號(hào)在棧頂而不能匹配，則彈出此符號(hào)。2022/7/17394.4 遞歸下降分析法一個(gè)設(shè)想1. 對(duì)應(yīng)每個(gè)變量設(shè)置一個(gè)處理子程序： AX1 X2 Xk Xn 當(dāng)遇到Xk是終極符號(hào)時(shí)直接進(jìn)行匹配; 當(dāng)遇到Xk是語(yǔ)法變量時(shí)就調(diào)用X對(duì)應(yīng)的處理子程序.2. 要求處理子程序是可以遞歸調(diào)用的ETE E+TE| TFT T*FT| F(E)|id2022/7/17404.4.1 遞歸下降分析法的基本思想例4.14 對(duì)于產(chǎn)生式E+TE，與E對(duì)應(yīng)的子程序可以按如下方式來(lái)編寫：procedure E begin match(+); T; /*調(diào)用識(shí)別T的過(guò)程*/E /*調(diào)用識(shí)別E的過(guò)程*

25、/ end; 2022/7/17414.4.1 遞歸下降分析法的基本思想其中，服務(wù)子程序match用來(lái)匹配當(dāng)前的輸入記號(hào)，其代碼為：procedure match(t:token); begin if lookhead=t then lookhead:=nexttoken; else error /*調(diào)用出錯(cuò)處理程序*/ end; 2022/7/17424.4.2 語(yǔ)法圖和遞歸子程序法狀態(tài)轉(zhuǎn)換圖（語(yǔ)法圖）是非常有用的設(shè)計(jì)工具語(yǔ)法分析器和詞法分析器的狀態(tài)轉(zhuǎn)換圖不同每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)狀態(tài)轉(zhuǎn)換圖，邊上的標(biāo)記是記號(hào)和非終結(jié)符記號(hào)上的轉(zhuǎn)換意味著如果該記號(hào)是下一個(gè)輸入符號(hào)，就應(yīng)進(jìn)行轉(zhuǎn)換非終結(jié)符A上的轉(zhuǎn)換

26、是對(duì)與A對(duì)應(yīng)的過(guò)程的調(diào)用2022/7/17434.4.2 語(yǔ)法圖和遞歸子程序法從文法構(gòu)造語(yǔ)法圖，對(duì)每個(gè)非終結(jié)符A執(zhí)行如下操作創(chuàng)建一個(gè)開(kāi)始狀態(tài)和一個(gè)終止?fàn)顟B(tài)（返回狀態(tài)）對(duì)每個(gè)產(chǎn)生式AX1X2 Xn，創(chuàng)建一條從開(kāi)始狀態(tài)到終止?fàn)顟B(tài)的路徑，邊上的標(biāo)記分別為X1，X2， ，Xn2022/7/1744例4.15 簡(jiǎn)單表達(dá)式文法的語(yǔ)法圖ETEE+TE|TFTT*FT|F(E)|id2022/7/17454.4.3基于語(yǔ)法圖的語(yǔ)法分析器工作方式 初始時(shí)，分析器進(jìn)入狀態(tài)圖的開(kāi)始狀態(tài)，輸入指針指向輸入符號(hào)串的第一個(gè)符號(hào)。如果經(jīng)過(guò)一些動(dòng)作后，它進(jìn)入狀態(tài)s，且從狀態(tài)s到狀態(tài)t的邊上標(biāo)記了終結(jié)符a，此時(shí)下一個(gè)輸入符又正

27、好是a，則分析器將輸入指針向右移動(dòng)一位，并進(jìn)入狀態(tài)t。2022/7/17464.4.3基于語(yǔ)法圖的語(yǔ)法分析器工作方式 另一方面，如果邊上標(biāo)記的是非終結(jié)符A，則分析器進(jìn)入A的初始狀態(tài)，但不移動(dòng)輸入指針。一旦到達(dá)A的終態(tài)，則立刻進(jìn)入狀態(tài)t，事實(shí)上，分析器從狀態(tài)s轉(zhuǎn)移到狀態(tài)t時(shí)，它已經(jīng)從輸入符號(hào)串“讀”了A （調(diào)用A對(duì)應(yīng)的過(guò)程）。最后，如果從s到t有一條標(biāo)記為的邊，那么分析器從狀態(tài)s直接進(jìn)入狀態(tài)t而不移動(dòng)輸入指針。 2022/7/1747圖4.6算術(shù)表達(dá)式的簡(jiǎn)化語(yǔ)法圖4.4.4 語(yǔ)法圖的化簡(jiǎn)與實(shí)現(xiàn) 左因子提取將形如AYX|YZ的產(chǎn)生式替換為AY(X|Z)； 右因子提取將形如AYX|ZX的產(chǎn)生式替換為

28、A(Y|Z)X； 尾遞歸消除將形如XYX|Z的產(chǎn)生式替換為XY*Z。2022/7/1748的子程序(ET(+T)*)procedure E; begin T; T的過(guò)程調(diào)用 while lookhead=+ do begin 當(dāng)前符號(hào)等于+時(shí) match(+); 處理終結(jié)符+ T T的過(guò)程調(diào)用 end end; lookhead：當(dāng)前符號(hào) 例4.16 簡(jiǎn)單算術(shù)表達(dá)式的語(yǔ)法分析器2022/7/1749的子程序(TF(*F)*)procedure T; begin F; F的過(guò)程調(diào)用 while lookhead=* then begin 當(dāng)前符號(hào)等于*時(shí) match(*); 處理終結(jié)符* F F的遞歸調(diào)用 end end;2022/7/1750