第3章文法和語言

第3章文法和語言

當(dāng)我們表述一種語言時(shí)，無非是說明這種語言的句子，如果語言只含有有窮多個(gè)句子，則只需列出句子的有窮集就行了，但對(duì)于含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。3.1文法的直觀概念

以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明(或者定義)句子的組成結(jié)構(gòu)，比如漢語句子可以是由主語后隨謂語而成，構(gòu)成謂語的是動(dòng)詞和直接賓語，我們采用EBNF來表示這種句子的構(gòu)成規(guī)則。BNF范式和語法圖1.巴科斯范式:EBNF <句子>→<主語><謂語> <主語>→<代詞>|<名詞> <代詞>→你|我|他 <名詞>→王明|大學(xué)生|工人 <謂語>→<動(dòng)詞><賓語> <動(dòng)詞>→是|學(xué)習(xí) <賓語>→<代詞>|<名詞>帶<>的叫非終止符,不帶<>的叫終止符。<邏輯值>→True|False例子：<句子><主語><謂語>

<代詞><謂語>

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

我是<直接賓語>

我是<名詞>我是大學(xué)生“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中一種描述元語言稱為文法。語言概述

語言是由句子組成的集合，是由一組符號(hào)所構(gòu)成的集合。漢語--所有符合漢語語法的句子的全體英語--所有符合英語語法的句子的全體程序設(shè)計(jì)語言--所有該語言的程序的全體研究語言內(nèi)容包括：每個(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è)記號(hào)之間的組合規(guī)律語義--表示各個(gè)記號(hào)的特定含義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系）語用--表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來源、使用和影響。每種語言具有兩個(gè)可識(shí)別的特性，即語言的形式和該形式相關(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ī)則只以什麼符號(hào)串能出現(xiàn)的方式來陳述。形式語言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計(jì)語言語法分析研究的基礎(chǔ)。例子:整數(shù)(1)單個(gè)數(shù)字是整數(shù)(2)整數(shù)再接上數(shù)字仍是整數(shù)用BNF范式表示:

<1><整數(shù)>→<數(shù)字><數(shù)字>→0|1|2|…|9<2><整數(shù)>→<整數(shù)><數(shù)字><整數(shù)>→<數(shù)字>|<整數(shù)><數(shù)字>所以合起來有：

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

標(biāo)識(shí)符:以字母開頭以后由字母和數(shù)字組成的符號(hào)串。例子：<標(biāo)識(shí)符>的巴科斯范式

<標(biāo)識(shí)符>→<字母><標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母><標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字><字母>→a|b|…|z

<數(shù)字>→0|1|…|9例子：判定字符串a(chǎn)4y是<標(biāo)識(shí)符>

<標(biāo)識(shí)符><標(biāo)識(shí)符><字母>

<標(biāo)識(shí)符>y

<標(biāo)識(shí)符><數(shù)字>y

<標(biāo)識(shí)符>4y

<字母>4y

a4y2、語法圖作用：直觀、形象的描述語法規(guī)則。例子：標(biāo)識(shí)符的語法圖表示標(biāo)識(shí)符字母字母數(shù)字例子：無符號(hào)數(shù)的語法圖表示2.45E+12無符號(hào)數(shù)無符號(hào)整數(shù)數(shù)字E無符號(hào)整數(shù)3.2符號(hào)和符號(hào)串1、字母表:它是非空有窮集。例如：∑={a,b,c}或∑={1,2,3}2、符號(hào)：字母表中的元素稱為符號(hào)。3、符號(hào)串：符號(hào)的有窮序列，符號(hào)串也稱為字。用ε來表示空符號(hào)串。例如：a,ab,abc,dsfsd4、長度：符號(hào)串的長度是指該串所包含的符號(hào)個(gè)數(shù)。用|x|表示符號(hào)串x的長度。例如：|a|=1，|abn|=35、連結(jié)：設(shè)x和y為符號(hào)串，則稱xy為他們的連結(jié)。

例如：x=aa,y=bb,則xy=aabb6、空集：不含任何元素的集合,記為。7、乘積：設(shè)A和B是符號(hào)串集，則用AB表示A和B的乘積。A={a,b},B={c,d},則AB={ac,ad,bc,bd}8、方冪：設(shè)A為符號(hào)串集，則定義A0={ε}A1=AAn=An-1A例如：A={a,b}則有：A0={ε}A1={a,b}A2={aa,ab,ba,bb}9、正閉包：設(shè)A為符號(hào)串集，則用A+表示A的正閉包，其具體定義如下：A+=A1∪A2∪A3∪…例如：A={a},A+={a,aa,aaa,……}10、星閉包：設(shè)A為一集合，則定義A的星閉包為A*，其具體定義如下A*=A0∪A+例如：A={a},A*={ε,a,aa,aaa,……}一、引言

例子：y:=a+b*x

3.3文法與語言的形式定義語法：賦值語句由變量加“:=”加表達(dá)式構(gòu)成。語義：右邊表達(dá)式求值與左變量結(jié)合賦值。用途：表達(dá)式的值的保存和計(jì)算。

形式化方法：用一整套帶有嚴(yán)格規(guī)定的符號(hào)體系來描述問題的理論和方法。

表示文法需要一種工具，其中最常用的工具是所謂的巴克斯范式(BNF)。例子:

A={an|n≥1}A={a2n|n≥1}其BNF表示有：其BNF表示有：(1)

A→a|aA(1)

A→aa|aaA

(2)

A→a|Aa(2)

A→aa|Aaa例子：

A={abna|n≥1}其BNF表示有多種如下：

(1)

A→aBaB→b|Bb(2)

A→aBaB→b|bB(3)

A→aBB→ba|bB如何來描述一種語言？如果語言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個(gè)途經(jīng)：生成方式（文法）：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過程，當(dāng)輸入的一任意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”，若不屬于，要麼能停止并回答“不是”，（要麼永遠(yuǎn)繼續(xù)下去。）

文法即是生成方式描述語言的：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造.下面給出文法的定義.進(jìn)而在文法的定義的基礎(chǔ)上,給出推導(dǎo)的概念,句型、句子和語言的定義.定義文法G定義為四元組(VN，VT，P，S)其中VN為非終結(jié)符號(hào)(或語法實(shí)體，或變量)集；VT為終結(jié)符號(hào)集；P為產(chǎn)生式(也稱規(guī)則)的集合；VN，VT和P是非空有窮集。

S稱作識(shí)別符號(hào)或開始符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。VN和VT不含公共的元素，即VN∩

VT=φ用V表示VN∪

VT，稱為文法G的字母表或字匯表規(guī)則，也稱重寫規(guī)則、產(chǎn)生式或生成式，是形如α→β或α∷=β的(α，β)有序?qū)?，其中α是字母表V的正閉包V+中的一個(gè)符號(hào)，β是V*中的一個(gè)符號(hào)。α稱為規(guī)則的左部，β稱作規(guī)則的右部。文法的定義例文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號(hào)例文法G=（VN，VT，P，S） VN={標(biāo)識(shí)符，字母，數(shù)字} VT={a,b,c,…x,y,z,0,1,…,9} P={<標(biāo)識(shí)符>→<字母> <標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母> <標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字><字母>→a,…,<字母>→z<數(shù)字>→0,…,<數(shù)字>→9} S表示<標(biāo)識(shí)符>，是初始符號(hào)文法的寫法1G：S→aAb

A→abA→aAb

A→ε2G[S]：S→aAb

A→abA→aAbA→ε3G[S]：S→aAb

A→ab|aAb|ε二、文法和語言形式定義1、規(guī)則式，產(chǎn)生式

例子：

B→b|Bb

A→a|A2、文法G[Z]：規(guī)則的非空有窮集合。Z：識(shí)別符號(hào)，開始符號(hào)。V：字母表，符號(hào)集合。 例子：G[S]={S→0，S，1} V＝{S，0，1}定義3.1

文法是一個(gè)四元組G(VN，VT，P，Z)。非終極符集記為VN(大寫字母)終極符集記為VT(小寫字母)產(chǎn)生式集記為P初始符記為Z例子：自然數(shù)G1(VN,VT,P,Z)和標(biāo)識(shí)符G2(VN,VT,P,I) VN={N,D} VT={0,1,2,9} P={N→D|ND,D→0|1|2||9}G1：N→D|NDD→0|1|2||9標(biāo)識(shí)符G2(VN,VT,P,I) VN={I,D,L} VT={0,1,2,9,a,b…z} P={I→L|IL|ID, L→a|b|…|zD→0|1|2||9}G2：I→L|IL|IDL→a|b|c||zD→0|1|2||9定義3.21、直接推導(dǎo)：設(shè)x和y是符號(hào)串，若用一次產(chǎn)生式可從x導(dǎo)出y，則稱y為x的直接推導(dǎo)，并記為xy。

例子：x=Ab,y=ab,A→a,Abab2、推導(dǎo)：若用若干次產(chǎn)生式可從x串導(dǎo)出y串，則稱y為x的推導(dǎo)，并記為xy。+

例子：X=AB,A→a,B→bABaBab即：ABab

+*3、星推導(dǎo):xy(當(dāng)且僅當(dāng)x=y或xy)。

例子：ABAB0步

ABaB1步

ABab2步即：ABab

+*+4、句型：稱x為句型，若有Zx，其中Z是文法的開始符。凡是由初始符推出的任意符號(hào)集合叫句型。例子：Z→AB,A→a,ZaB5、句子:稱x為句子，若有Zx，且x中不包含非終極符的句型。不包含非終極符的句型叫句子。***

例子：G[S]:S→0S1S→01 解: S0S100S11000111 所以有: S={01,0011,000111…}L(G)={0n1n|n≥1}6、語言:所有句子的集合稱為語言。設(shè)是G給定文法，Z是開始符，則語言L(G)可描述如下：定義3.3設(shè)G1,G2為給定文法，如果L(G1)=L(G2),則稱G1和G2等價(jià)。L(G)=｛x|Zx,x∈VT*｝

*例1已知文法求語言并判斷是否等價(jià)G1=(VN,VT,P,A)G2=(VN,VT,P,Z)VN={A}VN={A,B}VT={a,b}VT={a,b}P={A→ab}P={A→Bb,B→a}A1ab L(G1)={ab}A2Bbab

L(G2)={ab}G1與G2是等價(jià)的。例2:G3[S]:S→A|S-AA→a|b|cG4[S]:S→A|A-SA→a|b|c推導(dǎo)過程如下：SS-ASS-AAabcS-AS-A-AA-A-Aa-b-cG3與G4等價(jià)，但G3與G4的語義不同。推導(dǎo)過程如下：SA-SSA-SAA-SA-A-SA-A-Aa-b-cabca-b-c和a-b-c文法的等價(jià)若L（G1）=L（G2），則稱文法G1和G2是等價(jià)的。

如文法G1[A]：A→0R與G2[S]：S→0S1等價(jià)A→01S→01R→A1定義3.4

0型文法(短語結(jié)構(gòu)文法):產(chǎn)生式為：α→β，其中α和β是符號(hào)串。

1型文法(上下文有關(guān)文法)：產(chǎn)生式為：αAβ→αuβ，其中A∈VN，u為非空串。

2型文法(上下文無關(guān)文法):A→β，其中A∈VN，β為非空串。3.4文法的類型

3型文法(正則文法):產(chǎn)生式為：A→a,A→bB,其中A,B∈VN,#a,b∈VT是符號(hào)串。例子:

G[Z]:Z→a

Z→aA

A→b|bB

B→b

所以:G[Z]是3型文法文法的類型例：1型（上下文有關(guān)）文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD文法的類型例：2型（上下文無關(guān)）文法

文法G[S]： S→AB A→BS|0 B→SA|1

3型文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT I→l T→lT

T→dT

T→l

T→d

文法的類型2型文法1型文法0型文法四種文法之間的逐級(jí)“包含”關(guān)系3型文法文法和語言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）

文法和語言四種文法之間的關(guān)系是將產(chǎn)生式做進(jìn)一步限制而定義的。語言之間的關(guān)系依次：有不是上下文有關(guān)語言的0型語言，有不是上下文無關(guān)語言的1型語言，有不是正則語言的上下文無關(guān)語言。 根據(jù)形式語言理論,文法和識(shí)別系統(tǒng)間有這樣的關(guān)系0型文法（短語結(jié)構(gòu)文法）的能力相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的。1型文法（上下文有關(guān)文法）：產(chǎn)生式的形式為α1Aα2→α1βα2，即只有A出現(xiàn)在α1和α2的上下文中時(shí)，才允許β取代A。其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。3型文法（正規(guī)文法RG）：產(chǎn)生的語言是有窮自動(dòng)機(jī)（FA）所接受的集合

2型文法（上下文無關(guān)文法CFG）：產(chǎn)生式的形式為A→β，β取代A時(shí)與A的上下文無關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。

3型文法產(chǎn)生的語言是有窮自動(dòng)機(jī)（FA）所接受的集合.定理

設(shè)G=（VN，VT，P，S）是3型文法，則存在一個(gè)有窮自動(dòng)機(jī)M=(K,∑,f,A,Z)，使得L(M)=L(G)有窮自動(dòng)機(jī)NFAM這樣構(gòu)造：·∑=VT·K=VN∪{N},N為一個(gè)新狀態(tài),它不在VN中·A=S·Z={N}·對(duì)G中的形如D→tB的產(chǎn)生式,t為終結(jié)符或ε,有f(D,t)=B；對(duì)G中形如D→t的產(chǎn)生式，t為終結(jié)符或ε,有f(D,t)=N;

對(duì)VT中的每一個(gè)a,有f(N,a)=φG［Ｓ］：S→aA|bB

A→bB|aD|aB→aA|bD|bD→aD|bD|a|bBASaaabbba,bDZabab使其右部為空字符串的產(chǎn)生式，稱為空產(chǎn)生式。產(chǎn)生式記為A→或A→例子:G[S]:S→AaBA→AB|B→bB| 所以:G[S]含有空產(chǎn)生式定義3.5

直接左遞歸：若有產(chǎn)生式A→A…

直接右遞歸：若有產(chǎn)生式A→…A

左遞歸：若有推導(dǎo)式A

A…

右遞歸：若有推導(dǎo)式A…A

遞歸：若有產(chǎn)推導(dǎo)A…A…

+++例子： 直接遞歸：A→AaB→aBB 左遞歸：S→Qc|cQ→Rb|bR→Sa|a QRbSabQcab QQcab規(guī)范推導(dǎo)和句柄定義3.6

設(shè)xUyxuy是一直接推導(dǎo)。如果U是句型xUy中的最右非終極字符，則稱該推導(dǎo)為規(guī)范直接推導(dǎo)并記為xUy

xuy。如果xy中的每步都是規(guī)范直接推導(dǎo)，則稱該推導(dǎo)為規(guī)范推導(dǎo)并記為xy。

r+r+3.5上下無關(guān)文法及其語法樹如果每步都是最右非終極字符，則也稱該規(guī)范推導(dǎo)為最右推導(dǎo)。例子：G[S]：S→ABA→Aa|bBB→a|Sb SABbBBbaB(最左推導(dǎo)) SABASbAABbAAabAbBab(最右推導(dǎo))

SABASbbBSbbaSb(非左非右)語法樹與二義性定義3.8設(shè)G=(VN,VT,P,S)是給定文法,則稱滿足下面條件的樹為G的一棵語法樹。

每個(gè)結(jié)點(diǎn)都標(biāo)有G的一個(gè)文法符號(hào),且根結(jié)點(diǎn)標(biāo)有初始符S,非葉結(jié)點(diǎn)標(biāo)有非終極符。如果一個(gè)非葉結(jié)點(diǎn)A有n個(gè)兒子結(jié)點(diǎn)(從左到右)B1,B2,…,Bn,則A→B1B2…,Bn一定是G的一個(gè)產(chǎn)生式。定義3.9

由某一結(jié)點(diǎn)及其所屬分枝組成的部分樹稱為原樹的一棵子樹。

只有單層分枝的子樹稱為簡單子樹。例子：Z→ABA→aB→bcSABacb定義3.7

假設(shè)Z

xUy，U

u，則稱句型xuy中的u為該句型的短語，其中Z為初始符。

假設(shè)有ZxUy，Uu，則稱句型xuy中的u為該句型的簡單短語。

最左邊的簡單短語稱為句柄。

*+*3.6句型的分析例子：G[S]：S→ABA→AaA→bBB→aB→Sb

解：SABbBBbaBbaSbyBSbuxUU

Sb是句型baSb的短語，簡單短語SbaB*解：SABASbbBSbbaSbyBauxU

a是句型baSb的短語，且是簡單短語。USbBSb*yuxU

ba是句型baSb的短語，但不是簡單短語。所以：ba,a,Sb是句型baSb的短語a,Sb是句型baSb的簡單短語a是句型baSb的句柄。 USASb*Aba＋解：SABASbbBSbbaSb定理3.11、每個(gè)句型都有一棵語法樹，每個(gè)語法樹的葉組成一句型。2、每棵子樹的葉組成短語，每棵簡單子樹的葉組成簡單短語，最左簡單子樹的葉組成句柄。3、用語法樹可證明每個(gè)句子都有一規(guī)范推導(dǎo)。構(gòu)造語法樹G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

EEE+TE+TTEE+TTFEE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*F

a+F*Fa+F*aa+a*a

EE+TTT*FFFaaa看不出句型中的符號(hào)被替代的順序例子：G[S]：S→ABA→Aa|bBB→a|Sb

字符串：bBABb短語：bB,AB,ABb簡單短語：bB,AB句柄：bBSABbBbSBA上下文無關(guān)文法的語法樹的用處用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

a句型aabbaa的語法樹（推導(dǎo)樹）葉子結(jié)點(diǎn)：樹中沒有子孫的結(jié)點(diǎn)。

從左到右讀出推導(dǎo)樹的葉子標(biāo)記連接成的文法符號(hào)串，為G[S]的句型。也把該推導(dǎo)樹稱為該句型的語法樹。上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa一棵語法樹表示了一個(gè)句型的種種可能的(但未必是所有的)不同推導(dǎo)過程，包括最左(最右)推導(dǎo)。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語法樹呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?例：G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i定義3.10如果一個(gè)文法G存在某個(gè)句子,使得它有兩棵語法樹,則稱G為二義性文法。例子：證明G:E→E+E|E*EE→(E)|i是二義性文法。

因?yàn)榫渥觟+i*i具有兩棵語法樹分別如圖所示。EEE+i*EEiiEEE+i*EEii例子：證明G[S]:S→IfBThenSS→IfBThenSElseS是二義性文法。IfB1ThenIfB2ThenS2ElseS3

該句子具有二義性(其中S表示語句，Sx無條件語句，Bx表示布爾變量)，分析情況如下：IfB1ThenIfB2ThenS2ElseS3Ifx>1thenifx>2theny:=aelsey:=b解釋1:Ifx>1thenifx>2theny:=aelsey:=b解釋2:Ifx>1thenifx>2theny:=aelsey:=bIfB２ThenS２ElseS３SIfB１ThenS１第一種：IfB1ThenIfB2ThenS2ElseS3第二種：IfB１ThenS１ElseS３SIfB２ThenS２IfB1ThenIfB2ThenS2ElseS3改寫文法如下：S→M|UM→IfBThenMElseM|S1U→IfBThenS|IfBThenMElseU怎樣排除二義性：語義上限制。改寫文法。M為匹配語句，U為非匹配語句。得到語法樹如下：UIfB１ThenSSIfB２ThenS２ElseMMS33.7有關(guān)文法實(shí)用中的一些說明文法中不含有有害規(guī)則和多余規(guī)則有害規(guī)則：形如U→U的產(chǎn)生式。會(huì)引起文法的二義性多余規(guī)則：指文法中任何句子的推導(dǎo)都不會(huì)用到的規(guī)則文法中不含有不可到達(dá)和不可終止的非終結(jié)符1）文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，該非終結(jié)符稱為不可到達(dá)。2）文法中某些非終結(jié)符，由它不能推出終結(jié)符號(hào)串，該非終結(jié)符稱為不可終止。1.文法中不含有A→A的規(guī)則

例:S→0S1|01無二義性,可以改為:S→0S1|01|S句子0011有二義性。S0S101S0S101SS0S101S

2.文法中不包含多余規(guī)則

①不可到達(dá)：所有推導(dǎo)均不會(huì)用到此規(guī)則

②不可終止：推導(dǎo)不出終結(jié)符號(hào)串例子:文法G[S]：(1)S→Be(5)A→e(2)B→Ce不可終止(6)C→Cf不可終止(3)B→Af(7)D→f不可達(dá)(4)A→Ae對(duì)文法G=(VN,VT,S,P),為了保證其任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn),必須滿足如下兩個(gè)條件：

1.A必須在某句型中出現(xiàn)。即有SαAβ,其中α,β屬(VT∪VN)*。

2.必須能夠從A推出終結(jié)符號(hào)串t來。即At,其中t∈VT*。 因此檢查文法是否包含多余規(guī)則是很有必要的。*+3.9文法的等價(jià)轉(zhuǎn)變換定理3.2

對(duì)任一文法G1都可以構(gòu)造文法G2使得L(G1)=L(G2)，并且G2有這樣的特點(diǎn)，即文法的初始符不出現(xiàn)于產(chǎn)生式的右部。例子：G:E→E+E|E*E|(E)|i可改寫為：G:E’→EE→E+E|E*E|(E)|i

定理3.3

對(duì)任一文法G1都可以構(gòu)造文法G2使得L(G1)=L(G2)，并且G2的每個(gè)非終極符出現(xiàn)于某句型中。

定理3.4對(duì)任一文法G1均可構(gòu)造文法G2使得L(G1)=L(G2)，且在G2中沒有形如A→B的產(chǎn)生式,其中B∈VN。證明：我們稱形如A→B的產(chǎn)生式為特型產(chǎn)生式。G2的構(gòu)造算法是： 1、對(duì)每個(gè)A∈VN，求βA={D|AD,D∈VN} 2、令G1中所有的非特型產(chǎn)生式為G2的產(chǎn)生式。 3、若有D∈βA，且有D→x(非特型)，則令A(yù)→x∈G2 4、刪除無用的產(chǎn)生式。*例子：G[A]:A→B|aB→b求解如下： 保留：A→aB→b 擴(kuò)充：A→BB→b

A→b G[A]：A→a|bB→b(多余) G[A]:A→a|b例子：設(shè)有如下文法G1：A→B|dDB→A|C|bC→B|cD→d|DaA→BA→BB→A

A→AA→BB→