同濟(jì)大學(xué)編譯原理 第二章 高級語言及其語法描述

第二章高級語言及其語法描述概述要學(xué)習(xí)和構(gòu)造編譯程序，理解和定義高級語言是必不可少的本章概述高級語言的結(jié)構(gòu)和主要共同特征，重點(diǎn)介紹程序設(shè)計語言的語法描述方法內(nèi)容線索程序設(shè)計語言的定義高級語言的一般特性程序語言的語法描述程序設(shè)計語言的定義程序設(shè)計語言是為書寫計算機(jī)程序而人為設(shè)計的符號語言。機(jī)器語言匯編語言高級語言各級語言的比較比較

機(jī)器語言匯編語言高級語言硬件識別是唯一可以識別的語言不可識別不可識別是否可直接執(zhí)行可直接執(zhí)行不可，需匯編、連接不可，需編譯/解釋、連接特點(diǎn)面向機(jī)器占用內(nèi)存少執(zhí)行速度快使用不方便面向機(jī)器占用內(nèi)存少執(zhí)行速度快較為直觀與機(jī)器語言一一對應(yīng)面向問題/對象占用內(nèi)存大執(zhí)行速度相對慢標(biāo)準(zhǔn)化程度高便于程序交換，使用方便定位低級語言，極少使用低級語言，很少使用高級語言，種類多，常用程序語言的內(nèi)涵語法語義語用表示構(gòu)成語言句子的各個記號之間的組合規(guī)律(構(gòu)成規(guī)則)。表示按照各種表示方法所表示的各個記號的特定含義（各個記號和記號所表示的對象之間的關(guān)系）。表示各個記號或語言詞句與其使用之間的關(guān)系。舉例：C語言的賦值語句語法語義語用賦值語句由一個變量，后隨一個符號“=”，再在后面跟一個表達(dá)式所構(gòu)成。賦值語句先對該語句的右部表達(dá)式求值，然后把所得結(jié)果與語句左部的變量相結(jié)合，并取代該變量原有的值。賦值語句可用來計算和保存表達(dá)式的值。語法語言的語法是指可以形成和產(chǎn)生合式程序的一組規(guī)則。它包括詞法規(guī)則和語法規(guī)則。詞法規(guī)則是指程序中單詞符號的形成規(guī)則。單詞符號一般包括：標(biāo)識符、基本字、常量、算符和界符。語法規(guī)則是指程序中語法單位的形成規(guī)則。程序語言的語法單位有：表達(dá)式、語句、分程序、過程、函數(shù)、程序。描述方式：詞法規(guī)則和語法規(guī)則都可以用自然語言、語法圖、BNF范式、或文法等描述。語法描述方式（1）（1）自然語言例1.標(biāo)識符是由字母后跟若干個（包括0個）字母或數(shù)字的符號串組成的。例2.賦值語句由一個變量，后隨一個符號“=”，再在后面跟一個表達(dá)式所構(gòu)成。（2）語法圖是用圖解形式描述程序設(shè)計語言語法規(guī)則的工具。例1.標(biāo)識符的構(gòu)成規(guī)則用語法圖描述為：標(biāo)識符字母數(shù)字字母語法描述方式（2）（3）BNF范式巴科斯范式(BNF:Backus-NaurForm的縮寫)是由JohnBackus和PeterNaur首先引入的用來描述計算機(jī)語言語法的符號集?，F(xiàn)在，新的編程語言幾乎都使用巴科斯范式來定義編程語言的語法規(guī)則。

簡單算術(shù)表達(dá)式的BNF范式<簡單表達(dá)式>∷＝<簡單表達(dá)式>+<簡單表達(dá)式><簡單表達(dá)式>∷＝<簡單表達(dá)式>*<簡單表達(dá)式><簡單表達(dá)式>∷＝(<簡單表達(dá)式>)<簡單表達(dá)式>∷＝i或者

<簡單表達(dá)式>∷＝<簡單表達(dá)式>+<簡單表達(dá)式>|<簡單表達(dá)式>*<簡單表達(dá)式>|(<簡單表達(dá)式>)|i附：BNF表示α→β表示為α∷＝β非終結(jié)符用“<”和“>”括起來終結(jié)符：基本符號集其他β(α1|α2…|αn)≡βα1|βα2…|βαn{α1|α2…|αn}mn

[α]≡α|ε……語義對于一個語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義。這就是語義問題。語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意義。我們采用的方法為：基于屬性文法的語法制導(dǎo)翻譯方法。程序語言的功能一個程序語言的基本功能是描述數(shù)據(jù)和對數(shù)據(jù)的運(yùn)算。所謂程序，從本質(zhì)上來說是描述一定數(shù)據(jù)的處理過程。在現(xiàn)今的程序語言中，一個程序大體可以視為如圖所示的層次結(jié)構(gòu)內(nèi)容線索程序設(shè)計語言的定義高級語言的一般特性程序語言的語法描述高級語言的分類(1)過程式：ImperativeLanguage形式：語句序列舉例：Fortran、C、Pascal(2)函數(shù)式：ApplicativeLanguage形式：func1(…func(n))舉例：Lisp(3)基于規(guī)則：Rule-BasedLanguage形式：bird(x):-fly(x)&feather(x)舉例：Prolog(4)面向?qū)ο螅篛bject-OrientedLanguage形式：class,舉例：Smalltalk、C++、Java高級語言的一般特性程序結(jié)構(gòu)數(shù)據(jù)類型與操作語句與控制結(jié)構(gòu)程序結(jié)構(gòu)——單層結(jié)構(gòu)Fortran程序結(jié)構(gòu)主程序＋若干個輔程序段（子程序、函數(shù)）

ProgramMainRead(I,J)Callmax(I,J,K)Write(100,K)100Format(…)end

subroutinemax(x,y,z)integerx,y,zifx>ythenz＝xelsez＝y(tǒng)end程序結(jié)構(gòu)——多層結(jié)構(gòu)Pascal程序結(jié)構(gòu)程序允許嵌套定義ProgramP;vara,x:integer;procedureQ(b:integer);vari:integer;procedureR(u:integer;Varv:integer);varc,d:integer;begin…endbegin…endbegin….end初等類型、復(fù)合類型到抽象數(shù)據(jù)類型類型本不存在內(nèi)存里存儲的內(nèi)容，你認(rèn)為它是什么，它就是什么高級語言設(shè)計了初等數(shù)據(jù)類型：整型、浮點(diǎn)型、字符型等。不同的語言也會定義不同的初等類型等。初等數(shù)據(jù)類型并不能方便地解決所有問題復(fù)合數(shù)據(jù)類型是初等數(shù)據(jù)類型迭代派生而來典型的代表就是“結(jié)構(gòu)”，數(shù)組也可算作此類抽象數(shù)據(jù)類型(ADT)在復(fù)合數(shù)據(jù)類型的基礎(chǔ)上增加了對數(shù)據(jù)的操作抽象數(shù)據(jù)類型進(jìn)而進(jìn)化為“類(Class)”類型每個被計算對象都帶有自己的類型，以類型作為值的屬性的概括，因此每個類型都意味著一個值的集合。不同類型的值具有不同的操作運(yùn)算類型是一個值的集合和定義在這個值集上的一組操作的總稱。如C語言中的整型變量(int)，其值集為某個區(qū)間上的整數(shù)，定義在其上的操作為+,-,*,/等抽象數(shù)據(jù)類型一個抽象數(shù)據(jù)類型（AbstractDataType，ADT）定義為：（1）一個數(shù)據(jù)對象集，數(shù)據(jù)對象由一個或多個類型定義；（2）一個作用于這些數(shù)據(jù)對象的抽象操作集；（3）完全封裝，用戶除了能使用該類型的操作來處理這類數(shù)據(jù)對象之外，不能作其他的處理。抽象數(shù)據(jù)類型有兩個重要特征：信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離抽象數(shù)據(jù)類型…FirstComeFirstService（queue）InQueueOutQueueIsEmptyOverflowQueue（ADT）對外操作接口結(jié)構(gòu)數(shù)據(jù)維護(hù)接口結(jié)構(gòu)數(shù)據(jù)的物理實(shí)現(xiàn)抽象數(shù)據(jù)類型（續(xù)）FirstComeFirstService（queue）InQueueOutQueueIsEmptyOverflowQueue（ADT）對外操作接口結(jié)構(gòu)數(shù)據(jù)維護(hù)接口結(jié)構(gòu)數(shù)據(jù)的物理實(shí)現(xiàn)抽象數(shù)據(jù)類型的特點(diǎn)數(shù)據(jù)抽象用ADT描述程序處理的實(shí)體時，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。數(shù)據(jù)抽象的優(yōu)點(diǎn)程序組織和修改可讀性、可靠性、可維護(hù)性通過隱藏數(shù)據(jù)表示，用戶代碼不能直接訪問該類型對象，不依賴于其表示，因此可以修改該類型對象的表示而不影響用戶代碼語句與控制結(jié)構(gòu)表達(dá)式語句簡單語句：不含其它語句成分的基本句。說明語句賦值語句控制語句過程調(diào)用語句復(fù)合語句：句中有句的語句表達(dá)式表達(dá)式：一個表達(dá)式是由運(yùn)算量（亦稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。對于大多數(shù)程序語言來說，表達(dá)式的形成規(guī)則可概括為：（1）變量（包括下標(biāo)變量）、常數(shù)是表達(dá)式；（2）若E1、E2為表達(dá)式，θ為二元算符，則E1θE2為表達(dá)式；（3）若E為表達(dá)式，θ為一元算符，則θE為表達(dá)式；（4）若E為表達(dá)式，則(E)是表達(dá)式。語句不同程序語言含有不同形式和功能的各種語句。從功能上說語句大體可分執(zhí)行性語句和說明性語句兩大類：說明性語句旨在定義不同數(shù)據(jù)類型的變量或運(yùn)算。執(zhí)行性語句旨在描述程序的動作。執(zhí)行性語句又可分為賦值語句、控制語句和輸入/輸出語句從形式上說，語句可分為簡單句、復(fù)合句和分程序等。賦值語句A:=B意義是：“把B的值送入A所代表的單元”在賦值句中，賦值號‘：=’左右兩邊的變量名扮演著兩種不同的角色。對賦值號右邊的B我們需要的是它的值；對于左邊的A我們需要的是它們的所代表的存儲單元（的地址）。為了區(qū)分一個名字的這兩種特征，我們把一個名字所代表的那個存儲單元（地址）稱為該名字的左值；把一個名字的值稱為該名字的右值?？刂普Z句多數(shù)語言中所含的控制語句有：無條件轉(zhuǎn)移語句:gotoL條件語句：ifBthenSifBthenS1elseS2循環(huán)語句：whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS過程調(diào)用語句：callP(X1,X2,…,Xn)返回語句：return(E)說明語句說明語句旨在定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號表中，并檢查程序中名字的引用和說明是否相一致。內(nèi)容線索程序設(shè)計語言的定義高級語言的一般特性程序語言的語法描述概述對于高級程序語言及編譯程序而言，語言的語法定義是非常重要的。本節(jié)將介紹語法結(jié)構(gòu)的形式描述問題。編譯原理=形式語言理論+編譯技術(shù)形式語言自然語言人們平時說話時所使用的一種語言，不同的國家和民族有著不同的語言。形式語言通過人們公認(rèn)的符號、表達(dá)方式所描述的一種語言，是一種通用語言，沒有國籍之分。形式語言是某個字母表上的字符串的集合，有一定的描述范圍。為什么用形式語言形式語言的最初起因：語言學(xué)家喬姆斯基（Chomsky）想用一套形式化方法來描述語言。形式語言在自然語言研究中起步，在計算機(jī)科學(xué)中得到廣泛應(yīng)用。最初的應(yīng)用：編譯現(xiàn)在已廣泛應(yīng)用在人工智能、圖像處理、通信協(xié)議、通信軟件等多個領(lǐng)域在計算機(jī)理論科學(xué)方面：是可計算理論（算法―在有限步驟內(nèi)求得解、算法復(fù)雜性、停機(jī)問題、）、定理自動證明、程序轉(zhuǎn)換（程序自動生成）、模式識別等的基礎(chǔ)。形式語言與自動機(jī)理論的發(fā)展1956年，喬姆斯基（Chomsky）從產(chǎn)生的角度研究語言文法1951-1956年間，克林（Kleene）從識別的角度研究語言自動機(jī)1959年，喬姆斯基不僅確定了文法和自動機(jī)分別從生成和識別的角度去表達(dá)語言，而且證明了文法與自動機(jī)的等價性。形式語言真正誕生相關(guān)概念和知識概念字母表、符號、符號串、串長度、空符號串ε、子符號串、前綴、后綴、符號串集合注意區(qū)分：

、ε、{ε}（連接）積定義為:UV={∣U&V}閉包、正則閉包規(guī)定V0={}.

V*=V0V1V2…，稱V*是V的閉包。記V+=VV*,稱V+是V的正則閉包。。閉包定理.若A是符號串集合，則A*=(A*)*。則x∈AM，因此推得x∈A*，所以(A*)*

A*，故A*=(A*)*。證明：顯然A*

(A*)*,現(xiàn)證(A*)*

A*

任給符號串x∈(A*)*，則存在n，使得x∈(A*)n，必存在n個子串x1,…,xn

，使得x=x1…xn

，且xi∈A*

(i=1,…,n)。由xi∈A*

，必存在整數(shù)pi,使得xi∈Api

，令 文法（Grammar）所謂文法是用來定義語言的一個數(shù)學(xué)模型。表示語言的方法：若語言L是有限集合，可用列舉法若L是無限集合（集合中的每個元素有限長度），用其他方法。方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語言的每個句子方法二：機(jī)器識別系統(tǒng)：當(dāng)一個字符串能被一個語言的識別系統(tǒng)接受，則這個字符串是該語言的一個句子，否則不屬于該語言。Chomsky文法體系Chomsky文法體系中，任何一種文法必須包含兩個不同的有限符號的集合非終結(jié)符集合VN終結(jié)符集合VT一個起始符S一個形式規(guī)則的有限集合￡（產(chǎn)生式集合）。注意￡中的產(chǎn)生式是用來產(chǎn)生語言句子的規(guī)則，而句子則是僅由終結(jié)符組成的字符串。這些字符串必須從一個起始符S開始，不斷使用￡中的產(chǎn)生式而導(dǎo)出來。文法的核心是產(chǎn)生式的集合，它決定了語言中句子的產(chǎn)生。文法的術(shù)語與知識推導(dǎo)直接推導(dǎo)最左推導(dǎo)、最右推導(dǎo)歸約最左歸約、最右歸約句型、句子和語言文法體系3型文法、2型文法文法的形式定義文法G是一個四元組G=(VN,VT,S,￡)，其中VN

：非終結(jié)符的有限集合VT

：終結(jié)符的有限集合，VN∩VT=Φ

S：開始符號且S∈VN

?！辏盒问綖镻→α的產(chǎn)生式的有限集合，且P∈(VN∪VT)*VN(VN∪VT)*，α∈(VN∪VT)*文法示例文法G1=({N},{0,1},N,{N→0N,N→1N,N→0,N→1})

其中：VN={N}

VT={0,1}

S=N

￡={N→0N,N→1N,N→0,N→1}文法的解釋（1）非終結(jié)符號：需要進(jìn)一步定義的符號，不會出現(xiàn)在程序中。用來代表語法范疇。如“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“過程”等。一個非終結(jié)符代表一個一定的語法概念，因此非終結(jié)符是一個類（或集合）記號，而不是個體記號。終結(jié)符號：不需要再定義，會出現(xiàn)在程序中。組成語言的基本符號，即在程序語言中的單詞符號，如標(biāo)識符，常數(shù)，算符和界符等開始符號S至少在某個產(chǎn)生式的左部出現(xiàn)一次.文法的解釋（2）產(chǎn)生式（規(guī)則）：定義語法單位的一種書寫規(guī)則它的形式為：P→α（或P::=α）其中“→”讀作“定義為”，P，α為符號串，箭頭左邊稱為產(chǎn)生式左部，箭頭右邊稱為產(chǎn)生式右部。

例：S→0S1，0S→01若干個左部相同的產(chǎn)生式如P→α1,P→α2,P→α3,...,P→αn

可合并成一個,縮寫為

P→α1|α2|α3|...|αn,

其中,每個αi

稱為是P的一個候選式.習(xí)慣寫法VN:大寫字母A、B、C、S等VT: 小寫字母，0~9，+、－等運(yùn)算符，α、β、γ: 文法符號串,∈(VT∪VN)*S:開始符號，第一個產(chǎn)生式中出現(xiàn)→

:定義符號（推出）|：或文法的約定為了簡化，文法表示只寫出產(chǎn)生式部分約定第一個產(chǎn)生式的左部符號為初始符號或在產(chǎn)生式前寫上“G[A]”，其中G為文法名，A為初始符號.

例.文法G[N]:N→0N,N→1N,N→0,N→1

文法G[E]:E→E+E│E*E│(E)│i如何由文法產(chǎn)生語言的句子？基本思想：從識別符號開始，把當(dāng)前產(chǎn)生的符號串中的非終結(jié)符號替換為相應(yīng)產(chǎn)生式右部的符號串，直到最終全由終結(jié)符號組成。這種替換過程稱為推導(dǎo)或產(chǎn)生句子的過程，每一步稱為直接推導(dǎo)或直接產(chǎn)生。直接推導(dǎo)與歸約直接推導(dǎo)如果A→γ是一個產(chǎn)生式，而α，β∈（VT∪VN）*，則將產(chǎn)生式A→γ用于符號串αAβ得到符號串αγβ，記為αAβ

αγβ，稱αAβ直接推出αγβ。歸約是推導(dǎo)的逆過程若存在αAβ

αγβ，則稱αγβ能夠直接歸約成αAβ

。推導(dǎo)推導(dǎo)：設(shè)α1,α2,…,αn(n>0)∈(VT∪VN)*，且有

α1

α2

…

αn

則稱這個序列是從α1到αn的一個推導(dǎo)。若存在從α1到αn的一個推導(dǎo)，則稱α1可推導(dǎo)出αn。

α1

αn(經(jīng)一步或若干步推導(dǎo)）

α1

αn

（經(jīng)0步或若干步推導(dǎo)）+*最左（右）推導(dǎo)（歸約）若在推導(dǎo)關(guān)系中，每次最先替換最左（右）的非終結(jié)符，則稱為最左（右）推導(dǎo)；若在歸約過程中，每次最先歸約最左（右）的非終結(jié)符，則稱為最左（右）歸約。例.文法G[S]:S→ABA→A0|1BB→0|S1，請給出句子101001的最左和最右推導(dǎo)。最右推導(dǎo)：

S

AB

AS1AAB1

AA01

A1B01

A1001

1B1001

101001最左推導(dǎo)：

S

AB1BB10B10S110AB1

101BB11010B1101001句型、句子和語言句型：假定G是一個文法，S是它的開始符號，如果S

α，則稱α是文法G的一個句型。

例

(E+E),(i+E),(i+i),E都是G[E]的句型。句子：僅由終結(jié)符組成的句型稱為句子。例(i×i+i),(i+i)都是G[E]的句子。語言：文法G所產(chǎn)生句子的全體，即：

L(G)={α|S

α，α∈VT*}*+例.設(shè)有文法G1[S]:S→bA,A→aA|a

試求此文法所描述的語言。解：因?yàn)閺拈_始符號S出發(fā)可推出下列句子：

S

bA

ba S

bA

baA

baa S

bA

baA

baaA

baaa … S

bA

baA

…

baa…a

所以，L(G1)={ban|n≥1}例.設(shè)文法G2[S]：S→AB A→aA|a B→bB|b 該文法所描述的語言是什么？解：從文法開始符號S出發(fā)，可推出下列句子： S

AB

ab S

AB

aAB

aaB

aab S

AB

aAB

aaB

aabB

aabbB

aabbb S

AB

aa…abb…bmn所以，L(G2)={ambn|m,n

≥

1}例.試對如下語言L(G3)={anbn|n>=1}構(gòu)造文法G3。解：L(G3)由以下一些符號串x組成： n=1,x=abn=2,x=aabbn=3,x=aaabbb…L(G3)={ab,aabb,aaabbb,… 由此可見，集合L（G3）有如下特點(diǎn)：每個符號串呈對稱形式，即a,b成對出現(xiàn)；L(G3)為無窮集合，描述它的規(guī)則中含遞歸定義；文法中終結(jié)符只有a,b。因此可用以下兩條產(chǎn)生式定義語言L(G3)

S→aSb|ab即：G3=（{S}，{a,b}，{S→aSb|ab}，S)例.文法G[<數(shù)>]：

<數(shù)>→<數(shù)字串><數(shù)字串>→<數(shù)字串><數(shù)字>│<數(shù)字><數(shù)字>→0|1|2|3|4|5|6|7|8|9

語言L(G)為非負(fù)整數(shù)。例.寫一文法G3，使其描述的語言為正奇數(shù)集合。令G3={VN,VT,P,<正奇數(shù)>}，其中，

VT={0,1,2,3,4,5,6,7,8,9}，

VN={<正奇數(shù)>,<一位奇數(shù)>,<一位偶數(shù)>,<數(shù)字串>,<數(shù)字>}S：<正奇數(shù)>P：<正奇數(shù)>→<一位奇數(shù)>│<數(shù)字串><一位奇數(shù)><數(shù)字串>→<數(shù)字串><數(shù)字>│<數(shù)字><數(shù)字>→<一位奇數(shù)>│<一位偶數(shù)><一位奇數(shù)>→1│3│5│7│9<一位偶數(shù)>→0│2│4│6│8

思考：如果要求開頭元素非零，如何改造？<正奇數(shù)>→<一位奇數(shù)>│<數(shù)字串><一位奇數(shù)><數(shù)字串>→<數(shù)字串><數(shù)字>│<數(shù)字1><數(shù)字>→<一位奇數(shù)>│<一位偶數(shù)><數(shù)字1>→1│2│3│4│5│6│7│8│9<一位奇數(shù)>→1│3│5│7│9<一位偶數(shù)>→0│2│4│6│8或者：

S→A│BAB→BC│DC→0│E│AD→E│AE→2│4│6│8A→1│3│5│7│9Chomsky文法體系3012文法、形式語言和自動機(jī)的對應(yīng)關(guān)系遞歸可枚舉語言圖靈機(jī)0型文法上下文有關(guān)語言線性有界自動機(jī)1型文法上下文無關(guān)語言下推自動機(jī)2型文法正規(guī)語言有限自動機(jī)3型文法語法分析樹和文法的二義性語法分析樹，簡稱語法樹二義性什么是語法樹？語法樹是表示一個句型推導(dǎo)過程的圖，是一棵倒立的樹。結(jié)點(diǎn)邊根結(jié)點(diǎn)末端結(jié)點(diǎn)末端分支：A(a,b)和B(c,d)兄弟結(jié)點(diǎn)SBBdbaAcdc從推導(dǎo)構(gòu)造語法樹方法：把開始符號S做為語法樹的根結(jié)點(diǎn)，對每一個直接推導(dǎo)畫一次結(jié)點(diǎn)的擴(kuò)展，該結(jié)點(diǎn)是直接推導(dǎo)中被替換的非終結(jié)符號，其所有兒子結(jié)點(diǎn)所組成的符號串是推導(dǎo)中所用產(chǎn)生式右部。直到推出或句型或句子或無法再推導(dǎo)時結(jié)束。示例文法文法G=({S,A,B},{a,b,c,d},S,{S→AB,A→abB|ab,B→cBd|cd})S

abccdd?S

AB

AcBd

Accdd

abccddS（1）SBA（2）SBBdAc（3）SBBdbaAcdc（5）SBBdAcdc（4）語法樹的構(gòu)造過程給定文法G，G=(VN,VT,S,￡)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列特征：1、根結(jié)點(diǎn)的標(biāo)記是開始符號S；2、每個結(jié)點(diǎn)的標(biāo)記都是V中的一個符號；3、若一棵子樹的根結(jié)點(diǎn)為A，且其所有兒子結(jié)點(diǎn)的標(biāo)記從左向右的排列為A1A2…AR，那么A

A1A2..AR一定是￡中的一條產(chǎn)生式（規(guī)則）；4、若一標(biāo)記為A的結(jié)點(diǎn)至少有一個兒子，則A∈VN5、樹的葉結(jié)點(diǎn)符號所組成的符號串W就是所給句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。語法樹的特征例.文法G[E]：

E→E+T│TT→T*F│FF→(E)│i

句型E+F*i推導(dǎo)：

E

E+T

E+T*F

E+F*F

E+F*i

對應(yīng)的語法樹如右圖同一句型有不同的推導(dǎo)序列設(shè)有文法G[N1]:N1→NN→ND|DD→0|1|2

則句子12可由若干種不同的推導(dǎo)序列推導(dǎo)出來：

(1)N1

NND

N2D212(2)

N1

N

NDDD1D12同一句型（句子）可以通過不同的推導(dǎo)序列推導(dǎo)出來。E

E+Ei+Ei+E*Ei+i*Ei+i*i

E

E*EE+E*Ei+E*Ei+i*Ei+i*iEE+EE*EiiiEE*E+EEiii最左推導(dǎo)及相應(yīng)語法樹同理，該句子的最右推導(dǎo)及相應(yīng)語法樹也不同文法G[E]：E→E+E│E*E│(E)│i句子:

i+i*i語法樹解釋語法樹表明了在推導(dǎo)過程中使用了哪條規(guī)則和使用在哪個非終結(jié)符號上，但它并沒有表明使用規(guī)則（產(chǎn)生式）的順序。一個句型是否只有唯一的一個最左(最右)推導(dǎo)呢?否！一個句型是否只對應(yīng)唯一的一棵語法樹呢?否！因?yàn)椴煌淖钣遥ㄗ螅┩茖?dǎo)對應(yīng)不同的語法樹。二義性如果一個文法的句子（句型）存在兩棵語法樹,那么,該句子是二義性的。如果一個文法包含二義性的句子,則稱這個文法是二義性的;否則，該文法是無二義性的。說明中國足球誰也贏不了

中國乒乓球誰也贏不了1.一般來說，程序語言存在無二義性的文法描述，但是對于條件語句，經(jīng)常使用二義性文法描述它：

SifexprthenS

ifexprthenSelseSother二義性的句子:ife1thenife2thens1elses2可以用無二義文法來描述，但是比較復(fù)雜2.在能駕馭的情況下，使用二義性文法。語言的二義性與文法的二義性問題如語言L找到一個文法是無二義的，則L是無二義的；如未找到一個文法是無二義的，也不能斷定L二義。產(chǎn)生某上下文無關(guān)語言的每一個文法都是二義的，則稱此語言是先天二義的.

例.

aibicj

i,j

1

aibjcj

i,j

1

存在一個二義性的句子akbkck文法的二義性是不可判定的。

（因?yàn)槲姆ǖ亩x性由句子的語法樹決定，不可能對無窮句子來判別）二義文法改造為無二義文法文法G[E]：E

E+E

E*E

(E)

i是二義性的，如果規(guī)定“×”和“＋”的優(yōu)先性，并服從左結(jié)合，上式就可以構(gòu)造出無二義性文法。文法G[E]:ET|E×TTF|T+FF(E)|i句子的推導(dǎo)過程唯一：如：i×i+i作業(yè)P36689基本概念字母表：元素的非空有窮集合。例：{a,

b,

c,…,z}（拉丁字母表）

{α,

β,

γ,…,ω}（希臘字母表）

{0,1}

（二進(jìn)制數(shù)字字母表）符號：字母表中的元素。如a,

b,…基本概念符號串：字母表中的符號組成的任何有窮序列。例.設(shè)字母表∑={a,b,c}

其符號串有：a,b,c,ab,ac,aa,abc,…符號串與符號組成的順序有關(guān)。符號串的長度：符號串x中符號的數(shù)目,用|x|表示空符號串（空字）：不包含任何符號的符號串，記為ε。子符號串設(shè)有非空符號串u=xvy，則稱v為符號串u的子符號串。例.符號串x=a+b-(c+d)

則a,a+b-,(c+d)等都是x的子符號串，且其長度分別為：|a|=1,|a+b-|=4,|(c+d)|=5符號串的前綴與后綴符號串的前綴與后綴符號串左部的任意子串，稱為符號串的前綴；符號串右部的任意子串，稱為符號串的后綴。例.字母表A={a,b,c}上的符號串x=ab,則x的前綴有：

ε、a、ab；后綴有：

ε、b、ab?；靖拍罘柎希喝艏现兴性囟际悄匙帜副?/p>

上的符號串，則稱之為該字母表上的符號串集合。用*表示上的所有符號串的全體，空字也包括在其中。例.若={a,b}，

則*={,a,b,aa,ab,bb,aaa,…}。表示不含任何元素的空集{}注意區(qū)分：

、ε、{ε}（連接）積

*的子集U和V中的（連接）積定義為:UV={∣U&V}即集合UV中的符號串是由U和V的符號串連接而成的。例.設(shè)U={a,b},V={α，β，γ}

則UV={aα,aβ,aγ,bα,bβ,bγ}注意：一般UVVU，但（UV)W=U(VW).n次（連接）積V自身的n次（連接）積記為：規(guī)定V0={}.令：V*=V0V1V2…，稱V*是V的閉包。閉包V*中的每個符號都是由V中的符號串經(jīng)有限次連接而成的。記V+=VV*,稱V+是V的正則閉包。Vn=VVV…V

nChomsky文法體系分類文法G=(VN,VT,S,￡)，

￡：P→α，其中P∈(VN∪VT)*VN(VN∪VT)*，α∈(VN∪VT)*屬于Chomsky文法體系該體系對產(chǎn)生式的形式做了一些規(guī)定，分為四類，即0型、1型、2型、3型文法3型文法也稱正規(guī)文法右線性文法（Right-linearGrammar）：

A→ωB或A→ω，其中A、B∈VN,ω∈VT*。左線性文法（Left-linearGrammar）：

A→Bω或A→ω，其中A、B∈VN,ω∈VT*。對應(yīng)的語言：正規(guī)語言對應(yīng)的自動機(jī)：有限自動機(jī)（FiniteAutomation）。例.文法SaS，Sa

對應(yīng)正規(guī)式：a+，或者a*a2型文法也稱上下文無關(guān)文法（CFG：Context-freeGrammar)