第2章編譯程序構造的基礎知識兩個基本問題:一是如何生成正確的程序，二是如何自動檢查是正確的程序。圍繞這兩個問題，提出相關概念。

本章討論問題：文法和語言的概念和定義文法和語言的分類句型分析

語法分析樹的計算機生成

簡略回顧

?

對程序的理解程序是計算機執行的一系列指令；程序是計算任務的處理對象和處理規則的描述。

?

對程序設計語言的理解程序設計語言是程序的書寫規范；程序設計語言的要素：一組記號(符號)和一組規則。程序設計語言程序是：程序設計語言之符號集合上的、按一定規則組成的符號串。新概念?語言是一切句子的集合；程序設計語言是一切程序的集合；把程序看做程序設計語言的句子。?

程序是(程序設計）語言的句子?

如何系統地構造程序？或者，一般地，如何為一個(程序設計)語言生成句子？

2.1符號串與符號串集合語言實際上是一個符號串集合；句子是一個語言之字母表上按一定規則構造的符號串。1.字母表:

有窮非空的符號集合。

例∑={a,b,c}B={0,1}C語言字母表={字母，數字，界限符}

不同的語言有不同的字母表。字母表上的元素（即符號）組成符號串。2.符號串:

由字母表上的符號所組成的有窮序列。⑴字母表B={0，1}上的符號串：0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,0001,0010,0100,1000,0011,…,ε（空串）

字母表A={a,b,c}上的符號串：

a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac,baa,abcab,…,ε注意：順序是重要的,ab≠baC語言字母表上的符號串？長度：|aabcaca|=7|ε|=0⑵子符號串若u=xvy

，其中|v|≠0（|u|>=|v|），則v是u中的子符號串。例a+(b-c)/d中的子符號串:符號串的頭與尾

abc的頭：a,ab,abc,?

abc的尾：c,bc,abc,?x=t…(關注符號串x之頭t)x=…t(關注符號串x之尾t)x=…t…(關注t出現在符號串x中)⑶對符號串的運算聯結（或并置）：

x=aby=ba

xy=abba

yx=baab

對任何符號串x，有x=x=x。

方冪：xn=xx…x(x自身聯結n次)

xn=xn-1x=xxn-1

x0=?

x3=(ab)3=ababab|xy|=|x|+|y||xn|=n|x||x0|=0

特例：若x字母表，則|xn|=n,因為|x|=1。

3.符號串集合⑴概念

一切元素都是某字母表上的符號串的集合。

⑵表示法枚舉法{1，11，111，1111}

省略法{1，11，111，1111，┅}

描述法{1i|i≥1}或{x|x全由1組成,|x|≥1}

一般，描述法形式：{x|x滿足的條件}j注意：一定不能涉及含義,如{x|x=∑10i,j≥0}。

i=0⑶對符號串集合的運算乘積：AB={xy|x∈A且y∈B}{1,0}{a,b,c}=?

對任何符號串x有x=x=x，因此，{}A=A{}=A，但?A=A?=?。

方冪：An=AA…A(n個A乘積）

An=An-1A=AAn-1

特例，字母表A的方冪，x∈An,|x|=n{1,0}3=?{1,0}n=?4.字母表的閉包與正閉包閉包A*=A0∪A1∪┅∪An∪┅{0，1，2}*

正閉包A+=A1∪┅∪An∪┅{0，1，2}+

x∈A+,則|x|≥1

x∈A*,則|x|≥0

任何一個語言是其字母表之正閉包的真子集。如何找出此真子集？或說，如何找出其句子？2.2文法與語言文法規定語言中句子的構造規則。從文法生成的一切句子構成語言。2.2.1

文法及其應用1.重寫規則定義：U::=u

規則表示法：通常的E::=E+TE::=T

或E::=E+T|T

術語：非終結符號，非終結符號集VN

終結符號，終結符號集VT

（

VN∩VT=?V=

VN∪VT

）單規則U::=V其中U,VVN,

規則U::=ε2.文法文法G[Z]是非空有窮的重寫規則集合，其中Z是識別符號（或稱開始符號），G是文法名。例G1[E]：E::=E+TE::=TT::=T*FT::=FF:=(E)F::=iG2[E]：E::=E+T|TT::=T*F|FF::=(E)F::=i

文法的四要素：VN，VT，P，Z3.應用文法生成句子

G[<變量說明>]:1.<變量說明>::=<類型符><變量名>2.<類型符>::=int

6.<變量名>::=b

3.<類型符>::=float7.<變量名>::=c4.<類型符>::=char8.<變量名>::=d5.<變量名>::=a例試以文法G[<變量說明>]為例，考察如何應用文法來生成句子。替換為<變量說明>=><類型符><變量名>(規則1)

=>int<變量名>(規則2)=>inta

(規則5)

替換為<變量說明>=><類型符><變量名>(規則1)

=>float<變量名>(規則3)=>floatc

(規則7)這樣，得到兩個變量說明：

inta；floatc；它們不言而喻書寫上是正確的。顯然，應用不同的規則進行替換，就可以得到不同的變量說明。從識別符號出發，通過重復應用重寫規則，對非終結符號進行替換而生成的終結符號串稱為文法的句子。歸納起來，應用文法生成句子的步驟如下。步驟1從識別符號出發，以識別符號作為當前符號串；步驟2把當前符號串中最左的非終結符號，替換為以該非終結符號為左部的重寫規則之右部符號串；步驟3以替換所得的新符號串作為當前符號串，重復步驟2，直到當前符號串中再無非終結符號可被替換而結束。最終所得的就是句子，它全由終結符號組成。這樣生成的變量說明可以有多少個？顯然僅34=12個。現在對上面的文法G[<變量說明>]做一些修改。G[<變量說明>]：<變量說明>::=<類型符><變量名>；（1）<類型符>::=int

（2）<類型符>::=float（3）<類型符>::=char（4）<變量名>::=<字母>（5）<變量名>::=<變量名><字母>（6）<字母>::=a（7）<字母>::=b（8）<字母>::=c（9）<字母>::=d（10）

例現在以修改后的文法G[<變量說明>]為例，考察如何應用文法來生成句子。

替換為<變量說明>

=><類型符><變量名>

(規則1)

=>int<變量名>(規則2)=>int<變量名><字母>

(規則6)=>int<字母><字母>(規則5)=>inta<字母>(規則7)=>intab(規則8)

如果在第4步時不是應用規則5，而是應用規則6，則將生成符號串：int<變量名><字母><字母>，最終將生成由3個字母組成的變量名。每重復應用規則6一次，變量名中就將多一個字母。這表明將可以生成無限多個變量說明。因此，文法是以有窮的方式描述（構造）潛在地無窮的符號串集合的手段。

一個有限多個規則的文法,能生成無限多個的句子，是因為規則6那樣形式的規則。在對<變量名>進行替換時,每應用規則6一次，變量名中就將多增加一個字母，應用任意多次，便可生成任意長的變量名，從而生成任意的變量說明。規則6形式的規則稱為遞歸定義的規則,簡稱遞歸規則。關于遞歸，有規則遞歸與文法遞歸兩大類。規則遞歸：若規則形如U::=U…，則稱文法關于非終結符號U規則左遞歸；若規則形如U::=…U，則稱文法關于非終結符號U規則右遞歸；若規則形如U::=…U…，則稱文法關于非終結符號U規則（一般）遞歸。文法遞歸：文法關于非終結符號U，若存在U=>+U…,則稱文法關于非終結符號U文法左遞歸;若存在U=>+…U,則稱文法關于非終結符號U文法右遞歸;若存在U=>+…U…,則稱文法關于非終結符號U文法(一般)遞歸。引進概念：直接推導=><變量說明>=><類型符><變量名>

替換為<變量說明>=><類型符><變量名>(規則1)

<類型符><變量名>

=>int<變量名>(規則2)

int<變量名>=>int<變量名><字母>(規則6)

int<變量名><字母>=>int<字母><字母>(規則5)

int<字母><字母>=>int

a<字母>(規則7)

int

a<字母>=>intab(規則8)

直接推導時，給定v=xUy，在其中找出U，應用規則U::=u,

得到w=xuy，稱v直接推導到w,記為：v=>w

一般說，總有：U::=u

xUy=>xuy推導（直接推導序列）：=>+<變量說明>=><類型符><變量名>

=>int<變量名>=>int<變量名><字母>=>int<字母><字母>=>inta<字母>=>intab

因此，<變量說明>=>+

int

ab

推導時，給定符號串v，找到v=>u1=>u2=>…=>un-1=>w

得到符號串w,稱v推導到w,記為：v=>+w,也稱w是相對于v的一個字。一般，從識別符號開始推導，例如，

<變量說明>=>+int

<變量名><字母>(長度3)<變量說明>=>+int

ab(長度6)

推導長度：直接推導的步數。對照：直接推導v=>w(U::=uv=xUyw=xuy)

推導v=>+w(v=>u1=>…=>un-1=>w)

廣義推導v=>*w(v=>+w或v=w)

通常考慮的都是從識別符號出發的推導：

Z=>*xx∈(VN

∪VT)+

直接歸約：v=>ww直接歸約為v

歸約:v=>+ww歸約為v

廣義歸約:v=>*ww廣義歸約為v

請對照比較推導與歸約這兩個概念。應用文法生成句子的步驟：步驟1以識別符號為當前符號串；步驟2對當前符號串中的一個非終結符號進行替換,把它替換為以此非終結符號為左部的規則之右部符號串,生成新的當前符號串；步驟3重復步驟2,直到當前符號串中不包含非終結符號,最終不包含非終結符號的符號串就是所生成的句子。設G[Z]是一個文法。如果符號串x是從識別符號Z推導所得，即，Z=>*xx(VNVT)+則稱該符號串x是文法G的句型。如果一個句型x全部由終結符號組成，即，Z=>*xxVT+則稱該句型x是文法G的句子。重要概念：句型、句子句型：Z=>*x,x∈(VN∪VT)+

句子：Z=>*x,x∈VT+

例int

abcd

注意：應用文法生成句子僅是形式上的，看下頁的例子。

G[<句子>]:

1.<句子>::=<主語><謂語><狀語>

2.<主語>::=<名詞>6.<名詞>::=Marry

3.<謂語>::=<動詞>7.<名詞>::=chair

4.<狀語>::=<介詞><名詞>8.<動詞>::=seats

5.<名詞>::=Tom9.<介詞>::=on

可以有：

<句子>=>+Tomseatsonchair

但也可有：

<句子>=>+chairseatsonTom

注意：句子和<句子>在概念上的區別。

重要概念：短語、簡單短語

已知w=xuy是文法G的句型

短語

u:Z=>*

xUyU∈VN

U=>+u

簡單短語

u:Z=>*

xUyU∈VN

U=>u

如何尋找句型中的短語與簡單短語?

(句型中

⑴可(直接)歸約且

⑵(直接)歸約后所得新符號串仍為句型

的子符號串u

)

句柄

:句型中的最左簡單短語

任何一個句型的句柄總是存在且唯一的。例外是僅由識別符號組成的句型。

設有文法G[<標識符>]：<標識符>::=<字母>|<標識符><字母>|<標識符><數字><字母>::=a|b|c<數字>::=1|2|3|4簡單短語：<標識符>=>*<字母><字母>c,<標識符>=>*a<字母>c,且<字母>::=a<標識符>=>*a<字母><字母>,<標識符>=>*a<字母>c,且<字母>::=c短語：<標識符>=>*<標識符>c,<標識符>=>*a<字母>c,且<標識符>=>+a<字母>(長度為3)<標識符>=>*<標識符><字母>c,<標識符>=>*a<字母>c,且<標識符>=>+a（長度為2）<標識符>=>*a<字母><字母>,<標識符>=>*a<字母>c,且<字母>=>+c(長度為1)句柄：句型a<字母>c中的句柄是a。概括文法G:有窮非空的重寫規則集合四要素：VN，VT，P，Z句型：Z=>*t,t∈(VN∪VT)+句子：Z=>*t,t∈VT+概念：推導，歸約簡單短語，短語，句柄推導

^

E^ETFiiiii

++++++++

T^T^T^T^TFii

*

*

*

*

F^F^F^i^4.句子生成的計算機實現實質是推導的構造。要點是推導在計算機內的存儲表示。

其中包含兩類結點，一類鏈接結點結構形如：另一類符號結點結構形如：鏈接結點可采用結構類型定義如下：

typedef

struct

鏈接結點{符號結點類型*句型首符號結點指針；

struct

鏈接結點*下一句型鏈頭指針；}鏈接結點類型；鏈接結點可采用結構類型定義如下：

typedef

struct

符號結點{int

文法符號序號；

struct

符號結點*后繼符號結點指針；}符號結點類型；其中，為簡單起見，文法符號用文法符號的序號代替。

文法符號序號

后繼符號結點指針

句型首符號結點指針

下一句型鏈頭指針顯然每一“列”（垂直鏈）中各結點相應的符號組成一個句型。一個推導，其中的每一步直接推導，總是把相應句型中最左的非終結符號，替換為以其為左部的重寫規則之右部符號串，稱為最左推導。一個推導，其中的每一步直接推導，總是把相應句型中最右的非終結符號，替換為以其為左部的重寫規則之右部符號串，稱為最右推導。這易于用C語言結構類型實現。以最左推導的建立為例，程序控制流程示意圖如下。

建立最左推導

置初值

把識別符號置為當前句型,

建立一“列”結點

當前句型中包含

N

非終結符號

Y

復制當前句型一“列”結點，把所復制的作為當前句型，并建立與原有當前句型的鏈接

取到當前句型的最左非終結符號U相應的結點

以U為左部的Y

規則僅一個

N

顯示以U為左部的各規則

用戶選擇一個規則，

k=規則序號

關于規則k的右部生成結點鏈，代替U相應的結點出口k=規則序號

為顯示規則，并按規則右部展開，必須考慮文法在計算機內的存儲表示。G[E]：

E::=E+TE::=TT::=T*FT::=FF::=(E)F::=i一種是數組表示。一種是鏈表表示。數組表示：左部右部符號串右部長度相應的C語言數據結構定義：typedef

struct

{符號左部符號；符號右部符號串[MaxRightPartLength+1];

int

右部長度；}規則;規則

文法[MaxRuleNum+1];其中，typedefchar符號[MaxLength+1]；符號

非終結符號集[MaxVnNum+1];

符號

終結符號集[MaxVtNum+1];

為便于處理，以符號的序號代替符號本身：typedef

struct

{int

左部符號序號；

int

右部符號串[MaxRightPartLength+1];

int

右部長度；}規則;規則

文法[MaxRuleNum+1];文法G在計算機內的存儲表示:E::=E+TE::=T

T::=T*FT::=FF::=(E)F::=i規則E::=E+T:在計算機內的存儲表示:

文法[1]：

{101，

{101，

1，

102}，

3}規則E::=T在計算機內的存儲表示：文法[2]：

{101，

{102}，

1}T∈VT：T在VT中的序號,U∈VN：U在VN中的序號+100

101101，1，10231011021102102，2，103310210311033，101，4310351文法

規則左部

下一規

右部符

x11x12…x1n1

^

符號U1則指針

號指針

U2x21x22…x2n2

^

∶

Ul

^

xl1xl2…

xlnl

^

文法的鏈式表示：

文法G

EE+T^

ET^

TT*F^

TF^

F(E)^

F^i^

2.2.2語言的概念程序設計語言L是一切程序P的集合。

PL

L∑+

（∑=VT

）語言是相應文法一切句子的集合。

L(G[Z])={x|Z=>*x,x∈VT+

}

文法確定語言。

L(G[<程序>])={P|<程序>=>*P,P∈VT+

}

語言可能是有窮的，也可能是無窮的，這時是因為相應文法存在遞歸性：規則遞歸與文法遞歸。一個語言是無窮的,則它相應的文法必定是遞歸定義的。C語言中的規則遞歸和文法遞歸規則左遞歸有：

<整型常量>::=<整型常量><數字>

規則右遞歸有：

<因式>::=!<因式>

文法右遞歸于<語句>：

<語句>::=<控制語句><控制語句>::=<條件語句><條件語句>::=if(<表達式>)<語句>else<語句>

因此，

<語句>=>+…<語句>

也可以說，C語言文法遞歸于<語句>：<語句>=>+…<語句>…為語言構造文法

L1={ai

bj

ck|i,j,k≥1}aa…aabb…bbcc…ccABCABCABCSG1[S]:S::=ABCA::=Aa|a

B::=Bb|b