編譯原理 2 語(yǔ)言及其文法學(xué)習(xí)課件

第2章語(yǔ)言及其文法

哈爾濱工業(yè)大學(xué)陳?ài)幢菊聝?nèi)容2.1基本概念2.2文法的定義2.3語(yǔ)言的定義2.4文法的分類2.4CFG的語(yǔ)法分析樹(shù)2.1基本概念字母表(Alphabet)字母表∑是一個(gè)有窮符號(hào)集合。符號(hào)的典型例子包括字母、數(shù)字和標(biāo)點(diǎn)符號(hào)。例二進(jìn)制字母表：{0,1}ASCIIUnicode字母表上的運(yùn)算字母表∑1和∑2的乘積(product)∑1∑2={ab|a

∈∑1,b∈

∑2}例：{0,1}{a,b}={0a,0b,1a,1b}字母表上的運(yùn)算字母表∑1和∑2的乘積(product)字母表∑的n次冪(power)∑0={ε}∑n

=∑n-1∑

,n≥1例：{0,1}3={0,1}{0,1}{0,1}={000,001,010,011,100,101,110,111}字母表的n次冪：長(zhǎng)度為n的符號(hào)串構(gòu)成的集合字母表上的運(yùn)算字母表∑1和∑2的乘積(product)字母表∑的n次冪(power)字母表∑的正閉包(positiveclosure)∑+=∑∪∑2∪∑3∪…例：{a,b,c,d}+={a,b,c,d,aa,ab,ac,ad,ba,bb,bc,bd,…,aaa,aab,aac,aad,aba,abb,abc,…}字母表的正閉包：長(zhǎng)度正數(shù)的符號(hào)串構(gòu)成的集合字母表上的運(yùn)算字母表∑1和∑2的乘積(product)字母表∑的n次冪(power)字母表∑的正閉包(positiveclosure)字母表∑的克林閉包(Kleeneclosure)∑*

=∑0∪∑+=∑0∪∑∪∑2∪∑3∪…例：{a,b,c,d}*={ε,a,b,c,d,aa,ab,ac,ad,ba,bb,bc,bd,…,aaa,aab,aac,aad,aba,abb,abc,…}字母表的克林閉包：任意符號(hào)串（長(zhǎng)度可以為零）構(gòu)成的集合串

(String)設(shè)∑是一個(gè)字母表，

x∈∑*，x稱為是∑上的一個(gè)串串是字母表中符號(hào)的一個(gè)有窮序列串s的長(zhǎng)度，通常記作|s|，是指s中符號(hào)的個(gè)數(shù)例:|aab|=3

空串是長(zhǎng)度為0的串，用ε（epsilon）表示|ε|=0串上的運(yùn)算如果x和y是串，那么x和y的連接（concatenation）是把y附加到x后面而形成的串，記作xy。例如，如果

x=dog且

y

=house，那么xy=doghouse。

空串是連接運(yùn)算的單位元（identity），即，對(duì)于任何串s都有，εs=sε=s。串s的冪運(yùn)算

s0=ε，

sn=sn-1s

,n≥1s1

=

s0s

=εs=s，s2=ss，s3=sss，…例：如果s=ba，那么s1=ba，s2=baba，s3=bababa，…設(shè)x,y,z是三個(gè)字符串，如果x=yz，則稱y是x的前綴，z是x的后綴串s的n次冪：將n個(gè)s連接起來(lái)提綱2.1基本概念2.2文法的定義2.3語(yǔ)言的定義2.4文法的分類2.4CFG的語(yǔ)法分析樹(shù)2.2文法的定義自然語(yǔ)言的例子——句子的構(gòu)成規(guī)則句子名詞短語(yǔ)動(dòng)詞短語(yǔ)名詞短語(yǔ)形容詞名詞短語(yǔ)名詞短語(yǔ)名詞動(dòng)詞短語(yǔ)動(dòng)詞名詞短語(yǔ)

形容詞little名詞boy

名詞apple

動(dòng)詞eat未用尖括號(hào)括起來(lái)部分表示語(yǔ)言的基本符號(hào)尖括號(hào)括起來(lái)部分稱為語(yǔ)法成分文法的形式化定義

G

=(VT,VN,P

,S)VT：終結(jié)符集合終結(jié)符(terminalsymbol)是文法所定義的語(yǔ)言的基本符號(hào)，有時(shí)也稱為token例:

VT={apple,boy,eat,little}文法的形式化定義

G

=(VT,VN,P

,S)VT：終結(jié)符集合VN

：非終結(jié)符集合非終結(jié)符(nonterminal)是用來(lái)表示語(yǔ)法成分的符號(hào)，有時(shí)也稱為“

語(yǔ)法變量”例:VN

={

句子

,

名詞短語(yǔ)

,

動(dòng)詞短語(yǔ)

,

名詞

,

動(dòng)詞

,形容詞

,…}文法的形式化定義

G

=(VT,VN,P

,S)VT：終結(jié)符集合VN

：非終結(jié)符集合P：產(chǎn)生式集合產(chǎn)生式(production)描述了將終結(jié)符和非終結(jié)符組合成串的方法產(chǎn)生式的一般形式：

α→β讀作：α定義為βα

∈(VT∪VN)+，且α中至少包含VN中的一個(gè)元素：稱為產(chǎn)生使的頭(head)或左部(leftside)β∈(VT∪VN)*

：稱為產(chǎn)生使的體（body

）或右部（rightside）例：

P={

句子

名詞短語(yǔ)

動(dòng)詞短語(yǔ)

,…}VT∩VN=ΦVT∪VN：文法符號(hào)集文法的形式化定義

G

=(VT,VN,P

,S)VT：終結(jié)符集合VN

：非終結(jié)符集合P：產(chǎn)生式集合S：開(kāi)始符號(hào)S∈VN。開(kāi)始符號(hào)(start

symbol)表示的是該文法中最大的語(yǔ)法成分例：S

=句子文法的形式化定義

G=(VT,VN,P

,S)VT：終結(jié)符集合VN

：非終結(jié)符集合P：產(chǎn)生式集合S：開(kāi)始符號(hào)例：G=({id,+,*,(,)},{E},P,E)P={E→E+E, E→E*E,E→(E),E→id

}G:E→E+E

E→E*E

E→(E)

E→id約定：不引起歧義的前提下，可以只寫產(chǎn)生式產(chǎn)生式的簡(jiǎn)寫對(duì)一組有相同左部的α產(chǎn)生式α→β1,α→β2,…,α→βn

可以簡(jiǎn)記為：α→β1|β2|…|βn讀作：α定義為β1，或者β2，…，或者βn。β1，β2，…，βn稱為α的候選式(Candidate)例E→E+E

E→E*E

E→(E)E→idE→E+E

|

E*E|

(E)|id符號(hào)約定下述符號(hào)是終結(jié)符(a)字母表中排在前面的小寫字母，如

a、b、c(b)運(yùn)算符，如+、*等(c)標(biāo)點(diǎn)符號(hào)，如括號(hào)、逗號(hào)等(d)數(shù)字0、1、...、9(e)粗體字符串，如id、if等符號(hào)約定下述符號(hào)是終結(jié)符下述符號(hào)是非終結(jié)符(a)字母表中排在前面的大寫字母，如A、B、C(b)字母S。通常表示開(kāi)始符號(hào)(c)小寫、斜體的名字，如expr、stmt等(d)代表程序構(gòu)造的大寫字母。如E(表達(dá)式)、T(項(xiàng))和F(因子)符號(hào)約定下述符號(hào)是終結(jié)符下述符號(hào)是非終結(jié)符字母表中排在后面的大寫字母（如X、Y、Z）表示文法符號(hào)（即終結(jié)符或非終結(jié)符）字母表中排在后面的小寫字母（主要是u、v、...、z）表示終結(jié)符號(hào)串（包括空串）小寫希臘字母，如α、β、

γ，表示文法符號(hào)串（包括空串）除非特別說(shuō)明，第一個(gè)產(chǎn)生式的左部就是開(kāi)始符號(hào)終結(jié)符

a,b,c

終結(jié)符號(hào)串u,v,...,z非終結(jié)符A,B,C文法符號(hào)X,Y,Z

文法符號(hào)串

α,β,γ

提綱2.1基本概念2.2文法的定義2.3語(yǔ)言的定義2.4文法的分類2.4CFG的語(yǔ)法分析樹(shù)2.3語(yǔ)言的定義自然語(yǔ)言的例子文法：句子名詞短語(yǔ)動(dòng)詞短語(yǔ)名詞短語(yǔ)形容詞名詞短語(yǔ)名詞短語(yǔ)名詞動(dòng)詞短語(yǔ)動(dòng)詞名詞短語(yǔ)

形容詞little名詞boy

名詞apple

動(dòng)詞eat單詞串：little

boyeatsapple

有了文法（語(yǔ)言規(guī)則），如何判定一個(gè)詞串是否是滿足文法的句子？推導(dǎo)(Derivations)和歸約(Reductions)給定文法G=(VT,VN,P,S)，如果

α→β∈P，那么可以將符號(hào)串γαδ中的α替換為β，也就是說(shuō)，將γαδ重寫(rewrite)為γβδ，記作

γαδ

γβδ。此時(shí)，稱文法中的符號(hào)串

γαδ

直接推導(dǎo)(directlyderive)出

γβδ簡(jiǎn)而言之，就是用產(chǎn)生式的右部替換產(chǎn)生式的左部推導(dǎo)(Derivations)和歸約(Reductions)如果α1

α2，α2

α3，…，αn-1

αn，則可以記作α1

α2

α3

…

αn-1

αn，稱符號(hào)串α1經(jīng)過(guò)n步推導(dǎo)出αn，可簡(jiǎn)記為α1

nαnα

0

α

+表示“經(jīng)過(guò)正數(shù)步推導(dǎo)”

*表示“經(jīng)過(guò)若干（可以是0）步推導(dǎo)”推導(dǎo)(Derivations)和歸約(Reductions)

名詞短語(yǔ)動(dòng)詞短語(yǔ)

形容詞名詞短語(yǔ)<動(dòng)詞短語(yǔ)

little名詞短語(yǔ)<動(dòng)詞短語(yǔ)

little

名詞<動(dòng)詞短語(yǔ)

littleboy<動(dòng)詞短語(yǔ)

littleboy動(dòng)詞名詞短語(yǔ)

littleboyeats名詞短語(yǔ)

little

boyeats名詞

little

boyeatsapple

推導(dǎo)歸約文法：句子名詞短語(yǔ)動(dòng)詞短語(yǔ)名詞短語(yǔ)形容詞名詞短語(yǔ)名詞短語(yǔ)名詞動(dòng)詞短語(yǔ)動(dòng)詞名詞短語(yǔ)

形容詞little名詞boy

名詞apple

動(dòng)詞eat例句子

回答前面的問(wèn)題有了文法（語(yǔ)言規(guī)則），如何判定某一詞串是否是該語(yǔ)言的句子？句子的推導(dǎo)（派生）-從生成語(yǔ)言的角度句子的歸約

-從識(shí)別語(yǔ)言的角度均根據(jù)規(guī)則句型和句子如果S

*α，α∈(VT∪VN)*，則稱α是G的一個(gè)句型(sententialform)一個(gè)句型可能既包含終結(jié)符又包含非終結(jié)符，也可能是空串如果S

*w，w∈VT*，則稱w是G的一個(gè)句子(sentence)句子是不包含非終結(jié)符的句型例句子

名詞短語(yǔ)動(dòng)詞短語(yǔ)

形容詞名詞短語(yǔ)<動(dòng)詞短語(yǔ)

little

名詞短語(yǔ)<動(dòng)詞短語(yǔ)

little名詞<動(dòng)詞短語(yǔ)

littleboy<動(dòng)詞短語(yǔ)

littleboy動(dòng)詞名詞短語(yǔ)

littleboyeats名詞短語(yǔ)

little

boyeats名詞

little

boyeatsapple

句型句子語(yǔ)言的形式化定義由文法G的開(kāi)始符號(hào)S推導(dǎo)出的所有句子構(gòu)成的集合稱為文法G生成的語(yǔ)言，記為L(zhǎng)(G)。即L(G)={w|S

*w,

w∈VT*}文法E

→E+E|E*E|

(E)

|id生成的語(yǔ)言中包含多少個(gè)句子？例文法G①S→L|LT②T→L|D|TL|TD③L→a|b|c|…|z④D→0|1|2|3|…|9請(qǐng)寫出無(wú)符號(hào)整數(shù)和浮點(diǎn)數(shù)的文法T

TL

TDL

TDDL

TLDDL…

TD…LDDL

DD…LDDLT：字母數(shù)字串該文法生成的語(yǔ)言是：標(biāo)識(shí)符語(yǔ)言上的運(yùn)算例：令L={A，B，…，Z，a，b，…，z}，D={0，1，…，9}。則L(L∪D)*表示的語(yǔ)言是標(biāo)識(shí)符提綱2.1基本概念2.2文法的定義2.3語(yǔ)言的定義2.4文法的分類2.4CFG的語(yǔ)法分析樹(shù)2.4文法的分類Chomsky文法分類體系0型文法(Type-0Grammar)1型文法(Type-1Grammar)2型文法(Type-2Grammar)3型文法(Type-3Grammar)0型文法(Type-0Grammar)

α→β

無(wú)限制文法(UnrestrictedGrammar)/短語(yǔ)結(jié)構(gòu)文法(PhraseStructureGrammar,PSG)?α→β∈P，α中至少包含1個(gè)非終結(jié)符

0型語(yǔ)言由0型文法G生成的語(yǔ)言L(G)1型文法(Type-1Grammar)

上下文有關(guān)文法(Context-SensitiveGrammar,CSG)?α→β∈P，｜α｜≤｜β｜

產(chǎn)生式的一般形式：α1Aα2

→α1βα2

(β≠ε)

上下文有關(guān)語(yǔ)言（1型語(yǔ)言）由上下文有關(guān)文法(1型文法)G生成的語(yǔ)言L(G)

α→βCSG中不包含ε-產(chǎn)生式2型文法(Type-2Grammar)

上下文無(wú)關(guān)文法

(Context-FreeGrammar,CFG)?α→β∈P，α∈VN

產(chǎn)生式的一般形式：A→β 例：S→L|LTT→L|D|TL|TDL→a|b|c|d|…|zD→0|1|2|3|…|9

α→β

上下文無(wú)關(guān)語(yǔ)言（2型語(yǔ)言）由上下文無(wú)關(guān)文法(2型文法)G生成的語(yǔ)言L(G)

3型文法(Type-3Grammar)

正則文法

(RegularGrammar,RG)

右線性(RightLinear)文法：

A→wB

或

A→w

左線性(LeftLinear)文法：

A→Bw或A→w左線性文法和右線性文法都稱為正則文法例（右線性文法）①S→a|b|c|d②S→aT|bT|cT|dT③T→a|b|c|d|0|1|2|3|4|5④T→aT|bT|cT|dT|0T|1T|2T|3T|4T|5T

α→β文法G（

上下文無(wú)關(guān)文法）①S→L|LT②T→L|D|TL|TD③L→a|b|c|d④D→0|1|2|3|4|5

正則語(yǔ)言（3型語(yǔ)言）由正則文法(3型文法)G生成的語(yǔ)言L(G)正則文法能描述程序設(shè)計(jì)語(yǔ)言的多數(shù)單詞四種文法之間的關(guān)系逐級(jí)限制0型文法：α中至少包含1個(gè)非終結(jié)符1型文法（CSG）：｜α｜≤｜β｜2型文法（CFG）：α∈VN

3型文法（RG）：A→wB

或

A→w(A→Bw

或A→w)逐級(jí)包含2型文法集合1型文法集合0型文法集合3型文法集合提綱2.1基本概念2.2文法的定義2.3語(yǔ)言的定義2.4文法的分類2.4CFG的語(yǔ)法分析樹(shù)2.4CFG的語(yǔ)法分析樹(shù)

根節(jié)點(diǎn)的標(biāo)號(hào)為文法開(kāi)始符號(hào)

內(nèi)部結(jié)點(diǎn)表示對(duì)一個(gè)產(chǎn)生式A→β的應(yīng)用，該結(jié)點(diǎn)的標(biāo)號(hào)是此產(chǎn)生式左部A

。該結(jié)點(diǎn)的子結(jié)點(diǎn)的標(biāo)號(hào)從左到右構(gòu)成了產(chǎn)生式的右部β

葉結(jié)點(diǎn)的標(biāo)號(hào)既可以是非終結(jié)符，也可以是終結(jié)符。從左到右排列葉節(jié)點(diǎn)得到的符號(hào)串稱為是這棵樹(shù)的產(chǎn)出(yield)或邊緣(frontier)

G：①E→E+E②

E→E*E③

E→-E④E→(E)⑤

E→id分析樹(shù)是推導(dǎo)的圖形化表示給定一個(gè)推導(dǎo)

S

α1

α2

…

αn，對(duì)于推導(dǎo)過(guò)程中得到的每一個(gè)句型αi，都可以構(gòu)造出一個(gè)邊緣為αi的分析樹(shù)文法：①E→E+E②

E→E*E③

E→-E④E→(E)⑤

E→id推導(dǎo)過(guò)程：E

-E

-

(E

)

-(

E+E)

-(

id+E

)

-(

id+id)-E

(E)E+EididE分析樹(shù)：二義性文法

(AmbiguousGrammar)如果一個(gè)文法可以為某個(gè)句子生成多棵分析樹(shù)，則稱這個(gè)文法是二義性的例文法stmt

if

expr

then

stmt

ifexpr

then

stmt

else

stmt

other句型ifE1

then

ifE2

then

S1

else

S2

條件語(yǔ)句其他語(yǔ)句

stmtif

expr

thenstmtE1

if

expr

thenstmtelsestmt

E2S1S2

stmtif

expr

thenstmtelse