第三章 語法分析

1第三章語法分析詞法分析：字母是元素，組成字符串，記號的集合，線性結(jié)構(gòu)語法分析：記號是元素，組成句子，句子的集合，樹結(jié)構(gòu)語法的雙重含義語法規(guī)則：上下文無關(guān)文法(子集－LL文法、LR文法)語法分析：下推自動機(jī)(LL或LR分析器)，自上而下、自下而上分析主要內(nèi)容語法分析的若干問題上下文無關(guān)文法自上而下分析自下而上分析上機(jī)：DBMS的設(shè)計與實現(xiàn)—SQL的語法分析器23.1語法分析的若干問題語法分析器的作用語法分析器是編譯器前端的重要組成部分，許多編譯器，特別是由自動生成工具構(gòu)造的編譯器，往往其前端的中心部件就是語法分析器。語法分析器在編譯器中的位置和作用：33.1語法分析的若干問題語法分析器的兩個重要作用：根據(jù)詞法分析器提供的記號流，為語法正確的輸入構(gòu)造分析樹（或語法樹），這是本章重點，在以后各節(jié)中詳細(xì)討論；檢查輸入中的語法（可能包括詞法）錯誤，并調(diào)用出錯處理器進(jìn)行適當(dāng)處理，下邊簡單介紹語法錯誤處理的基本原則，而在以后的討論中忽略此問題。43.1語法分析的若干問題語法錯誤的處理原則源程序中可能出現(xiàn)的錯誤

兩類：語法錯誤和語義錯誤詞法錯誤如非法字符或拼寫錯關(guān)鍵字、標(biāo)識符等

@ intege 20times語法錯誤指結(jié)構(gòu)出錯，如少分號、begin/end不配對等

begin x:=a+b y:=x;靜態(tài)語義錯誤：如類型不一致、參數(shù)不匹配等

a,b:integer; x:array[1..10]ofinteger; x:=a+b;動態(tài)語義錯誤(邏輯錯誤)：如死循環(huán)、除數(shù)為變量零等

while(t){...}; a:=a/b;53.1語法分析的若干問題

大多數(shù)錯誤的診斷和恢復(fù)集中在語法分析階段。一個原因是大多數(shù)錯誤是語法錯誤，另一個原因是語法分析方法的準(zhǔn)確性，它們能以非常有效的方法診斷語法錯誤。編譯時想要準(zhǔn)確診斷語義或邏輯錯誤有時是很困難的。語法錯誤處理的目標(biāo)對語法錯誤的處理，一般希望達(dá)到以下基本目標(biāo)：清楚而準(zhǔn)確地報告錯誤的出現(xiàn)，地點正確、不漏報、不錯報也不多報；迅速地從每個錯誤中恢復(fù)過來（以便分析繼續(xù)進(jìn)行）；不應(yīng)使對語法正確的源程序的分析速度降低太多。63.1語法分析的若干問題語法錯誤的基本恢復(fù)策略緊急方式恢復(fù)：拋棄若干輸入，直到遇到同步記號。短語級恢復(fù)：采用串替換的方式對剩余輸入進(jìn)行局部糾正（拋棄＋插入）。出錯產(chǎn)生式：用出錯產(chǎn)生式捕捉錯誤（預(yù)測錯誤）。預(yù)置型的短語級恢復(fù)方式。全局糾正：對錯誤輸入序列x，找相近序列y，使得x變換成y所需的修改、插入、刪除次數(shù)最少。73.1語法分析的若干問題[例3.1]下述兩條是有語法錯誤的語句，其中第一條賦值句結(jié)束時忘記加分號，采用緊急恢復(fù)方式和短語級恢復(fù)方式的可能結(jié)果分別如下所示。

x:=a+b y:=c+d;

緊急方式：x:=a+b+d; --丟棄b后若干記號，直到遇到+

短語級恢復(fù)：x:=a+b; --加入分號，使之成為一個賦值句

y:=c+d;83.2上下文無關(guān)文法(CFG)CFG的定義與表示

上下文無關(guān)文法，ContextFreeGrammar，CFG定義3.1CFG是一個四元組：

G=（N，T，P，S），其中 （1）N是非終結(jié)符（Nonterminals）的有限集合； （2）T是終結(jié)符（Terminals）的有限集合，且N∩T=Φ； （3）P是產(chǎn)生式（Productions）的有限集合，形如：

A→α，其中A∈N（左部），α∈(N∪T)*（右部）， 若α=ε，則稱A→ε為空產(chǎn)生式（也可以記為A→）； （4）S是非終結(jié)符，稱為文法的開始符號（Start symbol）。93.2上下文無關(guān)文法(CFG)[例3.2]簡單算術(shù)表達(dá)式的上下文無關(guān)文法可表示如下：

N={E} T={+，*，(，)，-，id} S=E

P: E→E+E （1）

E→E*E （2）

E→（E） （3）(G3.1) E→-E （4）

E→id （5）產(chǎn)生式的一般讀法 記號→讀作“定義為”或者“可導(dǎo)出”。 “E→E+E”表述為“算術(shù)表達(dá)式定義為兩個算術(shù)表達(dá)式相加”；或者“一個算術(shù)表達(dá)式加上另一個算術(shù)表達(dá)式，仍然是一個算術(shù)表達(dá)式”。103.2上下文無關(guān)文法(CFG)由產(chǎn)生式集表示CFG

前提： 若文法正確

結(jié)論： 文法開始符號S是第一個產(chǎn)生式的左部；

N是可以出現(xiàn)在產(chǎn)生式左邊符號的記號集合；

T是絕不出現(xiàn)在產(chǎn)生式左邊符號的記號集合；

P: E→E+E （1）

E→E*E （2）

E→（E） （3）

E→-E （4）

E→id （5） 產(chǎn)生式表示也被稱為巴克斯范式（Backus-NaurForm，BNF），其中→用::=表示S=E N={E}T={+，*，(，)，-，id}113.2上下文無關(guān)文法(CFG)終結(jié)符與非終結(jié)符書寫上的區(qū)分

(a)

用大小寫區(qū)分：E→id (b)

用""區(qū)分：E→"id"E→E"+"E (c)

用<>區(qū)分：<E>→<E>+<E>

教材約定：大寫英文字母A、B、C表示非終結(jié)符； 小寫英文字母a、b、c表示終結(jié)符； 小寫希臘字母α、β、δ表示任意文法符號序列123.2上下文無關(guān)文法(CFG)產(chǎn)生式的縮寫形式當(dāng)多個產(chǎn)生式的左部非終結(jié)符相同時，可合并為一個產(chǎn)生式。新的產(chǎn)生式的左部是此非終結(jié)符，右部是所有原來右部的或運算（并集合）。[例3.3]G3.1可以重寫為如下形式：

E→ E+E （1）

|E*E （2）

|（E） （3） (G3.2) |-E （4）

|id （5） 用“|”連接的每個右部稱為一個候選項，具有平等的權(quán)利。

BNF如何表示？P:E→E+E (1)E→E*E (2)E→(E) (3)E→-E (4)E→id (5)13上次課總結(jié)語法分析器作用語法錯誤處理CFG的定義與表示143.2上下文無關(guān)文法(CFG)CFG產(chǎn)生語言的基本方法－推導(dǎo)CFG（產(chǎn)生式）通過推導(dǎo)的方法產(chǎn)生語言。通俗地講，產(chǎn)生式產(chǎn)生語言的過程是從開始符號S開始，對產(chǎn)生式左部的非終結(jié)符反復(fù)地使用產(chǎn)生式：將產(chǎn)生式左部的非終結(jié)符替換為右部的文法符號序列（展開產(chǎn)生式，用標(biāo)記=>表示），直到得到一個終結(jié)符序列。[例3.4]用(G3.2)產(chǎn)生終結(jié)符序列-(id+id)可如下：

E→E+E （1）

|E*E （2）

|（E） （3）(G3.2) |-E （4）

|id （5）E=>-E by(4)=>-(E) by(3)=>-(E+E) by(1)=>-(id+E) by(5)=>-(id+id) by(5)153.2上下文無關(guān)文法(CFG)定義3.2

利用產(chǎn)生式產(chǎn)生句子的過程中，將產(chǎn)生式A→γ的右部代替文法符號序列αAβ中的A得到αγβ的過程，稱αAβ直接推導(dǎo)出αγβ，記作：αAβ=>αγβ。若對于任意文法符號序列α1，α2，...αn，均有α1=>α2=>...=>αn，則稱此過程為零步或多步推導(dǎo)，記為：

α1=*>αn，其中α1=αn的情況為零步推導(dǎo)。若α1≠αn，即推導(dǎo)過程中至少使用一次產(chǎn)生式，則稱此過程為至少一步推導(dǎo)，記為：α1=+>αn。 兩點注意：

α，有α=*>α，即推導(dǎo)具有自反性；若α=*>β，β=*>γ，則α=*>γ，即推導(dǎo)具有傳遞性。163.2上下文無關(guān)文法(CFG)定義3.3

由CFGG所產(chǎn)生的語言L(G)被定義為:L(G)={ω┃S=+>ωandω∈T*}，

L(G)稱為上下文無關(guān)語言(ContextFreeLanguage,CFL)，ω稱為句子。 若S=*>α，α∈(N∪T)*，則稱α為G的一個句型。定義3.4

在推導(dǎo)過程中，若每次直接推導(dǎo)均替換句型中最左邊的非終結(jié)符，則稱為最左推導(dǎo)，由最左推導(dǎo)產(chǎn)生的句型被稱為左句型。類似可定義最右推導(dǎo)與右句型，最右推導(dǎo)也被稱為規(guī)范推導(dǎo)。

E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id) α1 α2 α3 α4 α5 α6 α6是句子，所有αi(i=1...6)均是句型。173.2上下文無關(guān)文法(CFG)推導(dǎo)、分析樹與語法樹

E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id)推導(dǎo)產(chǎn)生句子的方式不直觀。分析樹是推導(dǎo)的圖形直觀表示，同時反映語言結(jié)構(gòu)的實質(zhì)和推導(dǎo)過程。定義3.5

對CFGG的句型，分析樹被定義為具有下述性質(zhì)的一棵樹。 （1）根由開始符號所標(biāo)記； （2）每個葉子由一個終結(jié)符、非終結(jié)符、或ε標(biāo)記； （3）每個內(nèi)部結(jié)點由一個非終結(jié)符標(biāo)記； （4）若A是某內(nèi)部節(jié)點的標(biāo)記，且X1，X2，...，Xn是該節(jié)點從左到右所有孩子的標(biāo)記，則A→X1X2...Xn是一個產(chǎn)生式。若A→ε，則標(biāo)記為A的結(jié)點可以僅有一個標(biāo)記為ε的孩子。183.2上下文無關(guān)文法(CFG)分析樹與語言和文法的關(guān)系：每一直接推導(dǎo)(每個產(chǎn)生式)，對應(yīng)一棵僅有父子關(guān)系的子樹，即產(chǎn)生式左部非終結(jié)符“長出”右部的孩子；分析樹的葉子，從左到右構(gòu)成G的一個句型。若葉子僅由終結(jié)符標(biāo)記，則構(gòu)成一個句子。[例3.5]再考察-(id+id)的推導(dǎo)過程。

E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id)

最左推導(dǎo)和最右推導(dǎo)的中間過程對應(yīng)的分析樹可能不同，但最終的分析樹相同，因為最終是同一個句子193.2上下文無關(guān)文法(CFG)分析樹既反映了產(chǎn)生句型的推導(dǎo)過程，又反映了句型的結(jié)構(gòu)。在更多的情況下，僅關(guān)注句型結(jié)構(gòu)，而忽略推導(dǎo)過程。定義3.6

對CFGG的句型，表達(dá)式的語法樹被定義為具有下述性質(zhì)的一棵樹:

（1）根與內(nèi)部節(jié)點由表達(dá)式中的操作符標(biāo)記； （2）葉子由表達(dá)式中的操作數(shù)標(biāo)記； （3）用于改變運算優(yōu)先級和結(jié)合性的括弧，被隱含在語法樹的結(jié)構(gòu)中。 語法樹與分析樹的最根本區(qū)別在于內(nèi)部節(jié)點（包括根節(jié)點）：分析樹的內(nèi)部節(jié)點是非終結(jié)符；語法樹的內(nèi)部節(jié)點是操作符（運算符）；或者說語法樹中省略了反映分析過程的非終結(jié)符。203.2上下文無關(guān)文法(CFG)[例3.6]句子-(id+id)和句型ifCthens1elses2分析樹：左部非終結(jié)符“產(chǎn)生”右部文法符號序列；語法樹：操作符(運算)作用于操作數(shù)(運算對象)；習(xí)慣上它們分別被稱為具體語法樹和抽象語法樹。213.2上下文無關(guān)文法(CFG)二義性與二義性的消除 二義性問題：一個句子可能對應(yīng)多于一棵分析樹[例3.7]文法G3.2為 E→E+E|E*E|（E）|-E|id

句子id+id*id和id+id+id可能的分析樹有：223.2上下文無關(guān)文法(CFG)定義3.7

若文法G對同一句子產(chǎn)生不止一棵分析樹，則稱G是二義的。

原因：在產(chǎn)生句子的過程中某些直接推導(dǎo)有多于一種選擇注意：一個句子有多于一棵分析樹，僅與文法和句子有關(guān)，與采用的推導(dǎo)方法無關(guān)；文法中缺少對文法符號優(yōu)先級和結(jié)合性的規(guī)定?！皯铱眨╠angling）else”問題S→ ifCthenS (1) |ifCthenSelseS (2) |id:=E (3) (G3.3)C→ E=E|E<E|E>E (4)...(6)E→ E+E|-E|id|n (7)...(10)233.2上下文無關(guān)文法(CFG)[例3.8]條件語句ifx<3thenifx>0thenx:=5elsex:=-5if x<3then ifx>0thenx:=5else x:=-5else與離它遠(yuǎn)的then匹配if x<3then if x>0 then x:=5 else x:=-5else與離它近的then匹配243.2上下文無關(guān)文法(CFG)文法二義不能說明它所產(chǎn)生的語言一定是二義的。消除語言二義有兩種方法：①改寫二義文法為非二義文法；②規(guī)定二義文法中符號的優(yōu)先級和結(jié)合性。改寫[例3.9]與G3.2等價的非二義文法：

E→E+T|T T→T*F |F (G3.4) F→（E） |-F|id問題：如何改寫？E→E+E|E*E|（E）(G3.2)|-E|id25上次課總結(jié)語法分析器作用語法錯誤處理CFG的定義與表示推導(dǎo)(最左、最右推導(dǎo))、句子、句型分析樹語法樹二義性與二義性的消除原因：文法符號缺乏優(yōu)先級和結(jié)合性263.2上下文無關(guān)文法(CFG)觀察結(jié)論：新引入的非終結(jié)符限制每一步直接推導(dǎo)均有唯一選擇；最終分析樹的形狀，僅與文法有關(guān)，而與推導(dǎo)方法無關(guān)；非終結(jié)符的引入，增加了推導(dǎo)步驟(分析樹增高)；越接近S的文法符號的優(yōu)先級越低。(如E→E+T)對于A→αAβ，若A在終結(jié)符左邊出現(xiàn)(即終結(jié)符在β中)，則A產(chǎn)生式具有左結(jié)合性質(zhì)。改寫二義文法的關(guān)鍵步驟：引入新的非終結(jié)符，增加一個子結(jié)構(gòu)并提高一級優(yōu)先級；遞歸非終結(jié)符在終結(jié)符左邊，運算具有左結(jié)合性，否則具有右結(jié)合性。273.2上下文無關(guān)文法(CFG)[例3.10]改寫二義文法G3.2為G3.4：引入新的非終結(jié)符，增加一個子結(jié)構(gòu)并提高一級優(yōu)先級；遞歸非終結(jié)符在終結(jié)符左邊，運算具有左結(jié)合性，否則具有右結(jié)合性。優(yōu)先級： [+] [*] [(),-,id]結(jié)合性： 左結(jié)合 [+,*]

右結(jié)合 [-]

無結(jié)合 [id]非終結(jié)符與運算：

E: + （E產(chǎn)生式，左遞歸）

T: * （T產(chǎn)生式，左遞歸）

F: -,(),id（F產(chǎn)生式，右遞歸）E→E+E (1)|E*E (2)|（E） (3)|-E (4)|id (5)E→E+T|TT→T*F|FF→(E)|-F|id283.2上下文無關(guān)文法(CFG)“懸空else”問題：在復(fù)合if語句中，可能then多于else，使得else不知與哪個then結(jié)合。一般原則是右結(jié)合，即else與左邊最靠近的then結(jié)合。改寫文法的根據(jù)是將S分為完全匹配(MS)和不完全匹配(UMS)兩類，并且在UMS中規(guī)定else右結(jié)合。

S→MS (1) |UMS (2) MS→ifCthenMSelseMS (3) |id:=E (4) UMS→ifCthenS (5) |ifCthenMSelseUMS (6) C→E=E|E<E|E>E (7)...(9) E→E+T|T (10)...(11) T→(E)|-T|id|n (12)...(15)S→ifCthenS |ifCthenSelseS |id:=EC→E=E|E<E|E>EE→E+E|-E|id|n293.2上下文無關(guān)文法(CFG)S→MS|UMS (1)...(2)MS→ifCthenMSelseMS|id:=E (3)...(4)UMS→ifCthenS|ifCthenMSelseUMS (5)...(6) (G3.5)C→E=E|E<E|E>E (7)...(9)E→E+T|T (10)...(11)T→（E）|-T|id|n (12)...(15)if x<3then if x>0 then x:=5 else x:=-5303.2上下文無關(guān)文法(CFG)S→MS|UMS (1)...(2)MS→ifCthenMSelseMS|id:=E (3)...(4)UMS→ifCthenS|ifCthenMSelseUMS (5)...(6) (G3.5)C→E=E|E<E|E>E (7)...(9)E→E+T|T (10)...(11)T→（E）|-T|id|n (12)...(15)if x<3then ifx>0thenx:=5else x:=-5313.2上下文無關(guān)文法(CFG)規(guī)定優(yōu)先級和結(jié)合性 二義文法的優(yōu)點：比非二義文法容易理解；分析效率高(分析樹低，直接推導(dǎo)步驟少)。

YACC為二義文法規(guī)定優(yōu)先級和結(jié)合性：

%left'+' %left'*' %right'-'

E→E+E |E*E |（E）

|-E |idE→E+T|TT→T*F|FF→(E)|-F|id323.2上下文無關(guān)文法(CFG)修改語言的語法明確給出結(jié)束標(biāo)志，如Ada中用endif，于是有：

ifx<3thenifx>0thenx:=5;endif;elsex:=-5;endif; ifx<3thenifx>0thenx:=5;elsex:=-5;endif;endif; if x<3 then ifx>0 thenx:=5; endif; elsex:=-5; endif;給表達(dá)式加括號，如Pascal中邏輯和算術(shù)運算：

(a+b)>(c*d)if x<3then ifx>0 thenx:=5; elsex:=-5; endif;endif;333.3語言與文法簡介文法的重要作用：給出精確、易于理解的語言結(jié)構(gòu)說明；以文法為基礎(chǔ)的語言，便于加入新的、或修改、刪除舊的語言結(jié)構(gòu)；有些類別的文法，可以自動生成高效的分析器。本節(jié)從理論的角度對文法進(jìn)行簡單地討論。討論建立在形式語言與自動機(jī)的理論之上，且僅引用結(jié)論而忽略數(shù)學(xué)的證明，有興趣的同學(xué)可以參閱相關(guān)文獻(xiàn)。希望通過本節(jié)的討論，對文法的分類和它們在編譯器構(gòu)造中的作用有一定的了解，同時初步窺探計算機(jī)科學(xué)的理論基礎(chǔ)。343.3語言與文法簡介正規(guī)式與上下文無關(guān)文法正規(guī)式到CFG的轉(zhuǎn)換推論3.1

正規(guī)式描述的語言結(jié)構(gòu)均可用CFG描述，反之不一定從正規(guī)式到CFG的對應(yīng)關(guān)系：構(gòu)造正規(guī)式的NFA；若0為初態(tài)，則A0為開始符號；對于move(i,a)=j，引入產(chǎn)生式Ai→aAj；對于move(i,ε)=j，引入產(chǎn)生式Ai→Aj；若i是終態(tài)，則引入產(chǎn)生式Ai→ε。[例3.11]從正規(guī)式r=(a|b)*abb的NFA構(gòu)造CFG：A0→aA0|bA0|aA1A1→bA2A2→bA3A3→ε經(jīng)驗的方法：A→HTH→ε|Ha|HbT→abb353.3語言與文法簡介為什么用正規(guī)式而不用CFG描述詞法？詞法規(guī)則簡單，用正規(guī)式描述已足夠；正規(guī)式的表示比CFG更直觀、簡潔、易于理解；有限自動機(jī)的構(gòu)造比下推自動機(jī)簡單，且分析效率高；區(qū)分詞法和語法，為編譯器前端的模塊劃分提供方便。貫穿詞法分析和語法分析始終的思想：語言的描述和語言的識別是表示一個語言的兩個不同側(cè)面，二者缺一不可；（語言、文法、自動機(jī)）用正規(guī)式和CFG描述的語言，對應(yīng)的識別方法（自動機(jī)）不同；正規(guī)式適合描述線性結(jié)構(gòu)，如標(biāo)識符、關(guān)鍵字、注釋等；CFG適合描述具有嵌套（層次）性質(zhì)的非線性結(jié)構(gòu)，如不同結(jié)構(gòu)的句子if-then-else、while-do等。363.3語言與文法簡介上下文有關(guān)語言

ContextSensitiveLanguage,CSL

程序設(shè)計語言中除了CFG可以描述的結(jié)構(gòu)之外，還有一些是CFG無法描述的所謂上下文有關(guān)的結(jié)構(gòu)。典型的這類語言結(jié)構(gòu)包括：變量的聲明與引用、過程調(diào)用時形參與實參的一致性檢查等。描述它們的文法被稱為上下文有關(guān)文法（ContextSensitiveGrammar,CSG）。373.3語言與文法簡介[例3.12]不能用CFG描述的語言：L1={ωcω|ω∈(a|b)*} (標(biāo)識符聲明與引用一致性的抽象)L2={anbmcndm|n≥1和m≥1} (形參與實參一致性的抽象)L3={anbncn|n≥1} (計數(shù)問題的抽象)相近的CFL：L1'={ωcωr|ω∈(a|b)*}L2'={anbmcmdn|n≥1,m≥1}L2''={anbncmdm|n≥1,m≥1}L3'={ambmcn|m,n≥1}S→aSa|bSb|cS→aSd|aAdA→bAc|bcS→ABA→aAb|abB→cBd|cdA→ACA→aAb|abC→cC|c383.3語言與文法簡介計數(shù)問題L3={anbncn|n≥1} CSLL3'={ambmcn|m,n≥1} CFLL3''={akbmcn|k，m，n≥1} 正規(guī)集命題：L3'不是正規(guī)集，因為構(gòu)造不出可以識別L3'的DFA。證明：（反證）假設(shè)L3'是正規(guī)集，則可構(gòu)造n個狀態(tài)的DFAD，它接受L3'；考察D讀完ε，a，aa，...，an，分別到達(dá)S0，S1，...，Sn，共有n+1個狀態(tài)。根據(jù)鴿巢原理，序列中至少有兩個狀態(tài)相同，設(shè)Si=Sj（j>i），因為aibick∈L3'，所以存在路徑aibick。但是D中也有路徑ajbick，矛盾。故L3'不是正規(guī)集。A→ACA→aAb|abC→cC|c?a+b+c+S0SiSkfaibickaj-i39上次課總結(jié)二義性與二義性的消除原因：文法符號缺乏優(yōu)先級和結(jié)合性消除方法改寫二義文法為非二義文法為文法符號規(guī)定優(yōu)先級和結(jié)合性改變語言的結(jié)構(gòu)或書寫方式正規(guī)式到CFG的轉(zhuǎn)換上下文有關(guān)語言形式語言與自動機(jī)簡介403.3語言與文法簡介形式語言與自動機(jī)簡介

定義3.8

若文法G=(N，T，P，S)的每個產(chǎn)生式α→β中，均有α∈(N∪T)*，且至少含有一個非終結(jié)符，β∈(N∪T)*，則稱G為0型文法。對0型文法施加以下第i條限制，即得到i型文法。G的任何產(chǎn)生式α→β（S→ε除外）滿足|α|≤|β|；G的任何產(chǎn)生式形如A→β，其中A∈N，β∈(N∪T)*；G的任何產(chǎn)生式形如A→a或者A→aB(或者A→Ba)，其中A和B∈N，a∈T。文法語言自動機(jī)短語文法(0型)短語結(jié)構(gòu)語言圖靈機(jī)CSG(1型)CSL線性界線自動機(jī)CFG(2型)CFL下推自動機(jī)正規(guī)文法(3型)正規(guī)集有限自動機(jī)413.3語言與文法簡介再考察L3：L3={anbncn|n≥1}[例3.15]L3可用下述CSG描述：

S→aSBC (1) S→aBC (2) CB→BC (3) aB→ab (4) bB→bb (5) bC→bc (6) cC→cc (7)CSG、CFG、正規(guī)式能力遞減，但是能力越強(qiáng)的文法，其文法設(shè)計和自動機(jī)的構(gòu)造越困難，因此語法分析僅用到CFG（除特別指出，文法即指CFG）句子akbkck

的推導(dǎo)：S=>...=>ak-1S(BC)k-1 (by1) =>ak(BC)k (by2) =>...=>akBkCk (by3) =>akbBk-1Ck (by4) =>...=>akbkCk (by5) =>akbkcCk-1 (by6) =>...=>akbkck (by7)423.4自上而下語法分析自上而下分析的一般方法用推導(dǎo)的方法分析輸入序列：對輸入序列ω，從S開始進(jìn)行最左推導(dǎo)，直到得到一個合法句子或非法結(jié)構(gòu)；從左到右掃描輸入序列，試圖用一切可能的方法，自上而下建立它的分析樹；一種試探的過程，反復(fù)使用不同產(chǎn)生式，謀求與輸入序列匹配；[例3.16]用下述文法分析輸入序列ω=cad：S →cAdA →ab |a433.4自上而下語法分析問題：

若有A→αβ1|αβ2，公共左因子，則會虛假匹配和大量回溯；造成分析效率低、語義動作難以恢復(fù)、以及出錯位置的報告不確切等。若有A→Aα，左遞歸，則死循環(huán)使分析無法進(jìn)行下去。重寫文法：消除左遞歸，以避免陷入死循環(huán)；提取左因子，以避免回溯。消除左遞歸定義3.9

若文法G中的非終結(jié)符A，對某個文法符號序列α存在推導(dǎo)A=+>Aα，則稱G是左遞歸的。若G中有形如A→Aα的產(chǎn)生式，則稱該產(chǎn)生式對A直接左遞歸。443.4自上而下語法分析消除文法的直接左遞歸考慮：A→Aα|β 產(chǎn)生的語言：βα*替換為：A→βA' A'→αA'|ε 消除了一個直接左遞歸算法3.1

消除直接左遞歸輸入 G中所有的A產(chǎn)生式(含直接左遞歸)輸出 等價的不含直接左遞歸的G'方法 首先，整理A產(chǎn)生式為如下形式：

A→Aα1|Aα2|...|Aαm|β1|β2|...|βn

其中αi非空，βj均不以A開始。用下述產(chǎn)生式代替A產(chǎn)生式

A→β1A'|β2A'|...|βnA' A'→α1A'|α2A'|...|αmA'|ε

若αi為空，則形成一個有環(huán)的A產(chǎn)生式453.4自上而下語法分析[例3.17]消除算術(shù)表達(dá)式文法的直接左遞歸：E→E+E|E*E |(E)|-E|id (G3.2)E→TE' (1)E'→+TE'|ε (2)T→FT' (3)(G3.4')T'→*FT'|ε (4)F→(E)|-F|id (5)..(7)E→E+T|TT→T*F|F(G3.4)F→(E)|-F|id463.4自上而下語法分析消除文法的左遞歸算法3.2

消除左遞歸輸入 無回路文法G輸出 無左遞歸的等價文法G'方法 將非終結(jié)符合理排序：A1，A2，...，An; for iin2..n loopforjin1..i-1 loop

用Aj→δ1|δ2|...|δk的右部替換每個形如Ai→Ajγ產(chǎn)生式中的Aj,

得到新產(chǎn)生式：Ai→δ1γ|δ2γ|...|δkγ;

消除Ai產(chǎn)生式中的直接左遞歸; endloop; endloop;核心思想：將不是直接左遞歸的非終結(jié)符右部展開到其他產(chǎn)生式中注意：若G產(chǎn)生句子的過程中出現(xiàn)A=+>A，則無法消除左遞歸473.4自上而下語法分析核心思想：將不是直接左遞歸的符號右部展開到其他產(chǎn)生式關(guān)鍵步驟：合理排序非終結(jié)符：A1，A2，...，An;

用Aj→δ1|δ2|...|δk右部替換Ai→Ajγ中的Aj，得到Ai→δ1γ|δ2γ|...|δkγ； 消除Ai產(chǎn)生式中的直接左遞歸；[例3.18]用算法3.2消除文法S→Aa|bA→Ac|Sd|ε中的左遞歸。①將S的右部展開在A中，得到：

A→Ac|Aad|bd|ε②消除新產(chǎn)生式中的直接左遞歸，得到：

S→Aa|b A→bdA'|A' (G3.8') A'→cA'|adA'|ε483.4自上而下語法分析提取左因子S→cAdA→ab|a當(dāng)不確定用A產(chǎn)生式的哪個候選項替換A時，可以重寫A產(chǎn)生式來推遲這種決定，直到看見足夠的輸入，能正確決定所需選擇為止。這一過程被稱為提取左因子，它類似于有限自動機(jī)的確定化。將： A→αβ1|αβ2替換為： A→αA' A'→β1|β2等價于： A→α(β1|β2)493.4自上而下語法分析算法3.3

提取文法的左因子輸入 文法G輸出 等價的無左因子文法G'方法 重復(fù)過程，直到所有A產(chǎn)生式候選項中不再有公共前綴：重排A產(chǎn)生式：A→αβ1|αβ2|...|αβn|γ；并用A→αA'|γ和A'→β1|β2|...|βn取代原A產(chǎn)生式。[例3.20]考察懸空else文法：S→iCtS|iCtSeS|aC→b

用算法3.3提取左因子，得到如下文法：

S→iCtSS'|a S'→eS|ε C→b既有左遞歸又含左因子？先消除左遞歸。503.4自上而下語法分析遞歸下降分析直接以程序的方式模擬產(chǎn)生式產(chǎn)生語言的過程；每個產(chǎn)生式對應(yīng)一個子程序，產(chǎn)生式右邊的非終結(jié)符對應(yīng)子程序調(diào)用，終結(jié)符則與輸入序列匹配；它對文法的限制是不能有公共左因子和左遞歸；它是一種非形式化的方法，只要能寫出子程序，用什么樣的方法和步驟均可。一種穩(wěn)妥的方法構(gòu)造文法的狀態(tài)轉(zhuǎn)換圖并且化簡；將轉(zhuǎn)換圖轉(zhuǎn)化為EBNF表示；從EBNF構(gòu)造子程序。513.4自上而下語法分析構(gòu)造狀態(tài)轉(zhuǎn)換圖且化簡遞歸下降分析的文法：

L→E;L|εE→E+T|E-T|TT→T*F|T/F|TmodF|FF→(E)|id|num每個非終結(jié)符對應(yīng)一個狀態(tài)轉(zhuǎn)換圖：為非終結(jié)符A建立一個初態(tài)和一個終態(tài)；為A→X1X2...Xn構(gòu)造從初態(tài)到終態(tài)的路徑，邊標(biāo)記為X1，X2，...，Xn。根據(jù)識別同一集合的原則，化簡轉(zhuǎn)換圖。消除左遞歸后的等價文法:L→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num523.4自上而下語法分析L→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num533.4自上而下語法分析狀態(tài)圖的化簡原則①標(biāo)記為A的邊可等價為標(biāo)記ε的邊轉(zhuǎn)向A轉(zhuǎn)換圖的初態(tài)；②ε邊連接的兩個狀態(tài)可以合并（FA的確定化思想）；③標(biāo)記相同的路徑可以合并；④不可區(qū)分的狀態(tài)可以合并（DFA的最小化思想）。543.4自上而下語法分析文法的擴(kuò)展BNF（EBNF）表示{}：重復(fù)0或若干次（while）[]：可選擇（if或while）|：括弧()之內(nèi)的或關(guān)系（case）()：改變運算的優(yōu)先級和結(jié)合性EBNF表示：L→{E;}E→T{(+|-)T}T→F{(*|/|mod)F}F→(E)|id|num55上次課總結(jié)形式語言與自動機(jī)簡介自上而下分析：自上而下/從左到右(不能有左遞歸/左因子)消除左遞歸提取左因子遞歸下降分析563.4自上而下語法分析遞歸下降子程序procedureLisbeginlookahead:=lexan;while(lookahead/=eof) loopE;match(';'); endloop;endL;procedureEisbegin

T;whilelookahead∈(+|-)loopmatch(lookahead);T;endloop;endE;procedureFisbegin

caselookaheadis'(':match('(');E;match(')');id:match(id);num:match(num);others:error("syntaxerror2");endcase;endF;L→{E;}E→T{(+|-)T}T→F{(*|/|mod)F}F→(E)|id|num573.4自上而下語法分析如果不消除左遞歸： 若存在產(chǎn)生式E→E+id，則E的遞歸下降子程序如下：

procedureEis begin E; match('+'); --永不執(zhí)行

match(id); --永不執(zhí)行

endE;

此程序永不停機(jī)。 同樣，文法中的公共左因子也會給遞歸下降分析造成困難。583.4自上而下語法分析預(yù)測分析器非遞歸預(yù)測分析器的工作模式預(yù)測分析器的核心概念：分析方法：格局與格局變換分析表+驅(qū)動器（模擬算法）預(yù)測分析表的構(gòu)造LL（文法、語言、分析器）593.4自上而下語法分析預(yù)測分析表

L→E;L|ε E→TE' E'→+TE'|-TE'|ε T→FT' T'→*FT'|/FT'|modFT'|ε F→(E)|id|num分析表M[A,a]的內(nèi)容：若當(dāng)前棧頂是非終結(jié)符A，下一輸入終結(jié)符是a，則M[A,a]指示下一步動作。idnum+-*/mod();#LE;LE;LE;LεETE'TE'TE'E'+TE'-TE'εεTFT'FT'FT'T'εε*FT'/FT'modFT'εεFidnum(E)603.4自上而下語法分析工作方式放幻燈的方式：每張“幻燈片”稱為一個格局。從初始格局開始，經(jīng)過格局變化， 最終到達(dá)接收格局，表明分析成功；或者到達(dá)出錯格局，表明發(fā)現(xiàn)語法錯誤。格局：三元組，(棧內(nèi)容^top，剩余輸入^ip，改變格局的動作)改變格局的動作：匹配終結(jié)符：若^top=^ip(但≠#)，則pop且next(ip)；展開非終結(jié)符：若^top=X且M[X,a]=α(X→α)，則pop且push(α)；報告分析成功：若^top=^ip=#，則分析成功并結(jié)束；報告出錯：其它情況，調(diào)用錯誤恢復(fù)例程。61上次課總結(jié)遞歸下降分析預(yù)測分析器下推自動機(jī)符號棧、分析表、驅(qū)動器格局與格局的變換62驅(qū)動器算法算法3.4

非遞歸的預(yù)測分析輸入 輸入序列ω和文法G的預(yù)測分析表M輸出 若ω∈L(G)，得到ω的一個最左推導(dǎo)；否則指出一個錯誤方法 初始格局為:（#S，ω#，分析器的第一個動作） 令ip指向ω#中的第一個終結(jié)符，top指向S; loopx:=top^;a:=ip^; if x∈T then if x=a

thenpop(x);next(ip); --匹配終結(jié)符

elseerror(1); endif; --出錯：棧頂終結(jié)符不是a else if M[x,a]=X→Y1Y2...Yk thenpop(X);push(YkYk-1...Y2Y1); --展開非終結(jié)符

elseerror(2); endif; --出錯：產(chǎn)生式不匹配

endif; exitwhenx=#; --分析成功

endloop;63用預(yù)測分析器分析句子棧 當(dāng)前剩余輸入 動作 含義#L id+id*id;# pop(L),push(E;L) (L→E;L)#L;E id+id*id;# pop(E),push(TE') (E→TE')#L;E'T id+id*id;# pop(T),push(FT') (T→FT')#L;E'T'F id+id*id;# pop(F),push(id) (F→id)#L;E'T'id id+id*id;# pop(id),next(ip) id#L;E'T' +id*id;# pop(T') (T'→ε)#L;E' +id*id;# pop(E'),push(+TE') (E'→+TE')#L;E'T+ +id*id;# pop(+),next(ip) +#L;E'T id*id;# pop(T),push(FT') (T→FT')#L;E'T'F id*id;# pop(F),push(id) (F→id)#L;E'T'id id*id;# pop(id),next(ip) id#L;E'T' *id;# pop(T'),push(*FT') (T'→*FT')#L;E'T'F* *id;# pop(*),next(ip) *#L;E'T'F id;# pop(F),push(id) (F→id)#L;E'T'id id;# pop(id),next(ip) id#L;E'T' ;# pop(T') (T'→ε)#L;E' ;# pop(E') (E'→ε)#L; ;# pop(;),next(ip) ;#L # pop(L) (L→ε)# # 正確結(jié)束643.4自上而下語法分析構(gòu)造預(yù)測分析表首先構(gòu)造FIRST集合與FOLLOW集合；然后根據(jù)兩個集合構(gòu)造預(yù)測分析表。定義3.10

文法符號序列α的FIRST集合為: FIRST(α)={a|α=*>a...，a∈T}，若α=*>ε，則ε∈FIRST(α)定義3.11

非終結(jié)符A的FOLLOW集合如下: FOLLOW(A)={a|S=*>...Aa...，a∈T}， 若A是某句型的最右符號，則#∈FOLLOW(A)。通俗地講，α的FIRST集合就是從α開始可導(dǎo)出的文法符號序列中的開頭終結(jié)符。而A的FOLLOW集合，就是從開始符號可以導(dǎo)出的所有含A的文法符號序列中A之后的終結(jié)符。例如：FIRST(E)={(，id,num}，F(xiàn)OLLOW(E)={)，;}L→E;L|εE→TE' E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num653.4自上而下語法分析算法3.5

計算X的FIRST集合輸入 文法符號X輸出 X的FIRST集合方法 應(yīng)用下述規(guī)則：若X∈T，則FIRST(X)={X}；若X是非終結(jié)符且有X→ε，則加入ε到FIRST(X)；若X是非終結(jié)符且有X→Y1Y2...Yk，并設(shè)Y0=ε，Yk+1=ε。那么對所有j(0≤j≤k)，若a∈FIRST(Yj+1)且ε∈FIRST(Yj),則加入a到FIRST(X)。FIRST(X1X2...Xn)的計算方法與算法3.5中步驟3類似，即是所有FIRST(Xi)(i=1,2,..,k)的并集，其中k為第一個具有性質(zhì)ε不屬于FIRST(Xk)或k>n的文法符號，若k>n，則ε∈FIRST(X1X2...Xn)考慮：FIRST(E)=FIRST(TE')=FIRST(FT'E')={(，id,num}L→E;L|εE→TE' E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num663.4自上而下語法分析算法3.6

計算所有非終結(jié)符的FOLLOW集合輸入 文法G輸出 G中所有非終結(jié)符的FOLLOW集合方法 應(yīng)用下述規(guī)則:加入#到FOLLOW(S)，其中S是開始符號，#是輸入結(jié)束標(biāo)記若有產(chǎn)生式A→αBβ，則除ε外，F(xiàn)IRST(β)的全體加入到FOLLOW(B)。若有產(chǎn)生式A→αB或A→αBβ而ε∈FIRST(β)，則FOLLOW(A)的全體加入到FOLLOW(B)。

步驟3的理解： 若 S=*>δAa a緊跟A之后 則 =*>δαBa a也緊跟B之后因為ε∈FIRST(β)使得B成為A產(chǎn)生式右部最右的文法符號即對任何a∈FOLLOW(A)，均有a∈FOLLOW(B)，反之不然。673.4自上而下語法分析[例3.22]計算非終結(jié)符的FIRST與FOLLOW。提示：自下而上計算FIRST，自上而下計算FOLLOW FIRST(F)={(idnum} FIRST(T')={*/modε} FIRST(T)=FIRST(F)={(idnum} FIRST(E')= {+-ε} FIRST(E)=FIRST(T)=FIRST(F)={(idnum} FIRST(L)={ε}∪FIRST(E)={ε(idnum} FOLLOW(L)={#} FOLLOW(E)={);} FOLLOW(E')={);} FOLLOW(T)={+-;)} FOLLOW(T')={+-;)} FOLLOW(F)={+-*/mod);}L→E;L|εE→TE' E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num683.4自上而下語法分析算法3.7

構(gòu)造預(yù)測分析表輸入 文法G輸出 分析表M方法 應(yīng)用下述規(guī)則對文法的每個產(chǎn)生式A→α，執(zhí)行2和3；對FIRST(α)的每個終結(jié)符a，加入α到M[A，a]；若ε∈FIRST(α)，則FOLLOW(A)每個終結(jié)符b（包括#），加入α到M[A，b]；M中其它沒有定義的條目均是error。M[A，a]指導(dǎo)下一步動作：若當(dāng)前棧頂為A，當(dāng)前輸入為a，則規(guī)則2表示下一步動作是展開A→α，因為a∈FIRST(α)，展開后下一次正好匹配a。若當(dāng)前棧頂為A，當(dāng)前輸入為b且b∈FOLLOW(A)，則規(guī)則3表示下一步動作是展開A→ε，即棧頂彈出A，繼續(xù)分析A之后的部分，因為b∈FOLLOW(A)，彈出A后下一次正好匹配A的后繼b693.4自上而下語法分析FIRST(F/T/E)={(idnum}FIRST(T')={*/modε}FIRST(E')={+-ε}FIRST(L)={ε(idnum}FOLLOW(L)={#}FOLLOW(E/E')={);}FOLLOW(T/T')={+-;)}FOLLOW(F)={+-*/mod);}idnum+-*/mod();#LEE'TT'F對FIRST(α)的每個終結(jié)符a，加入α到M[A，a]；若ε∈FIRST(α)，則FOLLOW(A)每個終結(jié)符b(包括#)，加入α到M[A，b]；E;LE;LE;LTE'TE'TE'+TE'-TE'FT'FT'FT'*FT'/FT'modFT'idnum(E)εεεεεεεL→E;L|εE→TE' E'→+TE'|-TE'|εT→FT' T'→*FT'|/FT'|modFT'|εF→(E)|id|num70上次課總結(jié)預(yù)測分析器下推自動機(jī)符號棧、分析表、驅(qū)動器格局與格局的變換預(yù)測分析表的構(gòu)造FIRSTFOLLOW構(gòu)造分析表LL(1)文法及判定713.4自上而下語法分析LL(1)文法M[A,a]的作用：指導(dǎo)產(chǎn)生式產(chǎn)生句子（指導(dǎo)推導(dǎo)）問題：是否分析表M[A,a]中都最多有一個條目？[例3.23]二義文法的預(yù)測分析表： 文法：S→iCtSS'|a S'→eS|ε C→b FIRST與FOLLOW集合：

FIRST(C)= FIRST(S')={ε,e} FIRST(S)={i,a}FOLLOW(S)={#,e}FOLLOW(S')={#,e}FOLLOW(C)={t}abeit#SS'CaiCtSSesεbε723.4自上而下語法分析定義3.12

文法G被稱為是LL(1)文法，當(dāng)且僅當(dāng)為它構(gòu)造的預(yù)測分析表中不含多重定義的條目。由此分析表所組成的分析器被稱為LL(1)分析器，所分析的語言被稱為LL(1)語言。第一個L代表從左到右掃描輸入序列，第二個L表示產(chǎn)生最左推導(dǎo)，1表示在確定每一步動作時向前看一個終結(jié)符。判定LL(1)文法的方法：a)構(gòu)造分析表；b)無需構(gòu)造分析表。推論3.2G是LL(1)的，當(dāng)且僅當(dāng)G的任何兩個產(chǎn)生式A→α|β滿足：對任何終結(jié)符a，α和β不能同時推導(dǎo)出以a開始的串；α和β最多有一個可以推導(dǎo)出ε；若β=*>ε,則α不能導(dǎo)出以FOLLOW(A)中終結(jié)符開始的任何串。733.4自上而下語法分析對FIRST(α)的每個終結(jié)符a，加入α到M[A，a]；若ε∈FIRST(α)，則FOLLOW(A)每個終結(jié)符b(包括#)，加入α到M[A，b]；證明：若條件1不滿足，即存在終結(jié)符a，α和β同時推導(dǎo)出以a開始的串，則根據(jù)算法3.7步驟2，M[A，a]中有多重定義A→α和A→β；若條件2不滿足，即α和β均可推出ε串，則根據(jù)算法3.2步驟3，任何屬于FOLLOW（A）的終結(jié)符b(包括#)，M[A，b]中有多重定義A→α和A→β；若條件3不滿足，即存在終結(jié)符b，它既在FOLLOW(A)中，又在FIRST(α)中，則算法3.2步驟2把條目A→α加入到M[A，b]中，而步驟3又把條目A→β加入到M[A，b]中，即M[A，b]中有多重定義A→α和A→β。743.4自上而下語法分析

根據(jù)推論3.2，有左遞歸和左因子的文法不是LL(1)文法，二義文法也不是LL(1)文法。文法(G3.4)不是LL(1)的，因為不滿足條件1。文法(G3.4')是LL(1)的，因為三個條件均滿足。E→E+T|TT→T*F|F(G3.4)F→(E)|-F|idLL(1)文法的弱點：文法難寫、難懂；適應(yīng)范圍有限，往往寫不出有些語言的LL(1)文法。實際編譯器中使用更多的是一類LL(1)文法的真超集，即LR(1)文法。E→TE' (1)E'→+TE'|ε (2)T→FT' (3)(G3.4')T'→*FT'|ε (4)F→(E)|-F|id (5)..(7)753.5自下而上語法分析自上而下分析的方法是產(chǎn)生語言的自然過程。對于分析語言來講，自下而上分析的方法更自然，因為語法分析處理的對象一開始都是終結(jié)符組成的串，而不是文法的開始符號。同時，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要強(qiáng)，從而使得LR分析成為最為實用的語法分析方法。兩種主要的自下而上分析方法：算符優(yōu)先分析(不討論)LR分析763.5自下而上語法分析自下而上分析的基本方法思路：從句子ω開始，從左到右掃描ω，反復(fù)用產(chǎn)生式的左部替換產(chǎn)生式的右部、謀求對ω的匹配，最終得到文法的開始符號，或者發(fā)現(xiàn)一個錯誤。規(guī)范規(guī)約與“剪句柄”定義3.13

設(shè)αβδ是文法G的一個句型，若存在S=*>αAδ，A=+>β，則稱β是句型αβδ相對于A的短語，特別的，若有A→β，則稱β是句型αβδ相對于產(chǎn)生式A→β的直接短語。一個句型的最左直接短語被稱為句柄。直觀上，句型是一個完整結(jié)構(gòu)，短語是句型中針對某非終結(jié)符的局部。因此，開始符號S是句型而不是短語。短語形成的兩個要素：從S可以推導(dǎo)出A，即S=*>αAδ；從A至少一次推導(dǎo)出β，即A=+>β。773.5自下而上語法分析[例3.25]文法、分析樹與短語文法： E→E+T|T T→T*F|F F→id句型：id1+id2*id3分析樹：短語： id1+id2*id3 (E1) id2*id3 (T1) id1 (E2,T2,F1) id2 (T3,F3) id3 (F2)直接短語：id1 (F1) id2 (F3) id3 (F2)句柄： id1 (F1)短語：以非終結(jié)符為根子樹中所有從左到右的葉子直接短語：只有父子關(guān)系的樹中所有從左到右排列的葉子(樹高為2)句柄：最左邊父子關(guān)系樹中所有從左到右排列的葉子(句柄是唯一的)問題：id1+id2是句型id1+id2*id3的短語嗎？783.5自下而上語法分析定義3.14

若α是文法G的句子且滿足下述條件，則稱序列αn，αn-1，...，α0是α的一個最左歸約。αn=αα0=S（S是G的開始符號）對任何i(0<i<=n)，αi-1是將αi中句柄替換為相應(yīng)產(chǎn)生式左部非終結(jié)符得到的。[例3.26]文法(1)S→aABe(2)A→b(3)A→Abc(4)B→d

對句子abbcde的最左歸約： （2） （3）（4）（1）

abbcde<=aAbcde<=aAde<=aABe<=S提醒：最左歸約的逆過程是一個最右推導(dǎo)，分別稱最右推導(dǎo)和最左歸約為規(guī)范推導(dǎo)和規(guī)范歸約。問題：如何直觀地看出句柄并進(jìn)行歸約？793.5自下而上語法分析剪句柄文法(1)S→aABe(2)A→b(3)A→Abc (4)B→d句子：abbcde假設(shè)已經(jīng)有了句子的分析樹，則：需要解決的問題：確定右句型中將要歸約的子串（確定句柄）；確定如何選擇正確的產(chǎn)生式進(jìn)行歸約。移進(jìn)-歸約：用一個?！坝涀　睂⒁獨w約句柄的前綴，句柄未形成前移進(jìn)，形成后歸約。(2)A→b(3)A→Abc(4)B→d(1)S→aABe80上次課總結(jié)LL(1)文法及判定自下而上分析：歸約、短語、直接短語、句柄、規(guī)范(最左)歸約規(guī)范歸約的直觀表示：剪句柄移進(jìn)－歸約分析工作模式：格局與格局變換813.5自下而上語法分析移進(jìn)-歸約分析器工作模式預(yù)測分析器：分析方法：格局與格局變換分析表驅(qū)動器（模擬算法）預(yù)測分析表的構(gòu)造LL（文法、語言、分析器）移進(jìn)-歸約分析器：分析方法：格局與格局變換分析表驅(qū)動器（模擬算法）LR（文法、語言、分析器）SLR分析表的構(gòu)造823.5自下而上語法分析工作方法：放幻燈，每個幻燈片是一個格局。格局：（#棧，當(dāng)前剩余輸入#，改變格局的動作）改變格局的動作：移進(jìn)(shift)：輸入序列中的終結(jié)符進(jìn)棧。(匹配終結(jié)符)歸約(reduce)：將棧頂句柄替換為對應(yīng)非終結(jié)符(最左歸約)。接受(accept)：宣告分析成功。報錯(error)：發(fā)現(xiàn)語法錯誤，調(diào)用錯誤恢復(fù)例程。對照預(yù)測分析：匹配終結(jié)符（彈出）最左推導(dǎo)（展開非終結(jié)符）833.5自下而上語法分析[例3.27]用移進(jìn)-歸約方法分析abbcde：

abbcde<=aAbcde<=aAde<=aABe<=S棧 剩余輸入 改變格局的動作# abbcde# 移進(jìn)#a bbcde# 移進(jìn)#ab bcde# 歸約，(2)A→b#aA bcde# 移進(jìn)#aAb cde# 移進(jìn)#aAbc de# 歸約，(3)A→Abc#aA de# 移進(jìn)#aAd e# 歸約，(4)B→d#aAB e# 移進(jìn)#aABe # 歸約，(1)S→aABe#S # 接受需要解決的問題：（由分析表確定）如何保證棧中總是活前綴(指導(dǎo)移進(jìn))如何確定棧頂已經(jīng)形成句柄并選擇正確的產(chǎn)生式進(jìn)行歸約(指導(dǎo)歸約)(1)S→aABe(2)A→b(3)A→Abc(4)B→d結(jié)論：句柄總是在棧頂形成(最左歸約)。棧中保留的總是一個右句型的前綴(加上若干終結(jié)符形成句型)，稱為活前綴；最左歸約是邏輯上從下到上構(gòu)造一棵分析樹，或從下到上為分析樹剪句柄。843.5自下而上語法分析LR分析LR分析的特點：采用最一般的無回溯移進(jìn)－歸約方法可分析的文法是LL文法的真超集能及時發(fā)現(xiàn)錯誤，快到從左到右掃描輸入序列的最大可能分析表較復(fù)雜，難以手工構(gòu)造LR分析的核心：移進(jìn)－歸約分析表＋驅(qū)動器內(nèi)容：工作原理(分析表的組成、分析算法)－>分析表的構(gòu)造討論依據(jù)的文法：

E→E-T|T （1）（2）

T→T*F|F （3）（4）

F→-F|id （5）（6）853.5自下而上語法分析LR分析與LR文法id-*#ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r110r3r3r3動作表(action)轉(zhuǎn)移表(goto)action[s,a]確定改變格局的動作(與輸入有關(guān))goto[s,A]指示非終結(jié)符的狀態(tài)轉(zhuǎn)移分析表格局與動作：開始格局：(#0，ω#，移進(jìn))結(jié)束格局：(#0S，#，接受)出錯格局：(#δ，ω'#，報錯)改變格局的動作：action[s,a]=si：移進(jìn)

=rj：用第j個產(chǎn)生式的左 部替換棧中的句柄

=acc：接收

=blank：報錯goto[s,A]=s'：s狀態(tài)下遇到A轉(zhuǎn)移到狀態(tài)s'提示：②和⑤共同完成歸約。E→E-T|T T→T*F|F F→-F|id86算法3.8LR分析輸入 輸入序列ω和文法G的LR分析表（action與goto）輸出 若ω屬于L(G)，得到ω的規(guī)范歸約，否則指出一個錯誤方法 初始格局為：（#0，ω#，移進(jìn)），其中0是初態(tài)

ip指向ω#中的第一個終結(jié)符，top指向棧頂初始狀態(tài)；

loops:=top^;a:=ip^; caseaction[s，a]is shifts':push(a);push(s');next(ip);--移進(jìn)

reducebyA→β: pop(2*|β|); --彈出句柄和相應(yīng)狀態(tài)

s':=top^; --暴露出當(dāng)前棧頂狀態(tài)s' push(A); --產(chǎn)生式左部符號進(jìn)棧

push(goto(s'，A));--新棧頂狀態(tài)進(jìn)棧

write(A→β);--完成歸約，跟蹤分析軌跡

accept:return; --成功返回

others:error; --出錯處理

endcase; endloop;實際的算法中僅存放狀態(tài)，而在分析的格局中，僅顯示文法符號。873.5自下而上語法分析棧 剩余輸入 動作#0 id--id*id# s4#0id4 --id*id# r6(F→id)#0F3 --id*id# r4(T→F)#0T2 --id*id# r2(E→T)#0E1 --id*id# s5#0E1-6 -id*id# s5#0E1-6-5 id*id# s4#0E1-6-5id4 *id# r6(F→id)#0E1-6-5F8 *id# r5(F→-F)#0E1-6F3 *id# r4(T→F)#0E1-6T9 *id# s7#0E1-6T9*7 id# s4#0E1-6T9*7id4 # r6(F→id)#0E1-6T9*7F10 #r3(T→T*F)#0E1-6T9 #r1(E→E-T)#0E1 # accid-*#ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r110r3r3r3shifts':push(a);push(s');next(ip);reducebyA→β:pop(2*|β|);s':=top^;push(A);push(goto(s'，A));write(A→β);883.5自下而上語法分析定義3.15若為文法G構(gòu)造的移進(jìn)－歸約分析表中不含多重定義的條目，則稱G為LR(k)文法，分析器被稱為是LR(k)分析器，它所識別的語言被稱為LR(k)語言。L表示從左到右掃描