Part2

高級語言及其語法描述授課：胡靜內(nèi)容提要預(yù)備知識——形式語言基礎(chǔ)程序語言的定義（語法定義、語義定義）高級語言的一般特性（程序結(jié)構(gòu)、數(shù)據(jù)類型和操作、語句與控制結(jié)構(gòu)）程序語言的文法文法的類型上下文無關(guān)文法及其語法樹有關(guān)文法實用中的一些說明預(yù)備知識更多的概念和一些約定A,B,C,…用來表示非終結(jié)符a,b,c,…表示終結(jié)符…,X,Y,Z可以用來表示終結(jié)符或者非終結(jié)符…,w,x,y,z表示終結(jié)符號串α,β,γ,δ,…表示由終結(jié)符或非終結(jié)符構(gòu)成的符號串在產(chǎn)生式A→α中，A是產(chǎn)生式的左邊(lefthandside,LHS)α是產(chǎn)生式的右邊(righthandside,RHS)A→α1|…|αn

表示產(chǎn)生式A→α1,…,A→αn符號串和符號串集合的運算符號串和符號串集合的運算將字符看做符號，則單詞就是符號串，單詞集合就是符號串的集合將單詞看做符號，則句子就是符號串，而所有句子的集合（語言）就是符號串的集合程序語言的定義程序語言的語法定義所謂一個語言的語法是指這樣一組規(guī)則，用它可以形成和產(chǎn)生一個合式的程序。這些規(guī)則一部分稱為詞法規(guī)則則，另一部分稱為語法規(guī)則（或產(chǎn)生規(guī)則）詞法規(guī)則：詞法規(guī)則規(guī)定了字母表中哪樣的字符串是一個單詞符號，是單詞符號的形成規(guī)則語法規(guī)則：語言的語法規(guī)則規(guī)定了如何從單詞符號形成更大的結(jié)構(gòu)（即語法單位），換言之，語法規(guī)則是語法單位的形成規(guī)則程序語言的定義程序語言的語義定義所謂一個語言的語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意義。這些規(guī)則稱為語義。我們將要介紹的是目前大多數(shù)編譯程序普遍采用的一種方法，即基于屬性文法的語法制導(dǎo)翻譯方法，雖然還不是形式系統(tǒng)，但是比較接近形式化的。高級語言的一般特征高級語言的程序結(jié)構(gòu)程序子程序或分程序語句表達(dá)式數(shù)據(jù)引用算符函數(shù)調(diào)用數(shù)據(jù)類型和操作數(shù)據(jù)類型的要素：用于區(qū)別這種類型的數(shù)據(jù)對象的屬性；這種類型的數(shù)據(jù)對象可以具有的值；可以作用于這種類型的數(shù)據(jù)對象的操作；數(shù)據(jù)類型分類：初等數(shù)據(jù)類型：數(shù)值數(shù)據(jù)、邏輯數(shù)據(jù)、字符數(shù)據(jù)、指針類型數(shù)據(jù)結(jié)構(gòu)：數(shù)組、記錄、字符串、表格、棧、隊列和抽象數(shù)據(jù)類型（Ada通過程序包package提供，其余通過類class提供）語句與控制結(jié)構(gòu)表達(dá)式：一個表達(dá)式是由運算量（操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。語句：不同程序語言含有不同形式和功能的各種語句執(zhí)行語句：描述程序的動作，分為賦值語句、控制語句、輸入/輸出語句；說明性語句：定義各種不同數(shù)據(jù)類型的變量或運算從形式上分，語句可以分為簡單句、復(fù)合句和分程序等。文法的直觀概念關(guān)于文法的定義定義3.1文法G定義為四元組（VN,VT,P,S）。其中VN為非終結(jié)符號（或語法實體，或變量）集；VT為終結(jié)符號集；P為產(chǎn)生式（也稱規(guī)則）的集合；VN,VT和P是非空有窮集。S稱做識別符號或開始符號，是一個非終結(jié)符（S∈VN），至少要在一條規(guī)則中作為左部出現(xiàn)。VN和VT不含公共元素，即VN∩VT=Φ。通常V表示VN∪VT，V稱為文法G的字母表或字匯表。例3.1文法G=（VN，VT，P，S）

VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號文法可以簡寫，只需要指出開始符號和產(chǎn)生式即可。關(guān)于文法的定義（續(xù)）定義3.2如α→β是文法G=(VN,VT,P,S)的規(guī)則(或說是P中第一個產(chǎn)生式)，γ和δ是V*中的任意符號串，若有符號串v，w滿足：v=γαδ，w=γβδ，則說v（應(yīng)用規(guī)則α→β）直接產(chǎn)生w，或說w是v的直接推導(dǎo)。（v=>w）例：G[S]：S→0S1，S→01S0S100S11000S11100001111G關(guān)于文法的定義（續(xù)）定義3.3如果存在直接推導(dǎo)的序列：v=w0=>w1=>w2…=>wn=w，(n>0)，則稱v推導(dǎo)出（產(chǎn)生）w（推導(dǎo)長度為n）。記做v=>+w。定義3.4若有v=>+w，或v=w，則記做v=>*w。規(guī)范推導(dǎo)（最右推導(dǎo)）最左推導(dǎo)：若規(guī)則右端符號串中有兩個以上的非終結(jié)符時，先推導(dǎo)左邊的。最右推導(dǎo)：若規(guī)則右端符號串中有兩個以上的非終結(jié)符時，先推導(dǎo)右邊的。關(guān)于文法的定義（續(xù)）定義3.5設(shè)G[S]是一文法，如果符號串x是從識別符號推導(dǎo)出來的，即有S=>*x，則稱x是文法G[S]的句型。若x只由終結(jié)符號組成，則稱x為G[S]的句子。定義3.6文法G所產(chǎn)生的語言定義為集合{x|S=>*x，其中S為文法的開始符號，且x∈VT

*}?？捎肔(G)表示該集合。例：G：S→0S1，S→01S0S100S11000S11100001111L(G)={0n1n|n≥1}關(guān)于文法的定義（續(xù)）定義3.7若L(G1)=L(G2)，則稱文法G1和G2是等價的。例1：如文法G1[A]：A→0R與G2[S]： S→0S1等價

A→01 S→01 R→A1例2：G1[E]:E→i 與 G2[E]：E→T|E+T等價

E→E+E T→F|T*F E→E*E F→（E）|i E→(E)文法的類型Chomsky將文法分為四種類型：0型文法：對任一產(chǎn)生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：對任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅α→ε除外2型文法：對任一產(chǎn)生式α→β，都有α∈VN

，β∈(VN∪VT)*3型文法：任一產(chǎn)生式α→β的形式都為A→aB或A→a，其中A∈VN

，B∈VN

，a∈VT。上述叫做右線性文法，另有左線性文法，二者等價。文法的類型舉例1型（上下文有關(guān)）文法文法G[S]： S→CD Ab→bA

C→aCA

Ba→aB

C→bCB

Bb→bB

AD→aD

C→ε

BD→bD

D→ε

Aa→bDL(G)={ww|w∈{a,b}*}文法的類型舉例2型（上下文無關(guān)）文法文法G[S]： S→aB|bA

A→a|aS|bAA

B→b|bS|aBB

文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0文法的類型舉例定義標(biāo)識符的3型（正規(guī)）文法文法G[I]： I→lT I→l T→lT T→dT T→l T→d文法和語言0型文法0型文法（短語文法）的能力相當(dāng)于圖靈機，可以表征任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的1型文法（上下文有關(guān)文法）產(chǎn)生式的形式為α1Aα2→α1βα2，即只有A出現(xiàn)在α1和α2的上下文中時，才允許β取代A。其識別系統(tǒng)是線性界限自動機。2型文法（上下文無關(guān)文法）產(chǎn)生式的形式為A→β，β取代A時與A的上下文無關(guān)。其識別系統(tǒng)是不確定的下推自動機。3型文法（正則文法）產(chǎn)生的語言是有窮自動機（FA）所接受的集合上下文無關(guān)文法上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計語言的語法結(jié)構(gòu)算術(shù)表達(dá)式語句賦值語句條件語句讀語句……文法G=({E},{+,*,I,(,)},P,E} <條件語句>→if<條件>then<語句>

P: E→i |if<條件>then<語句>else<語句> E→E+E E→E*E E→(E)上下文無關(guān)文法的語法樹用于描述上下文無關(guān)文法的句型推導(dǎo)的直觀方法例:G[S]:

S→aAS

A→SbA A→SS S→a

A→ba

SaASSbAba句型aabbaa的語法樹（推導(dǎo)樹）葉子結(jié)點：樹中沒有子孫的結(jié)點。

從左到右讀出推導(dǎo)樹的葉子標(biāo)記，所得的句型為推導(dǎo)樹的結(jié)果。也把該推導(dǎo)樹稱為該句型的語法樹。aa上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序例:G[S]:

S→aAS

A→SbA A→SS S→a

A→ba

SaASSbAaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa文法的二義性最左（最右）推導(dǎo)：在推導(dǎo)的任何一步αβ，其中α、β是句型，都是對α中的最左（右）非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型文法的二義性例：G[E]:

E→i E→E+E E→E*E E→(E)

EE+EE*Eiii

EE*EiE+Eii句型i*i+i的兩個不同的最左推導(dǎo)：推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i文法的二義性若一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的?；蛘?，若一個文法存在某個句子有兩個不