編譯原理前后文無(wú)關(guān)文法和語(yǔ)言

編譯原理前后文無(wú)關(guān)文法和語(yǔ)言第1頁(yè)，共90頁(yè)，2023年，2月20日，星期二所謂形式化方法，簡(jiǎn)單地說(shuō)，就是用一整套帶有嚴(yán)格規(guī)定的符號(hào)體系來(lái)描述問(wèn)題的理論和方法。用形式化方法描述的語(yǔ)言（語(yǔ)法和語(yǔ)義）便是形式語(yǔ)言。本章將從形式語(yǔ)言的角度系統(tǒng)地介紹什么是程序設(shè)計(jì)語(yǔ)言的文法、文法和語(yǔ)言的關(guān)系等問(wèn)題。本章是本課程的理論基礎(chǔ)。2023/4/16第2頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.1文法和語(yǔ)言的表示枚舉法：把該語(yǔ)言中的全部句子一一列舉出來(lái)放在一個(gè)集合內(nèi)；當(dāng)一個(gè)語(yǔ)言僅含有有限個(gè)句子時(shí)，可采用枚舉法來(lái)表示這種語(yǔ)言；語(yǔ)言的定義可以采用如下的三種方法：例如：L={Iamateacher,Youarestudents}2023/4/16第3頁(yè)，共90頁(yè)，2023年，2月20日，星期二有限條規(guī)則：用來(lái)產(chǎn)生所要描述語(yǔ)言之中的全部句子；有限條或者無(wú)限條句子；裝置（一種算法或者過(guò)程）：以某一字母表上的所有符號(hào)串作為輸入，并檢驗(yàn)或者識(shí)別這些符號(hào)串，當(dāng)一個(gè)符號(hào)串時(shí)該字母表上某給定語(yǔ)言的句子時(shí)，就接受它，反之，就拒絕接受；文法表示自動(dòng)機(jī)2023/4/16第4頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.2文法和語(yǔ)言的定義基本概念和術(shù)語(yǔ)文法和語(yǔ)言的形式定義遞歸規(guī)則和遞歸文法2023/4/16第5頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.2.1基本概念和術(shù)語(yǔ)1.字母表：元素的非空有窮集合；符號(hào)符號(hào)集2.符號(hào)串：字母表中的符號(hào)所組成的任何有窮序列；例如：{a，b，c，+，.}特別的：空符號(hào)串ε（不包含任何符號(hào)）在編譯中起非同小可的作用2023/4/16第6頁(yè)，共90頁(yè)，2023年，2月20日，星期二3.字母表∑上的符號(hào)串的遞歸定義ε是∑上的符號(hào)串；若x是∑上的符號(hào)串，且a∈∑，則xa或ax是∑上的符號(hào)串；

若y是∑上的符號(hào)串，當(dāng)且僅當(dāng)y可由（1）和（2）產(chǎn)生；特別的：εx=xε=x2023/4/16第7頁(yè)，共90頁(yè)，2023年，2月20日，星期二ε是∑上的符號(hào)串∑上的所有符號(hào)串：ε，b,c,bb，bc，cb，cc,bbb，bbc，bcb，bcc，cbb，bcb，ccb，ccc……εb和εc即b，c是∑上的符號(hào)串bb，bc，cb，cc是∑上的符號(hào)串bbb，bbc，bcb，bcc，cbb，bcb，ccb，ccc是∑上的符號(hào)串…….例如：∑={b，c}，求∑上的所有符號(hào)串2023/4/16第8頁(yè)，共90頁(yè)，2023年，2月20日，星期二4.符號(hào)串的前綴、后綴和子串：設(shè)x是一符號(hào)串，從x的尾部（頭部）刪去若干個(gè)（包括0個(gè)）符號(hào)之后所剩余下的部分稱為x的前綴（后綴）；若x的前綴（后綴）不是x本身，則稱為x的真前綴（真后綴）；從一個(gè)符號(hào)串中刪去它的一個(gè)前綴和一個(gè)后綴之后所剩下的部分稱為此符號(hào)串的子串；2023/4/16第9頁(yè)，共90頁(yè)，2023年，2月20日，星期二x的前綴：x的真前綴：x的后綴：x的真后綴：x的子串：例如：設(shè)x=abcε，a，ab，abcε，a，abε，c，bc，abcε，c，bcε，abc，ab，a，bc，b，cx=εaεbεcε2023/4/16第10頁(yè)，共90頁(yè)，2023年，2月20日，星期二6.符號(hào)串的連接和方冪：設(shè)有符號(hào)串x,y，把y的符號(hào)寫(xiě)在x的符號(hào)之后所得的符號(hào)串，叫做x與y的連接，記xy；設(shè)有符號(hào)串x，則x的n次自身連接稱為x的n次方冪，記為xn

；x0=ε例如：符號(hào)串為x=ab，則其長(zhǎng)度|x|=25.符號(hào)串的長(zhǎng)度：符號(hào)串所含符號(hào)的個(gè)數(shù)；特別的：2023/4/16第11頁(yè)，共90頁(yè)，2023年，2月20日，星期二7.符號(hào)串集合A與B的和與積：A+B={w|w∈A或w∈B}AB={xy|x∈A且y∈B}8.符號(hào)串集合的方冪：設(shè)有符號(hào)串集合A，則定義A0={ε}，A1=A，A2=AA，A3=AAA=A2A，…例如：A={a,b,c}，B={00,11}A+B={a,b,c,00,11}AB={a00,b00,c00,a11,b11,c11}2023/4/16第12頁(yè)，共90頁(yè)，2023年，2月20日，星期二9.符號(hào)串集合的正閉包：設(shè)A為符號(hào)串集合，則定義A的正閉包A+為：A+=A1∪A2∪A3∪……∪An∪……

例如：A={a,b}A＋

={a,b}∪{aa,ab,ba,bb}∪……={a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,……}2023/4/16第13頁(yè)，共90頁(yè)，2023年，2月20日，星期二10.集合A的閉包A*

：比A+多一個(gè)ε

設(shè)A為符號(hào)集合，則定義A的閉包A*為：A*=A0∪A+={ε}∪A+

；A*由A上的元素a,b構(gòu)成的所有符號(hào)串的集合；2023/4/16第14頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.2.2文法和語(yǔ)言的形式定義文法的形式定義推導(dǎo)的形式定義語(yǔ)言的形式定義2023/4/16第15頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.2.2.1文法的形式定義規(guī)則（產(chǎn)生式）：定義有序?qū)Γ║，x）記為U::＝x或U→x；x是有窮符號(hào)串規(guī)則的右部U是符號(hào)規(guī)則的左部例如：S→abc<主函數(shù)>→main（參數(shù)表）<參數(shù)說(shuō)明>(函數(shù)體)文法G[Z]：規(guī)則的非空有窮集合

Z：開(kāi)始符號(hào)（識(shí)別符號(hào)），至少在一條規(guī)則的左部出現(xiàn)；U定義為x2023/4/16第16頁(yè)，共90頁(yè)，2023年，2月20日，星期二字匯表V：規(guī)則左右部中所有符號(hào)組成的集合

非終結(jié)符號(hào)：規(guī)則左部出現(xiàn)的符號(hào)為非終結(jié)符號(hào)，組成的集合為Vn

；終結(jié)符號(hào)集合：規(guī)則中不屬于Vn的符號(hào)為終結(jié)符號(hào)，組成集合Vt

；V=VnUVt

2023/4/16第17頁(yè)，共90頁(yè)，2023年，2月20日，星期二文法的四元式表示：G=（Vn

，Vt

，P，Z）

Vn

：非終結(jié)符號(hào)集；

Vt

：終結(jié)符號(hào)集；

P：規(guī)則的集合；

Z：開(kāi)始符號(hào)；當(dāng)規(guī)則中有相同的左部時(shí)：V→x，V→y，…V→z，可以寫(xiě)成：V→x|y|…|z；2023/4/16第18頁(yè)，共90頁(yè)，2023年，2月20日，星期二例如：G=(Vn,Vt,P,S)其中Vn={S,A,B},Vt={a,b}P:S→aB|bA，A→a|aS|bAA，B→b|bS|aBBG[S]：S→aB|bA A→a|aS|bAA B→b|bS|aBB一般規(guī)定：第一條規(guī)則的左部為開(kāi)始符號(hào)

2023/4/16第19頁(yè)，共90頁(yè)，2023年，2月20日，星期二問(wèn)題： 有了文法，如何確定語(yǔ)言呢？2023/4/16第20頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.2.2.2推導(dǎo)的形式定義直接推導(dǎo)：如果U→u是G中的一條規(guī)則，而x，y∈V*，則將規(guī)則U→u用于符號(hào)串r=xUy上得到符號(hào)串w=xuy，記為：xUy=>xuy(r=>w)，稱符號(hào)串w是符號(hào)串r的直接推導(dǎo)，或符號(hào)串r直接產(chǎn)生了符號(hào)串w，稱w直接歸約到r。

V*是字匯表的閉包，即x，y是字匯表上任意的兩個(gè)字符串；如果x=ε，y=ε，則U=>u；2023/4/16第21頁(yè)，共90頁(yè)，2023年，2月20日，星期二例如：G[S]：S→aB|bA A→a|aS|bAA B→b|bS|aBBS=>aBU=>u（規(guī)則U→u,x,y均為ε）abS=>abbAxU=>xu（規(guī)則U→u,x為ab,y為ε）aB=>aaBBxU=>xu（規(guī)則U→u,x為aaB,y為ε）每一步只能替換一個(gè)非終結(jié)符號(hào)

2023/4/16第22頁(yè)，共90頁(yè)，2023年，2月20日，星期二U→u：U=>u：

規(guī)則（產(chǎn)生式），可以用到不同的場(chǎng)合；推導(dǎo)的動(dòng)作；從語(yǔ)義的角度上來(lái)講，是完全不同的。

2023/4/16第23頁(yè)，共90頁(yè)，2023年，2月20日，星期二推導(dǎo)（長(zhǎng)度為n）：設(shè)u0,u1,…,un(n>0)均為V*中的符號(hào)串，且有

r=u0=>u1=>……=>un-1=>un=w，記為rw， 則稱以上序列為長(zhǎng)度n的推導(dǎo)，也稱r產(chǎn)生w(w歸約為r)。特例：如果rw（一步或一步以上）或r=w（0步），記為rw；2023/4/16第24頁(yè)，共90頁(yè)，2023年，2月20日，星期二推導(dǎo)過(guò)程

使用規(guī)則

S=>aB

S→aB

=>abS

B→bS

=>abbA

S→bA=>abbbAA

A→bAA=>abbbaA

A→a

=>abbbaa

A→a只要符號(hào)串中存在非終結(jié)符號(hào)，推導(dǎo)就能繼續(xù)，直至符號(hào)串全部由終結(jié)符號(hào)組成，這也是為什么稱終結(jié)符和非終結(jié)符的原因。例如：文法G[S]可進(jìn)行的推導(dǎo)文法BNF表示為G[S]:S→aB|bAA→a|aS|bAAB→b|bS|aBB2023/4/16第25頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.2.2.3語(yǔ)言的形式定義句型：設(shè)有文法G[Z]，如果有Zx，x∈V*，則稱x是文法G的一個(gè)句型。句型中既含有終結(jié)符號(hào)，又包括非終結(jié)符號(hào)；凡是由開(kāi)始符號(hào)（識(shí)別符號(hào)）推導(dǎo)出來(lái)的字匯表V上的任意符號(hào)串都叫做句型；任何文法的開(kāi)始符號(hào)都是該文法的一個(gè)句型；

Zx，可以有Z=x2023/4/16第26頁(yè)，共90頁(yè)，2023年，2月20日，星期二句子：設(shè)有文法G[Z]，如果有Zx，x∈Vt*，則稱x是文法G的一個(gè)句子。也有的版本寫(xiě)成Zx

；句子是句型的一個(gè)子集；

例如：S=>bA=>bbAA=>bbaA=>bbaa句型句子2023/4/16第27頁(yè)，共90頁(yè)，2023年，2月20日，星期二語(yǔ)言L(G[Z])：文法G[Z]所產(chǎn)生的所有句子的集合，稱為文法G[Z]所定義的語(yǔ)言。

L(G[Z])={x|x∈Vt*且Zx}

2023/4/16第28頁(yè)，共90頁(yè)，2023年，2月20日，星期二文法

推導(dǎo)句型句子文法的語(yǔ)言規(guī)則非空有窮集合同一個(gè)句子可以由不同的推導(dǎo)序列推導(dǎo)出來(lái)Zx，x∈V*Zx，x∈Vt*2023/4/16第29頁(yè)，共90頁(yè)，2023年，2月20日，星期二問(wèn)題： 文法與語(yǔ)言之間存在一一對(duì)應(yīng)的關(guān)系嗎？2023/4/16第30頁(yè)，共90頁(yè)，2023年，2月20日，星期二例如：G1[A]：A→BbB→aL(G1)={ab}G2[A]：A→abL(G2)={ab}G1≠G2但L(G1)=L(G2)，稱G1和G2為等價(jià)文法

2023/4/16第31頁(yè)，共90頁(yè)，2023年，2月20日，星期二給定文法后，可以確定它的語(yǔ)言，但由語(yǔ)言寫(xiě)出它的文法是比較難的，這里形式語(yǔ)言理論可以證明兩點(diǎn)：給定一文法，就能從結(jié)構(gòu)上唯一確定其語(yǔ)言，即G→L(G)；給定一語(yǔ)言，能確定其文法，但這種文法不是唯一的，即L→G1或G2…；2023/4/16第32頁(yè)，共90頁(yè)，2023年，2月20日，星期二設(shè)G=(Vn，Vt，P，S)為一文法，并設(shè)W→xVy是P中一產(chǎn)生式，且V→β1|β2|β3……|βn是P中V的全部產(chǎn)生式；又設(shè)G1=(Vn，Vt，P1，S)是其中P1從P中刪去W→xVy，加入W→xβ1y，W→xβ2y，…W→xβny所組成的集合，則L(G1)=L(G)；2023/4/16第33頁(yè)，共90頁(yè)，2023年，2月20日，星期二問(wèn)題： 語(yǔ)言為無(wú)限集時(shí)，該用什么樣的文法來(lái)表示呢？2023/4/16第34頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.2.3遞歸規(guī)則與遞歸文法

遞歸規(guī)則：形如V→xVy，V∈Vn，左右具有相同的非終結(jié)符號(hào)的規(guī)則。V→Vy(x=ε)，左遞歸規(guī)則；V→xV(y=ε)，右遞歸規(guī)則；V→xVy(x,y≠ε)，自嵌入遞歸規(guī)則；遞歸規(guī)則是對(duì)其左部的非終結(jié)符號(hào)進(jìn)行遞歸定義2023/4/16第35頁(yè)，共90頁(yè)，2023年，2月20日，星期二文法的遞歸性：直接遞歸性：文法中至少包含一條遞歸規(guī)則；

e.g.：Z→aZb, Z→ab間接遞歸性：文法的任一非終結(jié)符號(hào)經(jīng)一步以上推導(dǎo)產(chǎn)生的遞歸性文法的遞歸性原則：文法具有直接遞歸性或間接遞歸性，否則，文法無(wú)遞歸性；2023/4/16第36頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.3句型的分析源程序的翻譯工作，基本任務(wù)不是生成句子，而是識(shí)別句子和句子的結(jié)構(gòu)，以確定一符號(hào)串是不是文法的句子；用來(lái)進(jìn)行句型分析的方法大致分為兩類(lèi)：即自頂向下的分析和自底向上的分析。

2023/4/16第37頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.3.1規(guī)范推導(dǎo)和規(guī)范規(guī)約

例如： G[<標(biāo)識(shí)符>]：

<標(biāo)識(shí)符>→<字母>|<標(biāo)識(shí)符><字母>| <標(biāo)識(shí)符><數(shù)字> <字母>→a|b|…|z|A|…|Z<數(shù)字>→0|1|2|…|9句子a4y??2023/4/16第38頁(yè)，共90頁(yè)，2023年，2月20日，星期二對(duì)句子的結(jié)構(gòu)進(jìn)行確定性的分析，往往只采用兩種特殊的推導(dǎo)方式。

最左推導(dǎo)

最右推導(dǎo)2023/4/16第39頁(yè)，共90頁(yè)，2023年，2月20日，星期二最左（右）推導(dǎo)：在任一步直接推導(dǎo)V=>w中，都是對(duì)符號(hào)串V的最左（最右）非終結(jié)符號(hào)進(jìn)行替換，稱為最左(右)推導(dǎo)。每一個(gè)句子都必定有最左推導(dǎo)和最右推導(dǎo)，但不是每一句型都有；

<標(biāo)>=><標(biāo)><字>=><標(biāo)><數(shù)><字>=><標(biāo)>4<字>

<標(biāo)>=><標(biāo)><字>=><標(biāo)><數(shù)><字>=><標(biāo)>4<字>

2023/4/16第40頁(yè)，共90頁(yè)，2023年，2月20日，星期二左（右）句型：由最左（右）推導(dǎo)所得的句型；規(guī)范推導(dǎo)：即最右推導(dǎo)；規(guī)范句型：由規(guī)范推導(dǎo)所得的句型；規(guī)范歸約：規(guī)范推導(dǎo)的逆過(guò)程，即最左歸約；

2023/4/16第41頁(yè)，共90頁(yè)，2023年，2月20日，星期二最左推導(dǎo)最右推導(dǎo)規(guī)范歸約

逆過(guò)程

逆過(guò)程最右歸約最左歸約規(guī)范推導(dǎo)推導(dǎo)2023/4/16第42頁(yè)，共90頁(yè)，2023年，2月20日，星期二自頂向下的分析：從文法的開(kāi)始符號(hào)出發(fā)，以給定的符號(hào)串為目標(biāo)，試圖推導(dǎo)出此符號(hào)串；若采用自頂向下的語(yǔ)法分析來(lái)某一符號(hào)串是否是語(yǔ)言的句子，通常的做法是為該符號(hào)串建立一個(gè)從開(kāi)始符號(hào)到此符號(hào)串的最左推導(dǎo)；2023/4/16第43頁(yè)，共90頁(yè)，2023年，2月20日，星期二如何正確選擇規(guī)則？——語(yǔ)法分析<標(biāo)>=><標(biāo)><字>=><標(biāo)><數(shù)><字>=><字><數(shù)>

<字>=>a<數(shù)><字>=>a4

<字>=>a4

y2023/4/16第44頁(yè)，共90頁(yè)，2023年，2月20日，星期二自底向上的分析：從給定的符號(hào)串出發(fā)，反復(fù)用文法中有關(guān)產(chǎn)生式的左部去替換當(dāng)前符號(hào)串中的相應(yīng)子串，從而“歸約”為文法的開(kāi)始符號(hào)；若采用自底向上的語(yǔ)法分析來(lái)某一符號(hào)串是否是語(yǔ)言的句子，通常的做法是從該符號(hào)串出發(fā)，建立一個(gè)最右推導(dǎo)；2023/4/16第45頁(yè)，共90頁(yè)，2023年，2月20日，星期二<標(biāo)>=><標(biāo)><字>

=><標(biāo)>y=><標(biāo)><數(shù)>y=><標(biāo)>4y=><字>4y=>a4y問(wèn)題：如何正確選擇可歸約串？<標(biāo)><≠<標(biāo)><字>

<≠<標(biāo)>y<≠<標(biāo)><數(shù)>y<≠<標(biāo)>4y<≠<字>4y<≠a4y2023/4/16第46頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.3.2短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄

短語(yǔ)：設(shè)ω=xuy是文法G[Z]的一個(gè)句型，其中x，y∈V*，u∈V+，如有ZxVy，且V u，V∈Vn，稱u是句型ω相對(duì)于非終結(jié)符號(hào)V的短語(yǔ)。

簡(jiǎn)單短語(yǔ)（直接短語(yǔ)）：設(shè)ω=xuy是文法G[Z]的一個(gè)句型，其中x，y∈V*，u∈V+，如有

ZxVy，且V=>u，V∈Vn，稱u是句型ω相對(duì)于非終結(jié)符號(hào)V的簡(jiǎn)單短語(yǔ)。

2023/4/16第47頁(yè)，共90頁(yè)，2023年，2月20日，星期二短語(yǔ)或簡(jiǎn)單短語(yǔ)必須是針對(duì)某一句型來(lái)說(shuō)的，并且是該句型的一個(gè)子串；短語(yǔ)或簡(jiǎn)單短語(yǔ)必須是相對(duì)某一非終結(jié)符號(hào)的；兩個(gè)條件缺一不可；一個(gè)句型可以有幾個(gè)短語(yǔ)和簡(jiǎn)單短語(yǔ)；

2023/4/16第48頁(yè)，共90頁(yè)，2023年，2月20日，星期二句柄：句型的最左簡(jiǎn)單短語(yǔ)為該句型的句柄；一句型只有一個(gè)句柄。

2023/4/16第49頁(yè)，共90頁(yè)，2023年，2月20日，星期二例如：G[S]：S→AB，

A→Aa|bB，

B→a|Sb對(duì)于句型baSb，求短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄

S=>AB=>bBB=>baB，且B=>Sb，Sb是句型baSb相對(duì)于B的短語(yǔ)，且為簡(jiǎn)單短語(yǔ)；S=>AB=>ASb，且Aba，ba是句型baSb相對(duì)于A的短語(yǔ)；S=>AB=>ASb=>bBSb，且B=>a，a是句型baSb相對(duì)于B的短語(yǔ)，且為簡(jiǎn)單短語(yǔ)；句柄2023/4/16第50頁(yè)，共90頁(yè)，2023年，2月20日，星期二利用定義來(lái)找短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄，比較抽象，下面介紹語(yǔ)法樹(shù)的概念，利用語(yǔ)法樹(shù)可以直觀地找到句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。

2023/4/16第51頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.3.3語(yǔ)法樹(shù)語(yǔ)法樹(shù)：一個(gè)句型或句子推導(dǎo)過(guò)程的圖示法表示，形成一棵語(yǔ)法樹(shù)；例如：G[S]：S→AB，

A→Aa|bB，

B→a|Sb對(duì)于句型baSb的推導(dǎo)形成的語(yǔ)法樹(shù)

2023/4/16第52頁(yè)，共90頁(yè)，2023年，2月20日，星期二推導(dǎo)1：

S=>AB=>bBB=>baB=>baSbSABbBaSbG[S]：S→AB，

A→Aa|bB，

B→a|Sb2023/4/16第53頁(yè)，共90頁(yè)，2023年，2月20日，星期二推導(dǎo)2：

S=>AB=>ASb=>bBSb=>baSbSABbBaSbG[S]：S→AB，

A→Aa|bB，

B→a|Sb2023/4/16第54頁(yè)，共90頁(yè)，2023年，2月20日，星期二SABbBaSb根：文法的開(kāi)始符號(hào)子樹(shù)：某一非終結(jié)符號(hào)(子樹(shù)的根)及其下面的分支

葉：末端結(jié)點(diǎn)

2023/4/16第55頁(yè)，共90頁(yè)，2023年，2月20日，星期二有了語(yǔ)法樹(shù)，我們就可以利用這種概念和工具直觀的確定句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。2023/4/16第56頁(yè)，共90頁(yè)，2023年，2月20日，星期二短語(yǔ)：子樹(shù)的末端結(jié)點(diǎn)形成的符號(hào)串；短語(yǔ)相對(duì)的句型：整個(gè)樹(shù)的末端結(jié)點(diǎn)；簡(jiǎn)單短語(yǔ)：簡(jiǎn)單子樹(shù)，只有一層分支的子樹(shù)；

SABbBaSb2023/4/16第57頁(yè)，共90頁(yè)，2023年，2月20日，星期二對(duì)于句型baSb共有三棵子樹(shù)，三個(gè)短語(yǔ)：ba，a，Sb簡(jiǎn)單短語(yǔ)：a，Sb句柄：aSABbBaSb2023/4/16第58頁(yè)，共90頁(yè)，2023年，2月20日，星期二從語(yǔ)法樹(shù)的角度來(lái)看歸約：

S <≠AB <≠ASb <≠bBSb <≠baSbSABbBaSbABbBaSb用產(chǎn)生式的左部替換當(dāng)前句型中的相應(yīng)子串每次歸約的都是當(dāng)前句型中的某一直接短語(yǔ)2023/4/16第59頁(yè)，共90頁(yè)，2023年，2月20日，星期二因此，最左歸約歸約的是當(dāng)前句型的句柄

歸約非常重要，因?yàn)樵闯绦蚨际欠?hào)串形式的，這就需要把它歸約為開(kāi)始符號(hào)（程序）才算正確。它是語(yǔ)法分析所采用的方法，而要想從開(kāi)始符號(hào)推導(dǎo)出你的源程序是相當(dāng)困難的（對(duì)計(jì)算機(jī)來(lái)說(shuō)，工作量非常大），因?yàn)橐话銇?lái)說(shuō)，語(yǔ)言是無(wú)窮的。2023/4/16第60頁(yè)，共90頁(yè)，2023年，2月20日，星期二對(duì)每個(gè)語(yǔ)法樹(shù)，至少存在一個(gè)推導(dǎo)；對(duì)于每個(gè)推導(dǎo)，都有一個(gè)相應(yīng)的語(yǔ)法樹(shù)（但不同的推導(dǎo)可能有相同的語(yǔ)法樹(shù)）；樹(shù)的末端結(jié)點(diǎn)形成所要推導(dǎo)的句型；

結(jié)論：相同句型也可能對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)

2023/4/16第61頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.3.4文法的二義性如果文法G的某一個(gè)句子存在兩棵或兩棵以上不同的語(yǔ)法樹(shù)，則稱句子是二義性的；如果一個(gè)文法所定義的句子中含有二義性的句子，則稱該文法是二義性的，否則該文法是無(wú)二義性的；2023/4/16第62頁(yè)，共90頁(yè)，2023年，2月20日，星期二例如：E→E+E|E*E|(E)|i句子i+i*i，同是最左推導(dǎo)，對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)：E=>E+E =>i+E =>i+E*E =>i+i*E =>i+i*i最左推導(dǎo)1：EEEiEEii+*2023/4/16第63頁(yè)，共90頁(yè)，2023年，2月20日，星期二例如：E→E+E|E*E|(E)|i句子i+i*i，同是最左推導(dǎo)，對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)：E=>E*E =>E+E*E =>i+E*E

=>i+i*E

=>i+i*i最左推導(dǎo)2：EEEEEi*i+i2023/4/16第64頁(yè)，共90頁(yè)，2023年，2月20日，星期二句柄：i,i,i,E*E,E+E表示：i+(i*i)句柄：i,i,E+E,i,E*E表示：(i+i)*iEEEiEEii+*EEEEEi*i+i語(yǔ)法樹(shù)1：語(yǔ)法樹(shù)2：2023/4/16第65頁(yè)，共90頁(yè)，2023年，2月20日，星期二文法的二義性：某一句子有二個(gè)不同的最左（右）推導(dǎo)或二個(gè)不同的最左（規(guī)范）歸約；文法的二義性是不可判定的：不存在一種算法，只能用一些簡(jiǎn)單條件來(lái)判定是充分的，不是必要的，即滿足某些條件的文法可以說(shuō)是二義性的；特例：若一文法G既含左遞歸又含右遞歸，則G必是二義性文法；

2023/4/16第66頁(yè)，共90頁(yè)，2023年，2月20日，星期二以上的分析中，忽略了兩個(gè)問(wèn)題：自頂向下分析時(shí)：如有V→x1|x2…|xn，選哪一產(chǎn)生式可一次推導(dǎo)成功？自底向上分析時(shí)，如何盡快找到當(dāng)前句型的句柄？（進(jìn)行歸約）這些問(wèn)題將在語(yǔ)法分析時(shí)解決2023/4/16第67頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.4文法的化簡(jiǎn)和改造

文法的實(shí)用限制無(wú)用符號(hào)和無(wú)用產(chǎn)生式的刪除ε-產(chǎn)生式的消除（自己看書(shū)）單產(chǎn)生式的消除（自己看書(shū)）擴(kuò)充的BNF表示2023/4/16第68頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.4.1文法的實(shí)用限制在實(shí)用中，我們將限制文法中不含有：一、無(wú)用產(chǎn)生式二、有害產(chǎn)生式2023/4/16第69頁(yè)，共90頁(yè)，2023年，2月20日，星期二無(wú)用產(chǎn)生式：一個(gè)產(chǎn)生式的左部或右部含有無(wú)用符號(hào)。2.4.1文法的實(shí)用限制設(shè)G=（Vn，Vt，P，S）是一文法，G中的符號(hào)X∈Vn∪Vt是有用的，則X必滿足：①存在α，β∈V*，有SαXβ；②存在w∈Vt*，使得αXβw；否則，稱符號(hào)X是無(wú)用的；一、無(wú)用產(chǎn)生式：至少在某一推導(dǎo)過(guò)程中出現(xiàn)由X能推出終結(jié)符號(hào)2023/4/16第70頁(yè)，共90頁(yè)，2023年，2月20日，星期二二、有害產(chǎn)生式：V→V即使V是一個(gè)有用的符號(hào)，此類(lèi)產(chǎn)生式也是不必要的；如果一個(gè)句型中含有非終結(jié)符號(hào)V，那么可以任意多次使用產(chǎn)生式V→V，這樣會(huì)引起二義性；2023/4/16第71頁(yè)，共90頁(yè)，2023年，2月20日，星期二例如：G1[S]：S→0S1|01G1無(wú)二義性文法G2[S]：S→0S1|01|S

G2二義性文法對(duì)于句子0011的語(yǔ)法樹(shù)

2023/4/16第72頁(yè)，共90頁(yè)，2023年，2月20日，星期二G2文法句子0011的兩棵不同語(yǔ)法樹(shù).SSS

0S10S1

010173第73頁(yè)，共90頁(yè)，2023年，2月20日，星期二不含無(wú)用產(chǎn)生式；不含形如V→V的產(chǎn)生式；滿足上述條件的文法稱化簡(jiǎn)過(guò)或壓縮過(guò)的文法。

2023/4/16第74頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.4.2無(wú)用符號(hào)和無(wú)用產(chǎn)生式的刪除

算法2.1：將文法G=(Vn，Vt，P，S)改造為等價(jià)文法G1=(Vn①，Vt，P①，S)，使得對(duì)于任意X∈Vn①，滿足Xw1，其中w1∈Vt*，即G1中的任一非終結(jié)符號(hào)均能推導(dǎo)出終結(jié)符號(hào)串；算法2.2：對(duì)于給定文法G改造為等價(jià)G’=(Vn’，Vt’，P’，S)，使得使得對(duì)于任意X∈Vn’∪Vt’，都存在α，β∈(Vn’∪Vt’)*，有SαXβ；

假定L(G)≠?2023/4/16第75頁(yè)，共90頁(yè)，2023年，2月20日，星期二算法2.1：①分別置Vn①，P①為?；②對(duì)于P中的每一產(chǎn)生式A→δ，若δ∈Vt*，則將A置于Vn①中；③對(duì)于P中的每一個(gè)產(chǎn)生式A→X1X2X3……Xm，若每一個(gè)Xi都屬于Vt或Vn①則將A置于Vn①中；④重復(fù)步驟③，直到Vn①不再增大為止；⑤對(duì)于P中的每一產(chǎn)生式B→Y1Y2……Yn，若B及每一個(gè)Yi都屬于Vn①∪Vt，則將此產(chǎn)生式B→Y1Y2……Yn置于P①；

2023/4/16第76頁(yè)，共90頁(yè)，2023年，2月20日，星期二算法2.2：①分別置Vn’，Vt’及P’為?；②將文法G的開(kāi)始符號(hào)S置于Vn’中；③對(duì)于G中任何形如A→α1|α2|…|αm的產(chǎn)生式，如果A∈Vn’，則將符號(hào)串α1，α2，……αm中全部的非終結(jié)符號(hào)置于Vn’中，而將其中的全部終結(jié)符號(hào)置于Vt’中；④重復(fù)步驟③，直到Vn’和Vt’都不再增大為止；⑤將P中左右部?jī)H含Vn’∪Vt’中的符號(hào)的所有產(chǎn)生式置于P’；

2023/4/16第77頁(yè)，共90頁(yè)，2023年，2月20日，星期二例如：文法G=({S，U，V，W}，{a，b，c}，P，S)P由如下的產(chǎn)生式組成：

S→aS|W|U U→a V→bV|acW→aW2023/4/16第78頁(yè)，共90頁(yè)，2023年，2月20日，星期二執(zhí)行算法2.1：①置Vn①，P①為?；②由U→a，V→ac，故Vn①={U，V}；③由S→U，則S∈Vn①，Vn①={S，U，V}，Vn①不再增大；故G1={{S，U，V}，{a，b，c}，P1，S}P1

：S→aS|UU→aV→bV|ac2023/4/16第79頁(yè)，共90頁(yè)，2023年，2月20日，星期二執(zhí)行算法2.2：①分別置Vn’，Vt’及P’為?；②Vn’={S}；③由S→aS|U，則Vn’={S，U}，Vt’={a}， 由U→a，則Vn’={S，U}不再增大，Vt’={a}不再增大

G’={S，U}，{a}，P’，S}P’：S→aS|UU→a壓縮過(guò)的文法2023/4/16第80頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.4.3ε-產(chǎn)生式、單產(chǎn)生式的消除ε-產(chǎn)生式：右部為空符號(hào)串ε的產(chǎn)生式；某些詞法分析算法要求文法不含ε-產(chǎn)生式單產(chǎn)生式：右部?jī)H含有一個(gè)非終結(jié)符號(hào)的產(chǎn)生式A→B（A，B∈Vn）；如果一個(gè)文法含有過(guò)多的單產(chǎn)生式，將會(huì)增加編譯程序在工作時(shí)所需的時(shí)間和存儲(chǔ)空間，因此必要時(shí)應(yīng)該設(shè)法消除；2023/4/16第81頁(yè)，共90頁(yè)，2023年，2月20日，星期二2.4.4擴(kuò)充的BNF表示

例如：規(guī)則中有相同的左部時(shí)：

V→x，V→y，…V→z

寫(xiě)成：V→x|y|…|z