編譯原理清華大學(xué)第3章 文法和語言課件

【課前思考】

1計(jì)算機(jī)高級語言有哪些一般特性？

2你所見到的程序設(shè)計(jì)語言的手冊或語言標(biāo)準(zhǔn)是怎樣陳述語言的語法和語義的？

3從學(xué)習(xí)程序設(shè)計(jì)語言到定義程序設(shè)計(jì)語言,兩者的角度有何不同?4學(xué)習(xí)編譯程序?yàn)槭裁匆芯空Z言的描述問題？【學(xué)習(xí)目標(biāo)】

本章目的是為語言的語法描述尋求工具

1掌握對源程序給出精確無二義（嚴(yán)謹(jǐn)、簡潔、易讀）的語法描述手段之一：文法。

2熟練使用文法定義程序設(shè)計(jì)語言的單詞和語法成分。

3對形式語言的理論有一個(gè)初步基礎(chǔ)?！緦W(xué)習(xí)指南】

1什么是文法,什么是文法定義的語言？

2在喬姆斯基（Chomsky）的文法類型中，為什么特別關(guān)注上下文無關(guān)文法？3文法的遞歸性、二義性等性質(zhì)是什么？4句子、句型和語言的定義是什么？

5推導(dǎo)和歸約是什么？

6什么是語法分析？語法分析方法的分類？

7如何確定一個(gè)輸入符號串是否是所給文法的句子？3.0概述用高級語言編程比用低級語言方便，但要解決兩個(gè)問題：(1)計(jì)算機(jī)怎樣懂得高級語言程序，這就需要一個(gè)翻譯程序?qū)崿F(xiàn)從源程序到目標(biāo)程序的轉(zhuǎn)換。(2)用什么方法來精確定義高級語言，即怎樣精確描述高級語言。

要構(gòu)造一個(gè)編譯程序，應(yīng)深刻理解被編譯的源語言的結(jié)構(gòu)（即詞法和語法）及其含義（即語義），同時(shí)要弄清源語言的語法規(guī)則和語義規(guī)則是采用什么理論或什么方法來描述的。

本章目的為語言的語法描述尋求工具，該工具要對程序設(shè)計(jì)語言給出精確無二義的語法描述。（嚴(yán)謹(jǐn)、簡潔、易讀）

形式工具----形式語言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)?！靶问健?---：語言的所有規(guī)則只以符號串能出現(xiàn)的方式來陳述。

語言概述語言是由句子組成的集合，或說是由一組符號串所構(gòu)成的集合。漢語——所有符合漢語語法的句子的全體英語——所有符合英語語法的句子的全體程序設(shè)計(jì)語言——所有該語言的程序的全體每個(gè)句子構(gòu)成的規(guī)律研究語言每個(gè)句子的含義每個(gè)句子和使用者的關(guān)系研究程序設(shè)計(jì)語言每個(gè)程序構(gòu)成的規(guī)律每個(gè)程序的含義每個(gè)程序和使用者的關(guān)系語言研究的三個(gè)方面語法Syntax

語義Semantics

語用Pragmatics語法——表示構(gòu)成語言句子的各個(gè)記號之間的組合規(guī)律。語義——表示各個(gè)記號的特定含義。（各個(gè)記號和記號所表示的對象之間的關(guān)系）語用——表示在各個(gè)記號所出現(xiàn)的行為中，它們的來源、使用和影響。

每種語言具有兩個(gè)可開始的特性，即語言的形式和該形式相關(guān)聯(lián)的意義。語言的實(shí)例若在語法上是正確的，其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的，前者稱為語言的語義，后者是其語用意義。幽默、雙關(guān)語和謎語就是利用這兩方面意義間的差異。

如果不考慮語義和語用，即只從語法這一側(cè)面來看語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。“形式”是指這樣的事實(shí)：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述。形式語言理論是對符號串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計(jì)語言語法分析研究的基礎(chǔ)。

任何語言均可看作一個(gè)集合。這個(gè)集合中的每個(gè)元素都是在一定符號集（字母表）上的一個(gè)符號串。

對于自然語言來說，它們是定義在某個(gè)字母表上的句子的集合。對于程序語言來說，它們也是定義在某個(gè)字母表上的句子的集合。這里的句子，就是一個(gè)源程序。

通常，源程序是由關(guān)鍵字、標(biāo)識符、常數(shù)、運(yùn)算符以及一些界限符組成。這些語法成分統(tǒng)稱為單詞或單詞符號。單詞符號是語言中具有獨(dú)立意義的最基本單位。語言的單詞符號是由詞法規(guī)則所確定的，即詞法規(guī)則規(guī)定了單詞符號的形成規(guī)則。

當(dāng)我們表述一種語言時(shí)，無非是要說明這種語言的句子，如果語言只含有窮多個(gè)句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，就存在著如何給出它的有窮表示的問題。以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明(或者定義)句子的組成結(jié)構(gòu)，比如漢語句子可以是由主語后隨謂語而成，構(gòu)成謂語的是動(dòng)詞和直接賓語。

有了一組規(guī)則以后，按照如下方式用它們導(dǎo)出句子：開始去找∷=左端的帶有〈句子〉的規(guī)則并把它由∷=右端的符號串代替，這個(gè)動(dòng)作表示成：〈句子〉〈主語〉〈謂語〉，然后在得到的串〈主語〉〈謂語〉中，選取〈主語〉或〈謂語〉，再用相應(yīng)規(guī)則的∷=右端代替之。比如，選取了〈主語〉，并采用規(guī)則〈主語〉∷=〈代詞〉，那么得到：〈主語〉〈謂語〉〈代詞〉〈謂語〉，重復(fù)做下去，句子：“我是大學(xué)生”的全部動(dòng)作過程是：〈句子〉〈主語〉〈謂語〉〈代詞〉〈謂語〉我〈謂語〉我〈動(dòng)詞〉〈直接賓語〉

我是〈直接賓語〉我是〈名詞〉我是大學(xué)生“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中一種描述元語言稱為文法。二、符號串和符號串集合的運(yùn)算

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

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

特別地,|ε|=09.方冪運(yùn)算：符號串集合的方冪符號串的方冪有任一符號串集合A，定義:有任一符號串X，定義:A0={ε},X0=εA1=A,X1=XA2=AA,X2=XXA3=AAA,X3=XXX

…

…

An＝An-1A=AAn-1Xn=XX…X

＝AA…An個(gè)

n個(gè)其中:n≥010.符號串集合的閉包運(yùn)算：設(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

為什么對符號、符號串、符號串集合以及它們的運(yùn)算感興趣？若A為某語言的基本字符集

A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B為單詞集

B={begin,end,if,then,else,for,……,<標(biāo)識符>,<常量>,……}

則BA*

。語言的句子是定義在B上的符號串。若令C為句子集合，則CB*,程序C3.2文法的直觀理解1.什么是文法：

文法是對語言結(jié)構(gòu)的定義與描述。即從形式上用于描述和規(guī)定語言結(jié)構(gòu)的稱為“文法”（或稱為“語法”）。

例：有一句子：“我是大學(xué)生”。這是一個(gè)在語法、語義上都正確定句子，該句子的結(jié)構(gòu)（稱為語法結(jié)構(gòu)）是由它的語法決定的。在本例中它為“主謂結(jié)構(gòu)”。如何定義句子的合法性？有窮語言無窮語言

2.語法規(guī)則：

我們通過建立一組規(guī)則（產(chǎn)生式），來描述句子的語法結(jié)構(gòu)。規(guī)定用“::=”表示“由……組成”。<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=

王民|大學(xué)生|工人|英語<謂語>::=<動(dòng)詞><直接賓語><動(dòng)詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞><句子>

<主語><謂語>

<代詞><謂語>

我<謂語>

我<動(dòng)詞><直接賓語>

我是<直接賓語>

我是<名詞>

我是大學(xué)生<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=

王民|大學(xué)生|工人|英語<謂語>::=<動(dòng)詞><直接賓語><動(dòng)詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞>推導(dǎo)方法：從一個(gè)要開始的符號開始推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部來替代產(chǎn)生式的左部，每次僅用一條產(chǎn)生式去進(jìn)行推導(dǎo)。例：給定一組語法規(guī)則，考察一個(gè)句子：“我是大學(xué)生”的推導(dǎo)過程。例：有一英語句子：Thebigelephantatethepeanut.<句子>::=<主語><謂語><主語>::=<冠詞><形容詞><名詞><冠詞>::=the<形容詞>::=big<名詞>::=elephant<謂語>::=<動(dòng)詞><賓語><動(dòng)詞>::=ate<賓語>::=<冠詞><名詞><名詞>::=peanut上述推導(dǎo)可寫成<句子>=>thebigelephantatethepeanut+說明：

(1)有若干語法成分同時(shí)存在時(shí)，我們總是從最左的語法成分進(jìn)行推導(dǎo)，這稱之為最左推導(dǎo)，類似的有最右推導(dǎo)（一般推導(dǎo)）。

(2)從一組產(chǎn)生式可推出不同的句子，如以上產(chǎn)生式還可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它們在語法上都正確，但在語義上都不正確。

所謂文法是在形式上對句子結(jié)構(gòu)的定義與描述，而未涉及語義問題。4.語法樹：我們用語法樹來描述一個(gè)句子的語法結(jié)構(gòu)。<句子><主語><謂語><冠詞><形容詞><名詞><動(dòng)詞><賓語><冠詞><名詞>Thebigelephantatethepeanut語法成分（在形式語言中又稱“非終結(jié)符”）單詞符號（在形式語言中又稱“終結(jié)符號”)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}幾點(diǎn)說明：產(chǎn)生式左邊符號構(gòu)成集合VN，且Z∈VN有些產(chǎn)生式具有相同的左部，可以合在一起例、<無符號整數(shù)>→<數(shù)字串>；

<數(shù)字串>→<數(shù)字串><數(shù)字>|<數(shù)字>；

<數(shù)字>→0|1|2|3|……|9

文法的BNF表示給定一個(gè)文法，實(shí)際只需給出產(chǎn)生式集合，并指定開始符號例、G[<無符號整數(shù)>]<無符號整數(shù)>→<數(shù)字串>；

<數(shù)字串>→<數(shù)字串><數(shù)字>|<數(shù)字>；

<數(shù)字>→0|1|2|3|……|93.3.2推導(dǎo)與歸約

定義2：直接推導(dǎo)：文法G：v＝xUy，w＝xuy,

其中x、y∈V*

，U∈VN,u∈V*,

若U::u∈P，則vw，即xUyxuy。若x＝y(tǒng)＝ε，有U::u，則Uu

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

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

(6)==>==>(1)==>(3)(4)==>==>(2)(5)==>例：則有：

定義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。+直觀意義：規(guī)范推導(dǎo)＝最右推導(dǎo)

定義5：最右推導(dǎo)：若符號串α中有兩個(gè)以上的非終結(jié)符時(shí)，對推導(dǎo)的每一步堅(jiān)持把α中的最右非終結(jié)符進(jìn)行替換，稱為最右推導(dǎo)。最左推導(dǎo)：若符號串α中有兩個(gè)以上的非終結(jié)符時(shí)，對推導(dǎo)的每一步堅(jiān)持把α中的最左非終結(jié)符進(jìn)行替換，稱為最左推導(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'是兩個(gè)不同的文法，若L(G)=L(G'),

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

若x=ε,即U::=Uy，左遞歸； 若y=ε,即U::=xU，右遞歸；2.遞歸文法：文法G，存在U

∈VNifU==>…U…,則G為遞歸文法；

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

ifU==>…U,則G為右遞歸文法；+++4.遞歸文法的優(yōu)點(diǎn)：可用有窮條產(chǎn)生式，定義無窮語言

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

形式語言：用文法和自動(dòng)機(jī)所描述的沒有語義的語言。

文法定義：喬姆斯基將所有文法都定義為一個(gè)四元組：

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型文法：P：u::=v

其中u∈V*

，v∈V* 0型語言：L0這種語言可以用圖靈機(jī)(Turing)接受. 0型文法稱為短語結(jié)構(gòu)文法。產(chǎn)生式的左部和右部都可以是符號串，一個(gè)短語可以產(chǎn)生另一個(gè)短語。定義10：

1型文法：P：xUy::=xuy ︱其中U∈VN，x、y、u∈V*1型語言：L1這種語言可以由一種線性界限自動(dòng)機(jī)接受.

稱為上下文敏感或上下文有關(guān)。也即只有在x、y這樣的上下文中才能把U改寫為u定義10：

1型文法：P：u::=v ︱u︱≥︱v︱u,v∈V*定義11：2型文法：P：U::=u

其中U∈VN，u∈V*2型語言：L2這種語言可以由下推自動(dòng)機(jī)接受.

稱為上下文無關(guān)文法。也即把U改寫為u時(shí)，不必考慮上下文。注意：2型文法與BNF表示相等價(jià)。（右線性）

P：U::=t

或U::=tW

其中U、W∈VNt∈VT3型語言：L3又稱正則語言、正則集合 這種語言可以由有窮自動(dòng)機(jī)接受.3型文法又被稱為正則文法。它是對2型文法進(jìn)行進(jìn)一步限制。（左線性）

P：U::=t

或U::=Wt

其中U、W∈VNt∈VT定義12：

3型文法：

語言之間的關(guān)系：

L0L1L2L30型文法可以產(chǎn)生L0、L1、L2、L3;但2型文法只能產(chǎn)生L2、L3，不能產(chǎn)生L1?！取取?.5語法樹與二義性文法3.5.1推導(dǎo)與語法樹（1）語法樹：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由結(jié)點(diǎn)和有向邊組成。

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

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

ZUVabcd

注意一個(gè)重要事實(shí)：文法所能產(chǎn)生的句子，可以用不同的推導(dǎo)原則（使用產(chǎn)生式順序不同）將其推導(dǎo)出來。語法樹的生成規(guī)律不同，但最終生成的語法樹形狀完全相同。某些文法有此性質(zhì)，而某些文法不具此性質(zhì)。(2)句型的推導(dǎo)及語法樹的生成（自頂向下）給定G[Z]，句型w：可建立推導(dǎo)序列，Zw

可建立語法樹，以Z為樹根結(jié)點(diǎn)，每步推導(dǎo)生成語法樹的一層分支，最終可生成句型的語法樹。*

<無符號整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字>1(1)(2)(3)(5)(4)0一般推導(dǎo)：(3)子樹與簡單子樹

子樹：語法樹中的某個(gè)結(jié)點(diǎn)（子樹的根）連同它向下派生的部分所組成。簡單子樹：只有單層分枝的子樹稱為簡單子樹。

<無符號整數(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é)點(diǎn)開始，自上而下建立語法樹。例：給定文法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é)點(diǎn)，直至把整棵樹剪掉（留根），每剪一次對應(yīng)一次歸約。從句型開始，自右向左地逐步進(jìn)行歸約，建立歸約序列。規(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ī)范句型，因?yàn)椋?lt;無符號整數(shù)><數(shù)字串> <數(shù)字串><數(shù)字>

<數(shù)字><數(shù)字>RR3.5.2文法的二義性

定義14.1：若對于一個(gè)文法的某一句子存在兩棵不同的語法樹，則該文法是二義性文法，否則是無二義性文法。

換而言之，無二義性文法的句子只有一棵語法樹，盡管推導(dǎo)過程可以不同。下面舉一個(gè)二義性文法的例子：

G[E]: E:=E+E|E*E|(E)|i

VN

={E}

VT={+,*,(,),i}對于句子S＝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

定義14.2：若一個(gè)文法的某句子存在兩個(gè)不同的規(guī)范推導(dǎo)，則該文法是二義性的，否則是無二義性的。

以上是自頂向下來看文法的二義性，我們還可以自底向上來看文法的二義性。上例中，規(guī)范句型E+E*i

是由i＋i*i通過兩步規(guī)范規(guī)約得到的，但對于同一個(gè)句型E+E*i，它有兩個(gè)不同的句柄（對應(yīng)上述兩棵不同的語法樹）：i和E＋E。因此語法的二義性意味著句型的句柄不唯一。EEE+EE*iEEE*EE+i句柄：i句柄：E＋E

若文法是二義性的，則在編譯時(shí)就會(huì)產(chǎn)生不確定性，遺憾的是在理論上已經(jīng)證明：文法的二義性是不可判定的，即不可能構(gòu)造出一個(gè)算法，通過有限步驟來判定任一文法是否有二義性。

現(xiàn)在的解決辦法是：提出一些限制條件，稱為無二義性的充分條件，當(dāng)文法滿足這些條件時(shí)，就可以判定文法是無二義性的。

由于無二義性文法比較簡單，我們也可以采用另一種解決辦法：即不改變二義性文法，而是確定一種編譯算法，使該算法滿足無二義性充分條件。

定義14.3若一個(gè)文法的某規(guī)范句型的句柄不唯一，則該文法是二義性的，否則是無二義性的。例:算術(shù)表達(dá)式的文法：E::=E+E|E*E|(E)|iE::=E+T|TT::=T*F|FF::=(E)|i例:Pascal語言條件語句的文法<條件語句>::=If<布爾表達(dá)式>then<語句>|If<布爾表達(dá)式>then<語句>else<語句><語句>::=<條件語句>|<非條件語句>|…….3.6句型的分析

任務(wù)：給定G[Z]:S∈VT*,判定是否有S

L(G[E])?

這是詞法分析和語法分析所要做的工作，將在第三、四章中詳細(xì)介紹。3.6.1句型的短語、簡單短語和句柄*定義15:

給定文法G[Z],w=xuy∈V+，為該文法的句型,

若ZxUy,且U

u,則u是句型w相對于U的短語；其中U∈VN，u∈V+，x,y∈V*＋

直觀理解：短語是前面句型中的某個(gè)非終結(jié)符所能推出的符號串。或短語定義:

設(shè)G[Z]是給定文法,w=xuy∈V+，為該文法的句型,如果滿足下面兩個(gè)條件:①ZxUy；②Uu；則稱句型xuy中的子串u是句型xuy的短語。*＋定義17.

任一句型的最左簡單短語稱為該句型的句柄。

給定句型找句柄的步驟： 短語 簡單短語句柄

注意：短語、簡單短語是相對于句型而言，一個(gè)句型可能有多個(gè)短語、簡單短語，句柄只能有一個(gè)。定義16:

給定文法G[Z],w=xuy∈V+，為該文法的句型,

若ZxUy,且U

u,則u是句型w相對于U的簡單短語。其中U∈VN，u∈V+，x,y∈V**例：給定文法G：

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

E－T

T－T

T*F－T

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

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

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