第二章高級語言及其語法描述n

2.1程序語言的語法和語義

1語法任何語言均可看作一個集合。這個集合中的每個元素都是在確定符號集（字母表）上的一個符號串。對于自然語言來說，它們是定義在某個字母表上的句子的集合。對于程序語言來說，它們也是定義在某個字母表上的句子的集合。這里的句子，就是一個源程序。詞法規(guī)則單詞符號是語言中具有獨立意義的最基本單位。語言的單詞符號是由詞法規(guī)則所確定的，即詞法規(guī)則規(guī)定了單詞符號的形成規(guī)則。語法規(guī)則上下文無關(guān)文法

“我是高校生”。是漢語的一個句子用語法來描述：〈句子〉∷=〈主語〉〈謂語〉〈主語〉∷=〈代詞〉｜〈名詞〉〈代詞〉∷=我｜你｜他〈名詞〉∷=王明｜高校生｜工人｜英語〈謂語〉∷=〈動詞〉〈干脆賓語〉〈動詞〉∷=是｜學(xué)習(xí)〈干脆賓語〉∷=〈代詞〉｜〈名詞〉

2語義定義程序的意義。沒有公認的形式系統(tǒng)描述語義。

3

高級語言的分類強制式語言(ImperativeLanguage)/過程式語言FORTRAN,C,Pascal應(yīng)用式語言(ApplicativeLanguage)/函數(shù)式語言LISP基于規(guī)則的語言(Rule-basedLanguage)Prolog面對對象語言(Object-orientedLanguage)

2.3程序語言的語法描述一、字母表和符號串

字母表：符號的非空有限集合例：={a，b，c}

符號：字母表中的元素例：a，b，c

符號串：符號的有窮序列例：a,aa,ac,abc，..

空符號串：無任何符號的符號串(ε)

符號串的形式定義

有字母表，定義：（1）ε是上的符號串；（2）若x是上的符號串，且a，則ax或xa是上的符號串；（3）y是上的符號串，iff（當(dāng)且僅當(dāng)）y可由（1）和（2）產(chǎn)生。

符號串集合：由符號串構(gòu)成的集合。二、符號串和符號串集合的運算

1.符號串相等：若x、y是集合上的兩個符號串，則x＝y(tǒng)iff（當(dāng)且僅當(dāng)）組成x的每一個符號和組成y的每一個符號依次相等。

2.符號串的長度：x為符號串，其長度|x|等于組成該符號串的符號個數(shù)。例：x＝STV，|x|=3例：A＝{a,b},B={c,d},AB=？4.符號串集合的乘積運算：令A(yù)、B為符號串集合，定義

AB＝{xy|x∈A,y∈B}

{ac，ad，bc，bd}

因為εx＝xε＝x，所以{ε}A={ε}A=A3.符號串的連接：若x、y是定義在Σ是上的符號串，且x＝XY，y＝Y(jié)X，則x和y的連接xy＝XYYX也是Σ上的符號串。留意：一般xy≠yx，但εx＝xε6.符號串集合的閉包運算：設(shè)A是符號串集合，定義

A＋＝A1∪A2∪A3∪……∪An∪……

稱為集合A的正則閉包。

A*＝A0∪A＋

稱為集合A的閉包。例：A={x,y}A＋＝？

A*＝？

5.符號串集合的冪運算：有符號串集合A，定義A0={ε}, A1=A, A2=AA, A3=AAA,…………An＝An-1A=AAn-1，n>0{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A1

A2

A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A0A1

A2

A3為什么對符號、符號串、符號串集合以及它們的運算感愛好？若A為某語言的基本字符集A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B為單詞集B={begin,end,if,then,else,for,……,<標識符>,<常量>,……}則BA*。語言的句子是定義在B上的符號串。若令C為句子集合，則CB*,程序C三文法的直觀理解

1.什么是文法：文法是對語言結(jié)構(gòu)的定義與描述。即從形式上用于描述和規(guī)定語言結(jié)構(gòu)的稱為“文法”（或稱為“語法”）。例：有一句子：“我是高校生”。這是一個在語法、語義上都正確定句子，該句子的結(jié)構(gòu)（稱為語法結(jié)構(gòu)）是由它的語法確定的。在本例中它為“主謂結(jié)構(gòu)”。如何定義句子的合法性？有窮語言無窮語言

2.語法規(guī)則：我們通過建立一組規(guī)則（產(chǎn)生式），來描述句子的語法結(jié)構(gòu)。規(guī)定用“::=”表示“由……組成”。<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=王民|高校生|工人|英語<謂語>::=<動詞><干脆賓語><動詞>::=是|學(xué)習(xí)<干脆賓語>::=<代詞>|<名詞>由產(chǎn)生式推導(dǎo)句子：有了一組產(chǎn)生式之后，可以依據(jù)確定的方式用它們?nèi)ネ茖?dǎo)或產(chǎn)生句子。推導(dǎo)方法：從一個要識別的符號起先推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部來替代產(chǎn)生式的左部，每次僅用一條產(chǎn)生式去進行推導(dǎo)。<句子>=><主語><謂語><主語><謂語>=><代詞><謂語> …………這種推導(dǎo)始終進行下去，直到全部帶<>的符號都由終結(jié)符號替代為止。<句子>=><主語><謂語>

=><代詞><謂語>

=>我<謂語>=>我<動詞><干脆賓語>=>我是<干脆賓語>

=>我是<名詞>=>我是高校生<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=王民|高校生|工人|英語<謂語>::=<動詞><干脆賓語><動詞>::=是|學(xué)習(xí)<干脆賓語>::=<代詞>|<名詞>推導(dǎo)方法：從一個要識別的符號起先推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部來替代產(chǎn)生式的左部，每次僅用一條產(chǎn)生式去進行推導(dǎo)。例：有一英語句子：Thebigelephantatethepeanut.<句子>::=<主語><謂語><主語>::=<冠詞><形容詞><名詞><冠詞>::=the<形容詞>::=big<名詞>::=elephant<謂語>::=<動詞><賓語><動詞>::=ate<賓語>::=<冠詞><名詞><名詞>::=peanut<句子>=><主語><謂語>

=><冠詞><形容詞><名詞><謂語>

=>the<形容詞><名詞><謂語>

=>thebig<名詞><謂語>

=>thebigelephant<謂語>

=>thebigelephant<動詞><賓語>

=>thebigelephantate<賓語>

=>thebigelephantate<冠詞><名詞>

=>thebigelephantatethe<名詞>

=>thebigelephantatethepeanut<句子>::=<主語><謂語><主語>::=<冠詞><形容詞><名詞><冠詞>::=the<形容詞>::=big<名詞>::=elephant|peanut<謂語>::=<動詞><賓語><動詞>::=ate<賓語>::=<冠詞><名詞>上述推導(dǎo)可寫成<句子>=>thebigelephantatethepeanut+說明：

(1)有若干語法成分同時存在時，我們總是從最左的語法成分進行推導(dǎo)，這稱之為最左推導(dǎo)，類似的有最右推導(dǎo)（一般推導(dǎo)）。

(2)從一組產(chǎn)生式可推出不同的句子，如以上產(chǎn)生式還可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它們在語法上都正確，但在語義上都不正確。所謂文法是在形式上對句子結(jié)構(gòu)的定義與描述，而未涉及語義問題。

4.語法樹：我們用語法樹來描述一個句子的語法結(jié)構(gòu)。<句子><主語><謂語><冠詞><形容詞><名詞><動詞><賓語><冠詞><名詞>Thebigelephantatethepeanut語法成分（在形式語言中又稱“非終結(jié)符”）單詞符號（在形式語言中又稱“終結(jié)符號”)1文法的定義四文法和語言的形式定義定義1:文法G=（VN，VT，P，Z） VN：非終結(jié)符號集 VT：終結(jié)符號集 P：產(chǎn)生式或規(guī)則的集合Z：起先符號（識別符號）Z∈VNV＝VN∪VT稱為文法的字匯表產(chǎn)生式：U::xU∈VN,x∈V*其中:A.產(chǎn)生式：產(chǎn)生式是一個有序?qū)?U,x),通常寫為:U::x或Ux；|U|=1|x|0B.非終結(jié)符號：出現(xiàn)在產(chǎn)生式的左部,且能推出符號或符號串的那些符號。其全體構(gòu)成非終結(jié)符號集，記為VN

。C.終結(jié)符號：不出現(xiàn)在產(chǎn)生式的左部,且不能推出符號或符號串的那些符號。其全體構(gòu)成終結(jié)符號集，記為VT

。P={<無符號整數(shù)>→<數(shù)字串>；

<數(shù)字串>→<數(shù)字串><數(shù)字>；

<數(shù)字串>→<數(shù)字>；

<數(shù)字>→0；

<數(shù)字>→1；

…………

<數(shù)字>→9；

}Z=<無符號整數(shù)>；例：無符號整數(shù)的文法：

G[<無符號整數(shù)>]=（VN，VT，P，Z）

VN＝{<無符號整數(shù)>,<數(shù)字串>,<數(shù)字>} VT={0,1,2,3,……9}幾點說明：產(chǎn)生式左邊符號構(gòu)成集合VN，且Z∈VN有些產(chǎn)生式具有相同的左部，可以合在一起例、<無符號整數(shù)>→<數(shù)字串>；

<數(shù)字串>→<數(shù)字串><數(shù)字>|<數(shù)字>；

<數(shù)字>→0|1|2|3|……|9文法的BNF表示給定一個文法，實際只需給出產(chǎn)生式集合，并指定識別符號例、G[<無符號整數(shù)>]<無符號整數(shù)>→<數(shù)字串>；

<數(shù)字串>→<數(shù)字串><數(shù)字>|<數(shù)字>；

<數(shù)字>→0|1|2|3|……|92推導(dǎo)與歸約定義2：干脆推導(dǎo)：文法G：v＝xUy，w＝xuy,其中x、y∈V*，U∈VN,u∈V*,若U::u∈P，則vw。若x＝y(tǒng)＝ε，有U::u，則Uu換句話說，x和y是符號串，若運用一次產(chǎn)生式可以從x變換出y，則稱x干脆推導(dǎo)出y(或者說y是x的干脆推導(dǎo)），記為xy。當(dāng)符號串已沒有非終結(jié)符號時，推導(dǎo)就必需終止。因為終結(jié)符不行能出現(xiàn)在產(chǎn)生式左部，所以將在產(chǎn)生式左部出現(xiàn)的符號稱為非終結(jié)符號。例如：G[N]：

N→ND|DD→0|1|2|3|4|5|6|7|8|9NNDNDDND9N09D09109

(6)==>==>(1)==>(3)(4)==>==>(2)(5)==>＋N==>109定義3：

+推導(dǎo)：x和y是符號串，若使用若干次產(chǎn)生式可以從x變換出y，則稱x推導(dǎo)出y(或者說y是x的推導(dǎo)），記為xy。＋NNDNDDND9N09D09109

(6)==>==>(1)==>(3)(4)==>==>(2)(5)==>例：則：定義4：

*推導(dǎo)：x和y是符號串，若使用0次或若干次產(chǎn)生式可以從x變換出y，則稱x*推導(dǎo)出y(或者說y是x的*推導(dǎo)），記為xy。**N==>109則：*N==>N或者說：若有直接推導(dǎo)序列：x=U0==>U1==>U2==>……==>Un=y,則x==>y。+規(guī)范推導(dǎo)＝最右推導(dǎo)定義5：最右推導(dǎo)：若符號串α中有兩個以上的非終結(jié)符時，對推導(dǎo)的每一步堅持把α中的最右非終結(jié)符進行替換，稱為最右推導(dǎo)。最左推導(dǎo)：若符號串α中有兩個以上的非終結(jié)符時，對推導(dǎo)的每一步堅持把α中的最左非終結(jié)符進行替換，稱為最左推導(dǎo)。定義6：推導(dǎo)的逆過程稱之為歸約。例：x==>y,可稱為x干脆推導(dǎo)出y，也可稱為y干脆歸約出x。＋x==>y,可稱為x推導(dǎo)出y，也可稱為y歸約出x。3語言的形式定義文法G[Z]所產(chǎn)生的全部句子的集合定義7：文法G[Z] （1）句型：x是句型

Zx,且x∈V*； （2）句子：x是句子

Zx,且x∈VT*； （3）語言：L（G[Z]）={x|Zx，x∈VT*}；+*+例：{abna|n≥1},構(gòu)造其文法

G1[Z]：Z→aBa, B→b|bBG2[Z]：Z→aBa, B→b|Bb定義8.G和G'是兩個不同的文法，若L(G)=L(G'),

則G和G’為等價文法。編譯感愛好的問題是:給定終極符x,文法G,求xL(G)?x算法1算法2xL(G)?Gyn出錯處理停機4文法分類

形式語言：用文法和自動機所描述的沒有語義的語言。文法定義：喬姆斯基將全部文法都定義為一個四元組： G=（VN，VT，P，Z） VN：非終結(jié)符號集 VT：終結(jié)符號集 P：產(chǎn)生式或規(guī)則的集合 Z：起先符號（識別符號）Z∈VN

語言定義：L（G[Z]）={x|Z==>x,x∈VT*,}+文法和語言分類：0型、1型、2型、3型這幾類文法的差別在于對產(chǎn)生式施加不同的限制。定義9：0型文法：P：u→v

其中u∈V＋，v∈V*

0型語言：L0這種語言可以用圖靈機(Turing)接受.

0型文法稱為短語結(jié)構(gòu)文法。產(chǎn)生式的左部和右部都可以是符號串，一個短語可以產(chǎn)生另一個短語。定義10：1型文法：P：xUy→xuy

其中U∈VN，x、y、u∈V*

1型語言：L1這種語言可以由一種線性界限自動機接受. 稱為上下文敏感或上下文有關(guān)。也即只有在x、y這樣的上下文中才能把U改寫為u定義11：2型文法：P：U→u

其中U∈VN，u∈V*

2型語言：L1這種語言可以由下推自動機接受.稱為上下文無關(guān)文法。也即把U改寫為u時，不必考慮上下文。留意：2型文法與BNF表示相等價。（右線性）

P：U→T

或U→Tw

其中U、w∈VNT∈VT

3型語言：L3又稱正則語言、正則集合 這種語言可以由有窮自動機接受.

3型文法稱為正則文法。它是對2型文法進行進一步限制。（左線性）

P：U→T

或U→

wT

其中U、w∈VNT∈VT定義12：3型文法：根據(jù)上述討論，L0L1L2L30型文法可以產(chǎn)生L0、L1、L2、L3，但2型文法只能產(chǎn)生L2，不能產(chǎn)生L1。∪∪∪5語法樹與二義性文法1推導(dǎo)與語法樹語法樹：句子結(jié)構(gòu)的圖示表示法，通常表示成一棵倒立的樹。

結(jié)點：符號 根結(jié)點：識別符號 中間結(jié)點：非終結(jié)符 葉結(jié)點：終結(jié)符或非終結(jié)符

邊：表示結(jié)點間的派生關(guān)系。

ZUVabcd

注意一個重要事實：文法所能產(chǎn)生的句子，可以用不同的推導(dǎo)原則（使用產(chǎn)生式順序不同）將其推導(dǎo)出來。語法樹的生成規(guī)律不同，但最終生成的語法樹形狀完全相同。某些文法有此性質(zhì)，而某些文法不具此性質(zhì)。句型的推導(dǎo)及語法樹的生成（自頂向下）給定G[Z]，句型w：可建立推導(dǎo)序列，Z==>w

可建立語法樹，以Z為樹根結(jié)點，每步推導(dǎo)生成語法樹的一枝，最終可生成句型的語法樹。*

<無符號整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字>1(1)(2)(3)(5)(4)0一般推導(dǎo)：樹與推導(dǎo)句型推導(dǎo)過程

句型語法樹的生長過程 由推導(dǎo)構(gòu)造語法樹1從識別符號開始，自左向右建立推導(dǎo)序列。由根結(jié)點開始，自上而下建立語法樹。P={<無符號整數(shù)>→<數(shù)字串>；

<數(shù)字串>→<數(shù)字串><數(shù)字>；

<數(shù)字串>→<數(shù)字>；

<數(shù)字>→0；

<數(shù)字>→1；

…………

<數(shù)字>→9；

}Z=<無符號整數(shù)>；例：無符號整數(shù)的文法：

G[<無符號整數(shù)>]=（VN，VT，P，E）

VN＝{<無符號整數(shù)>,<數(shù)字串>,<數(shù)字>} VT={0,1,2,3,……9}例：G[<無符號整數(shù)>] 句型10[<無符號整數(shù)>]<無符號整數(shù)><數(shù)字串><數(shù)字串>==><數(shù)字串><數(shù)字><數(shù)字串><數(shù)字>==>0<數(shù)字串>0==><數(shù)字><數(shù)字>0==>110==>最右推導(dǎo) 由語法樹構(gòu)造推導(dǎo)2自葉而根修剪子樹的末端結(jié)點，直至把整棵樹剪掉（留根），每剪一次對應(yīng)一次歸約。從句型開始，自右向左地逐步進行歸約，建立推導(dǎo)序列。2