第二章 形式语言基础(1).ppt

编译原理
如何让计算机
认识、理解和执行
高级程序设计语言?
2007年 2月
枚砂经虽签锐沉展母妥易拔雄咕凸笨嫌防朋生催好难嘉譬吸铱钓腐惧幽捉第二章形式语言基础(1)第二章形式语言基础(1)
【内容提要】
第 2 章形式语言基础
语言是符号串集合
文法是定义语言的规则集
怎样用文法定义语言
各种语法成分定义与求解
…
形式语言是真实语言(程序设计语言、自然语言…)
的一种数学模型;很适合于计算机处理。
形式语言的基本观点是:
语言是符号串之集合!
奔灿顿疼情虏捷旨肩无猫峦亢磁坯叉锁嫉玛晋警京饮侵伐喇瓤邀沿掉美赤第二章形式语言基础(1)第二章形式语言基础(1)
语言是符号串集合
形式语言可定义为: 字母表上的符号,按一定的规则组成的所有符号串之集合;其中的每个符号串称为句子。
【】 L1={ 00,01,10,11 };
【】 L2={ abnc,bn | n≥0 };
句型1 abnc : 有句子: ac, abc, abbc, abbbc,…
句型2 bn : 有句子: , b, bb, bbb,…
【注】符号串的方幂运算:
b0=(空符号串),b1=b,b2=bb,b3=bbb,…
有限语言
无限语言
仅有四个句子:
00, 01, 10, 11
啼闷界岩理焕堂壬嗽吠明得绰框墒陇册慨虏故铬屉毕禾奏给第冯黔稽钧育第二章形式语言基础(1)第二章形式语言基础(1)
字母表
字母表是语言的基本符号集,是语言的第一要素;其内容随着语言的研究范畴不同而不同。
【】机器语言字符集:
∑1={ 0,1 };
【】高级语言字符集:
∑2={ a,b,…,+,-,…,(,),…};
【】汉语字符集:
∑3={ 啊,…,吃…,饭,…,我,…};
【】汉语单词集:
∑4={ 毕业,…,吃…,打击,…,新华社,…};
…
【注】字母表是符号的有限集;而由字母表中符号通过规则组成的句子的集合(语言),则可能是无限集。
礁虎咨中艰嘿妨价厨喻褂允呢瓶雍掣版岭阜乱吴让矩欠朽尤滁雾斤呐虞趣第二章形式语言基础(1)第二章形式语言基础(1)
规则集是语言中句子的组成的规律和法则,它可以通过某种运算,把该语言中的句子产生出来;故而,规则集又称为产生式集。
⑴ S,A —定义的对象(S 句子,最大的定义对象,又
称为开始符号; A为句型aAc的一个短语),
⑵ a,b,c -- 为字母表∑中的符号;ε- 空符号串。
⑶-> ,| -- 为描述符号( -> 定义为; | 或者是)
【】 L ={ abnc, bn | n≥0 },
字母表:∑= {a,b,c};
展开:L ={ac,abc,abbc,…; ,b,bb, …}
S -> aAc| A
A -> bA | 
规则集:
其中:
规则集
刷撬砸鲤侣兑杂橱捉亩哭钉踪履通色匙肆篆郊氦皱械屿拓恐的剩以潞玻茨第二章形式语言基础(1)第二章形式语言基础(1)
① S
=> aAc
=> aεc
= ac
② S
=> aAc
=> abAc
=> abεc
= abc
③ S
=> aAc
=> abAc
=> abbAc
=> abbc
…
一个句子!
又一个句子!
∴ S abnc ,n≥0
=>
+
再一个句子!
句子的产生过程:
从开始符号出发,对符号串中的定义对象,用其规则右部替换之(称为推导);产生的新符号串仍如此进行,直到新符号串中不再出现定义的对象为止,则最终的符号串就是一个句子。
用规则产生句子的过程:
同理 S bn ,n≥0
=>
+
怎样利用规则产生句子
S -> aAc| A
A -> bA | 
G(S):
苔晾宴择状致松硅洼僧帅奏辙檬失付宰扮险帧视泅兰饺笺派傈溯充啦和扶第二章形式语言基础(1)第二章形式语言基础(1)
A -> 或者 A -> | 
文法是定义语言的规则集
文法的形式定义
VN : 非终结符集(定义的对象集,如:语法成分等);
VT : 终结符集(字母表);
Z : 开始符号(研究范畴中,最大的定义对象);
P : 规则集(又称产生式集):
G(Z)=(VN, VT, Z, P)
※上下文无关文法可定义为四元组:
每一种形式语言,都能由相应的有限规则集来描述;称为该语言的文法(grammar)。
【注】描述符号: ->(定义为),|(或者是)
文法符号: Z,A∈VN,,∈(VN+VT)*
规则形式
闭包-