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

兩類：語法錯誤和語義錯誤詞法錯誤如非法字符或拼寫錯關鍵字、標識符等

@ intege 20times語法錯誤指結構出錯，如少分號、begin/end不配對等

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

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

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

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

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

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

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

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

上下文無關文法，ContextFreeGrammar，CFG定義3.1CFG是一個四元組：

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

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

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）產生式的一般讀法 記號→讀作“定義為”或者“可導出”。 “E→E+E”表述為“算術表達式定義為兩個算術表達式相加”；或者“一個算術表達式加上另一個算術表達式，仍然是一個算術表達式”。103.2上下文無關文法(CFG)由產生式集表示CFG

前提： 若文法正確

結論： 文法開始符號S是第一個產生式的左部；

N是可以出現在產生式左邊符號的記號集合；

T是絕不出現在產生式左邊符號的記號集合；

P: E→E+E （1）

E→E*E （2）

E→（E） （3）

E→-E （4）

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

(a)

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

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

用<>區分：<E>→<E>+<E>

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

E→ E+E （1）

|E*E （2）

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

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

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

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

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

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

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

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

在推導過程中，若每次直接推導均替換句型中最左邊的非終結符，則稱為最左推導，由最左推導產生的句型被稱為左句型。類似可定義最右推導與右句型，最右推導也被稱為規范推導。

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

E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id)推導產生句子的方式不直觀。分析樹是推導的圖形直觀表示，同時反映語言結構的實質和推導過程。定義3.5

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

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

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

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

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

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

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

原因：在產生句子的過程中某些直接推導有多于一種選擇注意：一個句子有多于一棵分析樹，僅與文法和句子有關，與采用的推導方法無關；文法中缺少對文法符號優先級和結合性的規定。“懸空（dangling）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上下文無關文法(CFG)[例3.8]條件語句ifx<3thenifx>0thenx:=5elsex:=-5if x<3then ifx>0thenx:=5else x:=-5else與離它遠的then匹配if x<3then if x>0 then x:=5 else x:=-5else與離它近的then匹配243.2上下文無關文法(CFG)文法二義不能說明它所產生的語言一定是二義的。消除語言二義有兩種方法：①改寫二義文法為非二義文法；②規定二義文法中符號的優先級和結合性。改寫[例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上次課總結語法分析器作用語法錯誤處理CFG的定義與表示推導(最左、最右推導)、句子、句型分析樹語法樹二義性與二義性的消除原因：文法符號缺乏優先級和結合性263.2上下文無關文法(CFG)觀察結論：新引入的非終結符限制每一步直接推導均有唯一選擇；最終分析樹的形狀，僅與文法有關，而與推導方法無關；非終結符的引入，增加了推導步驟(分析樹增高)；越接近S的文法符號的優先級越低。(如E→E+T)對于A→αAβ，若A在終結符左邊出現(即終結符在β中)，則A產生式具有左結合性質。改寫二義文法的關鍵步驟：引入新的非終結符，增加一個子結構并提高一級優先級；遞歸非終結符在終結符左邊，運算具有左結合性，否則具有右結合性。273.2上下文無關文法(CFG)[例3.10]改寫二義文法G3.2為G3.4：引入新的非終結符，增加一個子結構并提高一級優先級；遞歸非終結符在終結符左邊，運算具有左結合性，否則具有右結合性。優先級： [+] [*] [(),-,id]結合性： 左結合 [+,*]

右結合 [-]

無結合 [id]非終結符與運算：

E: + （E產生式，左遞歸）

T: * （T產生式，左遞歸）

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

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上下文無關文法(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上下文無關文法(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上下文無關文法(CFG)規定優先級和結合性 二義文法的優點：比非二義文法容易理解；分析效率高(分析樹低，直接推導步驟少)。

YACC為二義文法規定優先級和結合性：

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

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

|-E |idE→E+T|TT→T*F|FF→(E)|-F|id323.2上下文無關文法(CFG)修改語言的語法明確給出結束標志，如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;給表達式加括號，如Pascal中邏輯和算術運算：

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

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

ContextSensitiveLanguage,CSL

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

定義3.8

若文法G=(N，T，P，S)的每個產生式α→β中，均有α∈(N∪T)*，且至少含有一個非終結符，β∈(N∪T)*，則稱G為0型文法。對0型文法施加以下第i條限制，即得到i型文法。G的任何產生式α→β（S→ε除外）滿足|α|≤|β|；G的任何產生式形如A→β，其中A∈N，β∈(N∪T)*；G的任何產生式形如A→a或者A→aB(或者A→Ba)，其中A和B∈N，a∈T。文法語言自動機短語文法(0型)短語結構語言圖靈機CSG(1型)CSL線性界線自動機CFG(2型)CFL下推自動機正規文法(3型)正規集有限自動機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、正規式能力遞減，但是能力越強的文法，其文法設計和自動機的構造越困難，因此語法分析僅用到CFG（除特別指出，文法即指CFG）句子akbkck

的推導：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自上而下語法分析自上而下分析的一般方法用推導的方法分析輸入序列：對輸入序列ω，從S開始進行最左推導，直到得到一個合法句子或非法結構；從左到右掃描輸入序列，試圖用一切可能的方法，自上而下建立它的分析樹；一種試探的過程，反復使用不同產生式，謀求與輸入序列匹配；[例3.16]用下述文法分析輸入序列ω=cad：S →cAdA →ab |a433.4自上而下語法分析問題：

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

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

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

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

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

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

若αi為空，則形成一個有環的A產生式453.4自上而下語法分析[例3.17]消除算術表達式文法的直接左遞歸：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'方法 將非終結符合理排序：A1，A2，...，An; for iin2..n loopforjin1..i-1 loop

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

得到新產生式：Ai→δ1γ|δ2γ|...|δkγ;

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

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

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

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

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

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

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

L→E;L|εE→E+T|E-T|TT→T*F|T/F|TmodF|FF→(E)|id|num每個非終結符對應一個狀態轉換圖：為非終結符A建立一個初態和一個終態；為A→X1X2...Xn構造從初態到終態的路徑，邊標記為X1，X2，...，Xn。根據識別同一集合的原則，化簡轉換圖。消除左遞歸后的等價文法: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自上而下語法分析狀態圖的化簡原則①標記為A的邊可等價為標記ε的邊轉向A轉換圖的初態；②ε邊連接的兩個狀態可以合并（FA的確定化思想）；③標記相同的路徑可以合并；④不可區分的狀態可以合并（DFA的最小化思想）。543.4自上而下語法分析文法的擴展BNF（EBNF）表示{}：重復0或若干次（while）[]：可選擇（if或while）|：括弧()之內的或關系（case）()：改變運算的優先級和結合性EBNF表示：L→{E;}E→T{(+|-)T}T→F{(*|/|mod)F}F→(E)|id|num55上次課總結形式語言與自動機簡介自上而下分析：自上而下/從左到右(不能有左遞歸/左因子)消除左遞歸提取左因子遞歸下降分析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自上而下語法分析如果不消除左遞歸： 若存在產生式E→E+id，則E的遞歸下降子程序如下：

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

match(id); --永不執行

endE;

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

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

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

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

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

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

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

endloop;63用預測分析器分析句子棧 當前剩余輸入 動作 含義#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→ε)# # 正確結束643.4自上而下語法分析構造預測分析表首先構造FIRST集合與FOLLOW集合；然后根據兩個集合構造預測分析表。定義3.10

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

非終結符A的FOLLOW集合如下: FOLLOW(A)={a|S=*>...Aa...，a∈T}， 若A是某句型的最右符號，則#∈FOLLOW(A)。通俗地講，α的FIRST集合就是從α開始可導出的文法符號序列中的開頭終結符。而A的FOLLOW集合，就是從開始符號可以導出的所有含A的文法符號序列中A之后的終結符。例如：FIRST(E)={(，id,num}，FOLLOW(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集合方法 應用下述規則：若X∈T，則FIRST(X)={X}；若X是非終結符且有X→ε，則加入ε到FIRST(X)；若X是非終結符且有X→Y1Y2...Yk，并設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為第一個具有性質ε不屬于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

計算所有非終結符的FOLLOW集合輸入 文法G輸出 G中所有非終結符的FOLLOW集合方法 應用下述規則:加入#到FOLLOW(S)，其中S是開始符號，#是輸入結束標記若有產生式A→αBβ，則除ε外，FIRST(β)的全體加入到FOLLOW(B)。若有產生式A→αB或A→αBβ而ε∈FIRST(β)，則FOLLOW(A)的全體加入到FOLLOW(B)。

步驟3的理解： 若 S=*>δAa a緊跟A之后 則 =*>δαBa a也緊跟B之后因為ε∈FIRST(β)使得B成為A產生式右部最右的文法符號即對任何a∈FOLLOW(A)，均有a∈FOLLOW(B)，反之不然。673.4自上而下語法分析[例3.22]計算非終結符的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輸出 分析表M方法 應用下述規則對文法的每個產生式A→α，執行2和3；對FIRST(α)的每個終結符a，加入α到M[A，a]；若ε∈FIRST(α)，則FOLLOW(A)每個終結符b（包括#），加入α到M[A，b]；M中其它沒有定義的條目均是error。M[A，a]指導下一步動作：若當前棧頂為A，當前輸入為a，則規則2表示下一步動作是展開A→α，因為a∈FIRST(α)，展開后下一次正好匹配a。若當前棧頂為A，當前輸入為b且b∈FOLLOW(A)，則規則3表示下一步動作是展開A→ε，即棧頂彈出A，繼續分析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(α)的每個終結符a，加入α到M[A，a]；若ε∈FIRST(α)，則FOLLOW(A)每個終結符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上次課總結預測分析器下推自動機符號棧、分析表、驅動器格局與格局的變換預測分析表的構造FIRSTFOLLOW構造分析表LL(1)文法及判定713.4自上而下語法分析LL(1)文法M[A,a]的作用：指導產生式產生句子（指導推導）問題：是否分析表M[A,a]中都最多有一個條目？[例3.23]二義文法的預測分析表： 文法：S→iCtSS'|a S'→eS|ε C→b FIRST與FOLLOW集合：

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

根據推論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)文法的弱點：文法難寫、難懂；適應范圍有限，往往寫不出有些語言的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自下而上語法分析自上而下分析的方法是產生語言的自然過程。對于分析語言來講，自下而上分析的方法更自然，因為語法分析處理的對象一開始都是終結符組成的串，而不是文法的開始符號。同時，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要強，從而使得LR分析成為最為實用的語法分析方法。兩種主要的自下而上分析方法：算符優先分析(不討論)LR分析763.5自下而上語法分析自下而上分析的基本方法思路：從句子ω開始，從左到右掃描ω，反復用產生式的左部替換產生式的右部、謀求對ω的匹配，最終得到文法的開始符號，或者發現一個錯誤。規范規約與“剪句柄”定義3.13

設αβδ是文法G的一個句型，若存在S=*>αAδ，A=+>β，則稱β是句型αβδ相對于A的短語，特別的，若有A→β，則稱β是句型αβδ相對于產生式A→β的直接短語。一個句型的最左直接短語被稱為句柄。直觀上，句型是一個完整結構，短語是句型中針對某非終結符的局部。因此，開始符號S是句型而不是短語。短語形成的兩個要素：從S可以推導出A，即S=*>αAδ；從A至少一次推導出β，即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)短語：以非終結符為根子樹中所有從左到右的葉子直接短語：只有父子關系的樹中所有從左到右排列的葉子(樹高為2)句柄：最左邊父子關系樹中所有從左到右排列的葉子(句柄是唯一的)問題：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中句柄替換為相應產生式左部非終結符得到的。[例3.26]文法(1)S→aABe(2)A→b(3)A→Abc(4)B→d

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

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

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

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

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

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

=rj：用第j個產生式的左 部替換棧中的句柄

=acc：接收

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

ip指向ω#中的第一個終結符，top指向棧頂初始狀態；

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

reducebyA→β: pop(2*|β|); --彈出句柄和相應狀態

s':=top^; --暴露出當前棧頂狀態s' push(A); --產生式左部符號進棧

push(goto(s'，A));--新棧頂狀態進棧

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

accept:return; --成功返回

others:error; --出錯處理

endcase; endloop;實際的算法中僅存放狀態，而在分析的格局中，僅顯示文法符號。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為LR(k)文法，分析器被稱為是LR(k)分析器，它所識別的語言被稱為LR(k)語言。L表示從左到右掃描