第三章 語法分析

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

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

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

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

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

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

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

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

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

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

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

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

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é)符，稱為文法的開始符號(hào)（Start symbol）。93.2上下文無關(guān)文法(CFG)[例3.2]簡(jiǎn)單算術(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)生式的一般讀法 記號(hào)→讀作“定義為”或者“可導(dǎo)出”。 “E→E+E”表述為“算術(shù)表達(dá)式定義為兩個(gè)算術(shù)表達(dá)式相加”；或者“一個(gè)算術(shù)表達(dá)式加上另一個(gè)算術(shù)表達(dá)式，仍然是一個(gè)算術(shù)表達(dá)式”。103.2上下文無關(guān)文法(CFG)由產(chǎn)生式集表示CFG

前提： 若文法正確

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

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

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

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é)符； 小寫希臘字母α、β、δ表示任意文法符號(hào)序列123.2上下文無關(guān)文法(CFG)產(chǎn)生式的縮寫形式當(dāng)多個(gè)產(chǎn)生式的左部非終結(jié)符相同時(shí)，可合并為一個(gè)產(chǎn)生式。新的產(chǎn)生式的左部是此非終結(jié)符，右部是所有原來右部的或運(yùn)算（并集合）。[例3.3]G3.1可以重寫為如下形式：

E→ E+E （1）

|E*E （2）

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

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

BNF如何表示？P:E→E+E (1)E→E*E (2)E→(E) (3)E→-E (4)E→id (5)13上次課總結(jié)語法分析器作用語法錯(cuò)誤處理CFG的定義與表示143.2上下文無關(guān)文法(CFG)CFG產(chǎn)生語言的基本方法－推導(dǎo)CFG（產(chǎn)生式）通過推導(dǎo)的方法產(chǎn)生語言。通俗地講，產(chǎn)生式產(chǎn)生語言的過程是從開始符號(hào)S開始，對(duì)產(chǎn)生式左部的非終結(jié)符反復(fù)地使用產(chǎn)生式：將產(chǎn)生式左部的非終結(jié)符替換為右部的文法符號(hào)序列（展開產(chǎn)生式，用標(biāo)記=>表示），直到得到一個(gè)終結(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→γ的右部代替文法符號(hào)序列αAβ中的A得到αγβ的過程，稱αAβ直接推導(dǎo)出αγβ，記作：αAβ=>αγβ。若對(duì)于任意文法符號(hào)序列α1，α2，...αn，均有α1=>α2=>...=>αn，則稱此過程為零步或多步推導(dǎo)，記為：

α1=*>αn，其中α1=αn的情況為零步推導(dǎo)。若α1≠αn，即推導(dǎo)過程中至少使用一次產(chǎn)生式，則稱此過程為至少一步推導(dǎo)，記為：α1=+>αn。 兩點(diǎ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的一個(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)的圖形直觀表示，同時(shí)反映語言結(jié)構(gòu)的實(shí)質(zhì)和推導(dǎo)過程。定義3.5

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

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

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

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

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

原因：在產(chǎn)生句子的過程中某些直接推導(dǎo)有多于一種選擇注意：一個(gè)句子有多于一棵分析樹，僅與文法和句子有關(guān)，與采用的推導(dǎo)方法無關(guān)；文法中缺少對(duì)文法符號(hào)優(yōu)先級(jí)和結(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ī)定二義文法中符號(hào)的優(yōu)先級(jí)和結(jié)合性。改寫[例3.9]與G3.2等價(jià)的非二義文法：

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

右結(jié)合 [-]

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

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不知與哪個(gè)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)先級(jí)和結(jié)合性 二義文法的優(yōu)點(diǎn)：比非二義文法容易理解；分析效率高(分析樹低，直接推導(dǎo)步驟少)。

YACC為二義文法規(guī)定優(yōu)先級(jí)和結(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á)式加括號(hào)，如Pascal中邏輯和算術(shù)運(yùn)算：

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

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

ContextSensitiveLanguage,CSL

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

定義3.8

若文法G=(N，T，P，S)的每個(gè)產(chǎn)生式α→β中，均有α∈(N∪T)*，且至少含有一個(gè)非終結(jié)符，β∈(N∪T)*，則稱G為0型文法。對(duì)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。文法語言自動(dòng)機(jī)短語文法(0型)短語結(jié)構(gòu)語言圖靈機(jī)CSG(1型)CSL線性界線自動(dòng)機(jī)CFG(2型)CFL下推自動(dòng)機(jī)正規(guī)文法(3型)正規(guī)集有限自動(dòng)機(jī)413.3語言與文法簡(jiǎn)介再考察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ì)和自動(dòng)機(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)的方法分析輸入序列：對(duì)輸入序列ω，從S開始進(jìn)行最左推導(dǎo)，直到得到一個(gè)合法句子或非法結(jié)構(gòu)；從左到右掃描輸入序列，試圖用一切可能的方法，自上而下建立它的分析樹；一種試探的過程，反復(fù)使用不同產(chǎn)生式，謀求與輸入序列匹配；[例3.16]用下述文法分析輸入序列ω=cad：S →cAdA →ab |a433.4自上而下語法分析問題：

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

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

消除直接左遞歸輸入 G中所有的A產(chǎn)生式(含直接左遞歸)輸出 等價(jià)的不含直接左遞歸的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為空，則形成一個(gè)有環(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輸出 無左遞歸的等價(jià)文法G'方法 將非終結(jié)符合理排序：A1，A2，...，An; for iin2..n loopforjin1..i-1 loop

用Aj→δ1|δ2|...|δk的右部替換每個(gè)形如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自上而下語法分析核心思想：將不是直接左遞歸的符號(hào)右部展開到其他產(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)生式的哪個(gè)候選項(xiàng)替換A時(shí)，可以重寫A產(chǎn)生式來推遲這種決定，直到看見足夠的輸入，能正確決定所需選擇為止。這一過程被稱為提取左因子，它類似于有限自動(dòng)機(jī)的確定化。將： A→αβ1|αβ2替換為： A→αA' A'→β1|β2等價(jià)于： A→α(β1|β2)493.4自上而下語法分析算法3.3

提取文法的左因子輸入 文法G輸出 等價(jià)的無左因子文法G'方法 重復(fù)過程，直到所有A產(chǎn)生式候選項(xiàng)中不再有公共前綴：重排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)生語言的過程；每個(gè)產(chǎn)生式對(duì)應(yīng)一個(gè)子程序，產(chǎn)生式右邊的非終結(jié)符對(duì)應(yīng)子程序調(diào)用，終結(jié)符則與輸入序列匹配；它對(duì)文法的限制是不能有公共左因子和左遞歸；它是一種非形式化的方法，只要能寫出子程序，用什么樣的方法和步驟均可。一種穩(wěn)妥的方法構(gòu)造文法的狀態(tài)轉(zhuǎn)換圖并且化簡(jiǎn)；將轉(zhuǎn)換圖轉(zhuǎn)化為EBNF表示；從EBNF構(gòu)造子程序。513.4自上而下語法分析構(gòu)造狀態(tài)轉(zhuǎn)換圖且化簡(jiǎn)遞歸下降分析的文法：

L→E;L|εE→E+T|E-T|TT→T*F|T/F|TmodF|FF→(E)|id|num每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)狀態(tài)轉(zhuǎn)換圖：為非終結(jié)符A建立一個(gè)初態(tài)和一個(gè)終態(tài)；為A→X1X2...Xn構(gòu)造從初態(tài)到終態(tài)的路徑，邊標(biāo)記為X1，X2，...，Xn。根據(jù)識(shí)別同一集合的原則，化簡(jiǎn)轉(zhuǎn)換圖。消除左遞歸后的等價(jià)文法: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)圖的化簡(jiǎn)原則①標(biāo)記為A的邊可等價(jià)為標(biāo)記ε的邊轉(zhuǎn)向A轉(zhuǎn)換圖的初態(tài)；②ε邊連接的兩個(gè)狀態(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ùn)算的優(yōu)先級(jí)和結(jié)合性EBNF表示：L→{E;}E→T{(+|-)T}T→F{(*|/|mod)F}F→(E)|id|num55上次課總結(jié)形式語言與自動(dòng)機(jī)簡(jiǎn)介自上而下分析：自上而下/從左到右(不能有左遞歸/左因子)消除左遞歸提取左因子遞歸下降分析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ī)。 同樣，文法中的公共左因子也會(huì)給遞歸下降分析造成困難。583.4自上而下語法分析預(yù)測(cè)分析器非遞歸預(yù)測(cè)分析器的工作模式預(yù)測(cè)分析器的核心概念：分析方法：格局與格局變換分析表+驅(qū)動(dòng)器（模擬算法）預(yù)測(cè)分析表的構(gòu)造LL（文法、語言、分析器）593.4自上而下語法分析預(yù)測(cè)分析表

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

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

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

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

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

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

endloop;63用預(yù)測(cè)分析器分析句子棧 當(dāng)前剩余輸入 動(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ù)測(cè)分析表首先構(gòu)造FIRST集合與FOLLOW集合；然后根據(jù)兩個(gè)集合構(gòu)造預(yù)測(cè)分析表。定義3.10

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

非終結(jié)符A的FOLLOW集合如下: FOLLOW(A)={a|S=*>...Aa...，a∈T}， 若A是某句型的最右符號(hào)，則#∈FOLLOW(A)。通俗地講，α的FIRST集合就是從α開始可導(dǎo)出的文法符號(hào)序列中的開頭終結(jié)符。而A的FOLLOW集合，就是從開始符號(hào)可以導(dǎo)出的所有含A的文法符號(hào)序列中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

計(jì)算X的FIRST集合輸入 文法符號(hào)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=ε。那么對(duì)所有j(0≤j≤k)，若a∈FIRST(Yj+1)且ε∈FIRST(Yj),則加入a到FIRST(X)。FIRST(X1X2...Xn)的計(jì)算方法與算法3.5中步驟3類似，即是所有FIRST(Xi)(i=1,2,..,k)的并集，其中k為第一個(gè)具有性質(zhì)ε不屬于FIRST(Xk)或k>n的文法符號(hào)，若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

計(jì)算所有非終結(jié)符的FOLLOW集合輸入 文法G輸出 G中所有非終結(jié)符的FOLLOW集合方法 應(yīng)用下述規(guī)則:加入#到FOLLOW(S)，其中S是開始符號(hào)，#是輸入結(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之后因?yàn)棣拧蔉IRST(β)使得B成為A產(chǎn)生式右部最右的文法符號(hào)即對(duì)任何a∈FOLLOW(A)，均有a∈FOLLOW(B)，反之不然。673.4自上而下語法分析[例3.22]計(jì)算非終結(jié)符的FIRST與FOLLOW。提示：自下而上計(jì)算FIRST，自上而下計(jì)算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ù)測(cè)分析表輸入 文法G輸出 分析表M方法 應(yīng)用下述規(guī)則對(duì)文法的每個(gè)產(chǎn)生式A→α，執(zhí)行2和3；對(duì)FIRST(α)的每個(gè)終結(jié)符a，加入α到M[A，a]；若ε∈FIRST(α)，則FOLLOW(A)每個(gè)終結(jié)符b（包括#），加入α到M[A，b]；M中其它沒有定義的條目均是error。M[A，a]指導(dǎo)下一步動(dòng)作：若當(dāng)前棧頂為A，當(dāng)前輸入為a，則規(guī)則2表示下一步動(dòng)作是展開A→α，因?yàn)閍∈FIRST(α)，展開后下一次正好匹配a。若當(dāng)前棧頂為A，當(dāng)前輸入為b且b∈FOLLOW(A)，則規(guī)則3表示下一步動(dòng)作是展開A→ε，即棧頂彈出A，繼續(xù)分析A之后的部分，因?yàn)閎∈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對(duì)FIRST(α)的每個(gè)終結(jié)符a，加入α到M[A，a]；若ε∈FIRST(α)，則FOLLOW(A)每個(gè)終結(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ù)測(cè)分析器下推自動(dòng)機(jī)符號(hào)棧、分析表、驅(qū)動(dòng)器格局與格局的變換預(yù)測(cè)分析表的構(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]中都最多有一個(gè)條目？[例3.23]二義文法的預(yù)測(cè)分析表： 文法：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ù)測(cè)分析表中不含多重定義的條目。由此分析表所組成的分析器被稱為L(zhǎng)L(1)分析器，所分析的語言被稱為L(zhǎng)L(1)語言。第一個(gè)L代表從左到右掃描輸入序列，第二個(gè)L表示產(chǎn)生最左推導(dǎo)，1表示在確定每一步動(dòng)作時(shí)向前看一個(gè)終結(jié)符。判定LL(1)文法的方法：a)構(gòu)造分析表；b)無需構(gòu)造分析表。推論3.2G是LL(1)的，當(dāng)且僅當(dāng)G的任何兩個(gè)產(chǎn)生式A→α|β滿足：對(duì)任何終結(jié)符a，α和β不能同時(shí)推導(dǎo)出以a開始的串；α和β最多有一個(gè)可以推導(dǎo)出ε；若β=*>ε,則α不能導(dǎo)出以FOLLOW(A)中終結(jié)符開始的任何串。733.4自上而下語法分析對(duì)FIRST(α)的每個(gè)終結(jié)符a，加入α到M[A，a]；若ε∈FIRST(α)，則FOLLOW(A)每個(gè)終結(jié)符b(包括#)，加入α到M[A，b]；證明：若條件1不滿足，即存在終結(jié)符a，α和β同時(shí)推導(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)的，因?yàn)椴粷M足條件1。文法(G3.4')是LL(1)的，因?yàn)槿齻€(gè)條件均滿足。E→E+T|TT→T*F|F(G3.4)F→(E)|-F|idLL(1)文法的弱點(diǎn)：文法難寫、難懂；適應(yīng)范圍有限，往往寫不出有些語言的LL(1)文法。實(shí)際編譯器中使用更多的是一類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)生語言的自然過程。對(duì)于分析語言來講，自下而上分析的方法更自然，因?yàn)檎Z法分析處理的對(duì)象一開始都是終結(jié)符組成的串，而不是文法的開始符號(hào)。同時(shí)，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要強(qiáng)，從而使得LR分析成為最為實(shí)用的語法分析方法。兩種主要的自下而上分析方法：算符優(yōu)先分析(不討論)LR分析763.5自下而上語法分析自下而上分析的基本方法思路：從句子ω開始，從左到右掃描ω，反復(fù)用產(chǎn)生式的左部替換產(chǎn)生式的右部、謀求對(duì)ω的匹配，最終得到文法的開始符號(hào)，或者發(fā)現(xiàn)一個(gè)錯(cuò)誤。規(guī)范規(guī)約與“剪句柄”定義3.13

設(shè)αβδ是文法G的一個(gè)句型，若存在S=*>αAδ，A=+>β，則稱β是句型αβδ相對(duì)于A的短語，特別的，若有A→β，則稱β是句型αβδ相對(duì)于產(chǎn)生式A→β的直接短語。一個(gè)句型的最左直接短語被稱為句柄。直觀上，句型是一個(gè)完整結(jié)構(gòu)，短語是句型中針對(duì)某非終結(jié)符的局部。因此，開始符號(hào)S是句型而不是短語。短語形成的兩個(gè)要素：從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是α的一個(gè)最左歸約。αn=αα0=S（S是G的開始符號(hào)）對(duì)任何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

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

abbcde<=aAbcde<=aAde<=aABe<=S提醒：最左歸約的逆過程是一個(gè)最右推導(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)有了句子的分析樹，則：需要解決的問題：確定右句型中將要?dú)w約的子串（確定句柄）；確定如何選擇正確的產(chǎn)生式進(jìn)行歸約。移進(jìn)-歸約：用一個(gè)棧“記住”將要?dú)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ù)測(cè)分析器：分析方法：格局與格局變換分析表驅(qū)動(dòng)器（模擬算法）預(yù)測(cè)分析表的構(gòu)造LL（文法、語言、分析器）移進(jìn)-歸約分析器：分析方法：格局與格局變換分析表驅(qū)動(dòng)器（模擬算法）LR（文法、語言、分析器）SLR分析表的構(gòu)造823.5自下而上語法分析工作方法：放幻燈，每個(gè)幻燈片是一個(gè)格局。格局：（#棧，當(dāng)前剩余輸入#，改變格局的動(dòng)作）改變格局的動(dòng)作：移進(jìn)(shift)：輸入序列中的終結(jié)符進(jìn)棧。(匹配終結(jié)符)歸約(reduce)：將棧頂句柄替換為對(duì)應(yīng)非終結(jié)符(最左歸約)。接受(accept)：宣告分析成功。報(bào)錯(cuò)(error)：發(fā)現(xiàn)語法錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程。對(duì)照預(yù)測(cè)分析：匹配終結(jié)符（彈出）最左推導(dǎo)（展開非終結(jié)符）833.5自下而上語法分析[例3.27]用移進(jìn)-歸約方法分析abbcde：

abbcde<=aAbcde<=aAde<=aABe<=S棧 剩余輸入 改變格局的動(dòng)作# 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é)論：句柄總是在棧頂形成(最左歸約)。棧中保留的總是一個(gè)右句型的前綴(加上若干終結(jié)符形成句型)，稱為活前綴；最左歸約是邏輯上從下到上構(gòu)造一棵分析樹，或從下到上為分析樹剪句柄。843.5自下而上語法分析LR分析LR分析的特點(diǎn)：采用最一般的無回溯移進(jìn)－歸約方法可分析的文法是LL文法的真超集能及時(shí)發(fā)現(xiàn)錯(cuò)誤，快到從左到右掃描輸入序列的最大可能分析表較復(fù)雜，難以手工構(gòu)造LR分析的核心：移進(jìn)－歸約分析表＋驅(qū)動(dòng)器內(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動(dòng)作表(action)轉(zhuǎn)移表(goto)action[s,a]確定改變格局的動(dòng)作(與輸入有關(guān))goto[s,A]指示非終結(jié)符的狀態(tài)轉(zhuǎn)移分析表格局與動(dòng)作：開始格局：(#0，ω#，移進(jìn))結(jié)束格局：(#0S，#，接受)出錯(cuò)格局：(#δ，ω'#，報(bào)錯(cuò))改變格局的動(dòng)作：action[s,a]=si：移進(jìn)

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

=acc：接收

=blank：報(bào)錯(cuò)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ī)范歸約，否則指出一個(gè)錯(cuò)誤方法 初始格局為：（#0，ω#，移進(jìn)），其中0是初態(tài)

ip指向ω#中的第一個(gè)終結(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)生式左部符號(hào)進(jìn)棧

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

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

accept:return; --成功返回

others:error; --出錯(cuò)處理

endcase; endloop;實(shí)際的算法中僅存放狀態(tài)，而在分析的格局中，僅顯示文法符號(hào)。873.5自下而上語法分析棧 剩余輸入 動(dòng)作#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為L(zhǎng)R(k)文法，分析器被稱為是LR(k)分析器，它所識(shí)別的語言被稱為L(zhǎng)R(k)語言。L表示從左到右掃描