高級(jí)語(yǔ)言及其語(yǔ)法描述

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

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

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

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

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

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

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

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

。用

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

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

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

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

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

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

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

β（αＡβ直接推出αγ

β），當(dāng)且僅當(dāng)Ａ－＞γ是一個(gè)產(chǎn)生式，且α，β∈（ＶＴ∪ＶＮ）*（Ｅ＋Ｅ）->（ｉ＋Ｅ）Ｅ->ｉ2.3.1上下文無(wú)關(guān)文法第46頁(yè),共86頁(yè)，2024年2月25日，星期天例子Ｅ＝＞（Ｅ）＝＞（Ｅ＋Ｅ）＝＞（ｉ＋Ｅ）＝＞（ｉ＋ｉ）因?yàn)樗杂校海牛剑荆ǎ椋椋?2.3.1上下文無(wú)關(guān)文法第47頁(yè),共86頁(yè)，2024年2月25日，星期天語(yǔ)言的定義假定G是一個(gè)文法，S是它的開(kāi)始符號(hào)。如果S

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

2.3.1上下文無(wú)關(guān)文法第48頁(yè),共86頁(yè)，2024年2月25日，星期天例子例如：終結(jié)符號(hào)串（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)從開(kāi)始符號(hào)E至（i*i+i)的一個(gè)推導(dǎo)。而E,(E),(E*E+E)等是文法的句型。2.3.1上下文無(wú)關(guān)文法第49頁(yè),共86頁(yè)，2024年2月25日，星期天

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

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

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

求語(yǔ)言L(G).

解：

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

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

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

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

圖2.2語(yǔ)法樹(shù)E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)黑板演示過(guò)程E(E)(E+E)(E+i)=>(E*E+i)=>(E*i+i)=>(i*i+i)

2.3.2語(yǔ)法分析樹(shù)與二義性第58頁(yè),共86頁(yè)，2024年2月25日，星期天語(yǔ)法樹(shù)的意義語(yǔ)法樹(shù)表示了一個(gè)句型種種的可能的（但未必是所有的）不同推導(dǎo)過(guò)程，包括最左推倒和最右推導(dǎo)．一個(gè)語(yǔ)法樹(shù)是這些不同推導(dǎo)過(guò)程的共性抽象，是它們的代表．如果我們堅(jiān)持使用最左（最右）推導(dǎo)，這種等價(jià)性包括樹(shù)的步步成長(zhǎng)和推導(dǎo)的步步展開(kāi)之間的完全一致．2.3.2語(yǔ)法分析樹(shù)與二義性第59頁(yè),共86頁(yè)，2024年2月25日，星期天討論

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

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

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

*P.

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

VT*,使得P

+

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

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

(VNVT)*且至少有一個(gè)非終結(jié)符，而(VNVT)*。0型文法也稱短語(yǔ)文法。0型文法的能力相當(dāng)于圖靈機(jī)，是遞歸可枚舉的2.3.3形式語(yǔ)言鳥(niǎo)瞰第77頁(yè),共86頁(yè)，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→ε}對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)，0型文法有