編譯原理課件

前述內(nèi)參回顧

?編譯程序

?編譯方式與解釋方式的根本區(qū)別

-編譯程序的工作過程

,編譯程序的結(jié)構(gòu)II

?編譯程序的組織方式

,編譯程序的構(gòu)造

第二章文法和語言的基本知識(shí)

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

基本的概念和基礎(chǔ)知識(shí)，它是學(xué)習(xí)以后各章

的基石。

本章內(nèi)參簡(jiǎn)介

?文法的形式定義

?語言的形式定義

?為語言構(gòu)造文法與由文法推出語言

-語法樹及文法的二義性

?文法和語言的分類

■文法的實(shí)用限制

形式語言理論

由Chomsky于1956年首先提出。

；是指由數(shù)學(xué)方法——形式化方法研究自然語言（如英

語）和人工語言（如程序設(shè)計(jì)語言）的語法的理論。?

目前在自然語言的翻譯、計(jì)算機(jī)語言的描述和轉(zhuǎn)換、

編譯程序的構(gòu)造、模式識(shí)別等方面有廣泛的應(yīng)用。

2A語官的基本^叔?

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

rammar）以及它的語義。

；字母表是符號(hào)的有窮集，而符號(hào)構(gòu)成了語言中的句子。

語法是結(jié)構(gòu)規(guī)則的有窮集，這些規(guī)則定義了句子中符號(hào)

的合法上下文。

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

言編寫的任何程序在某個(gè)計(jì)算機(jī)上執(zhí)行的操作性效果。

2.2.1字母表與符號(hào)串

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

字母表是元素的有窮非空的集合。字母表中的元素稱為符號(hào)。

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

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

注意：字母表中至少包含一個(gè)元素。元素可以是字母、數(shù)字

或其他符號(hào)。?????????

李母表與符號(hào)串

2.符號(hào)、符號(hào)串及其運(yùn)算（P9）?????

字母表中的元素稱為符節(jié)；；；；；；；

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

母表示。

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

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

I擠2）符號(hào)串中的符號(hào)順序很重要。abrba????

3）符號(hào)串x中有ni個(gè)符號(hào)，貝||x|=mm是長(zhǎng)度。

2.2.2符號(hào)串運(yùn)算

■卷號(hào)串;的遂接；；；；；；

設(shè)X和y是符號(hào)串，則稱xy是他們的連接。

例如：x=abc,y=1a

則xy=abc1a,yx=1aabc

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

注意：對(duì)任意一個(gè)符號(hào)串￡；；；

我們有￡X=X￡=X

■符號(hào)串集合的乘積

設(shè)A和B是符號(hào)串的集合，則A和B的乘積定義為，

AB={xy|xGA,yGB}

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

則AB={aGad,bGbd}

集合的乘積是滿足于A,yeB的所有符號(hào)串xy

k所構(gòu)成的集合。；；；；；；；；

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

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

2、{￡}=00/{}

■符號(hào)串的方塞

■設(shè)X是符號(hào)串，X”是X自身連結(jié)n次。并且xO=E

■貝ijx1=x

■x2=XX

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

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

■例如，設(shè)x=abc,則

■x1=abc

■x2=abcabc

■符號(hào)串集合的方塞

■A是符號(hào)串的集合，An是集合A自身n次相乘，

■并且人。={￡}

■則A1=A

■A2=AA

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

■n個(gè)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}

■符號(hào)串集合的正閉包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構(gòu)成的所有符號(hào)串的集合。

2.3文法和語言的形式定義

2.3.1文法的有關(guān)概念

1.終結(jié)符號(hào)?????????

；終結(jié)符號(hào)是組成語言的基本符號(hào)，如保留字、標(biāo)識(shí)符、常數(shù)、

運(yùn)算符、界限符等。終結(jié)符號(hào)是語言的不可再分的基本符號(hào)。終

?結(jié)符號(hào)形成的集合記為一般用小寫字母表示。

2.非終結(jié)符號(hào)...........................

；小E終結(jié)符號(hào)用來表示語言的語法成分（或語法范疇、語法單

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

般用大寫字母來表示。

vTnvN=0

2.3文法和語言的形式定義

3.產(chǎn)生式：產(chǎn)生式（規(guī)則）是一個(gè)有序?qū)Γ╝,B）,通常寫作

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

+

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

|3e（VTUVN）j*o?；

'產(chǎn)生式是用來定義一個(gè)語法成分的。它描述了一個(gè)語法成分

的形成規(guī)則。例如標(biāo)識(shí)符的構(gòu)成規(guī)則可描述為：

＜標(biāo)識(shí)符》一＜字母）|＜標(biāo)識(shí)符X字母）|＜標(biāo)識(shí)符X數(shù)字）

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

pn稱為a的候選式

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

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

3)v謂語〉一v動(dòng)詞〉v賓語〉

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

5)v名詞〉—?mancar

6)v冠詞＞一the

7)v名詞＞—＞drive

Themandrivethecar

Thecardrivetheman一組規(guī)則規(guī)定一個(gè)語言

Thecardrivethecar的語法結(jié)構(gòu)

Themandrivetheman

2.3.2文法的形式定義

文法是產(chǎn)生式的有窮非空的集合。

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

:1r_終結(jié)您號(hào)藁。；；；；；；

IVN―u非終結(jié)符號(hào)集。?1III?

圈S——開始符號(hào)。至少要在一條產(chǎn)生式中作為左部出現(xiàn)。

P——表示產(chǎn)生式的有窮非空的集合。

例1定義標(biāo)識(shí)符的文法

G[＜標(biāo)識(shí)符＞]=（{A,B,Y,Z,0,1,...,9},

{＜標(biāo)識(shí)符＞,＜字母＞，＜數(shù)字＞},P,＜標(biāo)識(shí)符〉）

P定義為：

＜標(biāo)識(shí)符》一＜字母）I＜標(biāo)識(shí)符＞＜字母》I＜標(biāo)識(shí)符＞＜數(shù)字）

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

＜數(shù)字＞-01112I314|5I6|7|819

2.3.3和語言有關(guān)的幾個(gè)概念

1.直接推導(dǎo)

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

一個(gè)符號(hào)串，則將a一口作用于符號(hào)串ya6上得到符號(hào)串丫口6,稱

符號(hào)串YP6是符號(hào)串Ya6的直接推導(dǎo)，記為

ya6=>yP6

:直接推導(dǎo)的逆過程稱為直接歸約，即由符號(hào)串丫口6可直接歸約到丫

a6o

直接推導(dǎo)舉例

例1文法G[E]：

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

*TFn*T*FF

例2見P14

2.3.3和語言有關(guān)的幾個(gè)概念

超導(dǎo)；；；；；；；；0

\設(shè)鼠0、、、…Qn均為（VTUVJ*中的符號(hào)串，且有

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

則稱以上序列是長(zhǎng)度為n的推導(dǎo)，即a0可經(jīng)過n步推導(dǎo)得到a

+

今

aoan

顯然，這里n“，當(dāng)n=l,就是直接推導(dǎo)。'；；

當(dāng)n=0時(shí)，oco=ocn.當(dāng)n》我們稱為廣義推導(dǎo)。

推導(dǎo)的逆過程稱為歸約，即明可歸約到0t0。

2.3.3和語言有關(guān)的幾個(gè)概念

3.最左推導(dǎo)和最右推導(dǎo)

如果在某個(gè)推導(dǎo)過程中的任何一步直接推導(dǎo)an6中，

都是對(duì)符號(hào)串鼠的最左（右）非終結(jié)符號(hào)進(jìn)行替換，則稱其

為最左（右）推導(dǎo)。最右推導(dǎo)又叫做規(guī)范推導(dǎo)。規(guī)范推導(dǎo)的

逆過程（最左規(guī)約）稱為規(guī)范規(guī)約。

【例1】設(shè)有文法G[NJ

N]-N

N-ND|D

D->0|1|2

N1=>N=>ND=>N2=>D2=>12最右推導(dǎo)

N1=>N=>ND=>DD=>1D=>12最左推導(dǎo)

N1=>N=>ND=>DD=>D2=>12不是最左推導(dǎo)

也不是最右推導(dǎo)

【例2】設(shè)有文法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

請(qǐng)寫出字符串（i+i）*i-i最右推導(dǎo)

=>(E+i)*i-i

=>(T+i)*i-F

=>(F+i)*i-F

=>(i+i)*i-i

2.3.3和語言有關(guān)的幾個(gè)概念P15

4.句型

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

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

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

|設(shè)有文法G[S],如果S當(dāng)u，且UEV/,則稱符號(hào)串u為

文法G網(wǎng)的句子。

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

■【例1】設(shè)有文法G[S]：

■S-01I0S1

S=>01

S=>0S1

=>00S11

=>000111

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

■01和000111又是句型。

【例2】設(shè)有文法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和語言有關(guān)的幾個(gè)概念

6.語言

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

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

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

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

2.3.3和語言有關(guān)的幾個(gè)概念P17

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

；如果文法的產(chǎn)生式呈U-…U…形式，則稱其為規(guī)則遞歸，也

稱直接遞歸。（U為非終結(jié)符）IIIII

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

間接遞歸。

所謂遞歸即，規(guī)則的左部或右部具有相同的非終結(jié)符。

2.3.3和語言有關(guān)的幾個(gè)概念

8.規(guī)則左遞歸與規(guī)則右遞歸

如果文法的產(chǎn)生式呈U-U…的形式，則稱其為規(guī)則左遞歸。

如果文法的產(chǎn)生式呈U-...U的形式，則稱其為規(guī)則右遞歸。

規(guī)則左（右）遞歸，也稱直接左（右）遞歸。

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

如果文法中有推導(dǎo)U3U…，則稱其為文法左遞歸，也稱

間接左遞歸。III

如果文法中有推導(dǎo)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和語言有關(guān)的幾個(gè)概念

文法遞歸的作用：

用較少的產(chǎn)生式產(chǎn)生無窮多個(gè)句子，實(shí)現(xiàn)“用有窮表示無窮”。

G4[＜無符號(hào)整數(shù)＞]；:；；；；；；；；

,＜無符號(hào)整數(shù)＞-＜數(shù)字＞|＜無符號(hào)整數(shù)＞＜數(shù)字）11；

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

2.3文法的分類

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

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

這四類文法的區(qū)別在于：對(duì)產(chǎn)生式規(guī)則的形式上施加不同

的限制。從0型到3型對(duì)產(chǎn)生式的要求越來越嚴(yán)格，而其描述語

言的能力是逐步減弱的。

2.3文法的分類

■o型文法(無限制文法或短語結(jié)構(gòu)文法)

■產(chǎn)生式為：OCT|3

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

■pG(VNUVT)\

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

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

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

■P={S—OAB

■1B—0

■B—SA|01

■A1->SB1

■AO—SOB}

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

■對(duì)0型文法的產(chǎn)生式做些限制，可得到其它三種類

型的文法。

■1型文法（上下文有關(guān)文法）

■產(chǎn)生式為：oct。

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

11111

■?（VNUVp*1AGVN

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

■符號(hào)串力，方可以認(rèn)為是上下文，期間的A可以被符號(hào)

串3替代。因此1型文法又稱為上下文有關(guān)文法。

■此類文法對(duì)非終結(jié)符A進(jìn)行替換時(shí)必須考慮上下文，并

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

■1型文法描述的語言成為上下文有關(guān)語言。

文法的分類文法——舉例

例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型文法(上下文有關(guān)文法)要求：

+

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

■2型文法(上下文無關(guān)文法)

■產(chǎn)生式為：A->[3

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

■此類文法所定義的語法單位完全獨(dú)立于它所處的環(huán)境，

即與上下文無關(guān)。

■這種文法用于描述現(xiàn)今大多數(shù)程序設(shè)計(jì)語言的語法結(jié)構(gòu)。

也是我們研究的主要對(duì)象。

文法的分類文法——舉例

例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型文法(上下文無關(guān)文法)要求：

AfAGVN,PG(VNUVT)*

■3型文法（正規(guī)文法）

■產(chǎn)生式為：A-a或A—aB右線性文法

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

■其中：A,BGVN,aeVT

■這種文法用于描述現(xiàn)今大多數(shù)程序設(shè)計(jì)語言的詞法結(jié)構(gòu)。

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.表示標(biāo)識(shí)符的文法

〈標(biāo)識(shí)符》一〈字母＞|〈標(biāo)識(shí)符〉〈字母〉|〈標(biāo)識(shí)符》V數(shù)字〉

可抽象為：1-1IIIIId

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

例5.表示無符號(hào)整數(shù)的文法；；；；；

〈無符號(hào)整數(shù)〉一〈數(shù)字》I〈無符號(hào)整數(shù)X數(shù)字》

〈無符號(hào)整數(shù)〉一〈數(shù)字》I〈數(shù)字〉〈無符號(hào)整數(shù)》；

是右線性文法。

文法分類小結(jié)

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

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

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

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

形式語言與自動(dòng)機(jī)

0型文法（圖靈機(jī)）

1型文法（不確定的

界限自動(dòng)機(jī)）

2型文法（不確定的

工j學(xué)動(dòng)機(jī)）

3型文法（有限

自動(dòng)機(jī)）

N

0

g山

■

兩類題型

■由語言構(gòu)造文法

■由文法生成語言

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

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

'首先我們分析語言字符串的特點(diǎn)：；；.

■n=1L={aa,bb}

■n=2L={aaaa,bbbb}

■n=3L={aaaaaa,bbbbbb}

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

■可看出語言是由偶數(shù)個(gè)a,偶數(shù)個(gè)b組成的集合。

■下面開始構(gòu)造文法

■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設(shè)Z={a,b}設(shè)計(jì)文法可以描述語言

■L={abna|n>=0}

'首先我們分析語言字符串的特點(diǎn)；；

■n=0L={aa}

■n=1L={aba}

■n=2L={abba}

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

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

■n個(gè)b

例：{atPa吟o0},構(gòu)造其文法

o

■下面開始構(gòu)造文法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試構(gòu)造正規(guī)文法描述不以0開頭的正奇數(shù)。

■首先我們分析語言字符串的特點(diǎn)

1?90?9135,7,9

下面開始構(gòu)造文法

1）該語言最簡(jiǎn)單的形式

■S—1I3I5I7I9

2）該語言普通形式

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

-3)A最簡(jiǎn)單形式

■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}

■假設(shè)沒有正規(guī)文法限制

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,

■習(xí)題2.3?2

?設(shè)2={a,b}設(shè)計(jì)文法可以描述語言；

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

■首先我們分析語言字符串的特點(diǎn)：

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

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

?L是a與b的個(gè)數(shù)相等，并以c結(jié)尾的字符串的集合

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

下面開始構(gòu)造文法

S—ab]一最簡(jiǎn)單形式

S->Sc一產(chǎn)生n個(gè)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)

■習(xí)題2.3-3

■設(shè)Z={a,b}設(shè)計(jì)文法可以描述語言；

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

■首先我們分析語言字符串的特點(diǎn)：

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

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

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

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

?a與b的個(gè)數(shù)相等c與d的個(gè)數(shù)相等

■下面開始構(gòu)造文法

■S—AB]一兩部分構(gòu)成

■A—aAb一產(chǎn)生等同數(shù)目的ab

■A-ab'P一A最簡(jiǎn)單形式

■B—>cBd一產(chǎn)生等同數(shù)目的cd

■B―cd」一B最簡(jiǎn)單形式

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

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

小結(jié)：

1）首先分析該語言句子的特點(diǎn)」：；—

2）用;文法初造;語言;最簡(jiǎn);單/式。；；；??

3）試用遞歸規(guī)則構(gòu)造語言一般形式；可以分部分構(gòu)

；造;。引進(jìn)新的非終結(jié)符。；；；；；

4）對(duì)于每個(gè)部分也要遵循從簡(jiǎn)到繁的方法。

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

兩類題型

■由語言構(gòu)造文法

■由文法生成語言

復(fù)習(xí)——語言的形式定義

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

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

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

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

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

■S—01I0S1

s=>osi

=>00S11....

=>On-1SlnA=>Onln

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

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

■1）ST0S

■3）S-w

S=>IS.......

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

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

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

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

■1）和2）交替將產(chǎn)生01串或10串

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

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

■1)N1-N

■2)N—NDID

■3)D一0|C|2

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

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

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

■1)S—aTd

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

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

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

禰；從文法的開始符號(hào)出發(fā)，反復(fù)連續(xù)地實(shí)驗(yàn)

規(guī)則，對(duì)非終結(jié)符施行替換和展開，找出句子的規(guī)

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

■形式語言理論可以證明以下兩點(diǎn)：

(1)G-L(G)；文法結(jié)構(gòu)唯一確定語言。

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

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

已知文法，求語言，通過推導(dǎo)

/\

例：

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

S-aSb|ab

求其所產(chǎn)生的語言。；'

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

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

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

口，><___________________________>

課堂練習(xí)1：G[S]<X

n

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

A一aA|aWl>1

課堂練習(xí)2:G[S]

mn

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

A一aA|awi>1__________________________>