編譯原理第三講

1.文法的定義例文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號例文法G=（VN，VT，P，S） VN={標識符，字母，數(shù)字}

VT={a,b,c,…x,y,z,0,1,…,9} P={<標識符>→<字母> <標識符>→<標識符><字母>

<標識符>→<標識符><數(shù)字>

<字母>→a,…,<字母>→z<數(shù)字>→0,…,<數(shù)字>→9}

S=<標識符>文法的寫法1G：S→aAb

A→ab

A→aAb

A→ε2G[S]：A→abA→aAb

A→εS→aSb

3G[S]：A→ab|aAb|ε

S→aSb例1設∑={a,b}試設計文法描述語言L={a2n|n

≥

1}例2設∑={a,b}試設計文法描述語言L={a2n,b2n|n

≥

1}例3設∑={a,b}試設計文法描述語言L={abna|n

≥0}例4寫文法，是其語言是自然數(shù)的集合例5寫文法，是其語言是奇數(shù)集合，但不允許有以0打頭的奇數(shù)例6試設計一個表示所有標識符的文法字母字母或數(shù)字串2.推導的定義直接推導“”α→β是文法G的產生式，若有v,w滿足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*

則稱v直接推導到w,記作

vw例：G：S→0S1，S→01

注意:和→的區(qū)別推導的定義推導“”若存在vw0w1...wn=w,(n>0)

則記為vw，v推導出w

廣義推導“”

若有vw，或v=w，

則記為vw例：G：S→0S1，S→01S0S100S11000S111000011110S100S1100S11000S111000S11100001111

S00001111S000S111SS00S11

000S1113.歸約直接歸約:w

v(當且僅當vw)例:0S100S1100S110S1歸約:w

v(當且僅當vw)例:S0000111100001111S廣義歸約:w

v(當且僅當vw)例:00S1100S1100S11

00S11例：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

構造a+a*a的推導和歸約過程4.句型、句子的定義句型有文法G，若Sx，且x∈V*則稱x是文法G的句型。句子有文法G，若Sx，且x∈VT*，則稱x是文法G的句子。例：G：S→0S1，S→01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01例：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

句子：用符號a，+，*，(和)構成的算術表達式5.語言的定義由文法G生成的語言記為L(G),它是文法G的一切句子的集合:

L(G)={x|S=>*x，其中S為文法的開始符號，且x∈VT*}

例1：G：S→0S1，S→01L(G)={0n1n|n≥1}例2設有文法G[A]A→yBB→xB|x求該文法所描述的語言例3設有文法G[S]：SaSbab求該文法所描述的語言

SaSb

aaSbb

a3Sb3

……an-1Sbn-1

anbn例4文法G[S]： （1）S→aSBE

（2）S→aBE

（3）EB→BE （4）aB→ab

（5）bB→bb （6）bE→be （7）eE→ee

L（G）={anbnen

|n≥1}S

aSBE(S→aSBE)

aaBEBE(S→aBE)

aabEBE

(aB→ab)

aabBEE

(EB→BE)

aabbEE （bB→bb)

aabbeE

（bE→be)

aabbee

（eE→ee)

G生成的每個串都在L(G)中L(G)中的每個串確實能被G生成使用產生式(1)n-1次，得到推導序列：S=>*

an-1S(BE)n-1，然后使用產生式(2)一次，得到：S=>*

an-1S(BE)n-1

an(BE)n。然后從an(BE)n繼續(xù)推導，總是對EB使用產生式(3)的右部進行替換，而最終在得到的串中，所有的B都先于所有的E。例如，若n=3,

aaaBEBEBE

aaaBBEEBE

aaaBBEBEE

aaaBBBEEE。即有：S=>*

anBnEn接著，使用產生式(4)一次，得到S=>*

anbBn-1En，然后使用產生式(5)n-1次得到：S=>*

anbn

En，最后使用產生式(6)一次，使用產生式(7)n-1次，得到：S=>*

anbnen也能證明，對于n≥1，串anbnen是唯一形式的終結符號串

6.文法的等價若L（G1）=L（G2），則稱文法G1和G2是等價的。

如文法G1[A]：A→0R與G2[S]：S→0S1等價

A→01

S→01

R→A1文法的類型通過對產生式施加不同的限制，Chomsky將文法分為四種類型：0型文法：對任一產生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：對任一產生式α→β，都有|β|≥|α|，僅僅S→ε除外2型文法：對任一產生式α→β，都有α∈VN，β∈(VN∪VT)*3型文法：任一產生式α→β的形式都為A→aB或A→a，其中A∈VN，B∈VN，a∈VT文法的類型例：1型（上下文有關）文法文法G[S]： S→CD Ab→bA

C→aCA

Ba→aB

C→bCB Bb→bB

AD→aD C→ε BD→bD D→ε

Aa→bD文法的類型例：2型（上下文無關）文法

文法G[S]： S→AB A→BS|0 B→SA|1

3型文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT

I→l T→lT

T→dT

T→l

T→d

文法的類型2型文法1型文法0型文法四種文法之間的逐級“包含”關系3型文法文法和語言0型文法產生的語言稱為0型語言1型文法或上下文有關文法（CSG）產生的語言稱為1型語言或上下文有關語言（CSL）2型文法或上下文無關文法（CFG）產生的語言稱為2型語言或上下文無關語言（CFL）

3型文法或正則（正規(guī)）文法（RG）產生的語言稱為3型語言正則（正規(guī)）語言（RL）

文法和語言四種文法之間的關系是將產生式做進一步限制而定義的。語言之間的關系依次：有不是上下文有關語言的0型語言，有不是上下文無關語言的1型語言，有不是正則語言的上下文無關語言。 練習

1.寫一文法，使其語言是偶正整數(shù)的集合。要求：（1）允許0打頭（2）

不允許0打頭2.給出生成下述語言的上下文無關文法：