前后文無(wú)關(guān)文法和語(yǔ)言第一頁(yè)，共六十七頁(yè)，2022年，8月28日重點(diǎn)和難點(diǎn)重點(diǎn)：本章中涉及的概念和術(shù)語(yǔ)的理解文法和語(yǔ)言的形式定義難點(diǎn)：短語(yǔ)和句柄的識(shí)別二義性文法的判定第二頁(yè)，共六十七頁(yè)，2022年，8月28日2.1語(yǔ)言及其表示方法規(guī)定一種語(yǔ)言首先要規(guī)定它各種構(gòu)造成分的形式，詞匯、句子等的構(gòu)造規(guī)則及表示法。編譯原理則應(yīng)建立有關(guān)語(yǔ)言的數(shù)學(xué)化（形式化）模型，以便對(duì)程序語(yǔ)言進(jìn)行研究。第三頁(yè)，共六十七頁(yè)，2022年，8月28日定義1：相當(dāng)大的地區(qū)內(nèi)公眾所懂得并使用的“話”，以及組成這些“話”的方法的統(tǒng)一體。缺點(diǎn)：不夠形式化和精確化定義2：某一個(gè)字母表上的符號(hào)串的（句子）的集合。缺點(diǎn)：缺乏語(yǔ)言句子的結(jié)構(gòu)性組成描述，缺乏判斷任一符號(hào)串是否為合法句子判斷機(jī)制。因此，如果能刻畫(huà)一個(gè)語(yǔ)言句子，就定義了該語(yǔ)言。1、語(yǔ)言第四頁(yè)，共六十七頁(yè)，2022年，8月28日1956年，chomsky建立文法的數(shù)學(xué)模型，對(duì)形式化語(yǔ)言和自動(dòng)機(jī)理論的研究取得較大的成果。1960年。P.Nuaur和J.Boukas首先用BNF成功對(duì)ALGOL語(yǔ)言的文法進(jìn)行了描述，雖然對(duì)語(yǔ)義形式化描述不理想，但在程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述上有足夠的能力。至此，程序語(yǔ)言就有了形式化表述。第五頁(yè)，共六十七頁(yè)，2022年，8月28日枚舉（句子有限）例：L={Wearelearningcomputerscience,itisinteresting}數(shù)學(xué)表示(句子無(wú)限)例:{1,1/2,1/3,……1/n}→{1/n|n∈N}

制定有限條規(guī)則，用來(lái)產(chǎn)生所需描述語(yǔ)言中的句子全部，這些規(guī)則即文法。建立一種算法能對(duì)于任給的符號(hào)串，判別是否為給定語(yǔ)言的合法句子——自動(dòng)機(jī)理論。2、表示方法第六頁(yè)，共六十七頁(yè)，2022年，8月28日

語(yǔ)言可以看成在一個(gè)基本符號(hào)集上定義的，按一定規(guī)則構(gòu)成的一切基本符號(hào)串組成的集合。第七頁(yè)，共六十七頁(yè)，2022年，8月28日2.2文法的定義1、例：“我是大學(xué)生”是漢語(yǔ)的一個(gè)句子。〈句子〉∷=〈主語(yǔ)〉〈謂語(yǔ)〉〈主語(yǔ)〉∷=〈代詞〉｜〈名詞〉〈代詞〉∷=我｜你｜他〈名詞〉∷=王明｜大學(xué)生｜工人｜英語(yǔ)〈謂語(yǔ)〉∷=〈動(dòng)詞〉〈直接賓語(yǔ)〉〈動(dòng)詞〉∷=是｜學(xué)習(xí)〈直接賓語(yǔ)〉∷=〈代詞〉｜〈名詞〉返回第八頁(yè)，共六十七頁(yè)，2022年，8月28日∷=左端的規(guī)則由∷=右端的符號(hào)串代替：〈句子〉〈主語(yǔ)〉〈謂語(yǔ)〉

〈代詞〉〈謂語(yǔ)〉我〈謂語(yǔ)〉我〈動(dòng)詞〉〈直接賓語(yǔ)〉

我是〈直接賓語(yǔ)〉

我是〈名詞〉

我是大學(xué)生按照如下方式用它們導(dǎo)出句子：第九頁(yè)，共六十七頁(yè)，2022年，8月28日大學(xué)生〈句子〉〈主語(yǔ)〉〈謂語(yǔ)〉〈代詞〉〈動(dòng)詞〉〈直接賓語(yǔ)〉〈名詞〉我是“我大學(xué)生是”是否為<句子>?第十頁(yè)，共六十七頁(yè)，2022年，8月28日sentence–><subject><verb-phrase><object>subject–>This|Computers|Iverb-phrase–><adverb><verb>|<verb>adverb–>neververb–>is|run|am|tellobject–>the<noun>|a<noun>|<noun>noun–>university|world|cheese|liesThisisauniversity.Computersruntheworld.Iamthecheese.Inevertelllies.英語(yǔ)句子第十一頁(yè)，共六十七頁(yè)，2022年，8月28日2、文法的形式化表示符號(hào)：<>表示一個(gè)語(yǔ)法單位；∷=（–>）表示“定義為”；

|表示為“或”。文法：描述語(yǔ)言的形式結(jié)構(gòu)的規(guī)則。產(chǎn)生式，產(chǎn)生式左部，產(chǎn)生式右部第十二頁(yè)，共六十七頁(yè)，2022年，8月28日文法的一般構(gòu)成：一組終結(jié)符號(hào)：僅出現(xiàn)在產(chǎn)生式右部的符號(hào)VT；一組非終結(jié)符號(hào)：至少在產(chǎn)生式左部出現(xiàn)過(guò)一次的符號(hào)VN；一個(gè)開(kāi)始符號(hào)：特殊的非終結(jié)符，表示了定義語(yǔ)言中最感興趣的語(yǔ)法范疇。S；一組規(guī)則：P

G={VT，VN，S，P}

例如

第十三頁(yè)，共六十七頁(yè)，2022年，8月28日VN，VT和P是非空有窮集；

VN和VT不含公共的元素，即VN∩VT=φ；用V表示VN∪VT，稱文法G的字母表或字匯表；產(chǎn)生式是形如→或∷=的（，）有序?qū)Γ渲惺亲帜副鞻的一個(gè)非空符號(hào)串(V+)，是V中的一個(gè)符號(hào)串，可為空串(V*)。稱為產(chǎn)生式左部，稱作產(chǎn)生式右部。

說(shuō)明：第十四頁(yè)，共六十七頁(yè)，2022年，8月28日2.3由文法產(chǎn)生句子1、推導(dǎo)〈句子〉

〈主語(yǔ)〉〈謂語(yǔ)〉

〈代詞〉〈謂語(yǔ)〉

我〈謂語(yǔ)〉

……過(guò)程：文法的開(kāi)始符號(hào)開(kāi)始，每次把當(dāng)前串的一個(gè)非終結(jié)符號(hào)用于之對(duì)應(yīng)的產(chǎn)生式右部來(lái)代換，得到一個(gè)新符號(hào)串，稱一步推導(dǎo)。2、推導(dǎo)長(zhǎng)度第十五頁(yè)，共六十七頁(yè)，2022年，8月28日文法的作用就是用有限條規(guī)則產(chǎn)生無(wú)限多句子。某一文法產(chǎn)生的全部句子所組成的集合——該文法產(chǎn)生的語(yǔ)言。第十六頁(yè)，共六十七頁(yè)，2022年，8月28日一、基本定義1、符號(hào)：可以相互區(qū)別的記號(hào)（元素）。2、字母表：符號(hào)（元素）的非空有窮集合。3、符號(hào)串：由字母表中的符號(hào)組成的任何有窮序列。空符號(hào)串ε(沒(méi)有符號(hào)的符號(hào)串)是上的符號(hào)串。若x是上的符號(hào)串，a是的元素，則xa是上的符號(hào)串。

y是上的符號(hào)串，當(dāng)且僅當(dāng)它可以由1和2導(dǎo)出。例如：Σ={a,b}ε，a，b，aa，ab，aabba…都是上的符號(hào)串2.4有關(guān)定義和記號(hào)第十七頁(yè)，共六十七頁(yè)，2022年，8月28日4、符號(hào)串s的頭（前綴）：移走符號(hào)串s尾部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串。如：b是符號(hào)串banana的一個(gè)前綴.banana是banana前綴。

5、符號(hào)串s的尾（后綴）：刪去符號(hào)串s頭部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串。如:nana是符號(hào)串banana的一個(gè)后綴.banana是banana后綴。第十八頁(yè)，共六十七頁(yè)，2022年，8月28日6、符號(hào)串s的子串：從s中刪去一個(gè)前綴和一個(gè)后綴得到的符號(hào)串。如:ana是符號(hào)串banana的一個(gè)子串。7、符號(hào)串s的真前綴，真后綴，真子串：任何非空符號(hào)串x，是s的前綴，后綴或子串，并且sx。8、符號(hào)串的長(zhǎng)度：符號(hào)串中符號(hào)的個(gè)數(shù)。符號(hào)串s的長(zhǎng)度記為|s|。ε的長(zhǎng)度為0。對(duì)于每個(gè)符號(hào)串s，s和ε兩者都是符號(hào)串s的前綴，后綴和子串。第十九頁(yè)，共六十七頁(yè)，2022年，8月28日1、連接：符號(hào)串x、y的連接，是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串xy。如：x=ba,y=ck則xy=back有εa=aε2、方冪：符號(hào)串自身連接n次得到的符號(hào)串。

an定義為aa…aan個(gè)aa1=a,a2=aaa0=ε二、符號(hào)串的運(yùn)算第二十頁(yè)，共六十七頁(yè)，2022年，8月28日三、符號(hào)串集合若集合A中所有元素都是某字母表上的符號(hào)串，則稱A為字母表上的符號(hào)串集合。1、符號(hào)串集合乘積：兩個(gè)符號(hào)串集合A和B的乘積定義為

AB=xy|xA且yB例如：若集合A=ab，cdeB=0，1則AB=ab1，ab0，cde0，cde12、Σ的閉包：上的一切符號(hào)串（包括ε）組成的集合。記為Σ*

第二十一頁(yè)，共六十七頁(yè)，2022年，8月28日3、Σ的正閉包：上的除ε外的所有符號(hào)串組成的集合。記為Σ+例：Σ={a,b}，求Σ*和Σ＋。Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}第二十二頁(yè)，共六十七頁(yè)，2022年，8月28日Σ*包含Σ上的所有符號(hào)串，Σ+包含Σ上除空串ε外的任意符號(hào)串。第二十三頁(yè)，共六十七頁(yè)，2022年，8月28日1、語(yǔ)言：由句子組成的集合，為一符號(hào)串集合。即：字母表上的一個(gè)語(yǔ)言是上的一些符號(hào)串的集合，是*的一個(gè)子集。

L={S|S∈*}{}、{ε}都是語(yǔ)言例如：字母表Σ={a,b}

集合{w|w∈Σ*且w=anbn,n≥1}為上的一個(gè)語(yǔ)言。集合{w|w∈Σ*且w=an,n≥1}為上的一個(gè)語(yǔ)言。四、語(yǔ)言上的有關(guān)運(yùn)算第二十四頁(yè)，共六十七頁(yè)，2022年，8月28日2、語(yǔ)言“并”運(yùn)算：語(yǔ)言L和M的并為L(zhǎng)M，是一個(gè)語(yǔ)言:{w|wisinLorisinM}如：L1={a,b,…y,z}，M1={1,2…8,9}

L1M1={a,b,…y,z，1,2…8,9}設(shè)L是（上的）一個(gè)語(yǔ)言，M是（上的）一個(gè)語(yǔ)言，語(yǔ)言L和M的“并”，“交”，“差”，“連接”運(yùn)算結(jié)果是一個(gè)語(yǔ)言。第二十五頁(yè)，共六十七頁(yè)，2022年，8月28日3、語(yǔ)言L和M的連接運(yùn)算：記為L(zhǎng)?M(可簡(jiǎn)記為L(zhǎng)M)。

LM={st|s∈L且t∈M}如：L={a,b,…y,z}，M={1,2…8,9}

LM={a1,b1,…y1,z1,a2,b2…a9…z9}特別的：有L

ε=εL=L。

L的n次連接Ln=LL...L第二十六頁(yè)，共六十七頁(yè)，2022年，8月28日4、語(yǔ)言L的

閉包：記為L(zhǎng)*，L*=L0L1L2...L0=ε

，Ln=L

Ln-1=Ln-1L(n1)5、語(yǔ)言L的正

閉包：記為L(zhǎng)+，L+=L1L2L3...L+=LL*=L*L

L*=L+

ε

如：L1

={a,b,…y,z}M1={1,2…8,9}

（L1M1）={a,b,…y,z，1,2…8,9

}

（L1M1）*={a,b,…y,z，1,2…8,9,aa,1a,…,xyz,6789st..}

L1（L1M1）*={所有字母打頭的字母和數(shù)字符號(hào)串}第二十七頁(yè)，共六十七頁(yè)，2022年，8月28日練習(xí)1：L={A,B,C,……Z,a,b,c……z}D={0,1,2,3,4,5,6,7,8,9}計(jì)算：L∪D，LD，L4

，L*，L(L∪D)*，D+練習(xí)2：考慮一個(gè)文法G1:S→bAA→aA|a它定義了一個(gè)什么語(yǔ)言呢？從開(kāi)始符S出發(fā)，我們可以推出如下句子：

SbAbaSbAbaAbaaSbAbaA…baa…a可以寫為：L(G1)={ban|n≥1}第二十八頁(yè)，共六十七頁(yè)，2022年，8月28日2.5語(yǔ)言和文法的形式定義一個(gè)上下文無(wú)關(guān)文法G定義為四元組(VN，VT，P，S)其中：VN：非終結(jié)符號(hào)(或語(yǔ)法實(shí)體，或變量)集；VT：終結(jié)符號(hào)集；P：產(chǎn)生式(也稱規(guī)則)的集合；A→其中，∈(VN∪

VT)*，A∈VN

VN，VT和P是非空有窮集。

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

VT=φ

用V表示VN∪

VT

，稱為文法G的字母表或字匯表1、上下文無(wú)關(guān)文法第二十九頁(yè)，共六十七頁(yè)，2022年，8月28日例<1>文法G=（VN，VT，P，S）

VN={S},VT={0,1} P={S→0S1,S→01} S為開(kāi)始符號(hào)對(duì)此產(chǎn)生式可進(jìn)行推導(dǎo)產(chǎn)生句子。第三十頁(yè)，共六十七頁(yè)，2022年，8月28日2、推導(dǎo)直接推導(dǎo)“”

α→β是文法G的產(chǎn)生式，若有v,w滿足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*

則稱v直接推導(dǎo)到w,記作vw；也稱w直接歸約到v例：G：S→0S1，S→01

0S100S1100S11000S111000S11100001111S0S1第三十一頁(yè)，共六十七頁(yè)，2022年，8月28日例：G：S→0S1，S→01S0S100S11000S11100001111SS00S1100S11S00001111推導(dǎo)長(zhǎng)度為4

若存在v=w0w1...wn=w(n>0)

則記為vw，稱作v推導(dǎo)出w，或w歸約到v

若有vw或v=w，則記為vw

推導(dǎo)的長(zhǎng)度（長(zhǎng)度為n的推導(dǎo)）第三十二頁(yè)，共六十七頁(yè)，2022年，8月28日3、句型和句子例：G：S→0S1，S→01S0S100S11000S11100001111G的句型S，0S1，00S11，000S111，00001111G的句子00001111，01

句型

有文法G[S]，若Sx，x∈V*，則稱x是文法G的句型。

句子

有文法G[S]，若Sx，且x∈VT*，則稱x是文法G的句子。第三十三頁(yè)，共六十七頁(yè)，2022年，8月28日例：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

判斷：a+a*a是否為該文法的句子EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a句子：用符號(hào)a，+，*，(和)構(gòu)成的算術(shù)表達(dá)式第三十四頁(yè)，共六十七頁(yè)，2022年，8月28日4、語(yǔ)言由文法G生成的語(yǔ)言記為L(zhǎng)(G)，它是文法G的一切句子的集合:語(yǔ)言中的每個(gè)句子可以由上下文無(wú)關(guān)文法的開(kāi)始符號(hào)產(chǎn)生。例：G=（{0，1}，{S}，S，P）

P:S→0S1，S→01L(G)={0n1n|n≥1}L(G)={x|Sx，S為文法的開(kāi)始符號(hào)，且x∈VT*}第三十五頁(yè)，共六十七頁(yè)，2022年，8月28日G生成的每個(gè)串都在L(G)中，L(G)中的每個(gè)串確實(shí)能被G生成。文法所產(chǎn)生的語(yǔ)言L(G)是無(wú)限語(yǔ)言，原因是所定義的文法中含有遞歸。第三十六頁(yè)，共六十七頁(yè)，2022年，8月28日5、文法的遞歸性遞歸、直接遞歸：如果文法中有形如A→γAδ的產(chǎn)生式，其中γ，δ不同時(shí)為ε，則稱產(chǎn)生式A→是直接遞歸。例：G[E]：

E→E+T|TT→T*F|F

F→(E)|aAγAδ，直接遞歸AγAδ，遞歸A稱為遞歸和直接遞歸的非終結(jié)符號(hào)若存在A

γAδ,則稱A→是遞歸的。

左遞歸、右遞歸

γ=ε，δ≠ε左遞歸

γ≠ε，δ=ε右遞歸第三十七頁(yè)，共六十七頁(yè)，2022年，8月28日直接遞歸是遞歸的一種特殊情況，如果一個(gè)語(yǔ)言是無(wú)限的，則定義此語(yǔ)法的文法必然是遞歸的。

例：語(yǔ)言L={anbbn|n1},寫出產(chǎn)生L的文法。

G[S]:SaAbAaAb|b第三十八頁(yè)，共六十七頁(yè)，2022年，8月28日從語(yǔ)法定義的角度，遞歸定義是一種較好的方式，因?yàn)樗粌H使文法形式簡(jiǎn)練，而且也給無(wú)限語(yǔ)言的有限表示提供了一種有效的方法。然而左遞歸會(huì)影響某些語(yǔ)法分析方法實(shí)現(xiàn)，因此有時(shí)需要對(duì)文法進(jìn)行等價(jià)改造，以便消除其中的左遞歸。第三十九頁(yè)，共六十七頁(yè)，2022年，8月28日6、文法的等價(jià)性

若L（G1）=L（G2），則稱文法G1和G2是等價(jià)的。

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

A→01S→01R→A1第四十頁(yè)，共六十七頁(yè)，2022年，8月28日2.6句型的分析如何表示語(yǔ)言中的句子？任給的一個(gè)符號(hào)串是否為某一文法的句子（型）？需要進(jìn)行句型分析。自頂向下：從文法的開(kāi)始符號(hào)，以給定的符號(hào)串為目標(biāo)，試圖推導(dǎo)出串。自底向上：給定符號(hào)串出發(fā)，反復(fù)用文法中有關(guān)產(chǎn)生式的左部替換當(dāng)前符號(hào)串中的相應(yīng)子串，以期最后歸約為文法開(kāi)始符號(hào)。第四十一頁(yè)，共六十七頁(yè)，2022年，8月28日例：G[E]：

E→E+T|T

T→T*F|F

F→(E)|a

E判定a+a*a是否為文法的句子？E+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a第四十二頁(yè)，共六十七頁(yè)，2022年，8月28日1、規(guī)范推導(dǎo)規(guī)范句型最左（最右）推導(dǎo)：推導(dǎo)的每一步αβ，其中α、β是句型，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換。規(guī)范推導(dǎo)：最右推導(dǎo)稱為規(guī)范推導(dǎo)。規(guī)范句型：由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。注意：文法中的每個(gè)句子都必定有最左(右)推導(dǎo)，但對(duì)于一個(gè)句型，則不一定。G[E]：E→E+T|T

T→T*F|F

F→(E)|a

對(duì)句型T+a+T的推導(dǎo)：EE+TT*F+TT*a+T第四十三頁(yè)，共六十七頁(yè)，2022年，8月28日

問(wèn)題：對(duì)于推導(dǎo)中的每一步，SαXβ,如果X→α1|α2|α3|……|αk，（α，β）∈V*，X∈VN，則面臨選哪一個(gè)αi去匹配當(dāng)前串的問(wèn)題。使用不當(dāng)易引起回溯。2、句型分析過(guò)程自頂向下分析方法

從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否為該文法的句子

S S S

c A d

c A d

a

b推導(dǎo)過(guò)程：S

cAd

cAd

cabd第四十四頁(yè)，共六十七頁(yè)，2022年，8月28日自底向上分析方法從輸入符號(hào)串開(kāi)始，逐步進(jìn)行歸約，直至歸約到文法的開(kāi)始符號(hào)。例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否該文法的句子

S

A

A

cabd

ca

bd

ca

b

d

歸約過(guò)程構(gòu)造的推導(dǎo)：cAd

cabdScAd第四十五頁(yè)，共六十七頁(yè)，2022年，8月28日在自下而上的分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，該子串稱為“可歸約串”。歸約的子串應(yīng)是當(dāng)前句型的句柄。第四十六頁(yè)，共六十七頁(yè)，2022年，8月28日3、語(yǔ)法樹(shù)和二義性語(yǔ)法樹(shù)：設(shè)G=(VN,VT,P,S)為一cfg，若一棵樹(shù)滿足下列4個(gè)條件，則此樹(shù)稱作G的語(yǔ)法樹(shù)：每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)；根的標(biāo)記是S

若某結(jié)點(diǎn)至少有一個(gè)子孫，并且該結(jié)點(diǎn)標(biāo)記為A，則A∈VN；若某結(jié)點(diǎn)標(biāo)記A，其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，…，nk，其標(biāo)記分別為A1，A2，…，Ak，那么A→A1A2，…，Ak定是P中的一個(gè)產(chǎn)生式第四十七頁(yè)，共六十七頁(yè)，2022年，8月28日語(yǔ)法樹(shù)---句型推導(dǎo)的直觀表示給定上下文無(wú)關(guān)文法G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之相關(guān)的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))

定理：G為上下文無(wú)關(guān)文法， 對(duì)于

≠ε，有S=>*

，當(dāng)且僅當(dāng)文法G有以為結(jié)果的一棵語(yǔ)法樹(shù)(推導(dǎo)樹(shù))第四十八頁(yè)，共六十七頁(yè)，2022年，8月28日例:G[S]: S→aAS A→SbA A→SS S→a A→ba句子aabbaa的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）葉子結(jié)點(diǎn)：樹(shù)中沒(méi)有子孫的結(jié)點(diǎn)。

SaASSbAaaba第四十九頁(yè)，共六十七頁(yè)，2022年，8月28日推導(dǎo)過(guò)程中使用產(chǎn)生式的順序

例:G[S]:S→aASA→SbA|SS|baS→aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa

SaASSbAaaba第五十頁(yè)，共六十七頁(yè)，2022年，8月28日一棵語(yǔ)法樹(shù)可表示一個(gè)句子的多種可能的不同推導(dǎo)過(guò)程，包括最左(最右)推導(dǎo)。

一個(gè)句子是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)?一個(gè)句子是否只有唯一的一個(gè)最左(最右)推導(dǎo)?第五十一頁(yè)，共六十七頁(yè)，2022年，8月28日例：G[E]:

E→i E→E+E E→E*E E→(E)句型i*i+i的推導(dǎo)，有兩個(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

EE+EE*Eiii

EE*EiE+Eii第五十二頁(yè)，共六十七頁(yè)，2022年，8月28日

二義性文法若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的。若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是二義的

注意：

判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的，但可以為無(wú)二義性尋找一組充分條件。第五十三頁(yè)，共六十七頁(yè)，2022年，8月28日一個(gè)文法兼有左右遞歸是導(dǎo)致二義性的最常見(jiàn)原因。二義文法改造為無(wú)二義文法

G[E]:E→iG[E]：E→T|E+T E→E+ET→F|T*F E→E*EF→（E）|i E→(E)改寫文法，消除同時(shí)存在的左右遞歸。第五十四頁(yè)，共六十七頁(yè)，2022年，8月28日4、短語(yǔ)和句柄SαAδ且A

β，則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)對(duì)于文法G[S]：

句型的短語(yǔ)

句型的直接短語(yǔ)若有A

β，則稱β是句型αβδ相對(duì)于非終結(jié)符A的直接短語(yǔ)

句型的句柄一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄第五十五頁(yè)，共六十七頁(yè)，2022年，8月28日i*i+i的短語(yǔ)、直接短語(yǔ)和句柄EE+T

TFT*F

i3

短語(yǔ)：i1*i2+i3，

i1*i2

，F(xiàn)i2

i1

，

i2

，

i3

。i1

直接短語(yǔ)：

i1

，

i2

，

i3

。句柄：i1

例：

G[E]：

E→E+T|T

T→T*F|F

F→(E)|i句型：i*i+i第五十六頁(yè)，共六十七頁(yè)，2022年，8月28日G[S]: S→aAS

S→a A→SbA A→SS A→ba句子aabbaa的最左推導(dǎo)，指出此句子的全部短語(yǔ)、各步直接推導(dǎo)所得句型的句柄、該句子的句柄

S1a1A1S3S2b1A2a2a3b2a4練習(xí)第五十七頁(yè)，共六十七頁(yè)，2022年，8月28日通過(guò)對(duì)產(chǎn)生式施加不同限制，Chomsky將文法分為四類：0型文法：對(duì)任一產(chǎn)生式α→β，有α∈V+，β∈V*;1型文法：對(duì)任一產(chǎn)生式α→β，有|β|≥|α|(α,β∈V+)，僅S→ε除外。或者形如αAβ→αγβ產(chǎn)生式,A∈VN,γ∈V+,α,β∈V*2型文法：對(duì)任一產(chǎn)生式A→β，都有A∈VNβ∈V*;3型文法：任一產(chǎn)生式的形式都為A→αB或A→α(右線性)，A→Bα或A→α（左線性）其中A∈VN

，B∈VN

，a∈VT+2.8文法的類型第五十八頁(yè)，共六十七頁(yè)，2022年，8月28日四種文法之間的逐級(jí)“包含”關(guān)系0型文法1型文法2型文法3型文法第五十九頁(yè)，共六十七頁(yè)，2022年，8月28日AhierarchyofgrammarsType0:freeorunrestrictedgrammarsThesearethemostgeneral.Productionsareoftheformu–>vwherebothuandvarearbitrarystringsofsymbolsinV,withunon-null.Therearenorestrictionsonwhatappearsontheleftorright-handsideotherthantheleft-handsidemustbenon-empty.Type1:context-sensitivegrammarsProductionsareoftheformuXw–>uvwwhereu,vandwarearbitrarystringsofsymbolsinV,withvnon-null,andXasinglenonterminal.Inotherwords,Xmaybereplacedbyvbutonlywhenitissurroundedbyuandw.第六十頁(yè)，共六十七頁(yè)，2022年，8月28日Type2:context-freegrammarsProductionsareoftheformX–>vwherevisanarbitrarystringofsymbolsinV,andXisasinglenonterminal.WhereveryoufindX,youcanreplacewithv(regardlessofcontext).Type3:regulargrammarsProductionsareoftheformX–>aorX–>aYwhereXandYarenonterminalsandaisaterminal.Thatistheleft-handsidemustbeasinglenonterminalandtheright-handsidecanbeeitherasingleterminalbyitselforwithasinglenonterminal.Thesegrammarsarethemostlimitedintermsofexpressivepower.第六十一頁(yè)，共六十七頁(yè)，2022年，8月28日例：1型（上下文有關(guān)）文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD