第3章 文法和語言

第3章文法和語言3.0概述3.1形式語言基礎(chǔ)3.2文法的直觀理解3.3文法和語言的定義3.4文法的類型3.5語法樹與二義性3.6句型的分析3.0概述顯然，用高級語言編程比用低級語言來得方便，但要解決兩個問題：1.計算機怎樣懂得高級語言程序，這就需要一個翻譯程序?qū)崿F(xiàn)從源程序到目標程序的轉(zhuǎn)換。2.用什么方法來精確定義高級語言，即怎樣精確描述高級語言。要構(gòu)造一個編譯程序(翻譯程序)，應(yīng)深刻理解被編譯的源語言的結(jié)構(gòu)（即詞法和語法）及其含義（即語義），同時要弄清源語言的語法規(guī)則和語義規(guī)則是采用什么理論或什么方法來描述的。當我們表述一種語言時，無非是要說明這種語言的句子，如果語言只含有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，就存在著如何給出它的有窮表示的問題。以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明(或者定義)句子的組成結(jié)構(gòu)，比如漢語句子可以是由主語后隨謂語而成，構(gòu)成謂語的是動詞和直接賓語。任何語言均可看作一個集合。這個集合中的每個元素都是在一定符號集（字母表）上的一個符號串。對于自然語言來說，它們是定義在某個字母表上的句子的集合。對于程序語言來說，它們也是定義在某個字母表上的句子的集合。這里的句子，就是一個源程序。通常，源程序是由關(guān)鍵字、標識符、常數(shù)、運算符以及一些界限符組成。這些語法成分統(tǒng)稱為單詞或單詞符號。單詞符號是語言中具有獨立意義的最基本單位。語言的單詞符號是由詞法規(guī)則所確定的，即詞法規(guī)則規(guī)定了單詞符號的形成規(guī)則?！拔沂谴髮W(xué)生”。是漢語的一個句子?！淳渥印怠?〈主語〉〈謂語〉〈主語〉∷=〈代詞〉｜〈名詞〉〈代詞〉∷=我｜你｜他〈名詞〉∷=王明｜大學(xué)生｜工人｜英語〈謂語〉∷=〈動詞〉〈直接賓語〉〈動詞〉∷=是｜學(xué)習(xí)〈直接賓語〉∷=〈代詞〉｜〈名詞〉主語謂語用語法來描述：有了一組規(guī)則以后，按照如下方式用它們導(dǎo)出句子：開始去找∷=左端的帶有〈句子〉的規(guī)則并把它由∷=右端的符號串代替，這個動作表示成：〈句子〉〈主語〉〈謂語〉然后在得到的串〈主語〉〈謂語〉中，選取〈主語〉或〈謂語〉，再用相應(yīng)規(guī)則的∷=右端代替之。比如，選取了〈主語〉，并使用規(guī)則〈主語〉∷=〈代詞〉來處理，那么得到：〈主語〉〈謂語〉〈代詞〉〈謂語〉重復(fù)做下去:句子：“我是大學(xué)生”的全部動作過程是：〈句子〉〈主語〉〈謂語〉〈代詞〉〈謂語〉我〈謂語〉

我〈動詞〉〈直接賓語〉

我是〈直接賓語〉

我是〈名詞〉

我是大學(xué)生

〈句子〉∷=〈主語〉〈謂語〉〈主語〉∷=〈代詞〉｜〈名詞〉〈代詞〉∷=我｜你｜他〈名詞〉∷=王明｜大學(xué)生｜工人｜英語〈謂語〉∷=〈動詞〉〈直接賓語〉〈動詞〉∷=是｜學(xué)習(xí)〈直接賓語〉∷=〈代詞〉｜〈名詞〉“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中一種描述元語言稱為文法。語言概述語言是由句子組成的集合，或說是由一組符號串所構(gòu)成的集合。漢語——所有符合漢語語法的句子的全體英語——所有符合英語語法的句子的全體程序設(shè)計語言——所有該語言的源程序的全體每個句子構(gòu)成的規(guī)律研究語言每個句子的含義每個句子和使用者的關(guān)系研究程序設(shè)計語言每個程序構(gòu)成的規(guī)律每個程序的含義每個程序和使用者的關(guān)系語言研究的三個方面語法Syntax語義Semantics語用Pragmatics語法——表示構(gòu)成語言句子的各個記號之間的組合規(guī)律。語義——表示各個記號的特定含義。（各個記號和記號所表示的對象之間的關(guān)系）語用——表示在各個記號所出現(xiàn)的行為中，它們的來源、使用和影響。每種語言都具有兩個可識別的特性，即語言的形式和該形式相關(guān)聯(lián)的意義。語言的實例若在語法上是正確的，其相關(guān)聯(lián)的意義可以從兩個觀點來看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗到的意義。這兩個意義并非總是一樣的，前者稱為語言的語義，后者是其語用意義。幽默、雙關(guān)語和謎語就是利用這兩方面意義間的差異。如果不考慮語義和語用，即只從語法這一側(cè)面來看語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個數(shù)學(xué)系統(tǒng)?！靶问健笔侵高@樣的事實：語言的所有規(guī)則只以什么符號串能出現(xiàn)的方式來陳述。形式語言理論是對符號串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計語言語法分析研究的基礎(chǔ)。3.1形式語言基礎(chǔ)基本概念:一、字母表和符號串1.字母表：符號的非空有限集合。例：={a，b，c}2.符號：字母表中的元素。例：a，b，c3.符號串：符號的有窮序列。例：a,aa,ac,abc，..特別地,空符號串：無任何符號的符號串,記為ε。

有字母表，定義：（1）ε是上的符號串；（2）若x是上的符號串，且a，則ax或xa是上的符號串；（3）y是上的符號串，當且僅當y可由（1）和（2）產(chǎn)生。二、符號串和符號串集合的運算4.符號串集合：由符號串構(gòu)成的集合。符號串的形式定義

5.符號串相等：若x、y是集合上的兩個符號串，則x＝y(tǒng)當且僅當組成x的每一個符號和組成y的每一個符號依次相等。

6.符號串的長度：x為符號串，其長度|x|等于組成該符號串的符號個數(shù)。例：x＝STV，|x|=3

特別地,|ε|=07.符號串的聯(lián)接：若x、y是定義在Σ之上的符號串，且x＝ab，y＝bc，則x和y的聯(lián)接xy＝abbc也是Σ上的符號串。注意：一般xy≠yx，而εx＝xε＝x例：A＝{a,b},B={c,d},AB=？符號串集合的乘積運算：令A(yù)、B為符號串集合，定義AB＝{xy|x∈A，y∈B}。

{ac，ad，bc，bd}

因為εx＝xε＝x，所以{ε}A=A{ε}=A注:{ε}為空串集。9.空集:不包含任何元素的集合稱為空集合，記為Φ。即Φ={}。對任一集合A，有ΦA(chǔ)=AΦ=Φ。注：εΦ，即{ε}Φ。符號串集合的方冪有任一符號串集合A，定義:

A0={ε},A1=A,A2=AA,A3=AAA,…An＝An-1A=AAn-1＝AA…An個其中:n≥0符號串的方冪有任一符號串X，定義:X0=εX1=XX2=XXX3=XXX…Xn=XX…Xn個其中:n≥010.方冪運算：11.符號串集合的閉包運算：設(shè)A是符號串集合，定義A＋=A1∪A2∪A3∪……∪An∪…… 稱為集合A的正則閉包。

A*=A0∪A1∪A2∪A3∪……∪An∪……=A0∪A＋

稱為集合A的星閉包。例：A={x,y}A＋＝？

A*＝？{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A1

A2

A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A0A1

A2

A3

為什么對符號、符號串、符號串集合以及它們的運算感興趣？若A為某語言的基本字符集A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B為單詞集B={begin,end,if,then,else,for,…+,－,×,_/,(,),……}則BA*。語言的句子是定義在B上的符號串。若令C為句子集合，則CB*,程序C3.2文法的直觀理解1.什么是文法：

文法是對語言結(jié)構(gòu)的定義與描述。即從形式上用于描述和規(guī)定語言結(jié)構(gòu)的稱為“文法”（或稱為“語法”）。例：有一句子：“我是大學(xué)生”。這是一個在語法、語義上都正確定句子，該句子的結(jié)構(gòu)（稱為語法結(jié)構(gòu)）是由它的語法決定的。在本例中它為“主謂結(jié)構(gòu)”。如何定義句子的合法性？有窮語言無窮語言

2.語法規(guī)則：

我們通過建立一組規(guī)則（產(chǎn)生式），來描述句子的語法結(jié)構(gòu)。規(guī)定用“::=”表示“由……組成”。<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=王民|大學(xué)生|工人|英語<謂語>::=<動詞><直接賓語><動詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞>由產(chǎn)生式推導(dǎo)句子：

<句子><主語><謂語><主語><謂語>

<代詞><謂語> …………這種推導(dǎo)一直進行下去，直到所有帶<>的符號都由終結(jié)符號替代為止。有了一組產(chǎn)生式之后，可以按照一定的方式用它們?nèi)ネ茖?dǎo)或產(chǎn)生句子。

推導(dǎo)方法：從一個初始的符號開始推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部來替代產(chǎn)生式的左部，每次僅用一條產(chǎn)生式去進行推導(dǎo)。<句子>

<主語><謂語>

<代詞><謂語>

我<謂語>

我<動詞><直接賓語>

我是<直接賓語>

我是<名詞>

我是大學(xué)生<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=王民|大學(xué)生|工人|英語<謂語>::=<動詞><直接賓語><動詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞>推導(dǎo)方法：從一個初始的符號開始推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部來替代產(chǎn)生式的左部，每次僅用一條產(chǎn)生式去進行推導(dǎo)。例：給定一組語法規(guī)則，考察一個句子：“我是大學(xué)生”的推導(dǎo)過程。上述推導(dǎo)可寫成<句子>我是大學(xué)生+說明：(1)有若干語法成分同時存在時，我們總是從最左的語法成分進行推導(dǎo)，這稱之為最左推導(dǎo)，類似的有最右推導(dǎo)（一般推導(dǎo)）。(2)從一組產(chǎn)生式可推出不同的句子，如以上產(chǎn)生式還可推出“大學(xué)生是我”、“我學(xué)習(xí)英語”、“英語學(xué)習(xí)我”等句子，它們在語法上都正確，但在語義上不是都正確。所謂文法是在形式上對句子結(jié)構(gòu)的定義與描述，而未涉及語義問題。3.3.1文法的定義3.3文法和語言的形式定義定義1:文法是產(chǎn)生式的有窮集合,通常定義為四元組:G=（VN，VT，P，Z）

VN：非終結(jié)符號集

VT：終結(jié)符號集 P：產(chǎn)生式或規(guī)則的集合Z：開始符號（識別符號）Z∈VN其中:①產(chǎn)生式：產(chǎn)生式是一個有序?qū)?U,x),通常寫為:U::x或Ux；|U|=1|x|0②非終結(jié)符號：出現(xiàn)在產(chǎn)生式的左部,且能推出符號或符號串的那些符號。其全體構(gòu)成非終結(jié)符號集，記為VN

。③終結(jié)符號：不出現(xiàn)在產(chǎn)生式的左部,且不能推出符號或符號串的那些符號。其全體構(gòu)成終結(jié)符號集，記為VT

。V＝VN∪VT稱為文法的字匯表產(chǎn)生式：U::xU∈VN,x∈V*P={<無符號整數(shù)>→<數(shù)字串>；<數(shù)字串>→<數(shù)字串><數(shù)字>；<數(shù)字串>→<數(shù)字>；

<數(shù)字>→0；

<數(shù)字>→1；

…………

<數(shù)字>→9；}Z=<無符號整數(shù)>；例：無符號整數(shù)的文法： G[<無符號整數(shù)>]=（VN，VT，P，Z） VN＝{<無符號整數(shù)>,<數(shù)字串>,<數(shù)字>} VT={0,1,2,3,……9}幾點說明：產(chǎn)生式左邊符號構(gòu)成集合VN，且Z∈VN有些產(chǎn)生式具有相同的左部，可以合在一起例、<無符號整數(shù)>→<數(shù)字串>；<數(shù)字串>→<數(shù)字串><數(shù)字>|<數(shù)字>；<數(shù)字>→0|1|2|3|……|9文法的BNF表示元語言符號：::(即→)讀為“定義為”或者“生成為”|讀為“或者”

給定一個文法，實際只需給出產(chǎn)生式集合，并指定開始符號例:G[<無符號整數(shù)>]<無符號整數(shù)>→<數(shù)字串>；<數(shù)字串>→<數(shù)字串><數(shù)字>|<數(shù)字>；<數(shù)字>→0|1|2|3|……|9例3.6:用文法G1來定義下面的集合：L1={n|n是非負整數(shù)}。解題思路：顯而易見，該集合不能用枚舉法來定義。∵非負整數(shù)是一種數(shù)字串的集合，故離不開數(shù)字；不妨先定義：D→0|1|2|3|……|9顯然DL1，若xL1，則xDL1。這樣L1可按下法構(gòu)造出來：N→DN→NDD→0|1|2|3|……|9∴有解：G1=（VN，VT，P，N）其中：VN={N，D}，VT={0，1，2，3，……，9}P：N→ND|D，D→0|1|2|3|……|9作業(yè)：§3練習(xí)（P48）3,4,5題3.3.2推導(dǎo)與歸約定義2：直接推導(dǎo)：設(shè)有文法G，x＝αUβ，y＝αuβ,其中α、β∈V*,

，U∈VN,u∈V*,若U::u∈P，則xy

，即αUβαuβ。

x直接推導(dǎo)出y

。

換句話說，設(shè)x和y是符號串，若使用一次產(chǎn)生式可以從x變換出y，則稱x直接推導(dǎo)出y(或者說y是x的直接推導(dǎo)），記為xy。若α＝β＝ε，有U::u，則Uu；稱U直接推導(dǎo)出u。當符號串已沒有非終結(jié)符號時，推導(dǎo)就必須終止。因為終結(jié)符不可能出現(xiàn)在產(chǎn)生式左部，所以將在產(chǎn)生式左部出現(xiàn)的符號稱為非終結(jié)符號。例如：G[N]：N→ND|DD→0|1|2|3|4|5|6|7|8|9NNDNDDND9N09D09109

(6)

(1)

(3)(4)

(2)(5)

＋N

109定義3：+推導(dǎo)：x和y是符號串，若使用一次或多次產(chǎn)生式可以從x變換出y，則稱x推導(dǎo)出y(或者說y是x的推導(dǎo)），記為xy。＋例：則有：定義4：

*推導(dǎo)：x和y是符號串，若使用0次或多次產(chǎn)生式可以從x變換出y，則稱x*推導(dǎo)出y(或者說y是x的*推導(dǎo)），記為xy。**N

109則有：*N

N或者說：若有直接推導(dǎo)序列：x=U0

U1

U2

……

Un=y，則x

y。+NNDNDDND9N09D09109

(6)

(1)

(3)(4)

(2)(5)

定義5：

最右推導(dǎo)：若符號串α中有兩個以上的非終結(jié)符時，在推導(dǎo)的每一步堅持把α中的最右非終結(jié)符進行替換，稱為最右推導(dǎo)（也稱為規(guī)范推導(dǎo)）。

最左推導(dǎo)：若符號串α中有兩個以上的非終結(jié)符時，在推導(dǎo)的每一步堅持把α中的最左非終結(jié)符進行替換，稱為最左推導(dǎo)。定義6：推導(dǎo)的逆過程稱之為歸約。例：x

y,可稱為x直接推導(dǎo)出y，也可稱為y直接歸約出x。＋x

y,可稱為x推導(dǎo)出y，也可稱為y歸約出x。3.3.3語言的形式定義文法G[Z]所產(chǎn)生的所有句子的集合定義7：給定文法G[Z] （1）句型：x是句型

Zx,且x∈V*；**（2）句子：x是句子

Zx,且x∈VT*；*（3）語言：L（G[Z]）={x|Zx，x∈VT*}；即：句型是由文法開始符號推導(dǎo)出來的由終結(jié)符和非終結(jié)符組成的符號串。即：句子是由文法開始符號推導(dǎo)出來的由終結(jié)符組成的符號串。例：{abna|n≥1},構(gòu)造其文法G1[Z]：Z→aBa, B→b|bBG2[Z]：Z→aBa, B→b|Bb定義8:G和G'是兩個不同的文法，若L(G)=L(G'),

則G和G'為等價文法。編譯感興趣的問題是:給定串x和文法G,求xL(G)?x算法1算法2xL(G)?Gyn出錯處理停機3.3.4遞歸文法1.遞歸產(chǎn)生式：產(chǎn)生式右部有與左部相同的符號 對于U→

xUy，稱為遞歸產(chǎn)生式； 若x=ε,即U→

Uy，左遞歸產(chǎn)生式； 若y=ε,即U→

xU，右遞歸產(chǎn)生式；2.遞歸文法：文法G，存在U

∈VNifU

…U…,則G為遞歸文法；

ifU

U…,則G為左遞歸文法；

ifU

…U,則G為右遞歸文法；+++4.遞歸文法的優(yōu)點：可用有窮條產(chǎn)生式，定義無窮語言例：對于前面給出的無符號整數(shù)的文法是有遞歸文法，用13條產(chǎn)生式就可以定義出所有的無符號整數(shù)。若不用遞歸文法，那將要用多少條產(chǎn)生式呢？!3.左遞歸文法的缺點：不能用自頂向下的方法來進行語法分析會造成死循環(huán)（后面將詳細論述）3.4文法分類

形式語言：用文法或自動機描述語法的語言。文法定義：喬姆斯基將所有文法都定義為一個四元組： G=（VN，VT，P，Z） VN：非終結(jié)符號集；

VT：終結(jié)符號集； P：產(chǎn)生式或規(guī)則的集合； Z：開始符號（開始符號）Z∈VN。語言定義：L（G[Z]）={x|Z

x,x∈VT*}。*文法和語言分類：0型、1型、2型、3型這幾類文法的差別在于對產(chǎn)生式施加不同的限制。定義9：0型文法：對于文法G，P：α::=β

其中α∈V*

且至少含有一個非終結(jié)符，β∈V*。 0型語言：L0這種語言可以用圖靈機(Turing)接受。 0型文法稱為短語結(jié)構(gòu)文法。產(chǎn)生式的左部和右部都可以是符號串，一個短語可以產(chǎn)生另一個短語。定義10：1型文法：對于文法G，P：xαy::=xβy其中αVN，x、y、βV*且xβy≥xαy。1型語言：L1這種語言可以由一種線性界限自動機接受。 稱為上下文敏感或上下文有關(guān)。也即α只有在x、y這樣的上下文中才能把α改寫為β。定義11：2型文法：對于文法G，P：α::=β； 其中α∈VN，β∈V*。2型語言：L2這種語言可以由下推自動機接受。稱為上下文無關(guān)文法。也即把α改寫為β時，不必考慮上下文。注意：2型文法與BNF表示相等價。（右線性）

P：A::=a； 或A::=Ba；其中A、B∈VN，a∈VT。3型語言：L3又稱正則語言、正則集合， 這種語言可以由有窮自動機接受。3型文法又被稱為正則文法。它是對2型文法進行進一步限制。（左線性）

P：A::=a； 或A::=aB；其中A、B∈VN，a∈VT。定義12：3型文法：對于文法G，3.5語法樹與二義性文法3.5.1推導(dǎo)與語法樹（1）語法樹：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由結(jié)點和有向邊組成。

結(jié)點：符號 根結(jié)點：開始符號 中間結(jié)點：非終結(jié)符 葉結(jié)點：終結(jié)符或非終結(jié)符

有向邊：表示結(jié)點間的派生關(guān)系。

ZUVabcd

注意一個重要事實：文法所能產(chǎn)生的句子，可以用不同的推導(dǎo)原則（使用產(chǎn)生式順序不同）將其推導(dǎo)出來。語法樹的生成規(guī)律不同，但最終生成的語法樹形狀完全相同。某些文法有此性質(zhì)，而某些文法不具此性質(zhì)。(2)句型的推導(dǎo)及語法樹的生成（自頂向下）給定G[Z]，句型w：可建立推導(dǎo)序列，Zw*可建立語法樹，以Z為樹根結(jié)點，每步推導(dǎo)時語法樹向下生成一層分支，最終可生成一棵語法樹，其樹葉從左到右排列起來構(gòu)成一句型w

。一般推導(dǎo)：

<無符號整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字>1(1)(3)(5)(4)0(2)(3)子樹與簡單子樹子樹：語法樹中的某個結(jié)點（子樹的根）連同它向下派生的部分所組成。簡單子樹：只有單層分枝的子樹稱為簡單子樹。

<無符號整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字>1(1)(2)(3)(5)(4)0(4)樹與推導(dǎo)句型推導(dǎo)過程

句型語法樹的生長過程 由推導(dǎo)構(gòu)造語法樹1從開始符號開始，自左向右建立推導(dǎo)序列。由根結(jié)點開始，自上而下建立語法樹。例：給定文法G[<無符號整數(shù)>]和句型10,考察語法樹與推導(dǎo)過程。規(guī)范推導(dǎo)[<無符號整數(shù)>]<無符號整數(shù)><數(shù)字串><數(shù)字串>R<數(shù)字串><數(shù)字><數(shù)字串><數(shù)字>R<數(shù)字串>0R0<數(shù)字><數(shù)字>0R110R 由語法樹構(gòu)造歸約2自下而上地修剪子樹的末端結(jié)點，直至把整棵樹剪掉（留根），每剪一次對應(yīng)一次歸約。從句型開始，自右向左地逐步進行歸約，建立歸約序列。規(guī)范歸約與規(guī)范推導(dǎo)互為逆過程[<無符號整數(shù)>]<數(shù)字串><數(shù)字串><數(shù)字>0<數(shù)字>1<無符號整數(shù)><數(shù)字串>R<數(shù)字串><數(shù)字>R<數(shù)字串>0R<數(shù)字>0R10R定義14：通過規(guī)范推導(dǎo)或規(guī)范歸約所得到的句型稱為規(guī)范句型。不是規(guī)范推導(dǎo)在上例中，<數(shù)字><數(shù)字>就不是規(guī)范句型，因為：<無符號整數(shù)><數(shù)字串> <數(shù)字串><數(shù)字>

<數(shù)字><數(shù)字>RR3.5.2文法的二義性定義14.1：若對于一個文法的某一句子產(chǎn)對于同一種推導(dǎo)存在兩棵不同的語法樹，則該文法是二義性文法，否則是無二義性文法。換而言之，無二義性文法的句子對于同一種推導(dǎo)只有一棵語法樹，盡管推導(dǎo)過程可以不同。下面舉一個二義性文法的例子：G[E]: E::=E+E|E*E|(E)|i

VN

={E}

VT={+,*,(,),i}對于句子i＋i*i∈L（G[E]），存在不同的規(guī)范推導(dǎo)：EEE+EE*iiiEEE*EE+iii這兩種不同的推導(dǎo)對應(yīng)了兩種不同的語法樹(1)EE+EE+E*EE+E*iE+i*ii＋i*iRRRRR(2)EE*EE*iE+E*iE+i*ii＋i*iRRRRRG[E]: E::=E+E|E*E|(E)|i若文法是二義性的，則在編譯時就會產(chǎn)生不確定性，遺憾的是在理論上已經(jīng)證明：文法的二義性是不可判定的，即不可能構(gòu)造出一個算法，通過有限步驟來判定任一文法是否有二義性?，F(xiàn)在的解決辦法是：提出一些限制條件，稱為無二義性的充分條件，當文法滿足這些條件時，就可以判定文法是無二義性的。由于無二義性文法比較簡單，我們也可以采用另一種解決辦法：即不改變二義性文法，而是確定一種編譯算法，使該算法滿足無二義性充分條件。<條件語句>::=If<布爾表達式>then<語句><條件語句>::=If<布爾表達式>then<語句>else<語句><語句>::=<條件語句>|<非條件語句>|…….例:Pascal語言條件語句的文法S→ifBthenS1S→ifBthenS1elseS1S1→id:=E其中：B為布爾表達式，E為表達式（產(chǎn)生式省略），id為標識符

顯然，ifBthenifBthenS1elseS1是一個句型，若假設(shè)其中的B，S1均為終結(jié)符，則上述句型可以看作為一個句子，他對應(yīng)兩棵語法樹（最左推導(dǎo)）：顯然，ifBthenifBthenS1elseS1是一個句型，若假設(shè)其中的B，S1均為終結(jié)符，則上述句型可以看作為一個句子，它對應(yīng)兩棵語法樹（最左推導(dǎo)）：SifBthenSifBthenSelseSSifBthenSifBthenSelseS即可理解為：ifBthen（ifBthenS1elseS1）也可理解為：ifBthen（ifBthenS1）elseS1因此該文法是二義性文法。3.6句型的分析任務(wù)：給定G[Z]:S∈VT*,判定是否有S

L(G[E])?

這是詞法分析和語法分析所要做的工作，具體實現(xiàn)將在第四、五章中詳細介紹。3.6.1句型的短語、簡單短語和句柄定義15:給定文法G[Z],αuβ∈V+，為該文法的句型,若ZαUβ,且Uu,則u是句型αuβ相對于U的短語；其中U∈VN，u∈V+，α,β∈V*＋*直觀理解：短語是前面句型中的某個非終結(jié)符所能推出的符號串。或短語定義:設(shè)G[Z]是給定文法,αuβ

∈V+，為該文法的句型,如果滿足下面兩個條件:①ZαUβ；②Uu；則稱句型αuβ中的子串u是句型αuβ的短語。*＋定義17.任一句型的最左簡單短語稱為該句型的句柄。給定句型找句柄的步驟： 短語 簡單短語句柄

注意：短語、簡單短語是相對于句型而言，一個句型可能有多個短語和多個簡單短語，而句柄只能有一個。定義16:給定文法G[Z],αuβ∈V+

，為該文法的句型,若ZαUβ,且U

u,則u是句型αuβ相對于U的簡單短語。其中U∈VN，u∈V+，α,β

∈V**例：給定文法G：E→T|E+T|E－TT→F|T*F|T／FF→i|(E)符號串（T+i）*i－F是文法G的一個句型，求其短語、簡單短語和句柄。E

E－T

T－T

T－F

T*F－F

F*F－F(E)*F－F(T+T)*F－F(T+F)*F－F(T+i)*F－F(T+i)*i－F(T+i)*i－F解：短語有8個：1.E

E，E（T+i）*i－F則有：（T+i）*i－F2.E

T－F，T