編譯原理

文法和語言Tel:7046821E-mail:1編譯原理第03章文法和語言第三章 文法和語言本章目的為語言的語法描述尋求工具工具要對程序設(shè)計語言給出精確無二義的語法描述。（嚴謹、簡潔、易讀）形式工具--形式語言抽象地定義為一個數(shù)學系統(tǒng)?！靶问健笔侵高@樣的事實：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述。2編譯原理第03章文法和語言3.1文法的直觀概念3.2符號和符號串3.3文法和語言的形式定義3.4文法的類型3.5上下文無關(guān)文法及其語法樹3.6句型分析3.7實用說明第三章文法和語言3編譯原理第03章文法和語言文法的直觀概念一個程序設(shè)計語言是一個記號系統(tǒng)，如同自然語言一樣，它的完整的定義應包括語法和語義兩個方面。所謂一個語言的語法是指一組規(guī)則，用它可以形成和產(chǎn)生一個合適的程序。目前廣泛使用的手段是上下文無關(guān)文法，即用上下文無關(guān)文法作為程序設(shè)計語言語法的描述工具。語法只是定義什么樣的符號序列是合法的，與這些符號的含義毫無關(guān)系闡明語法的一個工具是文法，這是形式語言理論的基本概念之一。示例：漢語句子的描述語言概述4編譯原理第03章文法和語言漢語句子的描述語法規(guī)則定義字符串的判斷5編譯原理第03章文法和語言語法規(guī)則定義〈句子〉∷=〈主語〉〈謂語〉〈主語〉∷=〈代詞〉｜〈名詞〉〈代詞〉∷=我｜你｜他〈名詞〉∷=王明｜大學生｜工人｜英語〈謂語〉∷=〈動詞〉〈直接賓語〉〈動詞〉∷=是｜學習〈直接賓語〉∷=〈代詞〉｜〈名詞〉6編譯原理第03章文法和語言字符串的判斷有了一組規(guī)則以后，按照如下方式用它們導出句子：開始去找∷=左端的帶有〈句子〉的規(guī)則并把它由∷=右端的符號串代替，這個動作表示成：〈句子〉

〈主語〉〈謂語〉，然后在得到的串〈主語〉〈謂語〉中，選取〈主語〉或〈謂語〉，再用相應規(guī)則的∷=右端代替之。比如，選取了〈主語〉，并采用規(guī)則〈主語〉∷=〈代詞〉，那么得到：〈主語〉〈謂語〉

〈代詞〉〈謂語〉，重復做下去。句子：“我是大學生”的全部動作過程是：〈句子〉

〈主語〉〈謂語〉

〈代詞〉〈謂語〉

我〈謂語〉

我〈動詞〉〈直接賓語〉

我是〈直接賓語〉

我是〈名詞〉

我是大學生7編譯原理第03章文法和語言字符串的判斷“我是大學生”的構(gòu)成符合上述規(guī)則，而“我大學生是”不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中一種描述元語言稱為文法。8編譯原理第03章文法和語言符號和符號串定義：符號：可以相互區(qū)別的記號（元素）。字母表（）：符號（元素）的非空有窮集合。符號串：由字母表

中的符號組成的任何有窮序列稱為該字母表上的符號串。1.空符號串ε(沒有符號的符號串)是

上的符號串2.若x是

上的符號串,a是

的元素,則xa是

上的符號串3.

y是

上的符號串,當且僅當它可以由1和2導出。例如：Σ={a,b}ε,a,b,aa,ab,aabba…都是

上的符號串符號串的運算9編譯原理第03章文法和語言符號串的運算既然將語言定義為一個集合，那么有關(guān)集合的運算也適合語言。即：設(shè)L是（∑上的）一個語言,M是（∑上的）一個語言，則語言L和M的并，交，差，補是一個語言。符號串的頭、尾、子串符號串的長度符號串的連接符號串的方冪符號串的集合10編譯原理第03章文法和語言符號串的頭、尾、子串符號串s的頭（前綴）：移走符號串s尾部的零個或多于零個符號得到的符號串。如：b是符號串banana的一個前綴.符號串s的尾（后綴）：刪去符號串s頭部的零個或多于零個符號得到的符號串。如:nana是符號串banana的一個后綴.符號串s的子串：從s中刪去一個前綴和一個后綴得到的符號串。如:ana是符號串banana的一個子串.對于每個符號串s，s和ε兩者都是符號串s的前綴，后綴和子串。符號串s的真前綴，真后綴，真子串：任何非空符號串x,相應地，是s的前綴，后綴或子串，并且s

x。11編譯原理第03章文法和語言符號串中符號的個數(shù)。符號串s的長度記為|s|。ε的長度為0符號串的長度12編譯原理第03章文法和語言符號串的連接設(shè)x、y是符號串，則x、y的連接是把y的符號寫在x的符號之后得到的符號串xy如x=ab,y=cd則xy=abcd有εa=aε13編譯原理第03章文法和語言符號串的方冪方冪：設(shè)x是符號串，把x自身連接n次得到的符號串z，即z=aa…aa稱為符號串x的方冪。寫作z=an示例：a1=a,a2=aaa0=ε14編譯原理第03章文法和語言符號串集合若集合A中所有元素都是某字母表

上的符號串，則稱A為字母表

上的符號串集合。兩個符號串集合A和B的乘積定義為：AB=xy|xA且yB若集合A=ab,cdeB=0,1，則AB=ab1,ab0,cde0,cde1使用*表示上的所有有窮長符號串（包括ε）組成的集合。Σ*稱為Σ的閉包。

上的除ε外的所有符號串組成的集合記為

+。

Σ+稱為Σ的正閉包。Σ*=Σ0∪Σ1∪Σ2∪?∪Σn?Σ+=Σ1∪Σ2∪?∪Σn?Σ*={ε}∪Σ+Σ+=ΣΣ*=Σ*Σ15編譯原理第03章文法和語言文法和語言的形式定義文法和語言的形式定義文法的定義推導的定義句型（子）的定義語言的定義文法等價的定義16編譯原理第03章文法和語言語言概述語言是由句子組成的集合，是由一組符號所構(gòu)成的集合。漢語--所有符合漢語語法的句子的全體英語--所有符合英語語法的句子的全體每個句子構(gòu)成的規(guī)律語言研究每個句子的含義每個句子和使用者的關(guān)系每個程序構(gòu)成的規(guī)律研究程序設(shè)計語言每個程序的含義每個程序和使用者的關(guān)系語法Syntax

語言研究的三個方面語義Semantics

語用Pragmatics17編譯原理第03章文法和語言程序設(shè)計語言研究程序設(shè)計語言每個程序構(gòu)成的規(guī)律每個程序的含義每個程序和使用者的關(guān)系語言研究的三個方面語法Syntax

語義Semantics

語用Pragmatics18編譯原理第03章文法和語言

語言研究的三個方面語法--表示構(gòu)成語言句子的各個記號之間的組合規(guī)律語義--表示各個記號的特定含義。（各個記號和記號所表示的對象之間的關(guān)系）語用--表示在各個記號所出現(xiàn)的行為中，它們的來源、使用和影響。每種語言具有兩個可識別的特性，即語言的形式和該形式相關(guān)聯(lián)的意義。語言的實例若在語法上是正確的，其相關(guān)聯(lián)的意義可以從兩個觀點來看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗到的意義。這兩個意義并非總是一樣的，前者稱為語言的語義，后者是其語用意義。幽默、雙關(guān)語和謎語就是利用這兩方面意義間的差異。19編譯原理第03章文法和語言文法的定義文法G定義為四元組(VN，VT，P，S)其中VN為非終結(jié)符號(或語法實體，或變量)集；VT為終結(jié)符號集；P為產(chǎn)生式(也稱規(guī)則)的集合；VN，VT和P是非空有窮集。S稱作識別符號或開始符號，它是一個非終結(jié)符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。

VN和VT不含公共的元素，即VN∩

VT=φ

通常用V表示VN∪

VT

，稱為文法G的字母表或字匯表。規(guī)則，也稱重寫規(guī)則、產(chǎn)生式或生成式，是形如α→β或α∷=β的(α，β)有序?qū)?，其中α是字母表V的正閉包V+中的一個符號，β是V*中的一個符號。α稱為規(guī)則的左部，β稱作規(guī)則的右部。示例：例3.1例3.220編譯原理第03章文法和語言例3.1文法G=（VN，VT，P，S），VN={S},VT={0,1}，P={S→0S1,S→01}。這里，非終結(jié)符集中只含一個元素S；終結(jié)符集由兩個元素0和1組成；有兩條產(chǎn)生式；開始符號是S。21編譯原理第03章文法和語言例3.2文法G=(VN，VT，P，S)其中VN={標識符，字母，數(shù)字}VT={a,b,c,…，x,y,z,0,1,…，9}P={〈標識符〉→〈字母〉

〈標識符〉→〈標識符〉〈字母〉

〈標識符〉→〈標識符〉〈數(shù)字〉

〈字母〉→a

〈字母〉→b

…

〈字母〉→z

〈數(shù)字〉→0

〈數(shù)字〉→1

…

〈數(shù)字〉→9}

S=〈標識符〉

這里，使用尖括號"〈"和"〉"括起非終結(jié)符。22編譯原理第03章文法和語言推導的定義直接推導“”：如α→β是文法G=(Vn，VT，P，S)的規(guī)則(或說是P中的一產(chǎn)生式)，γ和δ是V*中的任意符號，若有符號串v，w滿足：v=γαδ，w=γβδ

則說v(應用規(guī)則α→β)直接產(chǎn)生w，或者說，w是v的直接推導，也可以說，w直接歸約到v，記作vw。如果存在直接推導的序列：示例：直接推導多步推導23編譯原理第03章文法和語言直接推導的示例對于例3.1的文法G，可以給出直接推導的一些例子如下：v=0S1,w=0011，直接推導：0S1

0011，使用的規(guī)則：S→01，這里γ=0，δ=1。v=S,w=0S1，直接推導：S

0S1使用的規(guī)則：S→0S1，這里γ=ε，δ=εv=0S1,w=00S11，直接推導：0S1

00S11，使用的規(guī)則：S→0S1，這里γ=0，δ=1。對于例3.2的文法G，直接推導的例子有：v=〈標識符〉，w=〈標識符〉〈字母〉，直接推導：〈標識符〉〈標識符〉〈字母〉，使用的規(guī)則：〈標識符〉→〈標識符〉〈字母〉，這里γ=δ=εv=〈標識符〉〈字母〉〈數(shù)字〉，w=〈字母〉〈字母〉〈數(shù)字〉，直接推導：〈標識符〉〈字母〉〈數(shù)字〉〈字母〉〈字母〉〈數(shù)字〉，使用的規(guī)則：〈標識符〉→〈字母〉。這里γ=ε，δ〈字母〉〈數(shù)字〉。v=abc〈數(shù)字〉，w=abc5，直接推導：abc〈數(shù)字〉abc5,使用的規(guī)則：〈數(shù)字〉→5，這里γ=abc,δ=ε。24編譯原理第03章文法和語言多步推導的示例對例3.1的文法，存在直接推導序列v=0S1

00S11

000S111

00001111=w，即0S100001111，也可記作0S100001111對例3.2的文法，存在直接推導序列v=〈標識符〉

〈標識符〉〈數(shù)字〉

〈字母〉〈數(shù)字〉

x〈數(shù)字〉

x1=w，即<標識符>x1，也可記作<標識符>x1。25編譯原理第03章文法和語言句型(子)的定義設(shè)G[S]是一文法，如果符號串x是從識別符號推導出來的，即有Sx，則稱x是文法G[S]的句型。若x僅由終結(jié)符號組成，即Sx，x∈VT*，則稱x為G[S]的句子。例：S，0S1，000111都是例3.1的文法G的句型，其中000111是G的句子?！礃俗R符〉〈字母〉，〈字母〉〈數(shù)字〉，a1等都是例3.2文法G的句型，其中a1是G的句子。26編譯原理第03章文法和語言語言的定義文法G所產(chǎn)生的語言定義為集合{x|Sx，其中S為文法識別符號，且x∈VT*}。可用L(G)表示該集合。從定義可以看出兩點：第一，符號串x可從識別符號推出，也即x是句型。第二，x僅由終結(jié)符號組成，即x是文法G的句子。也就是說，文法描述的語言是該文法一切句子的集合。例：例3.1G：S→0S1，S→01L(G)={0n1n|n≥1}例3.327編譯原理第03章文法和語言例3.3設(shè)G=(VN，VT，P，S)，VN={S,B,E}，VT={a,b,e}，P由下列產(chǎn)生式組成：(1)S→aSBE(2)S→aBE(3)EB→BE(4)aB→ab(5)bB→bb(6)bE→be(7)eE→ee則L（G）={anbnen|n≥1}

28編譯原理第03章文法和語言文法的等價若L（G1）=L（G2），則稱文法G1和G2是等價的。示例：文法G1[A]：A→0RA→01R→A1與G2[S]：S→0S1S→01等價。29編譯原理第03章文法和語言文法的類型喬姆斯基分類示例：例3.4例3.5喬姆斯基分類文法之間關(guān)系對應于喬姆斯基分類文法的語言文法和語言之間的關(guān)系30編譯原理第03章文法和語言喬姆斯基對文法的分類通過對產(chǎn)生式施加不同的限制，Chomsky（喬姆斯基）將文法分為四種類型：0型文法：對文法G=(VN，VT，P，S)的任一產(chǎn)生式α→β，都有α∈(VN∪VT)*且至少含有一個非終結(jié)符，β∈(VN∪VT)*。1型文法（上下文有關(guān)文法）：對文法G=(VN，VT，P，S)的任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅S→ε除外。2型文法（上下文無關(guān)文法）：對文法G=(VN，VT，P，S)的任一產(chǎn)生式α→β，都有α∈VN

，β∈(VN∪VT)*。3型文法（正規(guī)文法）：設(shè)G=(VN，VT，P，S)，若P中的每一個產(chǎn)生式的形式都是A→aB或A→a，其中A和B都是非終結(jié)符，a是終結(jié)符。3型文法G=(VN，VT，P，S)的P中的規(guī)則有兩種形式：一種是前面定義的形式，即：A→aB或A→a其中A，B∈VN

，a∈VT*，另一種形式是：A→Ba或A→a，前者稱為右線性文法，后者稱為左線性文法。正規(guī)文法所描述的是VT*上的正規(guī)集。31編譯原理第03章文法和語言例3.4G=({S,A,B},{a,b},P,S)，其中P由下列產(chǎn)生式組成：S→aBA→bAAS→bAB→bA→aB→bSA→aSB→aBB或?qū)改寫為：S→aB|bAA→bA|aA→a|A→aSB→bS|B→aB|b則G是正規(guī)文法或3型文法。32編譯原理第03章文法和語言例3.5文法G=({S,A,B},{0,1},P,S)，其中P由下列產(chǎn)生式組成：S→0AA→1BS→1BB→1BS→0B→1A→0AB→0A→0S或?qū)改寫為：S→0A|1B|0A→0S|1B|0AB→1B|1|0則G是正規(guī)文法或3型文法。33編譯原理第03章文法和語言喬姆斯基分類文法之間關(guān)系2型文法1型文法0型文法四種文法之間的逐級“包含”關(guān)系3型文法34編譯原理第03章文法和語言對應喬姆斯基分類文法的語言0型文法產(chǎn)生的語言稱為0型語言。1型文法或上下文有關(guān)文法（CSG

）產(chǎn)生的語言稱為1型語言或上下文有關(guān)語言（CSL）。2型文法或上下文無關(guān)文法（CFG

）產(chǎn)生的語言稱為2型語言或上下文無關(guān)語言（CFL）。

3型文法或正則（正規(guī)）文法（RG）產(chǎn)生的語言稱為3型語言正則（正規(guī)）語言（RL）。

35編譯原理第03章文法和語言文法和語言之間的關(guān)系四種文法之間的關(guān)系是將產(chǎn)生式做進一步限制而定義的。語言之間的關(guān)系依次：有不是上下文有關(guān)語言的0型語言，有不是上下文無關(guān)語言的1型語言，有不是正則語言的上下文無關(guān)語言。 36編譯原理第03章文法和語言上下文無關(guān)文法及其語法樹語法樹句型能夠構(gòu)造關(guān)聯(lián)語法樹的條件示例：例3.7最左（右）推導二義性文法判斷依據(jù)示例：例3.8二義性文法與二義性語言的區(qū)別37編譯原理第03章文法和語言句型能夠構(gòu)造關(guān)聯(lián)語法樹的條件給定文法G=(VN，VT，P，S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導樹)。這棵樹滿足下列4個條件：①每個結(jié)點都有一個標記，此標記是V的一個符號。②根的標記是S。③若一結(jié)點n至少有一個它自己除外的子孫（子結(jié)點），并且有標記A，則A肯定在VN中。④如果結(jié)點n的直接子孫，從左到右的次序是結(jié)點n1，n2，…，nk，其標記分別為A1，A2，…，Ak，那么A→A1A2…Ak一定是P中的一個產(chǎn)生式。38編譯原理第03章文法和語言例3.7G=(｛S,A｝,｛a,b｝,P,S)，其中P為：

①S→aAS

②A→SbA

③A→SS

④S→a

⑤A→ba右圖是G（aabbaa）的一棵推導樹。39編譯原理第03章文法和語言最左（右）推導如果在推導的任何一步α

β，其中α，β是句型，都是對α中的最左(最右)非終結(jié)符進行替換，則稱這種推導為最左(最右)推導。在形式語言中，最右推導常被稱為規(guī)范推導。由規(guī)范推導所得的句型稱為規(guī)范句型。最左推導示例S

aAS

aSbAS

aabAS

aabbaS

aabbaa最右推導示例S

aAS

aAa

aSbAa

aSbbaa

aabbaa40編譯原理第03章文法和語言二義文法的判斷依據(jù)若一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。

或者，若一個文法存在某個句子有兩個不同的最左（右）推導，則稱這個文法是二義的。如果產(chǎn)生上下文無關(guān)語言的每一個文法都是二義的，則說此語言是先天二義的。判定任給的一個上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個先天二義的上下文無關(guān)語言，這兩個問題是遞歸不可解的，即，不存在一個算法，它能在有限步驟內(nèi)，確切判定任給的一個文法是否為二義的。我們所能做的事是為無二義性尋找一組充分條件(當然它們未必都是必要的)。41編譯原理第03章文法和語言例3.8文法G=(｛E｝,｛+,*,i,(,)｝,P,E)其中P={

E→i

E→E+E

E→E*E

E→(E)}是二義性的，假若規(guī)定了運算符“+”與“*”的優(yōu)先順序和結(jié)合規(guī)則，即按慣例，讓“*”的優(yōu)先性高于“+”，且它們都服從左結(jié)合，那么就可以構(gòu)造出一個無二義文法。定義表達式的無二義文法G[E]：

E→T|E+T

T→F|T*F

F→(E)|i

它和上述文法產(chǎn)生的語言是相同的。即它們是等價的。42編譯原理第03章文法和語言二義性文法與二義性語言的區(qū)別文法的二義性和語言的二義性是兩個不同的概念。因為可能有兩個不同的文法G和G′，其中G是二義的，但是卻有L(G)=L(G′)，也就是說，這兩個文法所產(chǎn)生的語言是相同的。43編譯原理第03章文法和語言句型的分析句型分析是識別一個輸入符號串是否為語法上正確的程序的過程。在語言的編譯實現(xiàn)中，把完成句型分析的程序稱為分析程序或識別程序，分析算法又稱識別算法。從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號，直到分析結(jié)束。句型的分析算法分類句型的分析算法反映語法樹的構(gòu)造過程句型分析的有關(guān)定義句型分析的有關(guān)問題44編譯原理第03章文法和語言句型的分析算法分類自上而下分析法：是從文法的開始符號出發(fā)，反復使用各種產(chǎn)生式，尋找“匹配”于輸入符號串的推導。示例：例3.9自下而上分析法：從輸入符號串開始，逐步進行“歸約”，直至歸約到文法的開始符號。示例45編譯原理第03章文法和語言兩種方法反映語法樹的構(gòu)造過程自上而下方法：自上而下方法是從文法符號開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的末端結(jié)點符號串正好是輸入符號串。自下而上方法：自下而上方法是從輸入符號串開始，以它做為語法樹的末端結(jié)點符號串，自底向上地構(gòu)造語法樹。46編譯原理第03章文法和語言例3.9：自上而下分析例：考慮文法G[S]；

①S→cAd

②A→ab

③A→a

識別輸入串w=cabd是否該文法的句子。推導過程：S

cAd

cabd47編譯原理第03章文法和語言示例：自下而上分析例：考慮文法G[S]；

①S→cAd

②A→ab

③A→a

識別輸入串w=cabd是否該文法的句子。 S

A

A

cabd

ca

bd

ca

b

d

規(guī)約過程構(gòu)造的推導：cAd

cabdS

cAd48編譯原理第03章文法和語言句型分析的有關(guān)定義令G是一文法，S是文法的開始符號，αβδ是文法G的一個句型。如果有：SαAδ且Aβ則稱β是句型αβδ相對于非終結(jié)符A的短語。特別，如有A

β則稱β是句型αβδ相對于規(guī)則A→β的直接短語(也稱簡單短語)。一個句型的最左直接短語稱為該句型的句柄。示例從句型的推導樹中查找方法49編譯原理第03章文法和語言示例文法G[E]的一個句型i*i+i。為了敘述方便，將句型改寫為i1*i2+i3。因為有：EF*i2+i3

且F

i1則稱i1是句型i1*i2+i3的相對于非終結(jié)符F的短語，也是相對于規(guī)則F→i的直接短語。又有：Ei1*F+i3

且F

i2則i2是句型i1*i2+i3的相對于F的短語，也是相對于規(guī)則F→i的直接短語，還有：Ei1*i2+F且F

i3則i3也是句型i1*i2+i3的相對于F的短語，也是相對于規(guī)則F→i的直接短語。ET*i2+i3，且Ti1則i1是句型i*i2+i3的相對于T的短語。Ei1*i2+T且Ti3則i3是句型i1*i2+i3的相對于T的短語。EE+i3

且Ei1*i2則i1*i2是句型i1*i2+i3的相對于E的短語。EE且E

i1*i2+i3則i1*i2+i3是句型i1*i2+i3相對于E的短語。即i1，i2，i3，i1*i2和i1*i2+i3都是句型i1*i2+i3的短語，而且i1，i2，i3均為直接短語，其中i1是最左直接短語，即句柄。雖然i2+i3是句型i1*i2+i3的一部分，并不是它的短語，因為盡管有Ei2+i3，但不存在從文法開始符號E到i1*E的推導。50編譯原理第03章文法和語言從句型的推導樹中查找方法從句型的推導樹上很容易找出句型的短語和直接短語。設(shè)A是句型αβδ的某一子樹的根，其中β是形成此子樹的末端結(jié)點的符號串，則其中β是句型αβδ的相對于A的短語。若這個子樹只有一層分支，則β是句型αβδ的直接短語。示例51編譯原理第03章文法和語言示例：推導樹中找短語52編譯原理第03章文法和語言句型分析的有關(guān)問題在自上而下的分析方法中如何選擇使用哪個產(chǎn)生式進行推導？假定要被代換的最左非終結(jié)符號是B，且有n條規(guī)則：B→A1|A2|…|An，那么如何確定用哪個右部去替代B？在自下而上的分析方法中如何識別可歸約的串？在分析程序工作的每一步，都是從當前串中選擇一個子串，將它歸約到某個非終結(jié)符號，該子串稱為“可歸約串”。存在確定和不確定分析。53編譯原理第03章文法和語言實用說明

有關(guān)文法的實用限制上下文無關(guān)文法中的ε規(guī)則無用符號和無用產(chǎn)生式的消除ε-產(chǎn)生式的消除單產(chǎn)生式的消除54編譯原理第03章文法和語言有關(guān)文法的實用限制在實用中，我們將限制文法中不得含有有害規(guī)則和多余規(guī)則：有害規(guī)則，是指形為U→U的產(chǎn)生式。它對描述語言顯然是沒有必要的。說它有害，是說它只會引起文法的二義性。多余規(guī)則，是指文法中那些連一個句子的推導都用不到的規(guī)則，這類規(guī)則在文法中以兩種形式出現(xiàn)。一種是文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，所以任何句子的推導中不可能用到它。對文法G=(VN，VT，P，S)來說，為了保證其任一非終結(jié)符A在句子推導中出現(xiàn)，必須滿足如下兩個條件：①A必須在某句型中出現(xiàn)。即有SαAβ，其中α，β屬于(VT∪VN)*

。②必須能夠從A推出終結(jié)符號串t來。即At，其中t∈VT。若程序設(shè)計語言的文法包含有多余規(guī)則時，其中必定有錯誤存在，因此檢查文法是否包含多余規(guī)則是很有必要的。55編譯原理第03章文法和語言上下文無關(guān)文法中的ε規(guī)則上下文無關(guān)文法中某些規(guī)則可具有形式A→ε，稱這種規(guī)則為ε規(guī)則。ε規(guī)則會使得有關(guān)文法的一些討論和證明變得復雜,有時會限制這種規(guī)則的出現(xiàn)。上下文無關(guān)文法的相關(guān)定理定理3.1定理3.256編譯原理第03章文法和語言定理3.1若L是由文法G=(VN，VT，P，S)產(chǎn)生的語言，P中的每一個產(chǎn)生式的形式均為A→α，其中A∈VN，α∈(VN∪VT)*(即α可能為ε)，則L能由這樣一種文法產(chǎn)生：每一個產(chǎn)生式或者為A→β形式，其中A∈VN，β

∈(VN∪VT)+(即β≠ε)，或者S→ε且S不出現(xiàn)在任何產(chǎn)生式右邊。57編譯原理第03章文法和語言定理3.2如果G=(VN，VT，P，S)是一個上下文有關(guān)文法，則存在另一個上下文有關(guān)文法G1，它所產(chǎn)生的語言與G產(chǎn)生的相同，即L(G)=L(G1)，其中G1的開始符號不出現(xiàn)在G1的任何產(chǎn)生式的右邊。若G為上下文無關(guān)文法或正規(guī)文法，類似結(jié)論成立。58編譯原理第03章文法和語言無用符號和無用產(chǎn)生式的消除定義：設(shè)G=(VN，VT，P，S)是一文法，我們說G中的一個符號x(VN∪VT)是有用的指x至少出現(xiàn)在一個句子的推導過程中。即x必須同時滿足以下兩個條件：存在α、β

V*，有S?*∈αxβ存在w

VT*,αxβ?*w否則就說x是無用的。如果一個產(chǎn)生式的左部或右部含有無用符號，則此產(chǎn)生式稱之為無用產(chǎn)生式。消除算法算法1算法2示例59編譯原理第03章文法和語言算法11、分別置VN(1)和P(1)

為

；2、對于P中的每一產(chǎn)生式A→

，若

VT*，則將A置于VN(1)

中；3、對于P中的每一產(chǎn)生式A→x1x2…xm若每個xi都屬于VN(1)

或VT

，則將A置于VN(1)

；4、重復步驟3，直到VN(1)不再增大為止；5、對于P中的每一產(chǎn)生式B→y1y2…yn

，若B及每一個yi都屬于VN(1)∪VT

，則將此產(chǎn)生式B→y1y2…yn置于P(1)。60編譯原理第03章文法和語言算法21、分別置VN’、VT’和P’

為

；2、將文法的開始符號S置入VN’中；3、對于G(1)中任何形如A→x1|x2|

…|

xm的產(chǎn)生式，若A

VN’，則將符號串x1，x2，

…，

xm中的全部非終結(jié)符號置于VN’中，而將其中的全部終結(jié)符號置于VT’中；4、重復步驟3，直到VN’和VT’都不再增大為止；5、將P中左右部僅含VN’∪VT’中符號的所有產(chǎn)生式置P’

。61編譯原理第03章文法和語言示例文法的定義已知文法G=（{S,U,V,W}，{a,b,c}，P，S），產(chǎn)生式P的組成如下：S→aSS→WS→UU→aV→bVV→acW→aW執(zhí)行算法1執(zhí)行算法262編譯原理第03章文法和語言執(zhí)行算法1第一步，由于產(chǎn)生式U→a、V→ac的右部均為終結(jié)符號串，故置VN(1)

={U，V}；第二步，對于產(chǎn)生式S→U，由于U

VN(1)

，故將S置于中，所以VN(1)

={S，U，V}；于是得到以下文法G1：G1=（{S,U,V},{a,b,c},P(1),S），其中P(1)由如下產(chǎn)生式組成：S→aSS→UU→aV→bVV→ac63編譯原理第03章文法和語言執(zhí)行算法2第一步，置VN’={S}；第二步，因為G1中含有產(chǎn)生式S→U、U→a，故應將U、a分別置于，即VN’={S，U}VT’={a};因此得到等價的且不含無用符號和無用產(chǎn)生式的文法為G2=（{S，U}，{a}，P’，S），其中，P’由如下產(chǎn)生式組成：S→aSS→UU→a64編譯原理第03章文法和語言ε-產(chǎn)生式的消除算法3算法4（ε不屬于文法所產(chǎn)生的語言）算法5（ε屬于文法所產(chǎn)生的語言）示例：ε不屬于文法所產(chǎn)生的語言ε屬于文法所產(chǎn)生的語言65編譯原理第03章文法和語言算法31、作集合W1={A|產(chǎn)生式A→εP}；2、作集合序列

WK+1=WKU{B|B→

P,且

WK+}；K

1

并使WK+1

收斂；令W=WK+1,則對于每一個AW，有A?*ε。對于上述W，如果G中不含有可能導出ε的符號，則W=

。66編譯原理第03章文法和語言算法41、利用算法3，可將分