高級語言及其語法描述第一頁，共八十六頁，編輯于2023年，星期二2.2.4語句與控制結(jié)構(gòu)第二頁，共八十六頁，編輯于2023年，星期二一表達(dá)式概念一個(gè)表達(dá)式是由運(yùn)算量（亦稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。X+Y二元算符左運(yùn)算量右運(yùn)算量2.2.4語句與控制結(jié)構(gòu)第三頁，共八十六頁，編輯于2023年，星期二運(yùn)算符一元算符前綴:一元算符寫在運(yùn)算量的前面例子:-X,ヮB后綴:一元算符寫在運(yùn)算量的后面例子:P↑既是一元算符又是二元算符“-”二元算符中綴:二元算符寫在兩個(gè)運(yùn)算量之間例子:X+Y前綴:二元算符寫在兩個(gè)運(yùn)算量之前例子:+XY后綴:二元算符寫在兩個(gè)運(yùn)算量之后例子:XY+2.2.4語句與控制結(jié)構(gòu)第四頁，共八十六頁，編輯于2023年，星期二表達(dá)式的形成規(guī)則（1）變量（包括下標(biāo)變量）、常數(shù)是表達(dá)式；（2）若E1、E2為表達(dá)式，θ為二元算符，則E1θE2為表達(dá)式(一般用中綴形式)；（3）若E為表達(dá)式，θ為一元算符，則θE(或Eθ)為表達(dá)式；（4）若E為表達(dá)式，則（E)是表達(dá)式。例子2.2.4語句與控制結(jié)構(gòu)第五頁，共八十六頁，編輯于2023年，星期二例子1X1+x(1+x)-(1+x)2.2.4語句與控制結(jié)構(gòu)第六頁，共八十六頁，編輯于2023年，星期二表達(dá)式的運(yùn)算順序和結(jié)合性與通常的數(shù)學(xué)習(xí)慣一致例如:先乘除后加減,乘冪更優(yōu)先結(jié)合性對于同級算符,先左后右(左結(jié)合)或先右后左(右結(jié)合)2.2.4語句與控制結(jié)構(gòu)第七頁，共八十六頁，編輯于2023年，星期二練習(xí)X+Y*ZX-Y-ZX-Y+ZX**Y**ZX+++Y2.2.4語句與控制結(jié)構(gòu)第八頁，共八十六頁，編輯于2023年，星期二

在多數(shù)語言中算術(shù)算符和邏輯算符的優(yōu)先順序一般規(guī)定如下：乘冪（**或↑）一元負(fù)（-）乘、除（*，/，÷）加、減（+，-）關(guān)系符（<,=,>,<=,<>,>=)非（﹁，not,或.NOT.)與（∧，&,and或.AND.)或（∨，∣，or或.OR.)隱含（或imp)等值（≡,～或equi)2.2.4語句與控制結(jié)構(gòu)第九頁，共八十六頁，編輯于2023年，星期二討論:不同語言對算符優(yōu)先級和結(jié)合性的差異APL:右結(jié)合X-Y+ZX-(Y+Z)ALGOL:左結(jié)合X-Y+Z(X-Y)+ZFORTRAN:對于滿足左或右結(jié)合的算符,任取其一;對于滿足交換率的算符，左右運(yùn)算量的計(jì)算順序不加限制2.2.4語句與控制結(jié)構(gòu)第十頁，共八十六頁，編輯于2023年，星期二

算符的代數(shù)性質(zhì)（交換率、結(jié)合率和分配率）常常可用來優(yōu)化目標(biāo)程序的質(zhì)量。但是必須注意兩點(diǎn)：（1）代數(shù)性質(zhì)引用到什么程度視具體語言的不同而不同。如在ALGOL中把

A*B+C*D處理成C*D+A*B,則至少是對ALGOL不夠忠實(shí)。（2）數(shù)學(xué)上成立的代數(shù)性質(zhì)在計(jì)算機(jī)上未必完全成立。如：(A+B)+C=A+(B+C)在計(jì)算機(jī)上并不普遍成立。2.2.4語句與控制結(jié)構(gòu)第十一頁，共八十六頁，編輯于2023年，星期二不同類型的數(shù)據(jù)運(yùn)算0.5+3ALGOL允許FORTRAN禁止C++允許,但要做類型轉(zhuǎn)換2.2.4語句與控制結(jié)構(gòu)第十二頁，共八十六頁，編輯于2023年，星期二二語句不同程序語言含有不同形式和功能的各種語句。從功能上說語句大體可分:執(zhí)行性語句執(zhí)行性語句旨在描述程序的動(dòng)作。執(zhí)行性語句又可分賦值語句控制語句輸入/輸出語句.說明性語句說明性語句旨在定義不同數(shù)據(jù)類型的變量或運(yùn)算。從形式上說，語句還可分為簡單句、復(fù)合句和分程序等。2.2.4語句與控制結(jié)構(gòu)第十三頁，共八十六頁，編輯于2023年，星期二1賦值語句

我們知道，每個(gè)名字有兩方面的特征：一方面它代表一定的存儲單元，另一方面它又以該單元的內(nèi)容作為值。70weight0100Normal=(height-100)*weightWeight=802.2.4語句與控制結(jié)構(gòu)第十四頁，共八十六頁，編輯于2023年，星期二賦值語句的意義賦值語句A:=B的意義是：“把B的值送入A所代表的單元”也就是說：在賦值句中，賦值號‘：=’左右兩邊的變量名扮演著兩種不同的角色。對賦值號右邊的B我們需要的是它的值；對于左邊的A我們需要的是它們的所代表的存儲單元（的地址）。7001001000900ABA:=B2.2.4語句與控制結(jié)構(gòu)第十五頁，共八十六頁，編輯于2023年，星期二左值與右值為了區(qū)分一個(gè)名字的這兩種特征，我們把一個(gè)名字所代表的那個(gè)存儲單元（地址）稱為該名字的左值；把一個(gè)名字的值稱為該名字的右值?；仡機(jī)++的左值和右值概念2.2.4語句與控制結(jié)構(gòu)第十六頁，共八十六頁，編輯于2023年，星期二進(jìn)一步討論變量既可持有左值又持有右值常數(shù)和帶有算符的表達(dá)式一般持有右值指示器變量P,P↑既持有左值有持有右值出現(xiàn)在賦值號左邊的表達(dá)式必須持有左值出現(xiàn)在賦值號右邊的表達(dá)式只需持有右值對于出現(xiàn)在賦值號右邊表達(dá)式中的變量,我們要其右值(a=4)=28++(++a)++(a++)2.2.4語句與控制結(jié)構(gòu)第十七頁，共八十六頁，編輯于2023年，星期二(a=4)=28++(++a)++(a++)2.2.4語句與控制結(jié)構(gòu)第十八頁，共八十六頁，編輯于2023年，星期二2控制語句多數(shù)語言中所含的控制語句有：無條件轉(zhuǎn)移語句:gotoL條件語句：ifBthenSifBthenS1elseS2循環(huán)與句：whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS過程調(diào)用語句：callP(X1,X2,…,Xn)返回語句：return(E)

重要的是我們必須了解這些語句在不同語言中的不同含義。2.2.4語句與控制結(jié)構(gòu)第十九頁，共八十六頁，編輯于2023年，星期二3說明語句

說明語句旨在定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號表中，并檢查程序中名字的引用和說明是否相一致。許多說明語句沒有相應(yīng)的代碼。但有些語句，如過程說明語句，和可變數(shù)組說明語句則有相應(yīng)的目標(biāo)代碼。2.2.4語句與控制結(jié)構(gòu)第二十頁，共八十六頁，編輯于2023年，星期二4簡單句和復(fù)合句簡單句是指那些不含其它語句成分的基本句例如賦值句、goto句等。復(fù)合句則指那些句中有句的語句。例如:if(xeqy)got152.2.4語句與控制結(jié)構(gòu)第二十一頁，共八十六頁，編輯于2023年，星期二2.3程序語言的語法描述本節(jié)內(nèi)容是對高級語言中為編譯原理課程所關(guān)心特性的總結(jié)對于高級程序語言及編譯程序而言，語言的語法定義是非常重要的。本節(jié)將介紹語法結(jié)構(gòu)的形式描述問題。第二十二頁，共八十六頁，編輯于2023年，星期二首先引入幾個(gè)概念設(shè)是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)符號。上的一個(gè)符號串是指由中的符號所構(gòu)成的有窮序列。不包含符號的序列稱為空字，記為。用*表示上的所有符號串的全體，空字也包括在其中。如：若={a,b}則*={,a,b,aa,ab,bb,aaa,…}。表示不含任何元素的空集{}。這里要注意、{}和{}的區(qū)別。2.3程序語言的語法描述第二十三頁，共八十六頁，編輯于2023年，星期二*的子集U和V中的（連接）積定義為:UV={∣U&V}

即集合UV中的符號串是由U和V的符號串連接而成的。注意，一般UVVU，但（UV)W=U(VW).V自身的n次（連接）積記為：

Vn=VV…V(n個(gè)V)規(guī)定V0={}.

令：V*=V0V1V2…

稱V*是V的閉包。記V+=VV*,稱V+是V的正則包。閉包V*中的每個(gè)符號都是由V中的符號串經(jīng)有限次連接而成的。2.3程序語言的語法描述第二十四頁，共八十六頁，編輯于2023年，星期二課堂練習(xí)已知={a,b}，*={,a,b,aa,ab,bb,aaa,…}U={aa,ab}V={ba,bb}則UV＝｛aaba,aabb,abba,abbb｝U2＝UU=｛aaaa,aaab,abaa,abab｝U3＝UUU=(UU)U=｛aaaa,aaab,abaa,abab｝U=U*＝｛,aa,ab,aaaa,aaab,abaa,abab,aaaaaa…｝U+＝｛｝2.3程序語言的語法描述第二十五頁，共八十六頁，編輯于2023年，星期二2.3.1上下文無關(guān)文法文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。要求：強(qiáng)描述能力，足以描述各種不同結(jié)構(gòu)，有利于句子分析和翻譯，可自動(dòng)產(chǎn)生有效的語法分析程序所謂上下文無關(guān)文法是這樣一種文法，它所定義的語法范疇（或語法單位)是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的。例如：在程序語言中，當(dāng)碰到一個(gè)算術(shù)表達(dá)式，我們完全可以對它“就事論事”處理，而不必考慮它所處的上下文．例如：自然語言的字詞句與上下文密切關(guān)系上下文無關(guān)文法不能描述自然語言，但足以描述程序語言2.3程序語言的語法描述第二十六頁，共八十六頁，編輯于2023年，星期二例子有的句子還必須結(jié)合上下文的關(guān)系才能獲得正確的分析結(jié)果。例如，知道了上文是“狼來了”，理解下文“咬死了獵人的狗”時(shí)，就不會(huì)再有歧義；或者上文是“我爺爺年紀(jì)大了”，下文是“他只能算一個(gè)半勞力”，聯(lián)系上下文一起分析，“一個(gè)半勞力”便只剩下一種含義。

“狼來了”“我爺爺年紀(jì)大了”2.3.1上下文無關(guān)文法第二十七頁，共八十六頁，編輯于2023年，星期二例子例如：“乒乓球拍賣完了”，可以切分成“乒乓球拍賣完了”“乒乓球拍賣完了”如果沒有上下文其他的句子，恐怕誰也不知道“拍賣”在這里算不算一個(gè)詞。“乒乓球拍賣完了”“乒乓球拍賣完了”2.3.1上下文無關(guān)文法第二十八頁，共八十六頁，編輯于2023年，星期二例子：一個(gè)具體的英文例句分析請仔細(xì)閱讀課本P27頁的英文分析的例句，2.3.1上下文無關(guān)文法第二十九頁，共八十六頁，編輯于2023年，星期二直接賓語間接賓語謂語主語Hegavemeabook思考：如果你是英語老師，學(xué)生寫了這樣一個(gè)英語句子，你如何判斷該句子是對的？2.3.1上下文無關(guān)文法第三十頁，共八十六頁，編輯于2023年，星期二句型：主語謂語間接賓語直接賓語思考：假定有以下句型，如何判斷“Hegavemaabook”符合該句型如果“Hegavemaabook”符合該句型，則“Hegavemaabook”是一個(gè)正確的句子例子：常見英語句型2.3.1上下文無關(guān)文法第三十一頁，共八十六頁，編輯于2023年，星期二思考：如何判斷一個(gè)程序的語句是否正確？賦值語句變量：＝表達(dá)式X:=3.14*r*r2.3.1上下文無關(guān)文法第三十二頁，共八十六頁，編輯于2023年，星期二思考能不能將判斷一個(gè)句子是否符合一個(gè)句型的過程自動(dòng)化，使得今后可以通過編寫程序來完成這一過程？方法：建立語法規(guī)則，用程序自動(dòng)推導(dǎo)2.3.1上下文無關(guān)文法第三十三頁，共八十六頁，編輯于2023年，星期二解決方法規(guī)則推導(dǎo)2.3.1上下文無關(guān)文法第三十四頁，共八十六頁，編輯于2023年，星期二結(jié)論

定義英文句子的規(guī)則可以說是一個(gè)上下文無關(guān)文法。其中He,me,book,gave,a等，稱為終結(jié)符號；<句子>、<主語>、<謂語>等為非終結(jié)符號；這個(gè)文法最終是要定義<句子>的語法結(jié)構(gòu)，所以<句子>在這里成為開始符號；<間接賓語>→<冠詞><名詞>這種書寫形式稱為產(chǎn)生式。2.3.1上下文無關(guān)文法第三十五頁，共八十六頁，編輯于2023年，星期二歸納一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分：一組終結(jié)符號，一組非終結(jié)符，一個(gè)開始符號，以及一組產(chǎn)生式。所謂終結(jié)符號乃是組成語言的基本符號，即在程序語言中以前屢次提到的單詞符號，如基本字，標(biāo)識符，常數(shù)，算符和界符等所謂非終結(jié)符號（也稱語法變量）用來代表語法范疇。如“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“過程”等。一個(gè)非終結(jié)符代表一個(gè)一定的語法概念。因此非終結(jié)符是一個(gè)類（或集合）記號，而不是個(gè)體記號。2.3.1上下文無關(guān)文法第三十六頁，共八十六頁，編輯于2023年，星期二開始符號是一個(gè)特殊的非終結(jié)符號，它代表所定義的語言中我們最感興趣的語法范疇，這個(gè)語法范疇通常稱為“句子”。但在程序語言中我們最終感興趣的是“程序”這個(gè)語法范疇，而其他的語法范疇都只不過是構(gòu)造“程序”的一塊塊磚石。產(chǎn)生式（也稱為產(chǎn)生規(guī)則或簡稱規(guī)則）是定義語法范疇的一種書寫規(guī)則。一個(gè)產(chǎn)生式的形式是A→α,其中箭頭左邊的A是一個(gè)終結(jié)符，稱為產(chǎn)生式的左部符號；箭頭右邊的α是終結(jié)符號或與非終結(jié)符號組成的一符號串，稱為產(chǎn)生式的右部。2.3.1上下文無關(guān)文法第三十七頁，共八十六頁，編輯于2023年，星期二產(chǎn)生式是定義語法范疇的。例如：對于表達(dá)式的形成規(guī)則：“變量（包括下標(biāo)變量）、常數(shù)是表達(dá)式“可用產(chǎn)生式定義為：算術(shù)表達(dá)式→變量或算術(shù)表達(dá)式→i可用巴科斯范式表示為算術(shù)表達(dá)式：＝變量2.3.1上下文無關(guān)文法第三十八頁，共八十六頁，編輯于2023年，星期二有時(shí)需要多個(gè)產(chǎn)生式規(guī)則定義一個(gè)語法范疇例如：要定義一類含+、*的算術(shù)表達(dá)式，這個(gè)定義可以這樣給出：定義“變量是一個(gè)算術(shù)表達(dá)式；若E1和E2是算術(shù)表達(dá)式，則E1+E2、E1*E2和(E1)也是算術(shù)表達(dá)式。用產(chǎn)生式描述：E→iＥ→Ｅ＋ＥＥ→Ｅ＊ＥＥ→（Ｅ）其中Ｅ代表“算術(shù)表達(dá)式”，ｉ代表“變量”遞歸定義2.3.1上下文無關(guān)文法第三十九頁，共八十六頁，編輯于2023年，星期二上下文無關(guān)文法Ｇ的形式定義上下文無關(guān)文法是一個(gè)四元式（ＶＴ，ＶＮ，Ｓ，P）其中ＶＴ是一個(gè)非空有限集，它的每一個(gè)元素稱為終結(jié)符號；ＶＮ是一個(gè)非空有限集，它的每一個(gè)元素稱為非終結(jié)符號，ＶＴ∩ＶＮ＝；Ｓ是一個(gè)非終結(jié)符號，稱為開始符號；P是一個(gè)產(chǎn)生式（有限）集合，每個(gè)產(chǎn)生式形式是Ｐ→，其中，Ｐ∈ＶＮ，

∈（ＶＴ∪ＶＮ）＊開始符號S至少必須在某一產(chǎn)生式的左部出現(xiàn)一次。2.3.1上下文無關(guān)文法第四十頁，共八十六頁，編輯于2023年，星期二進(jìn)一步討論產(chǎn)生式縮寫若干個(gè)左部相同的產(chǎn)生式，如：Ｐ－＞ａ１Ｐ－＞ａ２．．．．．Ｐ－＞ａｎ可合并為：Ｐ－＞ａ１｜ａ２｜．．．｜ａｎ其中ai稱為侯選式箭頭讀為“定義為”直豎讀為“或”元語言符號：－＞｜2.3.1上下文無關(guān)文法第四十一頁，共八十六頁，編輯于2023年，星期二書寫約定非終結(jié)符號：大寫字母終結(jié)符號：小寫字母符號串：αβγ例子Ｅ－＞ｉ｜ＥＡＥＡ－＞＋｜＊2.3.1上下文無關(guān)文法第四十二頁，共八十六頁，編輯于2023年，星期二如何用上下文無關(guān)文法定義語言？中心思想：從文法的開始符號出發(fā)，反復(fù)連續(xù)使用產(chǎn)生式，對非終結(jié)符施行替換和展開例如：Ｅ－＞Ｅ＋Ｅ｜Ｅ＊Ｅ｜（Ｅ）｜ｉＥ－＞（Ｅ）從Ｅ可直接（一步）推出（Ｅ）用＝＞表示Ｅ＝＞（Ｅ）2.3.1上下文無關(guān)文法第四十三頁，共八十六頁，編輯于2023年，星期二例子從Ｅ推出（ｉ＋ｉ）Ｅ＝＞（Ｅ）＝＞（Ｅ＋Ｅ）＝＞（ｉ＋Ｅ）＝＞（ｉ＋ｉ）概念：將以上一系列替換序列稱為“推導(dǎo)“推導(dǎo)提供了一個(gè)證明推導(dǎo)每前進(jìn)一步必引用一條產(chǎn)生式（規(guī)則）＝＞表示僅推導(dǎo)一步2.3.1上下文無關(guān)文法第四十四頁，共八十六頁，編輯于2023年，星期二推導(dǎo)稱αＡβ=>

αγ

β（αＡβ直接推出αγ

β），當(dāng)且僅當(dāng)Ａ->γ是一個(gè)產(chǎn)生式，且α，β∈（ＶＴ∪ＶＮ）*定義推導(dǎo)如果α1=>α2=>…=>αn，則我們稱這個(gè)序列是從α1到αn的一個(gè)推導(dǎo)．如果存在a1至an的一個(gè)推導(dǎo),則稱a1推導(dǎo)出an。記a1=>an，表示從a1出發(fā)，經(jīng)過１步或若干步，可推導(dǎo)出an記a1＝＞an，表示從a1出發(fā)，經(jīng)過０步或若干步，可推導(dǎo)出an如果α＝＞β，或者α＝β，或者α＝＞β+*+*2.3.1上下文無關(guān)文法第四十五頁，共八十六頁，編輯于2023年，星期二例子（Ｅ＋Ｅ）＝＞（ｉ＋Ｅ）稱αＡβ＝＞αγ

β（αＡβ直接推出αγ

β），當(dāng)且僅當(dāng)Ａ－＞γ是一個(gè)產(chǎn)生式，且α，β∈（ＶＴ∪ＶＮ）*（Ｅ＋Ｅ）->（ｉ＋Ｅ）Ｅ->ｉ2.3.1上下文無關(guān)文法第四十六頁，共八十六頁，編輯于2023年，星期二例子Ｅ＝＞（Ｅ）＝＞（Ｅ＋Ｅ）＝＞（ｉ＋Ｅ）＝＞（ｉ＋ｉ）因?yàn)樗杂校海牛剑荆ǎ椋椋?2.3.1上下文無關(guān)文法第四十七頁，共八十六頁，編輯于2023年，星期二語言的定義假定G是一個(gè)文法，S是它的開始符號。如果S*(表示從S出發(fā)，經(jīng)0步或若干步可推出），則稱是一個(gè)句型。僅含終結(jié)符號的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為L(G).L(G)={|S+&∈VT*}

2.3.1上下文無關(guān)文法第四十八頁，共八十六頁，編輯于2023年，星期二例子例如：終結(jié)符號串（i*i+i)是文法E→E+E|E*E|(E)|ｉ(2.1)的一個(gè)句子。是因?yàn)橛蠩(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)從開始符號E至（i*i+i)的一個(gè)推導(dǎo)。而E,(E),(E*E+E)等是文法的句型。2.3.1上下文無關(guān)文法第四十九頁，共八十六頁，編輯于2023年，星期二

例考慮一個(gè)文法G1:S→bAA→aA|a它定義了一個(gè)什么語言呢？從開始符S出發(fā)，我們可以推出如下句子：

SbAbaSbAbaAbaaSbAbaA…baa…a可以寫為：L(G1)={ban|n≥1}幾個(gè)簡單文法的例子2.3.1上下文無關(guān)文法第五十頁，共八十六頁，編輯于2023年，星期二例考慮文法Ｇ２ Ｓ－＞ＡＢ Ａ－＞ａＡ｜a

Ｂ－＞ｂＢ｜ｂ解：L(G2)={ambn|m,n>=1}思考如何歸納出Ｌ（Ｇ２）2.3.1上下文無關(guān)文法第五十一頁，共八十六頁，編輯于2023年，星期二例構(gòu)造一個(gè)文法G3使

L(G3)={anbn|n≥1}

解;S→aSb|ab區(qū)別L(G2)={ambn|m,n>=1}與L(G3)={anbn|n≥1}2.3.1上下文無關(guān)文法第五十二頁，共八十六頁，編輯于2023年，星期二課堂練習(xí)例設(shè)有文法GS→P|aPPbP→ba|bQaQ→ab

求語言L(G).

解：

L(G)={ba,baba,abab,ababab…}2.3.1上下文無關(guān)文法第五十三頁，共八十六頁，編輯于2023年，星期二例子觀察下面的文法存在什么問題：文法1S→ABA→aA|aC→cB文法2S→ABA→aAB→Sb2.3.1上下文無關(guān)文法寫文法時(shí)注意不要犯錯(cuò)！第五十四頁，共八十六頁，編輯于2023年，星期二討論從一個(gè)句型到另一個(gè)句型的推導(dǎo)過程是不唯一的，例如：Ｅ＋Ｅ＝＞ｉ＋ｉ，而言，有兩個(gè)推導(dǎo)１Ｅ＋Ｅ＝＞Ｅ＋ｉ＝＞ｉ＋ｉ２Ｅ＋Ｅ＝＞ｉ＋Ｅ＝＞ｉ＋ｉ原因：對非終結(jié)符號的替換順序不同2.3.1上下文無關(guān)文法第五十五頁，共八十六頁，編輯于2023年，星期二最左推導(dǎo)和最右推導(dǎo)

為了對句子結(jié)構(gòu)進(jìn)行確定性分析，我們往往只考慮最左推導(dǎo)或最右推導(dǎo)。所謂最左推導(dǎo)是指：任何一步都是對中的最左非終結(jié)符進(jìn)行替換的。同樣，可定義最右推導(dǎo)。Ｅ＋Ｅ＝＞Ｅ＋ｉ＝＞ｉ＋ｉＥ＋Ｅ＝＞ｉ＋Ｅ＝＞ｉ＋ｉ最右推導(dǎo)最左推導(dǎo)2.3.1上下文無關(guān)文法第五十六頁，共八十六頁，編輯于2023年，星期二2.3.2語法分析樹與二義性

前面我們提到過可以用一張圖表示一個(gè)句型的推導(dǎo)，這種表示稱為語法分析樹，或簡稱語法樹。語法樹的根結(jié)由開始符號所標(biāo)記。隨著推導(dǎo)的展開，當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，這個(gè)非終結(jié)符的相應(yīng)結(jié)就產(chǎn)生了下一代新結(jié)。每個(gè)新結(jié)和其父親結(jié)間都有一條連線。在一棵語法樹生長過程中的任何時(shí)刻，所有那些沒有后代的端末結(jié)自左至右排列起來就是一個(gè)句型。第五十七頁，共八十六頁，編輯于2023年，星期二

例如對于文法（2.1)關(guān)于（i*i+i)的推導(dǎo)形成語法樹如圖2.2

圖2.2語法樹E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)黑板演示過程E(E)(E+E)(E+i)=>(E*E+i)=>(E*i+i)=>(i*i+i)

2.3.2語法分析樹與二義性第五十八頁，共八十六頁，編輯于2023年，星期二語法樹的意義語法樹表示了一個(gè)句型種種的可能的（但未必是所有的）不同推導(dǎo)過程，包括最左推倒和最右推導(dǎo)．一個(gè)語法樹是這些不同推導(dǎo)過程的共性抽象，是它們的代表．如果我們堅(jiān)持使用最左（最右）推導(dǎo)，這種等價(jià)性包括樹的步步成長和推導(dǎo)的步步展開之間的完全一致．2.3.2語法分析樹與二義性第五十九頁，共八十六頁，編輯于2023年，星期二討論

一個(gè)句型是否只對應(yīng)唯一的一棵語法樹呢？也就是說它是否只有唯一的一個(gè)最左（最右)推導(dǎo)呢？不盡然。2.3.2語法分析樹與二義性第六十頁，共八十六頁，編輯于2023年，星期二例子(文法2.1)E→E+E|E*E|(E)|ｉ（i*i+i)〔推導(dǎo)1〕E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)〔推導(dǎo)2〕E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)2.3.2語法分析樹與二義性第六十一頁，共八十六頁，編輯于2023年，星期二

圖2.2與圖2.3的不同之處在于從第二代三代過渡開始。對于前者，我們選用規(guī)則E→E+E,而后者我們選用E→E*E。這里不是同代兄弟生兒子的先后次序的不同而是生什么兒子的不同，后面的這個(gè)不同是本質(zhì)上的的差異。這意味著我們可以用兩種完全不同的辦法產(chǎn)生同一個(gè)句子。E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)問題所在：在推導(dǎo)過程中選擇產(chǎn)生式的順序不同2.3.2語法分析樹與二義性第六十二頁，共八十六頁，編輯于2023年，星期二二義性如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。也就是說，若一個(gè)文法存在某個(gè)句子，它有兩個(gè)不同的最左（最右)推導(dǎo)，則這個(gè)文法是法是二義的。2.3.2語法分析樹與二義性第六十三頁，共八十六頁，編輯于2023年，星期二文法二義性和語言的聯(lián)系可能存在兩個(gè)不同的文法Ｇ和Ｇ‘，其中一個(gè)是二義的另一個(gè)是無二義的．但可能存在Ｌ（Ｇ）＝Ｌ（Ｇ’），即兩個(gè)文法產(chǎn)生的語言是相同的．對于程序語言來說，我們希望它的文法是無二義的．這樣對其每個(gè)語句的分析是唯一的．如果我們能國控制和駕馭文法的二義性，文法的二義性的存在不一定是壞事．二義性是不可判定的（已證明），即不存在一個(gè)算法在有限步驟內(nèi)，確切地判定一個(gè)文法是否為二義的．2.3.2語法分析樹與二義性第六十四頁，共八十六頁，編輯于2023年，星期二圖示GG’L二義無二義文法語言2.3.2語法分析樹與二義性第六十五頁，共八十六頁，編輯于2023年，星期二思考：如何處理二義性？EE+EE*EEE+EE*E2.3.2語法分析樹與二義性第六十六頁，共八十六頁，編輯于2023年，星期二解決二義性的方法為無二義性尋找一組充分條件例如：假如規(guī)定文法２．１中的運(yùn)算符＋和＊的優(yōu)先順序和結(jié)合順序，就可構(gòu)造出無二義性文法2.3.2語法分析樹與二義性第六十七頁，共八十六頁，編輯于2023年，星期二例子Ｅ－＞Ｅ＋ＥＥ－＞Ｅ＊ＥＥ－＞（Ｅ）Ｅ－＞ｉＥ－＞T|Ｅ＋TT－＞F|T＊FF－＞（Ｅ）|i表達(dá)式－＞項(xiàng)｜表達(dá)式＋項(xiàng)項(xiàng)－＞因子｜項(xiàng)＊因子因子－＞（表達(dá)式）｜iＥ表達(dá)式Ｔ項(xiàng)Ｆ因子改變2.3.2語法分析樹與二義性第六十八頁，共八十六頁，編輯于2023年，星期二Ｅ－＞T|Ｅ＋TT－＞F|T＊FF－＞（Ｅ）|iＥ＝＞Ｔ＝＞F＝＞（Ｅ）＝＞（E+T）＝＞（T+T）＝＞（T*F＋T）＝＞（F*F＋T）＝＞（i*F＋T）＝＞（i*i＋T）＝＞（i*i＋F）＝＞（i*i＋i）例子2.3.2語法分析樹與二義性E→F|E+FE→F|E*FF→(E)|iＥ＝＞F＝＞（Ｅ）＝＞（E+F）＝＞（E*F+F）＝＞（F*F＋F）＝＞（i*F＋F）＝＞（i*i＋F）＝＞（i*i＋i）第六十九頁，共八十六頁，編輯于2023年，星期二E→F|E+FE→F|E*FF→(E)|iＥ＝＞F＝＞（Ｅ）＝＞（E+F）＝＞（E*F+F）＝＞（F*F＋F）＝＞（i*F＋F）＝＞（i*i＋F）＝＞（i*i＋i）Ｅ＝＞F＝＞（Ｅ）＝＞（E*F）＝＞（E+F*F）＝＞第七十頁，共八十六頁，編輯于2023年，星期二對描述程序語言的上下文無關(guān)文法的限制最后，作為描述程序語言的上下文無關(guān)文法，我們對它有幾點(diǎn)限制。（1）文法中不含任何下面形式的產(chǎn)生式：P→P因?yàn)檫@種產(chǎn)生式除了產(chǎn)生二義性外沒有任何用處。有害規(guī)則2.3.2語法分析樹與二義性第七十一頁，共八十六頁，編輯于2023年，星期二

（2）每個(gè)非終結(jié)符P必須有用處。這一方面意味著，必須存在含P的句型；也就是，從開始符號出發(fā)，存在推導(dǎo)S*P.

另一方面意味著，必須存在終結(jié)符串VT*,使得P+；也就是，對于P不存在永不終結(jié)的回路。我們以后所討論的文法均假定滿足上述兩條件。多余規(guī)則：用不著的規(guī)則。2.3.2語法分析樹與二義性第七十二頁，共八十六頁，編輯于2023年，星期二例子：找多余規(guī)則和有害規(guī)則例：文法G[S]:SBeBCe|AfAAe|eCCfDf其中Df是多余規(guī)則（用不到），CCf也是多余的（C永遠(yuǎn)推不到終結(jié)符）。同樣BCe也是多余的。2.3.2語法分析樹與二義性第七十三頁，共八十六頁，編輯于2023年，星期二例子觀察下列文法的錯(cuò)誤S→aABA→abB→baP→S2.3.2語法分析樹與二義性第七十四頁，共八十六頁，編輯于2023年，星期二例子觀察下列文法的錯(cuò)誤S→aABPA→abB→ba2.3.2語法分析樹與二義性第七十五頁，共八十六頁，編輯于2023年，星期二2.3.3形式語言鳥瞰喬姆斯基把文法分為四種類型即0型、1型、2型、3型。0行強(qiáng)于1型，1行強(qiáng)于2型，2型強(qiáng)于3型。這幾文法的差別在于對產(chǎn)生式施加不同的限制。第七十六頁，共八十六頁，編輯于2023年，星期二0型文法我們說G=(VT,VN,S,)是一個(gè)0型文法，如果它的每個(gè)產(chǎn)生式是這樣的結(jié)構(gòu)(VNVT)*且至少有一個(gè)非終結(jié)符，而(VNVT)*。0型文法也稱短語文法。0型文法的能力相當(dāng)于圖靈機(jī)，是遞歸可枚舉的2.3.3形式語言鳥瞰第七十七頁，共八十六頁，編輯于2023年，星期二0型文法例子G={Vn,Vt,S,P}Vn={S,A,B,C,D,E}Vt={a}P={S→ACaBCa→aaCCB→DBCB→EaD→DaAD→ACaE→EaAE→ε}對于程序設(shè)計(jì)語言來，0型文法有很大的隨意性，還須加以限制第七十