第二章

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

常用的高級(jí)語(yǔ)言

FORTRAN 數(shù)值計(jì)算COBOL 事務(wù)處理PASCAL 結(jié)構(gòu)程序設(shè)計(jì)ADA 大型程序、嵌入式實(shí)時(shí)系統(tǒng)PROLOG 邏輯程序設(shè)計(jì)ALGOL 算法語(yǔ)言C/C++ 系統(tǒng)程序設(shè)計(jì)Java Internet程序設(shè)計(jì)與機(jī)器語(yǔ)言或匯編語(yǔ)言比較，高級(jí)語(yǔ)言的優(yōu)點(diǎn)：較接近于數(shù)學(xué)語(yǔ)言和工程語(yǔ)言，比較直觀、自然和易于理解;便于驗(yàn)證其正確性，易于改錯(cuò);編寫效率高;易于移植.2.1 程序語(yǔ)言的定義程序語(yǔ)言由兩方面定義：語(yǔ)法語(yǔ)義語(yǔ)用一.語(yǔ)法程序本質(zhì)上是一定字符集上的字符串。語(yǔ)法：一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合式(well-formed)的程序。語(yǔ)法詞法規(guī)則：?jiǎn)卧~符號(hào)的形成規(guī)則。單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等。描述工具：有限自動(dòng)機(jī)語(yǔ)法規(guī)則：語(yǔ)法單位的形成規(guī)則。語(yǔ)法單位通常包括：表達(dá)式、語(yǔ)句、分程序、過(guò)程、函數(shù)、程序等;描述工具：上下文無(wú)關(guān)文法E→i E→E+E E→E*E E→(E)語(yǔ)法規(guī)則和詞法規(guī)則定義了程序的的形式結(jié)構(gòu)。定義語(yǔ)法單位的意義屬于語(yǔ)義問(wèn)題。二.語(yǔ)義語(yǔ)義：一組規(guī)則，用它可以定義一個(gè)程序的意義。描述方法：自然語(yǔ)言描述：隱藏錯(cuò)誤、二義性和不完整性形式描述：操作語(yǔ)義(PL/1)指稱語(yǔ)義(ADA)代數(shù)語(yǔ)義(PASCAL)三．程序語(yǔ)言的基本功能和層次結(jié)構(gòu)程序語(yǔ)言的基本功能：描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。所謂程序，本質(zhì)上說(shuō)是描述一定數(shù)據(jù)的處理過(guò)程。程序的層次結(jié)構(gòu)程序|子程序或分程序、過(guò)程、函數(shù)|語(yǔ)句|表達(dá)式|數(shù)據(jù)引用算符函數(shù)調(diào)用程序語(yǔ)言每個(gè)組成成分的邏輯和實(shí)現(xiàn)意義

抽象的邏輯的意義數(shù)學(xué)意義計(jì)算機(jī)實(shí)現(xiàn)的意義具體實(shí)現(xiàn)2.2高級(jí)語(yǔ)言的一般特性

高級(jí)語(yǔ)言的分類

強(qiáng)制式語(yǔ)言(ImperativeLanguge)也稱過(guò)程式語(yǔ)言：命令驅(qū)動(dòng)，面向語(yǔ)句FORTRAN、C、Pascal，Ada應(yīng)用式語(yǔ)言（ApplicativeLanguage）：注重程序所表示的功能，而不是一個(gè)語(yǔ)句接一個(gè)語(yǔ)句地執(zhí)行LISP、ML基于規(guī)則的語(yǔ)言（Rule-basedLanguage）：檢查一定的條件，當(dāng)它滿足值，則執(zhí)行適當(dāng)?shù)膭?dòng)作Prolog面向?qū)ο笳Z(yǔ)言（Object-OrientedLanguage）：封裝性、繼承性和多態(tài)性Smalltalk，C++，Java

2.3程序語(yǔ)言的語(yǔ)法描述2.2高級(jí)語(yǔ)言的一般特性2.2.2程序結(jié)構(gòu)FORTRAN一個(gè)程序由一個(gè)主程序段和若干輔程序段組成。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。每個(gè)程序段有一系列的說(shuō)明語(yǔ)句和執(zhí)行語(yǔ)句組成。各段可以獨(dú)立編譯。模塊結(jié)構(gòu)，沒(méi)有嵌套和遞歸各程序段中的名字相互獨(dú)立，同一個(gè)標(biāo)識(shí)符在不同的程序段中代表不同的名字。主程序PROGRAM…

…end輔程序1SUBROUTINE…

…end輔程序2FUNCTION…

…endPASCALPASCAL程序本身可以看成是一個(gè)操作系統(tǒng)所調(diào)用的過(guò)程，過(guò)程可以嵌套和遞歸。一個(gè)PASCAL過(guò)程：過(guò)程頭；說(shuō)明段（由一系列的說(shuō)明語(yǔ)句組成）；begin執(zhí)行體（由一系列的執(zhí)行語(yǔ)句組成）；end作用域：一個(gè)名字能被使用的區(qū)域范圍稱作這個(gè)名字的作用域。允許同一個(gè)標(biāo)識(shí)符在不同的過(guò)程中代表不同的名字。名字作用域規(guī)則--"最近嵌套原則"一個(gè)在子程序B1中說(shuō)明的名字X只在B1中有效（局部于B1）；如果B2是B1的一個(gè)內(nèi)層子程序且B2中對(duì)標(biāo)識(shí)符X沒(méi)有新的說(shuō)明，則原來(lái)的名字X在B2中仍然有效。如果B2對(duì)X重新作了說(shuō)明，那么，B2對(duì)X的任何引用都是指重新說(shuō)明過(guò)的這個(gè)X。programmain

varA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integer)PASCAL提供了豐富的數(shù)據(jù)類型和運(yùn)算方式，它允許用戶動(dòng)態(tài)地申請(qǐng)和退還存貯空間。ADA程序包(package)：把數(shù)據(jù)和操作代碼封裝在一起，支持?jǐn)?shù)據(jù)抽象。一個(gè)程序包分為兩部分：可見的規(guī)范說(shuō)明部分，它定義了程序包外面可以訪問(wèn)的對(duì)象。程序包體，它實(shí)際定義程序包的實(shí)現(xiàn)細(xì)節(jié)。packageSTACKSistypeELEMisprivate;typeSTACKislimitedprivate;procedurepush(S:inoutSTACK;E:inELEM);procedurepop(S:inoutSTACK;E:outELEM);…endSTACK;packagebodySTACKSisprocedurepush(S:inoutSTACK;E:inELEM);begin……實(shí)現(xiàn)細(xì)節(jié)endpush;procedurepop(S:inoutSTACK;E:outELEM);begin……實(shí)現(xiàn)細(xì)節(jié)endpop;end;JAVAJava是一種面向?qū)ο蟮母呒?jí)語(yǔ)言類（Class）繼承(Inheritance)多態(tài)性(Polymorphism)和動(dòng)態(tài)綁定(Dynamicbinding)classCar{intcolor_number;intdoor_number;intspeed;

…push_break(){

…}add_oil(){

…}}

classTrash_Carextendscar{doubleamount;fill_trash(){

…}}2.2.3數(shù)據(jù)類型與操作一個(gè)數(shù)據(jù)類型通常包括以下三種要素：用于區(qū)別這種類型數(shù)據(jù)對(duì)象的屬性這種類型的數(shù)據(jù)對(duì)象可以具有的值可以作用于這種類型的數(shù)據(jù)對(duì)象的操作2.2.3數(shù)據(jù)類型與操作一．初等數(shù)據(jù)類型數(shù)值類型：整型、實(shí)型、復(fù)數(shù)、雙精度，運(yùn)算：+，-，*，/等邏輯類型：布爾運(yùn)算：∨，∧，┑字符類型：符號(hào)處理指針類型標(biāo)識(shí)符與名字標(biāo)識(shí)符：以字母開頭的，由字母數(shù)字組成的字符串。標(biāo)識(shí)符與名字兩者有本質(zhì)區(qū)別：標(biāo)識(shí)符是語(yǔ)法概念名字有確切的意義和屬性Jordan?標(biāo)識(shí)符！??標(biāo)識(shí)符與名字名字：值：?jiǎn)卧械膬?nèi)容屬性：類型和作用域名字的性質(zhì)的說(shuō)明方式：由說(shuō)明語(yǔ)句來(lái)明確規(guī)定的隱含說(shuō)明：FORTRAN以I,J,K,…N為首的名字代表整型，否則為實(shí)型。動(dòng)態(tài)確定：走到哪里，是什么，算什么二數(shù)據(jù)結(jié)構(gòu)1數(shù)組邏輯上，數(shù)組是由同一類型數(shù)據(jù)所組成的某種n維矩形結(jié)構(gòu)，沿著每一維的距離，稱為下標(biāo)。數(shù)組可變與不可變：編譯時(shí)能否確定其存貯空間的大小。訪問(wèn)：給出數(shù)組名和下標(biāo)值存放方式:按行存放,按列存放數(shù)組元素地址計(jì)算數(shù)組A[10,20]的A[1，1]為a，各維下標(biāo)為1，按行存放，那么A[i，j]地址為：a+(i-1)*20+(j-1)數(shù)組元素地址計(jì)算公式內(nèi)情向量把數(shù)組的有關(guān)信息記錄在一個(gè)“內(nèi)情向量”中，每個(gè)數(shù)組的內(nèi)情向量必須包括：維數(shù)，各維的上、下限，首地址，以及數(shù)組（元素）的類型。2記錄邏輯上說(shuō)，記錄結(jié)構(gòu)由已知類型的數(shù)據(jù)組合在一起的一種結(jié)構(gòu)。 record{charNAME[20]; integerAGE; boolMARRIED; }CARD[1000]訪問(wèn)：復(fù)合名CARD[k].NAME存儲(chǔ)：連續(xù)存放域的地址計(jì)算：相對(duì)于記錄結(jié)構(gòu)起點(diǎn)的相對(duì)數(shù)OFFSET。3字符串、表格、棧字符串：符號(hào)處理、公式處理表格：本質(zhì)上是一種記錄結(jié)構(gòu)線性表：一組順序化的記錄結(jié)構(gòu)棧：一種線性表，后進(jìn)先出，POP,PUSH三抽象數(shù)據(jù)類型一個(gè)抽象數(shù)據(jù)類型包括：數(shù)據(jù)對(duì)象的一個(gè)集合；作用于這些數(shù)據(jù)對(duì)象的抽象運(yùn)算的集合；這種類型對(duì)象的封裝，即，除了使用類型中所定義的運(yùn)算外，用戶不能對(duì)這些對(duì)象進(jìn)行操作。程序設(shè)計(jì)語(yǔ)言對(duì)抽象數(shù)據(jù)類型的支持Ada語(yǔ)言通過(guò)程序包（package）提供了數(shù)據(jù)封裝的支持Smalltalk、C++和Java語(yǔ)言則通過(guò)類（Class）對(duì)抽象數(shù)據(jù)類型提供支持。2.2.4語(yǔ)句與控制結(jié)構(gòu)一．表達(dá)式表達(dá)式由運(yùn)算量（也稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符（操作符）組成。形式：中綴、前綴、后綴X*Y-AP↑表達(dá)式形成規(guī)則算符的優(yōu)先次序一般的規(guī)定PASCAL：左結(jié)合A+B+C=(A+B)+CFORTRAN：對(duì)于滿足左、右結(jié)合的算符可任取一種，如A+B+C就可以處理成(A+B)+C，也可以處理成A+(B+C)。注意兩點(diǎn)：代數(shù)性質(zhì)能引用到什么程度視具體的語(yǔ)言不同而不同；在數(shù)學(xué)上成立的代數(shù)性質(zhì)在計(jì)算機(jī)上未必完全成立。二．語(yǔ)句賦值語(yǔ)句：A:=B名字左值：該名字代表的那個(gè)單元（地址）稱為該名字的左值。(所代表的存貯單元的地址)右值：一個(gè)名字的值稱為該名字的右值。(所代表的存貯單元的內(nèi)容)控制語(yǔ)句：無(wú)條件轉(zhuǎn)移語(yǔ)句gotoL條件語(yǔ)句ifBthenSifB

thenS1elseS2循環(huán)語(yǔ)句whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS過(guò)程調(diào)用語(yǔ)句callP(X1,X2,...,Xn)返回語(yǔ)句

return(E)說(shuō)明語(yǔ)句：定義各種不同數(shù)據(jù)類型的變量或運(yùn)算，定義名字的性質(zhì)。簡(jiǎn)單句和復(fù)合句簡(jiǎn)單句：不包含其他語(yǔ)句成分的基本句復(fù)合句：句中有句的語(yǔ)句復(fù)習(xí)：程序語(yǔ)言的定義程序語(yǔ)言由兩方面定義：語(yǔ)法：一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合式(well-formed)的程序詞法規(guī)則：?jiǎn)卧~符號(hào)的形成規(guī)則。常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等。有限自動(dòng)機(jī)語(yǔ)法規(guī)則：語(yǔ)法單位的形成規(guī)則。表達(dá)式、語(yǔ)句、分程序、過(guò)程、函數(shù)、程序等;上下文無(wú)關(guān)文法語(yǔ)義:一組規(guī)則，用它可以定義一個(gè)程序的意義復(fù)習(xí)：程序語(yǔ)言的基本功能和層次結(jié)構(gòu)程序語(yǔ)言的基本功能：描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。所謂程序，本質(zhì)上說(shuō)是描述一定數(shù)據(jù)的處理過(guò)程。程序|子程序或分程序、過(guò)程、函數(shù)|語(yǔ)句|表達(dá)式|數(shù)據(jù)引用算符函數(shù)調(diào)用復(fù)習(xí)：高級(jí)語(yǔ)言的一般特性

高級(jí)語(yǔ)言的分類

程序結(jié)構(gòu)數(shù)據(jù)類型與操作初等數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型語(yǔ)句與控制結(jié)構(gòu)2.3

程序語(yǔ)言的語(yǔ)法描述

基本概念(一、術(shù)語(yǔ))元素的非空有窮集合。例如，∑={a,b,c}1.字母表

根據(jù)字母表的定義，Σ是字母表，它由a、b、c三個(gè)元素組成。基本概念(一、術(shù)語(yǔ))

是一個(gè)字母表，由0、1兩個(gè)元素組成。注意:例如，∑'={0,1}

(2)字母表中的元素,可以是字母、數(shù)字或其他符號(hào)。(1)字母表中至少包含一個(gè)元素?；靖拍?一、術(shù)語(yǔ))

字母表中的元素稱為符號(hào)或稱為字符。例如，前述例子中2.符號(hào)（字符）a、b、c是字母表Σ中的符號(hào)；0、1是字母表Σ'中的符號(hào)?；靖拍?一、術(shù)語(yǔ))

例如，設(shè)有字母表∑={a,b,c}

符號(hào)的有窮序列稱為符號(hào)串。

符號(hào)串總是建立在某個(gè)特定字母表上的且只由字母表上的有窮多個(gè)符號(hào)組成。

則有符號(hào)串a(chǎn)，b，ab，ba，cba，abc…

3.符號(hào)串（字）基本概念(一、術(shù)語(yǔ))說(shuō)明:不包含任何符號(hào)的符號(hào)串,稱為空符號(hào)串，用ε表示。符號(hào)串中符號(hào)的順序是很重要的。ab和ba是字母表Σ上的兩個(gè)不同的符號(hào)串?？辗?hào)串由0個(gè)符號(hào)組成，其長(zhǎng)度|ε|=0基本概念(二、運(yùn)算)

設(shè)x和y是符號(hào)串，則串xy稱為它們的連結(jié)。則XY＝ABC10A，YX＝10AABC。注意：對(duì)任意一個(gè)符號(hào)串x，1.符號(hào)串的連結(jié)例如，設(shè)X＝ABC，Y＝10A我們有εx＝xε＝x。基本概念(二、運(yùn)算)2.集合的乘積

設(shè)A和B是符號(hào)串的集合,則A和B的乘積定義為：

集合的乘積是滿足于x∈A,y∈B的所有符號(hào)串xy所構(gòu)成的集合。AB={xy|x∈A,y∈B}{}A=A{}=A基本概念(二、運(yùn)算)例如：設(shè)A={a,b},B={c,d}則AB={ac,ad,bc,bd}由于對(duì)任意的符號(hào)串x，總有x=x=x所以,對(duì)任意集合A,我們有:基本概念(二、運(yùn)算)

特別指出的是，是符號(hào)串,不是集合，而{}表示由空符號(hào)串所組成的集合,但這樣的集合不是空集合Φ={}

?；靖拍?二、運(yùn)算)

3.符號(hào)串的冪運(yùn)算

設(shè)x是符號(hào)串,則x的冪運(yùn)算定義為：

x0=

x1=x

x2=xx

x3=xxx

…

xn=xx…x=xxn-1(n>0)n注意：x0≠1基本概念(二、運(yùn)算)例如,設(shè)x＝abc則x0=x1=abcx2=xx=abcabc

…基本概念(二、運(yùn)算)

4.集合的冪運(yùn)算

設(shè)A是符號(hào)串的集合，則集合A的冪運(yùn)算定義為：A0={}A1=AA2=AA

…

An=AA…A=AAn-1(n>0)n基本概念(二、運(yùn)算)例如，設(shè)A={a,b}，則A0={}A1=A={a,b}A2=AA={aa,ab,ba,bb}

…A3=AAA=A2A={aaa,aab,aba,abb,baa,bab,bba,bbb}基本概念(二、運(yùn)算)5.集合A的正則閉包A＋與自反閉包A*

設(shè)A是符號(hào)串的集合，則A的正則閉包A＋和A的自反閉包A*的定義為:A+=A1∪A2∪…∪AnA*=A0∪A1∪A2∪…

∪An={ε}∪A+基本概念(二、運(yùn)算)

可見,集合A的正則閉包表示A上元素a,b構(gòu)成的所有符號(hào)串的集合,集合A的自反閉包比集合A的正則閉包多含一個(gè)空符號(hào)串。例如，設(shè)A={a,b},則：A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}∑*的子集U和V的連接（積）定義為UV＝{|U&V}

例：設(shè)：U＝{a,aa}V＝{b,bb}那么：

UV={ab,abb,aab,aabb}∑*的子集U和V的連接（積）定義為UV＝{|U&V}

V自身的n次積記為 Vn=VV…V規(guī)定V0={}，令V*=V0∪V1∪V2∪V3∪…稱V*是V的閉包;記V＋＝VV*，稱V+是V的正規(guī)閉包。設(shè)：U＝{a,aa}那么：

U*

={,a,aa,aaa,aaaa,…}U＋

={a,aa,aaa,aaaa,…}2.3.1上下文無(wú)關(guān)文法文法：描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則Hegavemeabook.<句子><主語(yǔ)><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)><主語(yǔ)><代詞><謂語(yǔ)><動(dòng)詞><間接賓語(yǔ)><代詞><直接賓語(yǔ)><冠詞><名詞><代詞>He<代詞>me<名詞>book<冠詞>a<動(dòng)詞>gave<句子><主語(yǔ)><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)><主語(yǔ)><代詞><謂語(yǔ)><動(dòng)詞><間接賓語(yǔ)><代詞><直接賓語(yǔ)><冠詞><名詞><代詞>He<代詞>me<名詞>book<冠詞>a<動(dòng)詞>gave<句子><主語(yǔ)><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)><代詞><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)>He<謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)>He<動(dòng)詞><間接賓語(yǔ)><直接賓語(yǔ)>Hegave<間接賓語(yǔ)><直接賓語(yǔ)>Hegave<代詞><直接賓語(yǔ)>Hegaveme<直接賓語(yǔ)>Hegaveme<冠詞><名詞>Hegavemea<名詞>Hegavemeabook終結(jié)符號(hào)【VT】：從語(yǔ)法角度看，終結(jié)符是一個(gè)語(yǔ)言的不可再分的基本符號(hào)。如：基本

字、標(biāo)識(shí)符、常數(shù)、算符和界符等。非終結(jié)符號(hào)（語(yǔ)法變量）【VN】：用來(lái)代表語(yǔ)法單位。如“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“賦值句”、“子程序”、“函數(shù)”等。一個(gè)非終結(jié)符代表一個(gè)一定的語(yǔ)法概念，是一個(gè)類（集合）記號(hào)，而不是一個(gè)個(gè)體記號(hào)。上下文無(wú)關(guān)文法的定義：一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT

VN=S：文法的開始符號(hào)，SVNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為P，PVN，(VT

VN)*開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。幾點(diǎn)規(guī)定：“”也可以用“::="表示，這種表示稱為巴科斯范式(BNF)P1

P2可縮寫為P1|2||n

Pn其中，“|”讀成“或”，稱為P的一個(gè)候選式。表示一個(gè)文法時(shí)，通常只給出開始符號(hào)和產(chǎn)生式，如上例，可表示為：G(E)：Ei|E+E|E*E|(E)例，定義只含+，*的算術(shù)表達(dá)式的文法G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列產(chǎn)生式組成：EiEE+EEE*EE(E)定義：稱A直接推出，即A僅當(dāng)A是一個(gè)產(chǎn)生式，且，(VT

VN)*。如果1

2

n，則我們稱這個(gè)序列是從1到n的一個(gè)推導(dǎo)。若存在一個(gè)從1到n的推導(dǎo)，則稱1可以推導(dǎo)出n。對(duì)文法G(E)：Ei|E+E|E*E|(E)E(E)(E+E)(i+E)(i+i)用表示：從1出發(fā)，經(jīng)過(guò)0步或若干步，可以推出n。

所以：即或定義：假定G是一個(gè)文法，S是它的開始符號(hào)。如果，則稱是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言，將它記為L(zhǎng)(G)。通常，用

表示：從1出發(fā)，經(jīng)過(guò)一步或若干步，可以推出n。例：(i*i+i)是文法G(E)：Ei|E+E|E*E|(E)的一個(gè)句子。證明：

E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E，(E)，(E*E+E)，…，(i*i+i)是句型。例：文法G1(A)：Ac|AbG1(A)的語(yǔ)言?L(G1)={c，cb，cbb，}以c開頭，后繼若干個(gè)b例：文法G2(S)：SABAaA|aBbB|bG2(S)的語(yǔ)言?L(G2)={ambn|m，n>0}例：給出產(chǎn)生語(yǔ)言為{anbn|n1}的文法。G3(S)：SaSbSab例：給出產(chǎn)生語(yǔ)言為{ambn|1≤n≤m≤2n}的文法。G4(S)：SaSb|aaSbSab|aab從一個(gè)句型到另一個(gè)句型的推導(dǎo)往往不唯一。E+Ei+Ei+iE+EE+ii+i最左推導(dǎo)：任何一步都是對(duì)中的最左非終結(jié)符進(jìn)行替換。

最右推導(dǎo)：任何一步都是對(duì)中的最右非終結(jié)符進(jìn)行替換。遞歸規(guī)則與遞歸文法遞歸規(guī)則是指那些在規(guī)則的右部含有與規(guī)則左部相同符號(hào)的規(guī)則。例如：U→xUy，右部含有與規(guī)則左部相同符號(hào)U，那么就是遞歸規(guī)則。如果這個(gè)相同的符號(hào)出現(xiàn)在右部的最左端，則為左遞歸規(guī)則。如U→Uy如果這個(gè)相同的符號(hào)出現(xiàn)在右部的最右端，則為右遞歸規(guī)則。如U→xU若文法中至少包含一條遞歸規(guī)則,則稱文法是直接遞歸的。若文法中不含遞歸規(guī)則，但有推導(dǎo)過(guò)程

U

xUy，所以該文法為間接遞歸文法。

遞歸文法使我們能用有窮的文法刻畫無(wú)窮的語(yǔ)言。

2.3.2語(yǔ)法樹與二義性用一張圖來(lái)表示一個(gè)句型的推導(dǎo)，有助于理解句子語(yǔ)法結(jié)構(gòu)的層次。定義：設(shè)文法G=(VN,VT,P,S),對(duì)于文法G的任意一個(gè)句型都存在一棵相應(yīng)的語(yǔ)法樹：結(jié)點(diǎn)由符號(hào)組成。根結(jié)點(diǎn)對(duì)應(yīng)于開始符號(hào)。只有非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對(duì)應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。用一張圖表示一個(gè)句型的推導(dǎo),稱為語(yǔ)法樹。(i*i+i)的語(yǔ)法樹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)一棵語(yǔ)法樹是不同推導(dǎo)過(guò)程的共性抽象。G(E)：Ei|E+E|E*E|(E)(i*i+i)如果使用最左(右)推導(dǎo)，則一個(gè)最左(右)推導(dǎo)與語(yǔ)法樹一一對(duì)應(yīng)。一個(gè)句型是否只對(duì)應(yīng)唯一一棵語(yǔ)法樹？定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩顆不同的語(yǔ)法樹，則說(shuō)這個(gè)文法是二義的。G(E)：Ei|E+E|E*E|(E)是二義文法。語(yǔ)言的二義性：一個(gè)語(yǔ)言是二義性的，如果對(duì)它不存在無(wú)二義性的文法。可能存在G和G’，一個(gè)為二義的，一個(gè)為無(wú)二義的。但L(G)=L(G’)二義性問(wèn)題是不可判定問(wèn)題，即不存在一個(gè)算法，它能在有限步驟內(nèi)，確切地判定一個(gè)文法是否是二義的?？梢哉业揭唤M無(wú)二義文法的充分條件。二義文法：G(E)：Ei|E+E|E*E|(E)表達(dá)式項(xiàng)|表達(dá)式+項(xiàng)項(xiàng)因子|項(xiàng)*因子因子

(表達(dá)式)|i無(wú)二義文法：G(E)：ET|E+TTF|T*FF(E)|i)EEEFFTTTTi+*(EFiiET

F