编译原理 2 语言及其文法学习课件

第2章语言及其文法

哈尔滨工业大学陈鄞本章内容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文法的定义自然语言的例子——句子的构成规则句子名词短语动词短语名词短语形容词名词短语名词短语名词动词短语动词名词短语

形容词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

有了文法（语言规则），如何判定一个词串是否是满足文法的句子？推导(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例句子

回答前面的问题有了文法（语言规则），如何判定某一词串是否是该语言的句子？句子的推导（派生）-从生成语言的角度句子的归约

-从识别语言的角度均根据规则句型和句子如果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的语法分析树

根节点的标号为文法开始符号

内部结点表示对一个产生式A→β的应用，该结点的标号是此产生式左部A

。该结点的子结点的标号从左到右构成了产生式的右部β

叶结点的标号既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串称为是这棵树的产出(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