《編譯原理-語法分析.ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理-語法分析.ppt（42頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、1,第三章 語法分析,詞法分析：字母是元素，組成字符串，記號的集合，線性結(jié)構(gòu) 語法分析：記號是元素，組成句子， 句子的集合，樹結(jié)構(gòu) 語法的雙重含意： 語法規(guī)則：上下文無關(guān)文法（子集LL文法或LR文法） 語法分析：下推自動機(jī)（LL或LR分析器），自上而下和自下而上分析,本章主要內(nèi)容： 與語法分析有關(guān)的基本概念和相關(guān)問題 上下文無關(guān)文法 自上而下分析 自下而上分析 上機(jī)作業(yè)第二部分：函數(shù)繪圖語言的語法分析器,結(jié)束（2010年3月25日）,2,3.1 語法分析的若干問題 3.1.1 語法分析器的作用,語法分析器是編譯器前端的重要組成部分，許多編譯器，特別是由自動生成工具構(gòu)造的編譯器，往往其前端的中心

2、部件就是語法分析器。 語法分析器在編譯器中的位置和作用：,3,3.1.1 語法分析器的作用（續(xù)）,根據(jù)詞法分析器提供的記號流，為語法正確的輸入構(gòu)造分析樹（或語法樹），這是本章的重點(diǎn)，在以后各節(jié)中詳細(xì)討論； 檢查輸入中的語法（可能包括詞法）錯誤，并調(diào)用出錯處理器進(jìn)行適當(dāng)處理，下邊簡單介紹語法錯誤處理的基本原則，而在以后的討論中忽略此問題。,語法分析器的兩個重要作用：,4,3.1.2 語法錯誤的處理原則,詞法錯誤如非法字符或拼寫錯關(guān)鍵字、標(biāo)識符等 intege20times 語法錯誤是指語法結(jié)構(gòu)出錯，如少分號、begin/end不配對等 beginx:=a+by:=x; 靜態(tài)語義錯誤：如類型不

3、一致、參數(shù)不匹配等 a,b:integer;x:array1..10 of integer; x:=a+b; 動態(tài)語義錯誤(邏輯錯誤)：如死循環(huán)、變量為零時作除數(shù)等 while (t) ...;a:=a/b;, 源程序中可能出現(xiàn)的錯誤 兩類：語法（包括詞法）錯誤和語義錯誤,5,3.1.2 語法錯誤的處理原則（續(xù)1）,大多數(shù)錯誤的診斷和恢復(fù)集中在語法分析階段。一個原因是大多數(shù)錯誤是語法錯誤，另一個原因是語法分析方法的準(zhǔn)確性，它們能以非常有效的方法診斷語法錯誤。 編譯時想要準(zhǔn)確診斷語義或邏輯錯誤有時是很困難的。,對語法錯誤的處理，一般希望達(dá)到以下基本目標(biāo)： 清楚而準(zhǔn)確地報(bào)告錯誤的出現(xiàn)，地點(diǎn)

4、正確、不漏報(bào)、不錯報(bào)也不多報(bào)； 迅速從每個錯誤中恢復(fù)過來（以便分析繼續(xù)進(jìn)行）； 不應(yīng)使對語法正確源程序的分析速度降低太多。, 語法錯誤處理的目標(biāo),6,3.1.2 語法錯誤的處理原則（續(xù)2）,緊急方式恢復(fù)：拋棄若干輸入，直到遇到同步記號。 短語級恢復(fù)：采用串替換的方式對剩余輸入進(jìn)行局部糾正（拋棄插入）。 出錯產(chǎn)生式：用出錯產(chǎn)生式捕捉錯誤（預(yù)測錯誤）。預(yù)置型的短語級恢復(fù)方式。 全局糾正：對錯誤輸入序列x，找相近序列y，使得x變換成y所需的修改、插入、刪除次數(shù)最少。, 語法錯誤的基本恢復(fù)策略,7,3.1.2 語法錯誤的處理原則（續(xù)3）,緊急方式： x := a + b + d; -- 丟棄b后若干記

5、號，直到遇到+ 短語級恢復(fù)：x := a + b; -- 加入分號，使之成為一個賦值句 y := c + d;,例3.1 下述兩條是有語法錯誤的語句，其中第一條賦值句結(jié)束時忘記加分號，采用緊急恢復(fù)方式和短語級恢復(fù)方式的可能結(jié)果分別如下所示。,x := a + b y := c + d;,8,3.2 上下文無關(guān)文法(Context Free Grammar,CFG)3.2.1 CFG的定義與表示,定義3.1 CFG是一個四元組G =（N，T，P，S），其中 （1） N是非終結(jié)符（Nonterminals）的有限集合； （2） T是終結(jié)符（Terminals）的有限集合，且NT=； （3

6、） P是產(chǎn)生式（Productions）的有限集合， A，其中AN（左部），(NT)*（右部）， 若=，則稱A為空產(chǎn)生式（也可以記為A ）； （4） S是非終結(jié)符，稱為文法的開始符號（Start symbol）。 ,9,3.2.1 CFG的定義與表示（續(xù)1）,N = E T = +，*，(，)，-，idS = E P: E E + E （1） E E * E （2） E （E） （3） (G3.1) E -E （4） E id （5）,例3.2 簡單算術(shù)表達(dá)式的上下文無關(guān)文法可表示如下：, 產(chǎn)生式的一般讀法 可以將產(chǎn)生式中的記號讀作“定義為

7、”或者“可導(dǎo)出”。 更一般的，“E E + E”可用自然語言表述為“算術(shù)表達(dá)式定義為兩個算術(shù)表達(dá)式相加”。 或者“一個算術(shù)表達(dá)式加上另一個算術(shù)表達(dá)式，仍然是一個算術(shù)表達(dá)式”。,10,3.2.1 CFG的定義與表示（續(xù)2）,前提：若文法正確，第一個產(chǎn)生式的左部是文法開始符號S 則： 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）,S=E N=E T=+，*，(，)，-，id, 由產(chǎn)生式集表示CFG,11,3.2.1 CFG的定義與表示（續(xù)3）,

8、(a) 用大小寫區(qū)分： E id (b) 用區(qū)分： E id E E + E (c) 用區(qū)分： + 約定：大寫英文字母A、B、C表示非終結(jié)符； 小寫英文字母a、b、c表示終結(jié)符； 小寫希臘字母、、表示任意文法符號序列。, 終結(jié)符與非終結(jié)符書寫上的區(qū)分,12,3.2.1 CFG的定義與表示（續(xù)4）,當(dāng)若干個產(chǎn)生式具有相同的左部非終結(jié)符時，可以將它們合并為一個產(chǎn)生式。 該產(chǎn)生式的左部是此非終結(jié)符， 右部是所有原來右部的或運(yùn)算（并集合）， 產(chǎn)生式以該非終結(jié)符命名。 例3.3 G3.1可以重寫為如下形式：,E E + E （1） | E * E （2） |（E）

9、 （3） (G3.2) | -E （4） | id （5）,P: E E + E （1） E E * E （2） E （E） （3） E -E （4） E id （5）, 產(chǎn)生式的縮寫形式,稱其為E產(chǎn)生式。 用“|”連接的每個右部稱為一個候選項(xiàng)，具有平等的權(quán)利。 即id是一個表達(dá)式，-E也是一個表達(dá)式。,13,3.2.2 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)記=表示)，直到得到一個

10、終結(jié)符序列。,E = -E by(4) = -(E) by(3) = -(E+E) by(1) = -(id+E) by(5) = -(id+id) by(5),E E + E （1） | E * E （2） |（E） （3） (G3.2) | -E （4） | id （5）,例3.4 用(G3.2)產(chǎn)生終結(jié)符序列-(id+id)可如下：,14,3.2.2 CFG產(chǎn)生語言的基本方法推導(dǎo)（續(xù)1）,若對于任意文法符號序列1，2，...n，均有1=2=...=n，則稱此過程為零步或多步推導(dǎo)，記為： 1=*n，其中1=n的情況為零步推導(dǎo)。 若1n，即推導(dǎo)過程中至少使用一次產(chǎn)生式，則稱此過程為至少

11、一步推導(dǎo)，記為：1=+n。 ,定義3.2強(qiáng)調(diào)了兩點(diǎn)： ，有=*，即推導(dǎo)具有自反性； 若=*，=*，則=*，即推導(dǎo)具有傳遞性。,定義3.2 利用產(chǎn)生式產(chǎn)生句子的過程中，將產(chǎn)生式A的右部代替文法符號序列A中的A得到的過程，稱A直接推導(dǎo)出，記作：A=。,15,3.2.2 CFG產(chǎn)生語言的基本方法推導(dǎo)（續(xù)2）,定義3.3 由CFG G所產(chǎn)生的語言L(G)被定義為: L(G) = S=+ and T* ， L(G)稱為上下文無關(guān)語言(Context Free Language, CFL)，稱為句子。 若S=*，(NT)*，則稱為G的一個句型。 ,定義3.4 在推導(dǎo)過程中，若每次直接推導(dǎo)均替換

12、句型中最左邊的非終結(jié)符，則稱為最左推導(dǎo)，由最左推導(dǎo)產(chǎn)生的句型被稱為左句型。 ,類似的可以定義最右推導(dǎo)與右句型，最右推導(dǎo)也被稱為規(guī)范推導(dǎo)。,16,3.2.2 CFG產(chǎn)生語言的基本方法推導(dǎo)（續(xù)3）,E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 1 2 3 4 5 6,E E + E （1） | E * E （2） |（E） （3） (G3.2) | -E （4） | id （5）,再考察-(id+id)的推導(dǎo)過程（這是一個最左推導(dǎo)）：,其中，1是文法開始符號，6是句子，其他i (i=2、3、4、5)均是句型。 句型是一個相當(dāng)廣泛的概念，根據(jù)定

13、義3.3可知，1和6同樣也是句型。,17,3.2.3 推導(dǎo)、分析樹與語法樹,推導(dǎo)：E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 產(chǎn)生句子的方式很不直觀，看起來十分困難。 分析樹是推導(dǎo)的圖形表示，它的表示很直觀，并且同時反映語言結(jié)構(gòu)的實(shí)質(zhì)和推導(dǎo)過程。,定義3.5 對CFG G的句型，分析樹被定義為具有下述性質(zhì)的一棵樹。 （1） 根由開始符號所標(biāo)記； （2） 每個葉子由一個終結(jié)符、非終結(jié)符、或標(biāo)記； （3） 每個內(nèi)部結(jié)點(diǎn)由一個非終結(jié)符標(biāo)記； （4） 若A是某內(nèi)部節(jié)點(diǎn)的標(biāo)記，且X1，X2，...，Xn是該節(jié)點(diǎn)從左到右所有孩子的標(biāo)記，則AX1X2.

14、..Xn是一個產(chǎn)生式。若A，則標(biāo)記為A的結(jié)點(diǎn)可以僅有一個標(biāo)記為的孩子。 ,18,3.2.3 推導(dǎo)、分析樹與語法樹（續(xù)1）,每一直接推導(dǎo)(每個產(chǎn)生式)，對應(yīng)一棵僅有父子關(guān)系的子樹，即產(chǎn)生式左部非終結(jié)符“長出”右部的孩子； 分析樹的葉子，從左到右構(gòu)成G的一個句型。若葉子僅由終結(jié)符標(biāo)記，則構(gòu)成一個句子。,分析樹與語言和文法的關(guān)系：,19,3.2.3 推導(dǎo)、分析樹與語法樹（續(xù)2）,E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 用分析樹的方式如下：,最左推導(dǎo)和最右推導(dǎo)的中間過程對應(yīng)的分析樹可能不同，因?yàn)榫湫筒煌?-(id+E) 或 -(E+id) 但是最終的分

15、析樹相同，因?yàn)樽罱K是同一個句子： -(id+id),例3.5 再考察-(id+id)的推導(dǎo)過程。,分析樹既反映了產(chǎn)生句型的推導(dǎo)過程，又反映了句型的結(jié)構(gòu)。,20,3.2.3 推導(dǎo)、分析樹與語法樹（續(xù)3）,更多的情況下，僅關(guān)注句型結(jié)構(gòu)，而忽略推導(dǎo)過程。,定義3.6 對CFG G的句型，表達(dá)式的語法樹被定義為具有下述性質(zhì)的一棵樹: （1） 根與內(nèi)部節(jié)點(diǎn)由表達(dá)式中的操作符標(biāo)記； （2） 葉子由表達(dá)式中的操作數(shù)標(biāo)記； （3）用于改變運(yùn)算優(yōu)先級和結(jié)合性的括弧，被隱含在語法樹的結(jié)構(gòu)中。 ,實(shí)質(zhì)上，語法樹與分析樹的最根本區(qū)別在于它們的內(nèi)部節(jié)點(diǎn)（包括根節(jié)點(diǎn)）： 分析樹的內(nèi)部節(jié)點(diǎn)是非終結(jié)符； 語法樹的內(nèi)部節(jié)點(diǎn)是操

16、作符（運(yùn)算符）； 或者說語法樹中省略了反映分析過程的非終結(jié)符。,21,3.2.3 推導(dǎo)、分析樹與語法樹（續(xù)4）,例3.6 句子-(id+id)和句型if C then s1 else s2 ：,分析樹：左部非終結(jié)符“產(chǎn)生出”右部文法符號序列； 語法樹：操作符（運(yùn)算）“作用于”操作數(shù)（運(yùn)算對象）； 習(xí)慣上：它們分別被稱為具體語法樹和抽象語法樹。,22,結(jié)束（2010年3月30日）,定義3.1 CFG 定義3.2 直接推導(dǎo)、零或多步推導(dǎo)、至少一步推導(dǎo) 定義3.3 CFL、句子、句型 定義3.4 最左推導(dǎo)、左句型（最右推導(dǎo)、右句型） 定義3.5 分析樹 定義3.6 語法樹,今天的重要概念,23,上次

17、課程內(nèi)容回顧,語法分析的基本概念、語法錯誤處理簡介 上下文無關(guān)文法（CFG） 文法的定義 文法的表示（產(chǎn)生式、終結(jié)符與非終結(jié)符的區(qū)分） CFG產(chǎn)生語言的基本方法推導(dǎo) 推導(dǎo)的基本概念 用推導(dǎo)的方法產(chǎn)生的語言（CFL，句子與句型） 推導(dǎo)的直觀表示分析樹 分析樹與語法樹二者的特點(diǎn)與區(qū)別,24,3.2.4 二義性與二義性的消除3.2.4.1 二義性（歧義，Ambiguity）,問題：一個句子可能對應(yīng)多于一棵分析樹 例3.7 句子id+id*id和id+id+id可能的分析樹：,EE+E | E*E |（E）| -E | id (G3.2),*優(yōu)先級高,+優(yōu)先級高,+左結(jié)合,+右結(jié)合,25,3.2.4.

18、1 二義性（續(xù)1）,原因：在產(chǎn)生句子的過程中某些直接推導(dǎo)有多于一種選擇 注意： 一個句子有多于一棵分析樹，僅與文法和句子有關(guān)，與采用的推導(dǎo)方法無關(guān)； 文法中缺少對文法符號優(yōu)先級和結(jié)合性的規(guī)定。,定義3.7 若文法G對同一句子產(chǎn)生不止一棵分析樹，則稱G是二義的。 ,26,3.2.4.1 二義性（續(xù)2）,S if C then S (1) | if C then S else S (2) | id := E (3) (G3.3) C E = E | E E (4)...(6) E E + E | - E | id | n (7)...(10),例3.8 條件語句 if x0 then x

19、:=5 else x:=-5,if x0 then x:=5 else x:=-5,“懸空（dangling）else”問題,else與離它遠(yuǎn)的then匹配,27,3.2.4.1 二義性（續(xù)3）,if x0 then x:=5 else x:=-5,例3.8 條件語句 if x0 then x:=5 else x:=-5,else與離它近的then匹配,28,3.2.4.2 二義性的消除,文法二義不能說明程序設(shè)計(jì)語言是二義。程序設(shè)計(jì)語言不能二義。 消除語言二義的兩種方法： 改寫二義文法為非二義文法； 規(guī)定二義文法中符號的優(yōu)先級和結(jié)合性，使僅產(chǎn)生一棵分析樹。 改寫二義文法為非二義文法,再分析

20、id+id*id和id+id+id：,例3.9 與G3.2等價的非二義文法: E E + T | T T T * F | F (G3.4) F （E） | -F | id,問題：如何將二義文法改寫為非二義文法？,EE+E | E*E |（E） (G3.2) | -E | id,29, 改寫二義文法為非二義文法（續(xù)1）,新引入的非終結(jié)符，限制了每一步直接推導(dǎo)均有唯一選擇； 最終分析樹的形狀，僅與文法有關(guān)，而與推導(dǎo)方法無關(guān)； 非終結(jié)符的引入，增加了推導(dǎo)步驟（分析樹增高）； 越接近S的文法符號的優(yōu)先級越低。（如EE+T）。 對于AA，若A在終結(jié)符左邊出現(xiàn)（即終結(jié)符在中），則A產(chǎn)生式具有左結(jié)合性質(zhì)。

21、,改寫二義文法的關(guān)鍵步驟： 引入一個新的非終結(jié)符，增加一個子結(jié)構(gòu)并提高一級優(yōu)先級； 遞歸非終結(jié)符在終結(jié)符左邊，運(yùn)算具有左結(jié)合性，否則具有右結(jié)合性。,可以看出：,30,例3.10 改寫二義文法G3.2為G3.4,優(yōu)先級：+ * ( ), -, id 結(jié)合性：左結(jié)合+, * 右結(jié)合- 無結(jié)合id 非終結(jié)符與運(yùn)算： E:+ （E產(chǎn)生式，左遞歸） T:*， （T產(chǎn)生式，左遞歸） F:-,( ),id （F產(chǎn)生式，右遞歸）,E E + T | T T T * F | F F (E) | -F | id,引入一個新的非終結(jié)符，增加一個子結(jié)構(gòu)并提高一級優(yōu)先級； 遞歸非終結(jié)符在終結(jié)符左邊，運(yùn)算具有左結(jié)合性，否

22、則具有右結(jié)合性。,E E + E | E * E |（ E ） (G3.2) | - E | id,31, 改寫二義文法為非二義文法（續(xù)2）,if-then-else和if-then：在一個復(fù)合if語句中，可能then多于else，使得else不知與哪個then結(jié)合。 一般原則是右結(jié)合，即else與其左邊最靠近的then結(jié)合。 改寫文法的根據(jù)是將S分為完全匹配（MS）和不完全匹配（UMS）兩類，并且在UMS中規(guī)定else右結(jié)合。,S if C then S | if C then S else S | id := E (G3.3) C E=E | EE E E+E | -E | id

23、 | n,S MS (1) | UMS (2) MS if C then MS else MS (3) | id := E (4) UMS if C then S (5) | if C then MS else UMS (6) (G3.5),再討論“懸空else”問題,E E + T | T (10)...(11) T -T | id | n (12)...(14),C E = E | E E (7)...(9),32, 改寫二義文法為非二義文法（續(xù)3）,if x0 then x:=5 else x:=-5,S MS (1) | UMS (2) MS if C then MS

24、else MS (3) | id := E (4) UMS if C then S (5) (G3.5) | if C then MS else UMS (6) C E = E | E E (7)...(9) E E + T | T (10)...(11) T T | id | n (12)...(14),33, 改寫二義文法為非二義文法（續(xù)4）,S MS (1) | UMS(2) MS if C then MS else MS (3) | id := E(4) UMS if C then S(5) (G3.5) | if C then MS else UMS(6),if x0 t

25、hen x:=5 else x:=-5,不可能！,不可能！,不可能！,34, 為文法符號規(guī)定優(yōu)先級和結(jié)合性,二義文法的優(yōu)點(diǎn)： 比非二義文法容易理解； 分析效率高（分析樹低，直接推導(dǎo)步驟少）。 對于：id+id*id,為二義文法規(guī)定優(yōu)先級和結(jié)合性（YACC的方法）： E : E + E | E * E | - E | ( E ) | id,E E + E | E * E | - E | ( E ) | id,EE+T|T TT*F|F F(E)|-F|id,%left + %left * %right -,35, 修改語言的語法（表現(xiàn)形式被改變）,if x0 then x:=5; en

26、d if; else x:=-5; end if;, 給表達(dá)式加括號，如Pascal中邏輯和算術(shù)運(yùn)算： (a+b)(c*d), 明確給出結(jié)束標(biāo)志，如Ada中用end if，于是有：,if x0 then x:=5; else x:=-5; end if; end if;,if x0 then x:=5; end if; else x:=-5; end if; if x0 then x:=5; else x:=-5; end if; end if;,36,3.3 語言與文法簡介,文法的重要作用： 給出精確、易于理解的語言結(jié)構(gòu)說明； 以文法為基礎(chǔ)的語言，便于加入新的、或修改、刪除舊的語言結(jié)構(gòu)； 有

27、些類別的文法，可以自動生成高效的分析器。,本節(jié)從理論的角度對文法進(jìn)行簡單地討論。討論建立在形式語言與自動機(jī)的理論之上，且僅引用結(jié)論而忽略數(shù)學(xué)的證明，有興趣的同學(xué)可以參閱相關(guān)文獻(xiàn)。 希望通過本節(jié)的討論，對文法的分類和它們在編譯器構(gòu)造中的作用有一定的了解。,37,3.3.1 正規(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)生式AiaAj； 對于move(i,)=j，引入產(chǎn)生式 AiAj； 若i是終態(tài)，則引入產(chǎn)生式

28、Ai 。,例3.11 從正規(guī)式r=(a|b)*abb的NFA構(gòu)造CFG：,A0 aA0|bA0|aA1 A1 bA2 A2 bA3 A3 ,經(jīng)驗(yàn)的方法： A HT H | Ha | Hb T abb,產(chǎn)生abb的分析樹：,38, 為什么用正規(guī)式而不用CFG描述詞法,詞法規(guī)則簡單，用正規(guī)式描述已足夠； 正規(guī)式的表示比CFG更直觀、簡潔、易于理解； 有限自動機(jī)的構(gòu)造比下推自動機(jī)簡單，且分析效率高； 區(qū)分詞法和語法，為編譯器前端的模塊劃分提供方便。,貫穿詞法分析和語法分析始終的思想： 語言的描述和語言的識別是表示一個語言的兩個不同側(cè)面，二者缺一不可；（語言、文法、自動機(jī)） 用正規(guī)式和CFG描述的語言

29、，對應(yīng)的識別方法（自動機(jī)）不同； 一般情況下，正規(guī)式適合描述線性結(jié)構(gòu)，如標(biāo)識符、關(guān)鍵字、注釋等； CFG適合描述具有嵌套（層次）性質(zhì)的非線性結(jié)構(gòu)，如不同結(jié)構(gòu)的句子if-then-else、while-do等。,39,3.3.2 上下文有關(guān)語言（Context Sensitive Language, CSL）,程序設(shè)計(jì)語言中除了CFG可以描述的結(jié)構(gòu)之外，還有一些是CFG無法描述的所謂上下文有關(guān)的結(jié)構(gòu)。 典型的這類語言結(jié)構(gòu)包括：變量的聲明與引用、過程調(diào)用時形參與實(shí)參的一致性檢查等。 描述它們的文法被稱為上下文有關(guān)文法（Context Sensitive Grammar, CSG）。,40,

30、3.3.2 上下文有關(guān)語言（續(xù)）,L1=c|(a|b)*(標(biāo)識符聲明與引用一致性的抽象) L2=anbmcndm|n1和m1(形參與實(shí)參一致性的抽象) L3=anbncn|n1 (計(jì)數(shù)問題的抽象),相近的CFL： L1 =cr|(a|b)* L2 =anbmcmdn|n1, m1 L2 =anbncmdm|n1, m1 L3 =ambmcn|m, n1,（SaSa|bSb|c） （SaSd|aAd AbAc|bc） （SAB AaAb|ab BcBd|cd） （AAC AaAb|ab CcC|c）,例3.12 不能用CFG描述的語言：,41,計(jì)數(shù)問題,L3=anbncn|n1 CSL L3 =

31、ambmcn|m,n1CFL L3 =akbmcn|k，m，n1正規(guī)集,命題：L3不是正規(guī)集，因?yàn)闃?gòu)造不出可以識別L3的DFA。 證明：（反證） 假設(shè)L3是正規(guī)集，則可構(gòu)造n個狀態(tài)的DFA D，它接受L3； 考察D讀完，a，aa，...，an，分別到達(dá)S0，S1，...，Sn，共有n+1個狀態(tài)。 根據(jù)鴿巢原理，序列中至少有兩個狀態(tài)相同，設(shè)Si=Sj（ji），因?yàn)閍ibickL3 所以存在路徑aibick。,但是D中也有路徑ajbick，矛盾。故L3不是正規(guī)集。 ,AAC AaAb|ab CcC|c a+b+c+,42,結(jié)束 2010年4月1日,主要內(nèi)容 文法的二義性與二義性的消除 一個句子有多于一棵的分析樹 原因是文法符號缺乏優(yōu)先級和結(jié)合性的規(guī)定 改寫文法為非二義的，或者規(guī)定文法符號的優(yōu)先級與結(jié)合性 語言與文法簡介 正規(guī)式（正規(guī)文法） 上下文無關(guān)文法 上下文有關(guān)文法 計(jì)數(shù)問題（三者之間的關(guān)系）,