編譯原理 2 語言及其文法學習課件

第2章語言及其文法

哈爾濱工業(yè)大學陳鄞本章內容2.1基本概念2.2文法的定義2.3語言的定義2.4文法的分類2.4CFG的語法分析樹2.1基本概念字母表(Alphabet)字母表∑是一個有窮符號集合。符號的典型例子包括字母、數字和標點符號。例二進制字母表：{0,1}ASCIIUnicode字母表上的運算字母表∑1和∑2的乘積(product)∑1∑2={ab|a

∈∑1,b∈

∑2}例：{0,1}{a,b}={0a,0b,1a,1b}字母表上的運算字母表∑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次冪：長度為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,…}字母表的正閉包：長度正數的符號串構成的集合字母表上的運算字母表∑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,…}字母表的克林閉包：任意符號串（長度可以為零）構成的集合串

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

x∈∑*，x稱為是∑上的一個串串是字母表中符號的一個有窮序列串s的長度，通常記作|s|，是指s中符號的個數例:|aab|=3

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

x=dog且

y

=house，那么xy=doghouse。

空串是連接運算的單位元（identity），即，對于任何串s都有，εs=sε=s。串s的冪運算

s0=ε，

sn=sn-1s

,n≥1s1

=

s0s

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

形容詞little名詞boy

名詞apple

動詞eat未用尖括號括起來部分表示語言的基本符號尖括號括起來部分稱為語法成分文法的形式化定義

G

=(VT,VN,P

,S)VT：終結符集合終結符(terminalsymbol)是文法所定義的語言的基本符號，有時也稱為token例:

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

G

=(VT,VN,P

,S)VT：終結符集合VN

：非終結符集合非終結符(nonterminal)是用來表示語法成分的符號，有時也稱為“

語法變量”例:VN

={

句子

,

名詞短語

,

動詞短語

,

名詞

,

動詞

,形容詞

,…}文法的形式化定義

G

=(VT,VN,P

,S)VT：終結符集合VN

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

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

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

：稱為產生使的體（body

）或右部（rightside）例：

P={

句子

名詞短語

動詞短語

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

G

=(VT,VN,P

,S)VT：終結符集合VN

：非終結符集合P：產生式集合S：開始符號S∈VN。開始符號(start

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

=句子文法的形式化定義

G=(VT,VN,P

,S)VT：終結符集合VN

：非終結符集合P：產生式集合S：開始符號例：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約定：不引起歧義的前提下，可以只寫產生式產生式的簡寫對一組有相同左部的α產生式α→β1,α→β2,…,α→β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符號約定下述符號是終結符(a)字母表中排在前面的小寫字母，如

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

γ，表示文法符號串（包括空串）除非特別說明，第一個產生式的左部就是開始符號終結符

a,b,c

終結符號串u,v,...,z非終結符A,B,C文法符號X,Y,Z

文法符號串

α,β,γ

提綱2.1基本概念2.2文法的定義2.3語言的定義2.4文法的分類2.4CFG的語法分析樹2.3語言的定義自然語言的例子文法：句子名詞短語動詞短語名詞短語形容詞名詞短語名詞短語名詞動詞短語動詞名詞短語

形容詞little名詞boy

名詞apple

動詞eat單詞串：little

boyeatsapple

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

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

γαδ

γβδ。此時，稱文法中的符號串

γαδ

直接推導(directlyderive)出

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

α2，α2

α3，…，αn-1

αn，則可以記作α1

α2

α3

…

αn-1

αn，稱符號串α1經過n步推導出αn，可簡記為α1

nαnα

0

α

+表示“經過正數步推導”

*表示“經過若干（可以是0）步推導”推導(Derivations)和歸約(Reductions)

名詞短語動詞短語

形容詞名詞短語<動詞短語

little名詞短語<動詞短語

little

名詞<動詞短語

littleboy<動詞短語

littleboy動詞名詞短語

littleboyeats名詞短語

little

boyeats名詞

little

boyeatsapple

推導歸約文法：句子名詞短語動詞短語名詞短語形容詞名詞短語名詞短語名詞動詞短語動詞名詞短語

形容詞little名詞boy

名詞apple

動詞eat例句子

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

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

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

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

名詞短語動詞短語

形容詞名詞短語<動詞短語

little

名詞短語<動詞短語

little名詞<動詞短語

littleboy<動詞短語

littleboy動詞名詞短語

littleboyeats名詞短語

little

boyeats名詞

little

boyeatsapple

句型句子語言的形式化定義由文法G的開始符號S推導出的所有句子構成的集合稱為文法G生成的語言，記為L(G)。即L(G)={w|S

*w,

w∈VT*}文法E

→E+E|E*E|

(E)

|id生成的語言中包含多少個句子？例文法G①S→L|LT②T→L|D|TL|TD③L→a|b|c|…|z④D→0|1|2|3|…|9請寫出無符號整數和浮點數的文法T

TL

TDL

TDDL

TLDDL…

TD…LDDL

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

α→β

無限制文法(UnrestrictedGrammar)/短語結構文法(PhraseStructureGrammar,PSG)?α→β∈P，α中至少包含1個非終結符

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

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

產生式的一般形式：α1Aα2

→α1βα2

(β≠ε)

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

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

上下文無關文法

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

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

α→β

上下文無關語言（2型語言）由上下文無關文法(2型文法)G生成的語言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（

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

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

3型文法（RG）：A→wB

或

A→w(A→Bw

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

根節(jié)點的標號為文法開始符號

內部結點表示對一個產生式A→β的應用，該結點的標號是此產生式左部A

。該結點的子結點的標號從左到右構成了產生式的右部β

葉結點的標號既可以是非終結符，也可以是終結符。從左到右排列葉節(jié)點得到的符號串稱為是這棵樹的產出(yield)或邊緣(frontier)

G：①E→E+E②

E→E*E③

E→-E④E→(E)⑤

E→id分析樹是推導的圖形化表示給定一個推導

S

α1

α2

…

αn，對于推導過程中得到的每一個句型αi，都可以構造出一個邊緣為αi的分析樹文法：①E→E+E②

E→E*E③

E→-E④E→(E)⑤

E→id推導過程：E

-E

-

(E

)

-(

E+E)

-(

id+E

)

-(

id+id)-E

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

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

if

expr

then

stmt

ifexpr

then

stmt

else

stmt

other句型ifE1

then

ifE2

then

S1

else

S2

條件語句其他語句

stmtif

expr

thenstmtE1

if

expr

thenstmtelsestmt

E2S1S2

stmtif

expr

thenstmtelse