第2章文法和語言

第2章文法和語言

隨著高級語言的出現(xiàn)和使用，必然面臨編譯理論的研究和編譯程序的設(shè)計。編譯過程是一個十分復(fù)雜的信息加工過程，其加工對象是用高級語言編寫的程序。1.為了順利完成編譯工作，要解決的問題是：

如何確切地描述或定義一種程序設(shè)計語言？如何識別和分析這些語言？2.在20世紀(jì)50年代，N.choumsky首先對語言的描述進(jìn)行探討。提出了用來描述語言的數(shù)學(xué)系統(tǒng)；定義了四類性質(zhì)不同的文法和語言（0型文法、1型文法、2型文法和3型文法）。主要內(nèi)容§

2.1語言和文法的直觀概念§

2.2符號和符號串§

2.3文法和語言的形式定義§

2.4文法的類型§

2.5上下文無關(guān)文法及其語法樹§

2.6句型的分析§

2.7有關(guān)文法中的一些說明§2.1語言和文法的直觀概念程序設(shè)計語言的定義 語言是一個記號系統(tǒng)。漢語--符合漢語語法的句子的全體英語--符合英語語法的句子的全體程序設(shè)計語言--該語言的程序的全體

程序設(shè)計語言由語法和語義定義：語法(syntax)定義:是一組規(guī)則，用它可以形成和產(chǎn)生一個合適的程序描述工具:文法作用:定義什么樣的符號序列是合法的，與符號的含義無關(guān)。語義(semantics)分類:靜態(tài)語義：一系列限定規(guī)則，確定哪些合乎語法的程序是合適的動態(tài)語義：表明程序要做什么描述工具:指稱語義,操作語義等作用:檢查類型匹配，變量作用域等文法的直觀概念如何來描述一種語言？文法是描述語言的語法（形式）結(jié)構(gòu)的形式規(guī)則。如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示如果語言是無窮的，要找出語言的有窮表示。有兩個途經(jīng)：生成方式（文法）：語言中的每個句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造識別方式（自動機(jī)）：用一個過程，當(dāng)輸入的一任意串屬于語言時，該過程經(jīng)有限次計算后就會停止并回答“是”，若不屬于，要么能停止并回答“不是”，要么永遠(yuǎn)繼續(xù)下去?！?.2符號和符號串字母表定義:元素的非空有窮集合例：∑={0?1}Α={a?b,c}元素也稱為符號，字母表也稱符號集。程序語言的字母表由字母數(shù)字和若干專用符號組成。符號串定義:由字母表中的符號組成的任何有窮序列例：

0,00,10是字母表∑={0，1}上的符號串

a,ab,aaca是Α={a，b，c}上的符號串在符號串中，符號是有順序的，順序不同,代表不同的符號串，如:ab和ba不同不含任何符號的符號串稱為空串，用ε表示

注意:{ε}并不等于空集合{}符號串長度:符號串中含有符號的個數(shù) 如: |abc|=3 |ε|=0子符號串設(shè)有非空符號串u=xvy，其中符號串則稱v為符號串u的子符號串。V≠ε例如符號串x=a+b*(c+d)，則a，a+b*，與(c+d)等都是x的子符號串，且其長度分別|a|=1，|a+b*|=4，|(c+d)|=5符號串的頭與尾如果z=xy是一個符號串，則x是z的頭，而y是z的尾。如果y非空，則x是z的固有頭；如果x非空，則y是z的固有尾。例如：字母表A={a,b,c}上的符號串x=abc,則x的頭：ε,a,ab,abc,尾:ε,c,bc,abc固有頭:ε,a,ab,固有尾:ε,c,bc符號串的運(yùn)算符號串的連接：設(shè)x、y是符號串,它們的連接是把y的符號寫在x的符號之后得到的符號串xy

例如x="ST"，y="abu"，則xy="STabu" 顯然εx=xε=x符號串的方冪：把符號串a(chǎn)自身連接n次得到的符號串a(chǎn)n=

aa…aa

例如a1=aa2=aaa0=ε符號串集合：定義:若集合A中所有元素都是某字母表上的符號串，則稱A為字母表上的符號串集合。符號串集合的乘積：符號串集合A和B的乘積定義為: AB={xy|x∈A且y∈B}，即AB是由A中的串x 和B中的串y連接而成的串xy組成的集合。 若集合A=ab,cdeB=0,1

則AB=ab0,ab1,cde0,cde1 顯然{ε}A=A{ε}=A符號串集合的方冪:設(shè)A是符號串的集合，則稱Ai為符號串集A的方冪，其中i是非負(fù)整數(shù)。具體定義如下:A0={ε}A1=A,A2=AAAK=AA......A(k個)集合的閉包閉包 集合Σ的閉包Σ*定義如下： Σ*=Σ0∪Σ1∪Σ2∪Σ3∪… 例：設(shè)有字母表Σ={0，1} 則Σ*=Σ0∪Σ1∪Σ2∪… ={ε,0,1,00,01,10,11,000,…} 即Σ*表示Σ上所有有窮長的串的集合。正閉包Σ+=Σ1∪Σ2∪Σ3∪…稱為Σ的正閉包。

+表示上的除ε外的所有用窮長串的集合Σ*=Σ0∪Σ+ Σ+=ΣΣ*=Σ*Σ 字母表上的一個語言是上符合某種規(guī)則的一些符號 串的集合，是*的一個子集。 例如：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}1.集合{ab,aabb,aaabbb,…,anbn,…}或 {w|w∈Σ*且w=anbn,n≥1}為字母表上的一個語言。集合{a,aa,aaa,…}或{w|w∈Σ*且w=an,n≥1}為字母表上的一個語言。ε是一個語言。小結(jié)1符號與字母表2符號串3符號串的運(yùn)算4符號串集合5集合的閉包6字母表的閉包§2.3文法和語言的形式定義1．文法的定義2．文法形式上的約定3．推導(dǎo)與歸約4．句型、句子、語言的定義5．文法的等價

1．文法的定義

“我是大學(xué)生”是漢語的一個句子

用::=表示的漢語句子的構(gòu)成規(guī)則：

〈句子〉∷=〈主語〉〈謂語〉 〈主語〉∷=〈代詞〉｜〈名詞〉 〈代詞〉∷=我｜你｜他 〈名詞〉∷=王明｜大學(xué)生｜工人｜英語 〈謂語〉∷=〈動詞〉〈直接賓語〉 〈動詞〉∷=是｜學(xué)習(xí) 〈直接賓語〉∷=〈代詞〉｜〈名詞〉句子“我是大學(xué)生”的推導(dǎo)過程如下：從句子出發(fā)，反復(fù)把規(guī)則中的”::=”左邊的成分替換成右邊的成分?！淳渥印?/p>

〈主語〉〈謂語〉

〈代詞〉〈謂語〉

我〈謂語〉 我〈動詞〉〈直接賓語〉

我是〈直接賓語〉

我是〈名詞〉

我是大學(xué)生關(guān)鍵思路從文法的開始符號出發(fā)，反復(fù)使用產(chǎn)生式，對非終結(jié)符進(jìn)行替換（展開），直到整個字符串中不在包含非終結(jié)符。這時，得到了這個文法的一個句子（一個程序）這個過程稱為推導(dǎo)文法的定義包括四個組成部分：一組終結(jié)符號（不能被替換的符號，單詞符號）一組非終結(jié)符號（能夠被替換為終結(jié)符號或非終結(jié)符號，語法單位）一個開始符號（從這個符號開始替換，最大語法單位-程序）一組產(chǎn)生式（替換規(guī)則，把左邊的字符串替換為右邊的字符串）文法的形式定義產(chǎn)生式（規(guī)則） 產(chǎn)生式是一個有序?qū)?α,β)，通常寫作 α→β（或α::=β）文法定義: 文法G(Grammar)定義為四元組（VN，VT，P，S） VN(Nonternimal)：非終結(jié)符集 VT(Terminal)：終結(jié)符集 P(Production)：產(chǎn)生式（規(guī)則）集合 S：開始符號或識別符號說明:V=VN∪VT，V稱為文法G的字母表P中產(chǎn)生式形如：α→β,其中α∈V+且至少含一個非終結(jié)符，β∈V*VN,VT和P是非空有窮集VN∩VT=φS是一個非終結(jié)符，且至少要在一條產(chǎn)生式的左部出現(xiàn)非終結(jié)符代表一個語言中的語法成分，如<賦值語句>，它是構(gòu)成程序的一個語法成分，這個符號本身不會在程序中出現(xiàn)，而終結(jié)符是組成程序的具體的符號。2.文法形式定義上的約定文法習(xí)慣上只將產(chǎn)生式寫出。并有如下約定：第一條產(chǎn)生式的左部是開始符號,或用G[S]表示S是開始符號用尖括號括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符G可寫成G[S]，S是開始符號希臘字母代表由終結(jié)符號和非終結(jié)符號組成的符號串α、β、γ左部相同的產(chǎn)生式A→α,A→β可以記為A→α|β， 其中“|”是“或”的意思，α,β分別稱為侯選式如：對于文法G：S→0S1可寫成G[S]：S→0S1S→01S→01例：文法G=(VN,VT,P,S) 其中：VN={S}，VT={0，1}，P={S→0S1,S→01} 開始符為S例：文法G=(VN,VT,P,S)

VN={標(biāo)識符，字母，數(shù)字}， VT={a,b,c,…x,y,z,0,1,…,9}， P={<標(biāo)識符>→<字母>， <標(biāo)識符>→<標(biāo)識符><字母> <標(biāo)識符>→<標(biāo)識符><數(shù)字>， <字母>→a,…,<字母>→z，

<數(shù)字>→0,…,<數(shù)字>→9}， S=<標(biāo)識符>例如: 文法G[S]：

S→A|SA|SD A→a|b|…|z D→0|1|…|93.推導(dǎo)(Derivation)與歸約(Reduction)直接推導(dǎo)和直接歸約： α→β是文法G的產(chǎn)生式，若有v，w滿足： v=γαδ,w=γβδ,其中γ,δ∈V* 則稱v直接推導(dǎo)出w,也稱w直接歸約到v, 記作vw直接推導(dǎo)就是用產(chǎn)生式的右部替換產(chǎn)生式的左部的過程直接歸約就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過程例文法G：S→0S1，S→01有直接推導(dǎo)： S0S1 （S→0S1） 0S100S11 （S→0S1） 00S11000S111 （S→0S1） 000S11100001111（S→01）

推導(dǎo)例題1文法G1：S->bA,A->aA|a定義了一個什么樣的語言？S=>bA=>baS=>bA=>baA=>baaS=>bA=>baA=>baaA=>baaa……S=>bA=>baA=>…=>ba…aL(G1)={ban|n>=1}L(G1)={以b開頭后跟一個或多個a的串}推導(dǎo)例題2e.g.文法產(chǎn)生的語言文法G4對句子aaabb的推導(dǎo)：S=>AB SAB

=>aAB AaA

=>aaAB AaA

=>aaaB Aa

=>aaabB BbB

=>aaabb BbA=>aB=>abA=>Ab=>abe.g.文法產(chǎn)生的語言文法G5對句子aaaabbbb的推導(dǎo)：S=>aSb SaSb =>aaSbb SaSb =>aaaSbbb SaSb =>aaaabbbb Sab直接推導(dǎo)序列和廣義推導(dǎo)直接推導(dǎo)序列：

或+若存在v=u0u1...un=w,(n>0)則稱v+w，v推導(dǎo)出w，或w歸約到v（至少有1步推導(dǎo)），這個直接推導(dǎo)序列的長度為n。廣義推導(dǎo)：或*

若有v+w或v=w，則記為v*w，v廣義推導(dǎo)出w，w廣義規(guī)約到v（可以包含0步推導(dǎo)）+*三種推導(dǎo)的比較直接推導(dǎo)（）的長度為1直接推導(dǎo)序列（+）的長度n≥1廣義推導(dǎo)（*）的長度≥0規(guī)范推導(dǎo)和規(guī)范歸約對于一文法而言，從開始符到某句型的推導(dǎo)過程可能不唯一。例如，文法G[E]中從E到i+i*i的推導(dǎo)有：(1)EE+TE+T*FT+T*FT+T*iF+T*ii+T*ii+F*ii+i*i(2)EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*Fi+i*i(3)EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i(4)……規(guī)范推導(dǎo)為了讓計算機(jī)自動地進(jìn)行推導(dǎo)，通常我們只考慮最左或最右推導(dǎo)。最左（右）推導(dǎo)：在推導(dǎo)序列的每一步直接推導(dǎo)中，被替換的總是當(dāng)前句型中最左（右）的非終結(jié)符。例如，上頁中的（2）、（3）分別是最左、最右推導(dǎo)。形式上，從符號串到符號串的推導(dǎo)序列 *xUy

xuy*總有xVT*(yVT*) 時，稱為最左（右）推導(dǎo)定義：最左（右）推導(dǎo)所得句型稱為左（右）句型；最右推導(dǎo)稱為規(guī)范推導(dǎo)；右句型稱為規(guī)范句型。

舉例例1:文法G[S]:S→ABA→A0|1BB→0|S1請給出句子101001的最左和最右推導(dǎo)。最左推導(dǎo)：SAB1BB10B

10S1

10AB1

101BB1

1010B1

101001最右推導(dǎo)：SAB

AS1AAB1

AA01

A1B01

A1001

1B1001

101001例2文法G： E→E+T|T T→T×F|F F→（E）|i句子i+i×i的推導(dǎo)過程如下：最左推導(dǎo)：

E=>E+T=>T+T=>F+T=>i+T=>i+T×F=>i+F×F =>i+i×F=>i+i×i最右推導(dǎo)：

E=>E+T=>E+T×F=>E+T×i=>E+F×i=>E+i×i =>T+i×i=>F+i×i=>i+i×i遞歸規(guī)則借助于自身來定義的規(guī)則，稱為遞歸規(guī)則。如<數(shù)字序列>::=<數(shù)字序列><數(shù)字>遞歸規(guī)則的存在，使得能用有窮個規(guī)則來定義無窮的語言。如果一個規(guī)則形如U::=…U…（或U→xUy），則該規(guī)則是遞歸的；如果規(guī)則形如U::=U…（或U→Uy），則稱左遞歸的；如果規(guī)則形如U::=…U（或U→xU），則稱右遞歸的。例：<標(biāo)識符表>::=<標(biāo)識符表>,<標(biāo)識符>（左遞歸規(guī)則）<因式>::=!<因式>（右遞歸規(guī)則）文法的遞歸性定義：對于某文法，存在U∈VN，如果U+…U...，則稱該文法遞歸于U；如果U+U…，則稱該文法左遞歸于U；如果U+…U，則稱該文法右遞歸于U。例1：C語言中：<語句>+…<語句>(文法右遞歸于<語句>)例2：U→VxV→Uy|z（都不遞歸）有U+Uxy，所以該文法是左遞歸的。注：描述程序設(shè)計語言的文法必定都是遞歸的。遞歸文法文法G[E]：

EE+T|T TT*F|F F(E)|i顯然，G1，G2都是遞歸定義的。所謂遞歸定義，指在定義一個語法成分時，直接或間接地使用了語法成分自身。遞歸文法例如，文法G1，含有遞歸非終結(jié)符<標(biāo)識符>，文法G2中的E、T是直接遞歸的，F(xiàn)是間接遞歸的：

F(E)(T)(F)注意，文法與語言之間無一一對應(yīng)的關(guān)系。一文法可唯一地確定一語言，但對一語言而言，產(chǎn)生它的文法不止一個。4．句型、句子、語言的定義句型和句子 設(shè)有文法G[S]，若符號串α是從開始符推導(dǎo)出來的,即S=>*α，則稱α是文法G的句型。若α僅由終結(jié)符組成,即S=>*

α，且α∈VT*，則稱α是文法G的句子。例文法G[S]：S→0S1，S→01 因?yàn)镾0S100S11000S11100001111 所以S,0S1,00S11,000S111,00001111都是G的句型00001111是G的句子

由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型語言的定義

由文法G生成的語言記為L(G),它是文法G的一切句子的集合,即 L(G)={x|S=>*x，且x∈VT*} 例文法G：S→0S1，S→01 S0S100S1103S13…0n-1S1n-1

0n1n L(G)={0n1n|n≥1}文法和語言的關(guān)系： 文法G生成的每個串都在L(G)中 L(G)中的每個串確實(shí)能被G生成根據(jù)文法，可以通過推導(dǎo)得到該文法相應(yīng)的語言；例：G[E]：E→E+T|T T→T×F|F F→(E)|aE

E+TT+TF+Ta+Ta+T×Fa+F×Fa+a×Fa+a×a 表示一切能用符號a，+，×，(，)構(gòu)成的算術(shù)表達(dá)式有了語言的要求，也可以為該語言設(shè)計文法例：若語言由0、1符號串組成，串中0和1的個數(shù)相同，構(gòu)造其文法為：

A→0B|1C

B→1|1A|0BB

C→0|0A|1CC5.文法的等價若L(G1)=L(G2)，則稱文法G1和G2是等價的。

例如文法 G1[A]：A→0RA→01R→A1 G2[S]：S→0S1S→01 所定義的語言都是0n1n 兩文法等價§§2.4文法的類型

Chomsky對文法中的規(guī)則施加不同限制，將文法和語言分為四大類：0型文法（PSG）0型語言或短語結(jié)構(gòu)語言1型文法（CSG）1型語言或上下文有關(guān)語言2型文法（CFG）2型語言或上下文無關(guān)語言3型文法（RG）3型語言或正則（正規(guī)）語言文法的四元組表示是由N.Chomsky于1956年描述形式語言時給出的。他還對產(chǎn)生式的形式給予不同的限制而定義了四類基本文法。0型文法:若P中任一產(chǎn)生式都有一般形式V+V*且對，不加任何限制，則稱G為0型文法（短語結(jié)構(gòu)文法，記為PSG:PhraseStructureGrammar)。由0型文法生成（或者說：定義）的語言稱為0型（遞歸可枚舉）語言。它可由圖靈（Turing）機(jī)識別。例如：SACaBCaaaCCBDBCBEaDDaADACaEEaAE就是一個0型文法，它所產(chǎn)生的語言為對于程序設(shè)計語言來，0型文法有很大的隨意性，還須加以限制1型文法和語言若一0型文法所有產(chǎn)生式具有形式1A2

12其中，1,2V*V+AVN,則稱G為1型(前后文有關(guān))文法，記為CSG(ContextSensitiveGrammar)。1型文法產(chǎn)生的語言稱為前后文有關(guān)語言CSL，它可由線性限界自動機(jī)識別。命名的由來：只有當(dāng)非終結(jié)符A的前后分別為1,2時，才能將A替換為。1型文法還有另一種定義形式：G的每個產(chǎn)生式形為且滿足： ||||,V+則G是1型文法上述兩種定義形式是等價的。即任一種形式定義的文法所產(chǎn)生的語言都可由另一種形式定義的文法產(chǎn)生注：根據(jù)定義，含有產(chǎn)生式的文法不是1型文法。由于實(shí)際需要，我們將-產(chǎn)生式作為1型文法的特例而接受之。例文法G：S|AAaABCAabCCBBCbBbbbCbccCcc因G含有-產(chǎn)生式，所以它不是一個嚴(yán)格意義下的1型文法。它所產(chǎn)生的語言為2型文法和語言若一1型文法G中所有產(chǎn)生式具有形式: A

V+ AVN

則稱G為2型(前后文無關(guān))文法，記為CFG(ContextFreeGrammar)。2型文法產(chǎn)生的語言稱為前后文無關(guān)語言CFL，它可由下推自動機(jī)識別。若允許-產(chǎn)生式存在，則CFG產(chǎn)生式形式為 A V* AVN例：G[S]=({S},{a,b},{SaSbSab},S)產(chǎn)生的語言為3型文法和語言若一2型文法G中僅含有形如 AaBAa的產(chǎn)生式，其中A,B

VN,aVT則稱G為右線性文法。類似地，若G中僅含有形如

ABaAa的產(chǎn)生式，則稱G為左線性文法。通常，把左線性文法和右線性文法都稱為3型文法（正規(guī)文法）3型文法產(chǎn)生的語言稱為3型（正規(guī)）語言，它可由有限自動機(jī)識別。正規(guī)語言可用正規(guī)表達(dá)式表示。注：若一文法即含左線性又含右線性產(chǎn)生式，則它不一定是3型文法！3型文法還可拓廣定義為ABA（

VT+）四類語言之間的關(guān)系由各類文法的定義可知，3型語言一定是2型語言，而反之不一定成立；同理，2型語言是1型的也是0型的，反之不真。若把各類語言視為語言族LK

，K=0,1,2,3則它們之間有真包含關(guān)系：四種文法之間的逐級“包含”關(guān)系2型文法1型文法3型文法0型文法§2.5上下文無關(guān)文法及其語法樹1．上下文無關(guān)文法(Context-FreeGrammar)

自然語言是上下文有關(guān)的。上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計語言的語法結(jié)構(gòu)例：算術(shù)表達(dá)式：E→i|E+E|E*E|（E） <賦值語句>→i:=E <條件語句>→if<條件>then<語句> |if<條件>then<語句>else<語句>我們更關(guān)心上下文無關(guān)文法產(chǎn)生的句子的分析2.語法樹(推導(dǎo)樹ParseTree)作用:直觀地描述上下文無關(guān)文法的句型推導(dǎo)過程。給定文法G=(VN,VT,P,S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹語法樹的概念定義：語法樹是這樣的一個語法結(jié)構(gòu)，它的結(jié)點(diǎn)由符號組成。根結(jié)點(diǎn)對應(yīng)于識別符號。只有非終結(jié)符號對應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。并且，一個結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對應(yīng)于文法中的一個規(guī)則的左部和右部。引入語法樹的意義：作為識別句子的輔助工具，語法樹可以表示句子的結(jié)構(gòu)。這一點(diǎn)對于其后的語義分析有非常重要的意義。語法樹的相關(guān)概念結(jié)點(diǎn)：每個樹的結(jié)點(diǎn)對應(yīng)于一個符號。結(jié)點(diǎn)的名字就是該符號。邊：兩個結(jié)點(diǎn)之間的連線。根結(jié)點(diǎn)：沒有邊進(jìn)入的結(jié)點(diǎn)。分支：某個結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)）子樹：語法樹的某個結(jié)點(diǎn)和它向下射出的部分末端結(jié)點(diǎn)：沒有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對于句型的語法樹中，末端結(jié)點(diǎn)可能是非終結(jié)符號。語法樹的特征給定文法G，G=(VN,VT,P,S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列特征：1、根結(jié)點(diǎn)的標(biāo)記是開始符號S；2、每個結(jié)點(diǎn)的標(biāo)記都是V中的一個符號；3、若一棵子樹的根結(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳1A2…AR，那么A::=A1A2..AR一定是P中的一條規(guī)則；4、若一標(biāo)記為A的結(jié)點(diǎn)至少有一個除它以外的子孫，則A∈VN5、若樹的所有葉結(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。從推導(dǎo)構(gòu)造語法樹方法：把識別符號做為根結(jié)點(diǎn)，對每一個直接推導(dǎo)畫一個分支，分支的名字是直接推導(dǎo)中被替換的非終結(jié)符號，直到再無分支可畫結(jié)束。例如：推導(dǎo)SABAcBdAccddabccddSBBdbaAcdc語法樹的構(gòu)造過程SABAcBdAccddabccddSSBASBBdAc（1）（2）（3）SBBdAcdcSBBdbaAcdc（5）（4）例：文法G：E→E+T|T T→T×F|F F→（E）|i 句型T+T×F的推導(dǎo)過程與語法樹TFT×E=>E+TEET+EET+TFT×E=>E+T=>E+T×F=>T+T×F=>T+T=>T+T×F從語法樹中看不出句型中的符號被替代的順序從左到右讀出葉子結(jié)點(diǎn)得到的符號串，為文法的句型。也把該語法樹稱為該句型的語法樹。從語法樹構(gòu)造推導(dǎo)方法：從分支建立直接推導(dǎo)，然后從語法樹中剪去之這個分支，直到無分支可剪。語法樹表明了在推導(dǎo)過程中使用了哪條規(guī)則和使用在哪個非終結(jié)符號上，但它并沒有表明使用規(guī)則的順序。一棵語法樹可能對應(yīng)不止一種推導(dǎo)。從語法樹構(gòu)造推導(dǎo)的過程例如文法G[S]：S::=ABA::=aAb|abB::=cBd|cd存在下面的推導(dǎo)可能：SABAcBd

(4)(3)Accddabccdd(2)(1)SAB

abBabcBd

abccdd（從后往前看）SBBdbaAcdc(1)(2)(3)(4)文法G：E→E+E|E×E|（E）|i句子i×i+i兩個不同的最左推導(dǎo)：推導(dǎo)1：E

E+EE×E+Ei×E+Ei×i+Ei×i+i推導(dǎo)2：EE×Ei×Ei×E+Ei×i+Ei×i+i3.文法的二義性(Ambiguity)文法的二義性存在這樣的文法G，其某個句子wL(G),可對應(yīng)結(jié)構(gòu)不同的語法樹，即w對應(yīng)了多個不同的最左（右）推導(dǎo)，這類文法稱為二義性文法。例如，G3[E]：EE+E|E*E|(E)|i的句型i+i*i及文法CifBthenC|ifBthenCelseC CS

的句型：ifB1

then

ifB2

thenS1

elseS2上面兩個句型均有兩個不同的語法推導(dǎo)樹（見下頁），所以，它們是二義性文法EEEEE+*iiiEEEEE+*iii

S1 S2ifB1thenCelse CifB2

thenCCCifB1

thenCS1S2ifB1thenCelseC二義性語法的例子關(guān)于二義性文法應(yīng)指出，二義性是一種常見的語法現(xiàn)象，然而，對于編譯程序而言，二義性文法是有害的。為解決二義性文法帶來的不確定性問題，通常的方法一是修改文法。二是利用附加條件。例如，i+i*i的歸約過程中，若規(guī)定*比+優(yōu)先級高，則可強(qiáng)制性地讓系統(tǒng)先按E*E進(jìn)行歸約，而不是先按E+E進(jìn)行歸約；又比如，若強(qiáng)制規(guī)定else只能和距其最近的尚未被匹配的then進(jìn)行匹配，就可解決else懸空的問題。關(guān)于二義性文法應(yīng)指出，任一前后文無關(guān)文法是否是二義性的是不可判定的。對于某個具體的文法而言，其二義性還是可判定的。存在一些判定文法是否二義性的充分條件：若一文法含有既是左遞歸又是右遞歸的文法符號，即有 A+AvAvV* 或 A+A 或 A+A及AA

則G必定是二義性的。并非所有的文法可消除二義性。即存在這樣的CFL，定義它的一切文法都是二義性的。這樣的語言稱為先天二義性語言。例如，為一先天二義性語言。CFL的先天二義性也是不可判定的。為什么要避免文法產(chǎn)生二義性？二義性的文法將給編譯程序的執(zhí)行帶來問題。當(dāng)編譯程序?qū)Χx性文法生成的句子結(jié)構(gòu)進(jìn)行語法分析時，就會產(chǎn)生兩種甚至更多種不同的理解。語法結(jié)構(gòu)上的不確定性，必將導(dǎo)致語義處理上的不確定性。因此，希望描述語言的文法是無二義性的。如何消除文法的二義性？方法二：構(gòu)造一個等價的無二義性的文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。如文法G[E]:E→iE→E+EE→E*EE→(E)將運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則加到原有文法中，則可構(gòu)造無二義性的文法G’[E]:E→T|E+TT→F|T*FF→（E）|i二義性文法的改造注意：文法的二義性性與語言二義性的區(qū)別因?yàn)榭赡苡袃蓚€不同的文法G1和G2，其中有一個是二義性的，但卻有L(G1)=L(G2)。如果產(chǎn)生某上下文無關(guān)語言的每個文法都是二義性的，則說明該語言是先天二義性的，即該語言是二義性的?！?.6 句型的分析任務(wù):句型分析就是識別一個符號串是否為某文法的句型，是某個推導(dǎo)的構(gòu)造過程。對于程序設(shè)計語言來說，句型分析就是一個識別輸入符號串是否為語法上正確的程序的過程。它是一種推導(dǎo)或語法樹的構(gòu)造過程。對于一個給定的符號串，試圖按照文法的規(guī)則構(gòu)造其對應(yīng)的推導(dǎo)，或語法樹。句型的分析算法分類自頂向下的語法分析(Top-Downparsing)自底向上的語法分析(Bottom-Upparsing)§2.6.1自頂向下的分析方法定義:

對于給定的符號串w，采用自頂向下的分析來判斷w是否為L(G[S])的句子的常見方法是：試圖建立從開始符S到w最左推導(dǎo): S*w

顯然，每步推導(dǎo)時，對應(yīng)于最左非終結(jié)符相應(yīng)的產(chǎn)生式可能會有多個，若無特殊的辦法，只能一個一個地試探。因此，推導(dǎo)過程可能是帶回溯的。

為提高效率，就應(yīng)盡量避免回溯

語法樹的構(gòu)造：將文法的開始符號作為語法樹的根，向下逐步建立語法樹，使語法樹的末端結(jié)點(diǎn)符號串正好是輸入符號串。

例文法G：S→cAd

A→ab

A→a

識別輸入串w=cabd是否為該文法的句子S推導(dǎo)過程：cAdab=>cabdS=>cAd自上而下方法的主要問題對輸入串cabd自上而下構(gòu)造語法樹的另一過程不成功，不成功的原因是選錯產(chǎn)生式A→a自上而下分析的主要問題是選擇產(chǎn)生式:假定要被代換的最左非終結(jié)符號是B，且有n條規(guī)則：B→A1|A2|…|An，那么如何確定用哪個右部去替代B？ScAda~就是從已給的符號串w出發(fā)，試圖以相反的方向?yàn)閣建立一個規(guī)范推導(dǎo)，最終得到文法的開始符。推導(dǎo)的逆過程稱作歸約，它是把當(dāng)前的符號串中的構(gòu)成文法某個產(chǎn)生式A右部的子串替換成產(chǎn)生式的左部符號A，得到一個新的符號串A。這樣的一步動作，稱為進(jìn)行了一步歸約。例如，符號串F+i*i中的F可按產(chǎn)生式TF歸約為T，從而得到新的符號串T+i*i。若從給定的符號串w出發(fā)，一步步地將其歸約，最終得到文法的開始符號，則說明w是該文法定義的一個句子。歸約成功，否則，歸約失敗。若歸約的每一步都?xì)w約的是當(dāng)前符號串中最左邊的某產(chǎn)生式的右部，則稱該歸約是規(guī)范歸約（即最左歸約）。規(guī)范歸約是規(guī)范推導(dǎo)的逆過程。關(guān)于最左（右）歸約、直接歸約、歸約等的形式定義不再贅述。2.6.2自底向上的語法分析例符號串i+i*i的歸約過程由上表可以看出，歸約過程是最左歸約，它恰好是規(guī)范推導(dǎo)的逆過程。這正是把最左歸約定義為規(guī)范歸約的原因。例文法G：S→cAd

A→ab

A→a

識別輸入串w=cabd是否為該文法的句子cabd歸約過程：用“|-”表示歸約，下劃線部分為被歸約符號cabd|-cAd|-SAS關(guān)于歸約的一點(diǎn)說明注意，前面例子中歸約的第五步中，當(dāng)前的符號串為E+T*i，除了可將i歸約成F外，還可將E+T或T歸約成E，分別得到符號串E*i和E+E*i。但是，若真按這兩個方案進(jìn)行歸約，則當(dāng)我們把其歸約成E*E或E+E*E時，就再也歸約不下去了。這就告訴我們在第五步時，唯一正確的歸約是將i歸約為F，也就是說，i是唯一可被歸約的最左子串。對輸入串cabd的兩種歸約過程 （1）cabd|-cAd|-S歸約到開始符 （2）cabd|-cAbd不能歸約到開始符那么，對于規(guī)范歸約的每一步，如何確定符號串中的當(dāng)前應(yīng)被歸約的最左子串呢？短語和句柄問題:在自底向上(簡記為)的語法分析中,對于每一步直接歸約,應(yīng)如何正確地確定當(dāng)前句型中應(yīng)被歸約的最左子串?考慮文法G2[E]的句型=E+T*F+i,從開始符E推導(dǎo)出的語法樹見右圖該樹中含有若干子樹,如T(2)為根的子樹對應(yīng)的葉結(jié)點(diǎn)為T(3)*F(3),由于它是一直接子樹,文法中必有產(chǎn)生式T->T*F;因此,稱T*F是句型相對于產(chǎn)生式T->T*F的直接短語.同理,F(1)對應(yīng)的直接短語為i.以E(1)為根的子樹相應(yīng)的葉結(jié)點(diǎn)為E(2)+T(3)*F(3),所以,稱為句型相對于非終結(jié)符E的短語.同理,i是相對于T(1)的短語EE(1) +T(1)E(2)+T(2)T(3)*F(3)F(1)i短語、直接短語及句柄的定義定義: 設(shè)αβδ是文法G[S]中的一個句型，如果有S=>*αAδ且A=>+β，則稱β是句型αβδ相對于非終結(jié)符A的短語 特別的如有A=>β，則稱β是句型αβδ相對于規(guī)則A→β的(直接短語)簡單短語。 一個句型的最左簡單短語稱為該句型的句柄(Handle)。句柄就是“可歸約串”例如，對句型=E+T*F+i，由定義，有：(1)E*E+T+i(=E+,A=T,=+i)及TT*F(=),故T*F是相對于產(chǎn)生式T->T*F的直接短語;(2)E*E+T*F+FFi,i是相對于產(chǎn)生式F->i的直接短語;(3)E*E+i與E+E+T*F,E+T*F是相對于非終結(jié)符E的短語;(4)E*E及E*E+T*F+i(=),是相對于E的短語注:由定義可知,直接短語也是短語,但短語不一定是直接短語.歸約時被替換子串的選擇從句型=E+T*F+i的語法樹可知,E+T絕不是它的一個直接短語,因?yàn)殡m然E->E+T是G2的一個產(chǎn)生式,但不存在從E到E*F+i的推導(dǎo),所以,當(dāng)判斷一符串是否為某一句型的短語時,須檢查定義的兩個條件是否同時滿足.采用分析時,每步歸約就是將一個產(chǎn)生式右部替換其左部,也就是把該句型的語法樹中的一棵直接子樹的末端結(jié)點(diǎn)剪去.即每次歸約的符號串必是當(dāng)前句型的一個直接短語.但是,對一句型而言,其直接短語可能不唯一.為了讓分析能夠機(jī)械地進(jìn)行,我們只考慮規(guī)范歸約(最左歸約),即歸約過程替換的是歸左直接短語.我們以L(G2)的句子i+i*i+i為例,給出其最右推導(dǎo)(規(guī)范歸約的逆過程),來說明每次規(guī)范歸約的子符號串用語法樹求短語、句柄短語：（子）樹的末端結(jié)點(diǎn)形成的符號串是相對于(子)樹根的短語。簡單短語（直接短語）：簡單子樹的末端結(jié)點(diǎn)形成的符號串是相對于簡單子樹根的簡單短語。句柄：最左簡單子樹的末端結(jié)點(diǎn)形成的符號串是句柄。例：對于文法G[S]：S::=ABA::=Aa|bBB::=a|Sb

求句型baSb的全部短語、直接短語和句柄？baSb為句型baSb的相對于S的短語；ba為句型baSb的相對于A的短語；a為句型baSb的相對于B的短語,且為直接短語和句柄；Sb為句型baSb的相對于B的短語,且為直接短語。SSABbabSB例：文法G[E]:E→E+T|T T→T×F|F F→（E）|i的一個句型是T×F+i，相應(yīng)的語法樹見右圖：EET+TTF×Fi

.因?yàn)镋=>*T+i且T=>T×F，所以T×F

是句型相對于T的短語，且是相對 于T→T×F的直接短語.因?yàn)镋=>*T×F+F且F=>i，所以i是句 型相對于F的短語，且是相對于F→i 的直接短語.因?yàn)镋=>*E且E=>+T×F+i，所以 T×F+i是句型相對于E的短語

.T×F是最左直接短語，即句柄

文法G[E]: E→E+T|T T→T×F|F F→（E）|i的一個句型是T×F+iEET+TTF×Fi雖然F+i是句型T×F+i的一部分，但不是短語，因?yàn)楸M管有E=>+F+i，但是不存在從文法開始符E=>*T×E的推導(dǎo)短語與語法樹 從句型的語法樹上很容易找出句型的短語語法樹中每棵子樹的末端結(jié)點(diǎn)構(gòu)成相對于子樹根的短語 例：文法G[E]的句型T×F+i語法樹：EET+TTF×Fi五棵子樹對應(yīng)三個短語T×F，i，T×F+i兩層子樹的末端結(jié)點(diǎn)構(gòu)成直接短語兩棵兩層子樹對應(yīng)兩個直接短語： T×F，i位于最左邊的兩層子樹的末端結(jié)點(diǎn)構(gòu)成句柄： T×FEE+TE+FE+iE+T+iE+T*F+iE+T*i+iE+F*i+iE+i*i+iT+i*i+iF+i*i+ii+i*i+iEE+TE+TT*FTFiFFiii1234567891011§2.7有關(guān)文法實(shí)用中的一些說明有關(guān)文法的實(shí)用限制有害規(guī)則和多余規(guī)則有害規(guī)則：U→U,無用且引起文法的二義多余規(guī)則：所有句子推導(dǎo)都用不到的規(guī)則，表現(xiàn)形式：不可到達(dá)：不在任何句型中出現(xiàn)的非終結(jié)符的規(guī)則，即除了開始符號外，U不出現(xiàn)在該文法的任何其他的規(guī)則的右部。不可終止：不可推出終結(jié)符號串的非終結(jié)符的規(guī)則，若在推導(dǎo)中使用該規(guī)則，則在也不能推出終結(jié)符號串。文法的化簡與改造1無用符號和無用產(chǎn)生式的刪除設(shè)G=(VN,VT,P,S)是一文法,XVNVT,X稱為是有用的,若X至少出現(xiàn)在一個句子的推導(dǎo)過程中,即X滿足:(1)存在,V*,有S*X (2.12)(2)存在wVT*,使 X*w (2.13)否則,稱X是無用的.若一產(chǎn)生式含有無用符號,則此產(chǎn)生式稱為無用產(chǎn)生式.無用產(chǎn)生式給語法分析帶來了許多麻煩,應(yīng)予以刪除.消除無用產(chǎn)生式的算法算法2.1將文法G=(VN,VT,P,S),改造為G1=(V’N,VT,P’,S),使得對于每個XV’N,存在wVT*,滿足X*w.(1)置V’N,P’為空;(2)對于P中每個產(chǎn)生式A,若(V’NVT)*,則將A加入V’N中;(