前述內參回顧

?編譯程序

?編譯方式與解釋方式的根本區別

-編譯程序的工作過程

,編譯程序的結構II

?編譯程序的組織方式

,編譯程序的構造

第二章文法和語言的基本知識

本章主要介紹形式語言理論中的一些最

基本的概念和基礎知識，它是學習以后各章

的基石。

本章內參簡介

?文法的形式定義

?語言的形式定義

?為語言構造文法與由文法推出語言

-語法樹及文法的二義性

?文法和語言的分類

■文法的實用限制

形式語言理論

由Chomsky于1956年首先提出。

；是指由數學方法——形式化方法研究自然語言（如英

語）和人工語言（如程序設計語言）的語法的理論。?

目前在自然語言的翻譯、計算機語言的描述和轉換、

編譯程序的構造、模式識別等方面有廣泛的應用。

2A語官的基本^叔?

一個語言的成分包括字母表（Alphabet），文法（G

rammar）以及它的語義。

；字母表是符號的有窮集，而符號構成了語言中的句子。

語法是結構規則的有窮集，這些規則定義了句子中符號

的合法上下文。

語義通常是操作規則的有窮集，這些規則定義了用該語

言編寫的任何程序在某個計算機上執行的操作性效果。

2.2.1字母表與符號串

1.字母表.......................

字母表是元素的有窮非空的集合。字母表中的元素稱為符號。

例如{a,b,.........y,z},{0,1}等。

，常用X來表示.....................................

注意：字母表中至少包含一個元素。元素可以是字母、數字

或其他符號。?????????

李母表與符號串

2.符號、符號串及其運算（P9）?????

字母表中的元素稱為符節；；；；；；；

符號串是字母表中的符號所組成的任何有窮序列，通常用小寫的字

母表示。

例：S={0,1}貝|00,11,01,10,010..........是符號串。

注意：1）不包含任何符號的符號串為空串，記為￡。；

I擠2）符號串中的符號順序很重要。abrba????

3）符號串x中有ni個符號，貝||x|=mm是長度。

2.2.2符號串運算

■卷號串;的遂接；；；；；；

設X和y是符號串，則稱xy是他們的連接。

例如：x=abc,y=1a

則xy=abc1a,yx=1aabc

即|x|=3,|y|=2,|xy|=3+2=5

注意：對任意一個符號串￡；；；

我們有￡X=X￡=X

■符號串集合的乘積

設A和B是符號串的集合，則A和B的乘積定義為，

AB={xy|xGA,yGB}

例如：A={a,b}B={c,d}

則AB={aGad,bGbd}

集合的乘積是滿足于A,yeB的所有符號串xy

k所構成的集合。；；；；；；；；

注意：；；；；；；；；；；

1、對于任何集合A,有{￡}A=A{4=A

2、{￡}=00/{}

■符號串的方塞

■設X是符號串，X”是X自身連結n次。并且xO=E

■貝ijx1=x

■x2=XX

■Xn=XX..........X=Xxn-1

■、；nk____j______；___J；；；；；；

■例如，設x=abc,則

■x1=abc

■x2=abcabc

■符號串集合的方塞

■A是符號串的集合，An是集合A自身n次相乘，

■并且人。={￡}

■則A1=A

■A2=AA

■A』的..,…A=AAn'1(n>0)

■n個A

■例1A={a,b}A0={E}A1={a,b}

■A2={aa,ab‘ba’bb}

■A3={aa,ab,ba,bb}?{a,b}

■={aaa,aab,aba,abb,baa,bab,bba,bbb}

■符號串集合的正閉包A+與閉包A*

■；A型集合

■A的正閉包A+=A1UA2U......UAn

■A的閉包A*=A0UA1UA2U......UAn

■={￡}UA+

?A={a,b}

■A+={a,b,aa,ab,ba,bb,aaa,aab9....}

■A*={a,a,b,aa,ab,ba,bb,aaa,aab,....}

■A+表示A上元素a,b構成的所有符號串的集合。

2.3文法和語言的形式定義

2.3.1文法的有關概念

1.終結符號?????????

；終結符號是組成語言的基本符號，如保留字、標識符、常數、

運算符、界限符等。終結符號是語言的不可再分的基本符號。終

?結符號形成的集合記為一般用小寫字母表示。

2.非終結符號...........................

；小E終結符號用來表示語言的語法成分（或語法范疇、語法單

后位），例如“賦值語句”。非終結符號所形成的集合記為Vg-

般用大寫字母來表示。

vTnvN=0

2.3文法和語言的形式定義

3.產生式：產生式（規則）是一個有序對（a,B）,通常寫作

oc—6（或鼠：：=|3）

+

其中0C稱為產生式的左部，|3稱為產生式的右部。ae（VTUVN）,

|3e（VTUVN）j*o?；

'產生式是用來定義一個語法成分的。它描述了一個語法成分

的形成規則。例如標識符的構成規則可描述為：

＜標識符》一＜字母）|＜標識符X字母）|＜標識符X數字）

假如有若干條規則有相同的左部，通常寫作：a-PJp2|...|pn

pn稱為a的候選式

例如：1)V句子＞-V主語〉V謂語〉

2)v主語〉一v冠詞〉v名詞〉

3)v謂語〉一v動詞〉v賓語〉

4)v賓語〉一v冠詞〉v名詞〉

5)v名詞〉—?mancar

6)v冠詞＞一the

7)v名詞＞—＞drive

Themandrivethecar

Thecardrivetheman一組規則規定一個語言

Thecardrivethecar的語法結構

Themandrivetheman

2.3.2文法的形式定義

文法是產生式的有窮非空的集合。

文法G是一個四元組，G[S]=(VrVN,P,S)o；

:1r_終結您號藁。；；；；；；

IVN―u非終結符號集。?1III?

圈S——開始符號。至少要在一條產生式中作為左部出現。

P——表示產生式的有窮非空的集合。

例1定義標識符的文法

G[＜標識符＞]=（{A,B,Y,Z,0,1,...,9},

{＜標識符＞,＜字母＞，＜數字＞},P,＜標識符〉）

P定義為：

＜標識符》一＜字母）I＜標識符＞＜字母》I＜標識符＞＜數字）

＜字母＞-A|B|C|D|E|F|G|.......|U|V|W|X|Y|Z

＜數字＞-01112I314|5I6|7|819

2.3.3和語言有關的幾個概念

1.直接推導

如果a->0是文法G的一條產生式，而丫,6是(VTUVN)*中任意

一個符號串，則將a一口作用于符號串ya6上得到符號串丫口6,稱

符號串YP6是符號串Ya6的直接推導，記為

ya6=>yP6

:直接推導的逆過程稱為直接歸約，即由符號串丫口6可直接歸約到丫

a6o

直接推導舉例

例1文法G[E]：

E->E+T|TT-T*F|F一(E)|i

*TFn*T*FF

例2見P14

2.3.3和語言有關的幾個概念

超導；；；；；；；；0

\設鼠0、、、…Qn均為（VTUVJ*中的符號串，且有

0C0=>ot1=>OC2n???0C「10an

則稱以上序列是長度為n的推導，即a0可經過n步推導得到a

+

今

aoan

顯然，這里n“，當n=l,就是直接推導。'；；

當n=0時，oco=ocn.當n》我們稱為廣義推導。

推導的逆過程稱為歸約，即明可歸約到0t0。

2.3.3和語言有關的幾個概念

3.最左推導和最右推導

如果在某個推導過程中的任何一步直接推導an6中，

都是對符號串鼠的最左（右）非終結符號進行替換，則稱其

為最左（右）推導。最右推導又叫做規范推導。規范推導的

逆過程（最左規約）稱為規范規約。

【例1】設有文法G[NJ

N]-N

N-ND|D

D->0|1|2

N1=>N=>ND=>N2=>D2=>12最右推導

N1=>N=>ND=>DD=>1D=>12最左推導

N1=>N=>ND=>DD=>D2=>12不是最左推導

也不是最右推導

【例2】設有文法G[E]：E=>E-T=>E-F=>E-i

E一E+T|E-T|T

=>T-i=>T*F-i=>T*i-i

T—T*F|T/F|F

F->(E)|i=>F*i?i=>(E)*i?i

=>(E+T)*i-i

=>(E+F)*i?i

請寫出字符串（i+i）*i-i最右推導

=>(E+i)*i-i

=>(T+i)*i-F

=>(F+i)*i-F

=>(i+i)*i-i

2.3.3和語言有關的幾個概念P15

4.句型

?設有文法G[S],如果S3u，且(VTUVN)*則稱符號串u

為文法G⑻的句型。由規范推導(最右推導)得至》的句型稱為規范句型.

5.句子；；；；；；；；；；

|設有文法G[S],如果S當u，且UEV/,則稱符號串u為

文法G網的句子。

由此可看出：句型包含句子

■【例1】設有文法G[S]：

■S-01I0S1

S=>01

S=>0S1

=>00S11

=>000111

■S,01,0S1,00S11Q00111者B是句型。

■01和000111又是句型。

【例2】設有文法G[E]：E=>E-T=>E-F=>E-i

E一E+T|E-TIT

T—T*F|T/F|F11=>T-i=>T*F-i=>T*i-i

F一(E)|I=>F*i?i=>(E)*i?i

證明：字符串(i+i)*i-i是文法G[E]的=>(E+T)*i-i

句子

=>(E+F)*i?i

字符串(i+i)*i?i是句子=>(E+i)*i-i

方框里面的字符串是句型=>(T+i)*i-F

=>(F+i)*i-F

=>(i+i)*i-i

2.3.3和語言有關的幾個概念

6.語言

文法G[S]產生的所有句子的集合稱為G所定義的語言，記為L(G[S])

L(G[S])|isi>ui，旦uevj}IIllI

由此可知：1)當文法給定，語言也就確定。

2)L(G)是V/的子集，即屬于V/的符號串x不一定屬于L(G)

2.3.3和語言有關的幾個概念P17

7直接遞歸與間接遞歸?|||?

；如果文法的產生式呈U-…U…形式，則稱其為規則遞歸，也

稱直接遞歸。（U為非終結符）IIIII

1如果文法中有推導Um…U…，則稱其為文法遞歸，也稱

間接遞歸。

所謂遞歸即，規則的左部或右部具有相同的非終結符。

2.3.3和語言有關的幾個概念

8.規則左遞歸與規則右遞歸

如果文法的產生式呈U-U…的形式，則稱其為規則左遞歸。

如果文法的產生式呈U-...U的形式，則稱其為規則右遞歸。

規則左（右）遞歸，也稱直接左（右）遞歸。

9.文法左遞歸與文法右遞歸

如果文法中有推導U3U…，則稱其為文法左遞歸，也稱

間接左遞歸。III

如果文法中有推導ut...u,則稱其為文法右遞歸，也稱

間接右遞歸。

遞歸舉例

：

GJS]S->Sa|Ab|b|cG2[S]：S^a|s|aTb

A—>Bc|aT—S,T|S

B->Sb|b

t直接左遞歸Ii直接右遞歸

G3[S]:S—Aa|c

A—>Bc|a間接左遞歸

B一Sb|b

2.3.3和語言有關的幾個概念

文法遞歸的作用：

用較少的產生式產生無窮多個句子，實現“用有窮表示無窮”。

G4[＜無符號整數＞]；:；；；；；；；；

,＜無符號整數＞-＜數字＞|＜無符號整數＞＜數字）11；

＜數字）一0|1|2|3|4|5|6|7|8|9

2.3文法的分類

喬姆斯基（Chomsky）把文法分成四種類型，即0型、1型、

2型芾3型；；；；；；；；；

這四類文法的區別在于：對產生式規則的形式上施加不同

的限制。從0型到3型對產生式的要求越來越嚴格，而其描述語

言的能力是逐步減弱的。

2.3文法的分類

■o型文法(無限制文法或短語結構文法)

■產生式為：OCT|3

■其中：ae(VNUVT)*且至少包含一個非終結符

■pG(VNUVT)\

■。型文法沒有其他任何限制條件，故稱無限制文法。

■0型文法所生成的語言稱為無限制語言。

■例如有0型文法G=(VN，V「P,S)，其中

■P={S—OAB

■1B—0

■B—SA|01

■A1->SB1

■AO—SOB}

■其描述的。型語言為L(G[S])={}

■對0型文法的產生式做些限制，可得到其它三種類

型的文法。

■1型文法（上下文有關文法）

■產生式為：oct。

■其中：ct=*方；P=y向2；且I

11111

■?（VNUVp*1AGVN

■；；3w；（VNUVT）+；；；；；；；

■符號串力，方可以認為是上下文，期間的A可以被符號

串3替代。因此1型文法又稱為上下文有關文法。

■此類文法對非終結符A進行替換時必須考慮上下文，并

且3一般不可以是空串。即l4|oc|4||3|

■1型文法描述的語言成為上下文有關語言。

文法的分類文法——舉例

例1.文法GJZ]：

GJZ]=({S,B,C,D},{a,b,c},P,S),其中P為

S-aSBC|aBCCB-CD

CD->BDBD-BC

aB->abbBfbb?1

bCfbecC—cc

1型文法(上下文有關文法)要求：

+

a->P1<|?|<|P|，ae(VNUVT),pe(VNUVTf

■2型文法(上下文無關文法)

■產生式為：A->[3

■其中：AGVN,|3G(VNUVT)*JII「I

■此類文法所定義的語法單位完全獨立于它所處的環境，

即與上下文無關。

■這種文法用于描述現今大多數程序設計語言的語法結構。

也是我們研究的主要對象。

文法的分類文法——舉例

例2.文法G2[Z]：

G2[Z]=({Z,S,A,B,C},{a,b,c},P,Z),

其中P為：Z-SCS-aAc

A-*aAc|bBbC-aCb|E

裳.瞿iiB-bB|E1111

2型文法(上下文無關文法)要求：

AfAGVN,PG(VNUVT)*

■3型文法（正規文法）

■產生式為：A-a或A—aB右線性文法

■A—a或A—Ba左線性文法

■其中：A,BGVN,aeVT

■這種文法用于描述現今大多數程序設計語言的詞法結構。

2.3文法的分類文法——舉例

例3.文法G3[Z〕：

G3[Z]=({Z,U,V},{0,1},P,Z),其中P為

IIIZ->UO|V1Illi

U->Z1|1IIIII

平11V-Z0|0

左線性3型文法要求：A->a或A-Ba,A,BeVN,aeVT

例4.表示標識符的文法

〈標識符》一〈字母＞|〈標識符〉〈字母〉|〈標識符》V數字〉

可抽象為：1-1IIIIId

奉左線性文凈；；；；；；；

例5.表示無符號整數的文法；；；；；

〈無符號整數〉一〈數字》I〈無符號整數X數字》

〈無符號整數〉一〈數字》I〈數字〉〈無符號整數》；

是右線性文法。

文法分類小結

?1）。型文法到3型文法，其產生式的限制條件是逐

漸增加埠。；；；；；；；；；

-2）0型文法＞1型文法＞2型文法＞3型文法：

?3）他們所描述的語言的范圍也是逐漸縮小的。

形式語言與自動機

0型文法（圖靈機）

1型文法（不確定的

界限自動機）

2型文法（不確定的

工j學動機）

3型文法（有限

自動機）

N

0

g山

■

兩類題型

■由語言構造文法

■由文法生成語言

■例1設Z={a，b}設計文法可以描述語言(P12)

■L={a2n,b2n|n>=1}

'首先我們分析語言字符串的特點：；；.

■n=1L={aa,bb}

■n=2L={aaaa,bbbb}

■n=3L={aaaaaa,bbbbbb}

■L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb......}

■可看出語言是由偶數個a,偶數個b組成的集合。

■下面開始構造文法

■A—aa|bb

■A—aaB|bbD

PI

■B—aaBIaa

■D—bbDIbbj

■G=(VN，VT,PJ,S)

"VN={A,B,D}VT={a,b}

■A—B|D

■B一aBaIaa>P2

■D—bDbIbb

■G=(VN，VT,P2,S)

■VN={A,B,D}VT={a,b}

■說明同一種語言可以用多種文法來描述。

■例2設Z={a,b}設計文法可以描述語言

■L={abna|n>=0}

'首先我們分析語言字符串的特點；；

■n=0L={aa}

■n=1L={aba}

■n=2L={abba}

■nL={ab.....ba}

"------Y------'

■n個b

例：{atPa吟o0},構造其文法

o

■下面開始構造文法o

------------X--、

■S->aBa若n2L如何？二>1^

■B—BbyPV

■:B—E；；J；；

G2[S]:

S一aBa

?GI=（VN，VT，P.S）??B一b|Bb

"VN={S,B}VT={a,b}

■例3試構造正規文法描述不以0開頭的正奇數。

■首先我們分析語言字符串的特點

1?90?9135,7,9

下面開始構造文法

1）該語言最簡單的形式

■S—1I3I5I7I9

2）該語言普通形式

S—1A|2A|3A|4A|5A|6A|7A|A|9A

-3)A最簡單形式

■A-1|3|5|7|9

■4)A普通形式

■A->0A|1A|2A|3A|4A|5A|6A|7AA|9A

■G1=(VN,VT,Pi,S)

VT={04,2,3,4,5,6,7,8,9}

■VN={S,A}

■假設沒有正規文法限制

1?90?9135,7,9

ABC

S—CACIABC

234567rU

ki

A一1oB1B2B3B4BLJ5B6B

|8B|9

-0|1|2|3|4|5|6|7|9

CT1|3|5|7|9

■G2=(VN,VT,P2,S)

■VN={S,A,B,C}VT={0,1,2,3,4,5,6,7,

■習題2.3?2

?設2={a,b}設計文法可以描述語言；

■L={anbnci|n>=1,i>=0}

■首先我們分析語言字符串的特點：

■n=1,i=0L={ab}是語言的最簡形式

■n>2,i>1L={aabbc,aabbcc,aaabbbc......}

?L是a與b的個數相等，并以c結尾的字符串的集合

L={anbnc'|n>=1,i>=0}

下面開始構造文法

S—ab]一最簡單形式

S->Sc一產生n個c

S—A>P1

A—aAbG2[S]：

S-AC

A—>ab>A—aAb|ab

C->cC|E

G=(VN,VT,Pj,S)G2=(VN,VT,P1,S)

VN={S,A,C}VT={a,b,c}

VN={S,A}VT={a,b,c)

■習題2.3-3

■設Z={a,b}設計文法可以描述語言；

■L={anbncmdm|n>=1,m>=1}

■首先我們分析語言字符串的特點：

■n=1,m=1L={abcd）是語言的最簡形式

■n=2,m=2L={aabbccdd}

■n=1,m=2L={abccdd}

■n=2,m=1L={aabbcd}

?a與b的個數相等c與d的個數相等

■下面開始構造文法

■S—AB]一兩部分構成

■A—aAb一產生等同數目的ab

■A-ab'P一A最簡單形式

■B—>cBd一產生等同數目的cd

■B―cd」一B最簡單形式

?G=(VN，VT,P,S)

■VN={SAB}VT={a,b,c,d}

小結：

1）首先分析該語言句子的特點」：；—

2）用;文法初造;語言;最簡;單/式。；；；??

3）試用遞歸規則構造語言一般形式；可以分部分構

；造;。引進新的非終結符。；；；；；

4）對于每個部分也要遵循從簡到繁的方法。

5）最后檢查這組規則是否能表示語言的全部句子。

兩類題型

■由語言構造文法

■由文法生成語言

復習——語言的形式定義

文法G[S]產生的所有句子的集合稱為G所定義的語言，記為L(G[S])

，(6南)=|xIjst>xi,本}；；\；；

由此可知：1)當文法給定，語言也就確定。

2)L⑹是V/的子集，即屬于V/的符號串x不一定屬于L(G)

■【例1】設有文法G[S],求所定義的語言。(p15)

■S—01I0S1

s=>osi

=>00S11....

=>On-1SlnA=>Onln

■L(G[S])={On1nIn>=1}

■【例2】設有文法G[S],求所定義的語言。

■1）ST0S

■3）S-w

S=>IS.......

S=>01S.......或IOS.........

■解：3）代入1）和2）S=>0,S=>1

■口）代表所有以。開頭的字符串，每次用1）產生0

■；，2）代表所有以1開頭的字符串，每次用2）產生1

■1）和2）交替將產生01串或10串

■L（G[S]）={1和0組成的長度為任意的字符串}

■【例3】設有文法G[N1],求所定義的語言。

■1)N1-N

■2)N—NDID

■3)D一0|C|2

N1=>N=>ND=>NND=>DDD

■其定義的語言｛0,1,2)+

■【例4】設有文法G[S],求所定義的語言。

■1)S—aTd

-2)T—bT|cT|c|b

■其定義的語言a{b,c}+d；；；；；；

■由文法確定語言的中心思想：?????

禰；從文法的開始符號出發，反復連續地實驗

規則，對非終結符施行替換和展開，找出句子的規

律，用式子或自然語言描述出來。

■形式語言理論可以證明以下兩點：

(1)G-L(G)；文法結構唯一確定語言。

(2)L(G)->G1,G2,……,Gn；

描述一種語言的文法是不唯一的。

已知文法，求語言，通過推導

/\

例：

G[S]；\L(G[S]>{anbn|n>l}

S-aSb|ab

求其所產生的語言。；'

1L(G[S])={anbn|n>0}

cTZ若S一aSb|S,或口何？一

y—----------------->—_____

口，><___________________________>

課堂練習1：G[S]<X

n

S-bA\\L(G[S]>{ba|n>l}

A一aA|aWl>1

課堂練習2:G[S]

mn

S—ABL(G[S])={ab|m?n>l}

A一aA|awi>1__________________________>