西安電子科技大學(xué)《編譯原理》.ppt

《西安電子科技大學(xué)《編譯原理》.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《西安電子科技大學(xué)《編譯原理》.ppt（32頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1,第三章 語法分析,詞法分析：元素是字母表，組成字符串，線性結(jié)構(gòu)，單詞的集合 語法分析：元素是終結(jié)符，組成句子，樹結(jié)構(gòu)， 句子的集合 語法的雙重含意： ① 語法規(guī)則：上下文無關(guān)文法（子集－LL文法或LR文法） ② 語法分析：下推自動(dòng)機(jī)（LL或LR分析器），自上而下和自下而上分析,本章主要內(nèi)容： 與語法分析有關(guān)的基本概念和相關(guān)問題 上下文無關(guān)文法 自上而下分析 自下而上分析 上機(jī)作業(yè)－第二部分：函數(shù)繪圖語言的語法分析器,2,3.1 語法分析的若干問題 3.1.1 語法分析器的作用,語法分析器是編譯器前端的重要組成部分，許多編譯器，特別是由自動(dòng)生成工具構(gòu)造的編譯器，往往其前端的中心部件就是語法分析器。語法分析器在編譯器中的位置和作用下：,它的主要作用有兩點(diǎn)： 根據(jù)詞法分析器提供的記號流，為語法正確的輸入構(gòu)造分析樹（或語法樹），這是本章的重點(diǎn)，在以后各節(jié)中詳細(xì)討論； 檢查輸入中的語法（可能包括詞法）錯(cuò)誤，并調(diào)用出錯(cuò)處理器進(jìn)行適當(dāng)處理，下邊簡單介紹語法錯(cuò)誤處理的基本原則，而在以后的討論中忽略此問題。,3,3.1.2 語法錯(cuò)誤的處理原則, 源程序中可能出現(xiàn)的錯(cuò)誤 兩類：語法錯(cuò)誤和語義錯(cuò)誤。 ① 詞法錯(cuò)誤如非法字符或拼寫錯(cuò)關(guān)鍵字、標(biāo)識符等； @ intege 20times ② 語法錯(cuò)誤是指語法結(jié)構(gòu)出錯(cuò)，如少分號、begin/end不配對等。 begin x:=a+b y:=x; ③ 靜態(tài)語義錯(cuò)誤：如類型不一致、參數(shù)不匹配等； a,b:integer; x:array[110] of integer; x:=a+b; ④ 動(dòng)態(tài)語義錯(cuò)誤（邏輯錯(cuò)誤）：如無窮遞歸、變量為零時(shí)作除數(shù)等。 while (t) { .}; a:=a/b;,大多數(shù)錯(cuò)誤的診斷和恢復(fù)集中在語法分析階段。一個(gè)原因是大多數(shù)錯(cuò)誤是語法錯(cuò)誤，另一個(gè)原因是語法分析方法的準(zhǔn)確性，它們能以非常有效的方法診斷語法錯(cuò)誤。 在編譯的時(shí)侯，想要準(zhǔn)確診斷語義或邏輯錯(cuò)誤有時(shí)是很困難的。,4,3.1.2 語法錯(cuò)誤的處理原則（續(xù)1）, 語法錯(cuò)誤處理的目標(biāo) 對語法錯(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)使對語法正確源程序的分析速度降低太多。,5,3.1.2 語法錯(cuò)誤的處理原則（續(xù)2）, 語法錯(cuò)誤的基本恢復(fù)策略 緊急方式恢復(fù)：拋棄若干輸入，直到遇到同步記號。 短語級恢復(fù)：采用串替換的方式對剩余輸入進(jìn)行局部糾正（拋棄＋插入）。 出錯(cuò)產(chǎn)生式：用出錯(cuò)產(chǎn)生式捕捉錯(cuò)誤（預(yù)測錯(cuò)誤）。預(yù)置型的短語級恢復(fù)方式。 全局糾正：對錯(cuò)誤輸入序列x，找相近序列y，使得x變換成y所需的修改、插入、刪除次數(shù)最少。,例3.1 下述兩條是有語法錯(cuò)誤的語句，其中第一條賦值句結(jié)束時(shí)忘記加分號，采用緊急恢復(fù)方式和短語級恢復(fù)方式的可能結(jié)果分別如下所示。 x := a + b y := c + d; 緊急方式： x := a + b + d; -- 丟棄b之后的若干記號，直到遇到同步記號+為止。 短語級恢復(fù)：x := a + b; -- 加入分號，使之成為一個(gè)賦值句 y := c + d;,6,3.2 上下文無關(guān)文法(Context Free Grammar, CFG) 3.2.1 CFG的定義與表示,定義3.1 CFG是一個(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é)符，稱為文法的開始符號（Start symbol）?！?例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）,7, 由產(chǎn)生式集表示CFG 3.2.1 CFG的定義與表示（續(xù)1）,前提：若文法正確，第一個(gè)產(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）, 產(chǎn)生式的一般讀法 可以將產(chǎn)生式中的記號→讀作“定義為”或者“可導(dǎo)出”。 更一般的，“E → E + E”可用自然語言表述為“算術(shù)表達(dá)式定義為兩個(gè)算術(shù)表達(dá)式相加”， 或者“一個(gè)算術(shù)表達(dá)式加上另一個(gè)算術(shù)表達(dá)式，仍然是一個(gè)算術(shù)表達(dá)式”。, 終結(jié)符與非終結(jié)符書寫上的區(qū)分 (a) 用大小寫區(qū)分： E → id (b) 用“”區(qū)分： E → “id“ E → E “+“ E (c) 用區(qū)分： → + 約定：大寫英文字母A、B、C表示非終結(jié)符； 小寫英文字母a、b、c表示終結(jié)符； 小寫希臘字母α、β、δ表示任意文法符號序列。,S=E N={E} T={+，*，(， )，-，id},8, 產(chǎn)生式的縮寫形式 3.2.1 CFG的定義與表示（續(xù)2）,當(dāng)若干個(gè)產(chǎn)生式具有相同的左部非終結(jié)符時(shí)，可以將它們合并為一個(gè)產(chǎn)生式。 該產(chǎn)生式的左部是此非終結(jié)符， 右部是所有原來右部的或運(yùn)算（并集合）， 產(chǎn)生式也以非終結(jié)符命名。,例3.3 G3.1可以重寫為如下形式： E → E + E （1） | E * E （2） |（E） （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）,我們可以稱它為E產(chǎn)生式。 用“|”連接的每個(gè)右部稱為一個(gè)候選項(xiàng)，它們具有平等的權(quán)利。 即id是一個(gè)表達(dá)式，-E也是一個(gè)表達(dá)式。,9,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)記=表示），直到得到一個(gè)終結(jié)符序列。,例3.4 用(G3.2)產(chǎn)生終結(jié)符序列-(id+id)可如下： 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）,10,3.2.2 CFG產(chǎn)生語言的基本方法－推導(dǎo)（續(xù)1）,定義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。 ■,定義3.2強(qiáng)調(diào)了兩點(diǎn)： ① ?α，有α=*α，即推導(dǎo)具有自反性； ② 若α=*β，β=*γ，則α=*γ，即推導(dǎo)具有傳遞性。,定義3.3 由CFG G所產(chǎn)生的語言L(G)被定義為: L(G) = { ω┃S=+ω and ω∈T* }， L(G)稱為上下文無關(guān)語言（Context Free Language, CFL），ω稱為句子。若S=*α，α∈(N∪T)*，則稱α為G的一個(gè)句型。 ■,11,3.2.2 CFG產(chǎn)生語言的基本方法－推導(dǎo)（續(xù)2）,定義3.4 在推導(dǎo)過程中，若每次直接推導(dǎo)均替換句型中最左邊的非終結(jié)符，則稱為最左推導(dǎo)，由最左推導(dǎo)產(chǎn)生的句型被稱為左句型。 ■,類似的可以定義最右推導(dǎo)與右句型，最右推導(dǎo)也被稱為規(guī)范推導(dǎo)。,再考察-(id+id)的推導(dǎo)過程（這是一個(gè)最左推導(dǎo)）： E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) α1 α2 α3 α4 α5 α6 其中，α1是文法開始符號，α6是句子，其他αi(i=2、3、4、5)均是句型。句型是一個(gè)相當(dāng)廣泛的概念，根據(jù)定義3.3可知，α1和α6同樣也是句型。,12,3.2.3 推導(dǎo)、分析樹與語法樹,對于推導(dǎo)：E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 它產(chǎn)生句子的方式很不直觀，看起來十分困難。 分析樹是推導(dǎo)的圖形表示，它的表示很直觀，并且同時(shí)反映語言結(jié)構(gòu)的實(shí)質(zhì)和推導(dǎo)過程。,定義3.5 對CFG G的句型，分析樹被定義為具有下述性質(zhì)的一棵樹。 （1） 根由開始符號所標(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)記為ε的孩子。 ■,分析樹與語言和文法的關(guān)系： ① 每一直接推導(dǎo)（每個(gè)產(chǎn)生式），對應(yīng)一棵僅有父子關(guān)系的子樹，即產(chǎn)生式左部非終結(jié)符“長出”右部的孩子； ② 分析樹的葉子，從左到右構(gòu)成G的一個(gè)句型。若葉子僅由終結(jié)符標(biāo)記，則構(gòu)成一個(gè)句子。,13,3.2.3 推導(dǎo)、分析樹與語法樹（續(xù)1）,例3.5 再考察-(id+id)的推導(dǎo)過程。 E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 用分析樹的方式如下：,E → -E,E → ( E ),E → E + E,E → id,最左推導(dǎo)和最右推導(dǎo)的中間過程對應(yīng)的分析樹可能不同，因?yàn)榫湫筒煌?-(id+E) 或 -(E+id) 但是最終的分析樹相同，因?yàn)樽罱K是同一個(gè)句子： -(id+id),分析樹既反映了產(chǎn)生句型的推導(dǎo)過程，又反映了句型的結(jié)構(gòu)。,14,3.2.3 推導(dǎo)、分析樹與語法樹（續(xù)2）,更多的情況下，僅關(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)中。 ■,15,3.2.3 推導(dǎo)、分析樹與語法樹（續(xù)3）,例3.6 句子-(id+id)和句型if C then s1 else s2 ：,S → if C then S1 else S2,分析樹：左部非終結(jié)符“產(chǎn)生”右部文法符號序列； 語法樹：操作符（運(yùn)算）“作用于”操作數(shù)（運(yùn)算對象）； 習(xí)慣上：分析樹和語法樹被分別稱為具體語法樹和抽象語法樹。,16,3.2.4 二義性與二義性的消除 3.2.4.1 二義性（歧義，Ambiguity）,問題：一個(gè)句子可能對應(yīng)多于一棵分析樹 例3.7 句子id+id*id和id+id+id可能的分析樹：,G3.2： E → E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5）,定義3.7 若G對同一句子產(chǎn)生不止一棵分析樹，則稱G是二義的。 ■ 原因：在產(chǎn)生句子的過程中某些直接推導(dǎo)有多于一種選擇,一個(gè)句子有多于一棵分析樹，僅與文法和句子有關(guān)，與采用的推導(dǎo)方法無關(guān)； 文法中缺少對文法符號優(yōu)先級和結(jié)合性的規(guī)定。,17,“懸空（dangling）else”問題 3.2.4.1 二義性（續(xù)1）,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:=5 else x:=-5,if x0 then x:=5 else x:=-5,if x0 then x:=5 else x:=-5,18,3.2.4.2 二義性的消除,文法二義不能說明程序設(shè)計(jì)語言是二義。程序設(shè)計(jì)語言不能二義。 消除語言二義的兩種方法： ① 改寫二義文法為非二義文法； ② 規(guī)定二義文法中符號的優(yōu)先級和結(jié)合性，使僅產(chǎn)生一棵分析樹。 改寫二義文法為非二義文法,再分析id+id*id和id+id+id：,例3.9 與G3.2等價(jià)的非二義文法: E → E + T | T T → T * F | F (G3.4) F →（E） | -F | id,問題：如何將二義文法改寫為非二義文法？,19,可以看出： 改寫二義文法為非二義文法（續(xù)1）,① 新引入的非終結(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)鍵步驟： (a) 引入一個(gè)新的非終結(jié)符，增加一個(gè)子結(jié)構(gòu)并提高一級優(yōu)先級； (b) 遞歸非終結(jié)符在終結(jié)符左邊，運(yùn)算具有左結(jié)合性，否則具有右結(jié)合性。,例3.10 改寫二義文法G3.2為G3.4 ：,E → E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5）,E → E + T | T T → T * F | F F → (E) | -F | id,20,再討論“懸空else”問題 改寫二義文法為非二義文法（續(xù)2）,if-then-else和if-then：在一個(gè)復(fù)合if語句中，可能then多于else，使得else不知與哪個(gè)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 C → E = E | E E E → E + E | - E | id | 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) C → E = E | E E (7).(9) E → E + T | T (10).(11) T → T * F | F (12).(13) F → （E） | -F | id | n (14).(17),21, 改寫二義文法為非二義文法（續(xù)3）,if x0 then x:=5 else x:=-5,if x0 then x:=5 else x:=-5,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) C → E = E | E E (7).(9) E → E + T | T (10).(11) (G3.5) T → T * F | F (12).(13) F → （E） | -F | id | n (14).(17),22, 為文法符號規(guī)定優(yōu)先級和結(jié)合性,二義文法的優(yōu)點(diǎn)： ① 比非二義文法容易理解； ② 分析效率高（分析樹低，直接推導(dǎo)步驟少）。 對于：id+id*id,為二義文法規(guī)定優(yōu)先級和結(jié)合性（YACC的方法）： %left + %left * %right - E : E + E | E * E | - E | ( E ) | id,E → E + E | E * E | - E | ( E ) | id,E→E+T|T T→T*F|F F→(E)|-F|id,23, 修改語言的語法（表現(xiàn)形式被改變）,① Ada中用end if結(jié)束條件語句，于是有： if x0 then if x0 then x:=5; then x:=5; end if; else x:=-5; else x:=-5; end if; end if; end if;,② 給表達(dá)式加括號，如Pascal中邏輯和算術(shù)運(yùn)算： (a+b)(c*d),24,3.3 語言與文法簡介,文法的重要作用： 給出精確、易于理解的語言結(jié)構(gòu)說明； 以文法為基礎(chǔ)的語言，便于加入新的、或修改、刪除舊的語言結(jié)構(gòu)； 有些類別的文法，可以自動(dòng)生成高效的分析器。,本節(jié)從理論的角度對文法進(jìn)行簡單地討論。討論建立在形式語言與自動(dòng)機(jī)的理論之上，且僅引用結(jié)論而忽略數(shù)學(xué)的證明，有興趣的同學(xué)可以參閱相關(guān)文獻(xiàn)。 希望通過本節(jié)的討論，對文法的分類和它們在編譯器構(gòu)造中的作用有一定的了解。 （證明技術(shù).ppt：語言與問題、證明技術(shù)等簡單介紹）,25,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)生式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|aA1 A1 → bA2 A2 → bA3 A3 → ε,經(jīng)驗(yàn)的方法： A → HT H →ε| Ha | Hb T → abb 分別產(chǎn)生abb的分析樹：,26, 為什么用正規(guī)式而不用CFG描述詞法,① 詞法規(guī)則簡單，用正規(guī)式描述已足夠； ② 正規(guī)式的表示比CFG更直觀、簡潔、易于理解； ③ 有限自動(dòng)機(jī)的構(gòu)造比下推自動(dòng)機(jī)簡單，且分析效率高； ④ 區(qū)分詞法和語法，為編譯器前端的模塊劃分提供方便。,貫穿詞法分析和語法分析始終的思想： 語言的描述和語言的識別是表示一個(gè)語言的兩個(gè)不同側(cè)面，二者缺一不可；（語言、文法、自動(dòng)機(jī)） 用正規(guī)式和CFG描述的語言，對應(yīng)的識別方法（自動(dòng)機(jī)）不同； 一般情況下，正規(guī)式適合描述線性結(jié)構(gòu)，如標(biāo)識符、關(guān)鍵字、注釋等； CFG適合描述具有嵌套（層次）性質(zhì)的非線性結(jié)構(gòu)，如不同結(jié)構(gòu)的句子if-then-else、while-do等。,27,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í)形參與實(shí)參的一致性檢查等。 描述它們的文法被稱為上下文有關(guān)文法（Context Sensitive Grammar, CSG）。,例3.12 不能用CFG描述的語言： L1={ωcω|ω∈(a|b)*} （ 標(biāo)識符聲明與引用一致性的抽象） L2={anbmcndm|n≥1和m≥1} （形參與實(shí)參一致性的抽象） L3={anbncn|n≥1} （計(jì)數(shù)問題的抽象）,相近的CFL： L1={ωcωr|ω∈(a|b)*} （S→aSa|bSb|c） L2={anbmcmdn|n≥1, m≥1} （S→aSd|aAd A→bAc|bc） L2={anbncmdm|n≥1, m≥1} （S→AB A→aAb|ab B→cBd|cd） L3={ambmcn|m, n≥1} （A→AC A→aAb|ab C→cC|c）,28,計(jì)數(shù)問題,L3={anbncn|n≥1} CSL L3={ambmcn|m,n≥1} CFL（A→AC A→aAb|ab C→cC|c）,命題：L3不是正規(guī)集，因?yàn)闃?gòu)造不出可以識別L3的DFA。 ■ 證明：（反證） 假設(shè)L3是正規(guī)集，則可構(gòu)造n個(gè)狀態(tài)的DFA D，它接受L3； 考察D讀完ε，a，aa，.，an，分別到達(dá)S0，S1，.，Sn，共有n+1個(gè)狀態(tài)。 根據(jù)鴿巢原理，序列中至少有兩個(gè)狀態(tài)相同，設(shè)Si=Sj（ji）， 因?yàn)閍ibick ∈L3 所以存在路徑aibick。,但是D中也有路徑ajbick，矛盾。故L3不是正規(guī)集。 ■,L3={akbmcn|k，m，n≥1} （a+b+c+ ）,29,3.3.3 形式語言與自動(dòng)機(jī)簡介,定義3.8 若文法G=(N，T，P，S)的每個(gè)產(chǎn)生式α→β中，均有α∈(N∪T)*，且至少含有一個(gè)非終結(jié)符，β∈(N∪T)*，則稱G為0型文法。 對0型文法施加以下第i條限制，即得到i型文法。 1. G的任何產(chǎn)生式α→β（S→ε除外）滿足|α|≤|β|； 2. G的任何產(chǎn)生式形如A→β，其中A∈N，β∈(N∪T)*； 3. G的任何產(chǎn)生式形如A→a或者A→aB(或者A→Ba)，其中A，B∈N，a∈T。 ■,文法、語言與自動(dòng)機(jī),30,再考察L3： 3.3.3 形式語言與自動(dòng)機(jī)簡介（續(xù)）,L3={anbncn|n≥1} L3={ambmcn|m,n≥1} （A→AC A→aAb|ab C→cC|c） L3={akbmcn|k，m，n≥1} （a+b+c+ ）,例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),句子akbkck 的推導(dǎo)： S =.= ak-1S(BC)k-1 (1) = ak(BC)k (2) =.= akBkCk (3) = akbBk-1Ck (4) =.= akbkCk (5) = akbkcCk-1 (6) =.= akbkck (7),結(jié)論：CSG、CFG、正規(guī)式能力遞減（看教材） 但是：能力越強(qiáng)的文法，其文法的設(shè)計(jì)和自動(dòng)機(jī)的構(gòu)造越困難 因此：語法分析僅用到CFG（除特別指出，文法即指CFG ）,31,結(jié) 束,32,改寫二義文法：,(a) 引入一個(gè)新的非終結(jié)符，增加一個(gè)子結(jié)構(gòu)并提高一級優(yōu)先級； (b) 遞歸非終結(jié)符在終結(jié)符左邊，運(yùn)算具有左結(jié)合性，否則具有右結(jié)合性。,E → E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5）,1. 優(yōu)先級：[+] [*] [( ), -, id] 2. 結(jié)合性：左結(jié)合[+, *] 右結(jié)合[-] 無結(jié)合[id] 3. 非終結(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,問題： 如何看待( )？ 返回,