高級語言及其語法描述

高級語言及其語法描述2.2.4語句與控制結(jié)構(gòu)第2頁,共86頁，2024年2月25日，星期天一表達(dá)式概念一個表達(dá)式是由運算量（亦稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。X+Y二元算符左運算量右運算量2.2.4語句與控制結(jié)構(gòu)第3頁,共86頁，2024年2月25日，星期天運算符一元算符前綴:一元算符寫在運算量的前面例子:-X,ヮB后綴:一元算符寫在運算量的后面例子:P↑既是一元算符又是二元算符“-”二元算符中綴:二元算符寫在兩個運算量之間例子:X+Y前綴:二元算符寫在兩個運算量之前例子:+XY后綴:二元算符寫在兩個運算量之后例子:XY+2.2.4語句與控制結(jié)構(gòu)第4頁,共86頁，2024年2月25日，星期天表達(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)第5頁,共86頁，2024年2月25日，星期天例子1X1+x(1+x)-(1+x)2.2.4語句與控制結(jié)構(gòu)第6頁,共86頁，2024年2月25日，星期天表達(dá)式的運算順序和結(jié)合性與通常的數(shù)學(xué)習(xí)慣一致例如:先乘除后加減,乘冪更優(yōu)先結(jié)合性對于同級算符,先左后右(左結(jié)合)或先右后左(右結(jié)合)2.2.4語句與控制結(jié)構(gòu)第7頁,共86頁，2024年2月25日，星期天練習(xí)X+Y*ZX-Y-ZX-Y+ZX**Y**ZX+++Y2.2.4語句與控制結(jié)構(gòu)第8頁,共86頁，2024年2月25日，星期天

在多數(shù)語言中算術(shù)算符和邏輯算符的優(yōu)先順序一般規(guī)定如下：乘冪（**或↑）一元負(fù)（-）乘、除（*，/，÷）加、減（+，-）關(guān)系符（<,=,>,<=,<>,>=)非（﹁，not,或.NOT.)與（∧，&,and或.AND.)或（∨，∣，or或.OR.)隱含（

或imp)等值（≡,～或equi)2.2.4語句與控制結(jié)構(gòu)第9頁,共86頁，2024年2月25日，星期天討論:不同語言對算符優(yōu)先級和結(jié)合性的差異APL:右結(jié)合X-Y+ZX-(Y+Z)ALGOL:左結(jié)合X-Y+Z(X-Y)+ZFORTRAN:對于滿足左或右結(jié)合的算符,任取其一;對于滿足交換率的算符，左右運算量的計算順序不加限制2.2.4語句與控制結(jié)構(gòu)第10頁,共86頁，2024年2月25日，星期天

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

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

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

重要的是我們必須了解這些語句在不同語言中的不同含義。2.2.4語句與控制結(jié)構(gòu)第19頁,共86頁，2024年2月25日，星期天3說明語句

說明語句旨在定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號表中，并檢查程序中名字的引用和說明是否相一致。許多說明語句沒有相應(yīng)的代碼。但有些語句，如過程說明語句，和可變數(shù)組說明語句則有相應(yīng)的目標(biāo)代碼。2.2.4語句與控制結(jié)構(gòu)第20頁,共86頁，2024年2月25日，星期天4簡單句和復(fù)合句簡單句是指那些不含其它語句成分的基本句例如賦值句、goto句等。復(fù)合句則指那些句中有句的語句。例如:if(xeqy)got152.2.4語句與控制結(jié)構(gòu)第21頁,共86頁，2024年2月25日，星期天2.3程序語言的語法描述本節(jié)內(nèi)容是對高級語言中為編譯原理課程所關(guān)心特性的總結(jié)對于高級程序語言及編譯程序而言，語言的語法定義是非常重要的。本節(jié)將介紹語法結(jié)構(gòu)的形式描述問題。第22頁,共86頁，2024年2月25日，星期天首先引入幾個概念設(shè)是一個有窮字母表，它的每個元素稱為一個符號。上的一個符號串是指由中的符號所構(gòu)成的有窮序列。不包含符號的序列稱為空字，記為

。用

*表示上的所有符號串的全體，空字也包括在其中。如：若={a,b}則*={,a,b,aa,ab,bb,aaa,…}。

表示不含任何元素的空集{}。這里要注意、{}和{}的區(qū)別。2.3程序語言的語法描述第23頁,共86頁，2024年2月25日，星期天

*的子集U和V中的（連接）積定義為:UV={∣U&V}

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

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

令：V*=V0V1V2

…

稱V*是V的閉包。記V+=VV*,稱V+是V的正則包。閉包V*中的每個符號都是由V中的符號串經(jīng)有限次連接而成的。2.3程序語言的語法描述第24頁,共86頁，2024年2月25日，星期天課堂練習(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程序語言的語法描述第25頁,共86頁，2024年2月25日，星期天2.3.1上下文無關(guān)文法文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。要求：強描述能力，足以描述各種不同結(jié)構(gòu)，有利于句子分析和翻譯，可自動產(chǎn)生有效的語法分析程序所謂上下文無關(guān)文法是這樣一種文法，它所定義的語法范疇（或語法單位)是完全獨立于這種范疇可能出現(xiàn)的環(huán)境的。例如：在程序語言中，當(dāng)碰到一個算術(shù)表達(dá)式，我們完全可以對它“就事論事”處理，而不必考慮它所處的上下文．例如：自然語言的字詞句與上下文密切關(guān)系上下文無關(guān)文法不能描述自然語言，但足以描述程序語言2.3程序語言的語法描述第26頁,共86頁，2024年2月25日，星期天例子有的句子還必須結(jié)合上下文的關(guān)系才能獲得正確的分析結(jié)果。例如，知道了上文是“狼來了”，理解下文“咬死了獵人的狗”時，就不會再有歧義；或者上文是“我爺爺年紀(jì)大了”，下文是“他只能算一個半勞力”，聯(lián)系上下文一起分析，“一個半勞力”便只剩下一種含義。

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

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

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

αγ

β（αＡβ直接推出αγ

β），當(dāng)且僅當(dāng)Ａ->γ是一個產(chǎn)生式，且α，β∈（ＶＴ∪ＶＮ）*定義推導(dǎo)如果α1=>α2=>…=>αn，則我們稱這個序列是從α1到αn的一個推導(dǎo)．如果存在a1至an的一個推導(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)文法第45頁,共86頁，2024年2月25日，星期天例子（Ｅ＋Ｅ）＝＞（ｉ＋Ｅ）稱αＡβ＝＞αγ

β（αＡβ直接推出αγ

β），當(dāng)且僅當(dāng)Ａ－＞γ是一個產(chǎn)生式，且α，β∈（ＶＴ∪ＶＮ）*（Ｅ＋Ｅ）->（ｉ＋Ｅ）Ｅ->ｉ2.3.1上下文無關(guān)文法第46頁,共86頁，2024年2月25日，星期天例子Ｅ＝＞（Ｅ）＝＞（Ｅ＋Ｅ）＝＞（ｉ＋Ｅ）＝＞（ｉ＋ｉ）因為所以有：Ｅ＝＞（ｉ＋ｉ）+2.3.1上下文無關(guān)文法第47頁,共86頁，2024年2月25日，星期天語言的定義假定G是一個文法，S是它的開始符號。如果S

*(表示從S出發(fā)，經(jīng)0步或若干步可推出），則稱是一個句型。僅含終結(jié)符號的句型是一個句子。文法G所產(chǎn)生的句子的全體是一個語言，將它記為L(G).L(G)={|S+&∈VT*}

2.3.1上下文無關(guān)文法第48頁,共86頁，2024年2月25日，星期天例子例如：終結(jié)符號串（i*i+i)是文法E→E+E|E*E|(E)|ｉ(2.1)的一個句子。是因為有E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)從開始符號E至（i*i+i)的一個推導(dǎo)。而E,(E),(E*E+E)等是文法的句型。2.3.1上下文無關(guān)文法第49頁,共86頁，2024年2月25日，星期天

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

SbAbaSbAbaAbaaSbAbaA…baa…a可以寫為：L(G1)={ban|n≥1}幾個簡單文法的例子2.3.1上下文無關(guān)文法第50頁,共86頁，2024年2月25日，星期天例考慮文法Ｇ２ Ｓ－＞ＡＢ Ａ－＞ａＡ｜a

Ｂ－＞ｂＢ｜ｂ解：L(G2)={ambn|m,n>=1}思考如何歸納出Ｌ（Ｇ２）2.3.1上下文無關(guān)文法第51頁,共86頁，2024年2月25日，星期天例構(gòu)造一個文法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)文法第52頁,共86頁，2024年2月25日，星期天課堂練習(xí)例設(shè)有文法GS→P|aPPbP→ba|bQaQ→ab

求語言L(G).

解：

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

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

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

例如對于文法（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語法分析樹與二義性第58頁,共86頁，2024年2月25日，星期天語法樹的意義語法樹表示了一個句型種種的可能的（但未必是所有的）不同推導(dǎo)過程，包括最左推倒和最右推導(dǎo)．一個語法樹是這些不同推導(dǎo)過程的共性抽象，是它們的代表．如果我們堅持使用最左（最右）推導(dǎo)，這種等價性包括樹的步步成長和推導(dǎo)的步步展開之間的完全一致．2.3.2語法分析樹與二義性第59頁,共86頁，2024年2月25日，星期天討論

一個句型是否只對應(yīng)唯一的一棵語法樹呢？也就是說它是否只有唯一的一個最左（最右)推導(dǎo)呢？不盡然。2.3.2語法分析樹與二義性第60頁,共86頁，2024年2月25日，星期天例子(文法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語法分析樹與二義性第61頁,共86頁，2024年2月25日，星期天

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

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

*P.

另一方面意味著，必須存在終結(jié)符串

VT*,使得P

+

；也就是，對于P不存在永不終結(jié)的回路。我們以后所討論的文法均假定滿足上述兩條件。多余規(guī)則：用不著的規(guī)則。2.3.2語法分析樹與二義性第72頁,共86頁，2024年2月25日，星期天例子：找多余規(guī)則和有害規(guī)則例：文法G[S]:SBeBCe|AfAAe|eCCfDf其中Df是多余規(guī)則（用不到），CCf也是多余的（C永遠(yuǎn)推不到終結(jié)符）。同樣BCe也是多余的。2.3.2語法分析樹與二義性第73頁,共86頁，2024年2月25日，星期天例子觀察下列文法的錯誤S→aABA→abB→baP→S2.3.2語法分析樹與二義性第74頁,共86頁，2024年2月25日，星期天例子觀察下列文法的錯誤S→aABPA→abB→ba2.3.2語法分析樹與二義性第75頁,共86頁，2024年2月25日，星期天2.3.3形式語言鳥瞰喬姆斯基把文法分為四種類型即0型、1型、2型、3型。0行強于1型，1行強于2型，2型強于3型。這幾文法的差別在于對產(chǎn)生式施加不同的限制。第76頁,共86頁，2024年2月25日，星期天0型文法我們說G=(VT,VN,S,

)是一個0型文法，如果它的每個產(chǎn)生式是這樣的結(jié)構(gòu)

(VNVT)*且至少有一個非終結(jié)符，而(VNVT)*。0型文法也稱短語文法。0型文法的能力相當(dāng)于圖靈機，是遞歸可枚舉的2.3.3形式語言鳥瞰第77頁,共86頁，2024年2月25日，星期天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è)計語言來，0型文法有