第二章 形式语言基础.ppt

编译程序的设计原理与实现
如何让计算机
认识、理解和执行
高级程序设计语言?
第 2 章形式语言基础
计算机处理语言,首先应考虑语言的形式化、规
范化,使其具有可计算性和可操作性;这就是形式语
言理论研究的问题。
形式语言诞生于1956年,由chomsky创立。通常,
语言研究至少涉及三个方面:语法、语义和语用;
这里仅侧重于语法的研究。
※形式语言的基本观点是:
语言是符号串之集合!
※形式语言理论研究的基本问题是:
研究符号串集合的表示方法、结构特性
以及运算规律。
【前言】
【内容提要】
第 2 章形式语言基础
形式语言是符号串集合
形式语言是由文法定义的
主要语法成分的定义
两类特性文法
文法变换方法
关于形式语言的分类问题
字母表-- 元素(符号)的非空有限集合;
符号串-- 符号的有限序列;
符号串集合-- 有限个或者无限个符号串组成的集合;
规则-- 以某种形式表达的在一定范围内共同遵守的章程和制度;这里,指符号串的组成规则。
形式语言是符号串集合
【形式语言】是字母表上的符号,按一定的
规则组成的所有符号串集合;其中的每个符号串
称为句子。
【名词解释】:
三要素!
【】 L1={ 00,01,10,11 };
字母表∑1= {0,1},
句子有:00,01,10,11
【注】⑴ b0=(空符号串),b1=b,b2=bb,b3=bbb,…
⑵ L1 为有限语言; L2 为无限语言。
形式语言概念示例:
【】 L2={ abmc,bn | m>0,n≥0 }
字母表∑2= {a,b,c},
句型1: abmc ,
有句子: abc, abbc, abbbc,…
句型2: bn ;
有句子: , b, bb, bbb,…
两个语言!
1. 连接:.= 如 =ab
符号串(集合)的运算
3. 方幂: n = …= n-1 = n-1
4. 闭包:
n个
Ⅰ. 符号串的运算
设, 为两个符号串,则:
的正闭包: + = 1|2|…|n|…
的星闭包: * = 0|1|2|…|n|…
※0 =(空符号串)
什麽符号也没有的符号串!
1= ; 2 = ;…
2. 或: |= (或者)
这是一种
泛指!
符号串(集合)的运算(续1)
【例】:
⑵ ab|cd = ab(或者 cd )
⑴ = abcde
⑶(a|b)1 =(a|b)= a|b
(a|b)* =(a|b)0 |(a|b)1 |(a|b)2 |…
(a|b)2 =(a|b)(a|b)=aa|ab|ba|bb
…
即:(a|b)* = (a|b)n ,n≥0
同理: (a|b)+ = (a|b)n ,n>0
※符号串运算示例
泛指:
由a,b组成的
任意符号串!
(包括空串)
: AB={xy |xA 且 yB}
符号串(集合)的运算(续2)
:
A 的正闭包: A+ = A1∪A2∪…∪An∪…
A 的星闭包: A* = A0∪A1∪A2∪…∪An∪…
设 A 和 B 为两个符号串集合,则:
2. 和: A∪B=A+B={x| xA 或 xB}
: An = AA…A = AAn-1 = An-1A
n个
※ A0 ={};
A1 =A ; A2 =AA ; A3 =AAA ; …
Ⅱ. 符号串集合的运算
符号串集合运算示例:
【】设 A={a,b},B={c,d}
则 A+B={a,b,c,d}
则 AB={xy|xA,yB}={ac,ad,bc,bd}
【】设 A={a}
则 A* = A0∪A1∪A2∪…∪An∪…
={}+{a}+{aa}+{aaa}+…
={,a,aa,aaa,…}
={an|n≥0}
【】设 A={a,b}, A* = ?
∵ A* = A0∪A1∪A2∪…∪An∪…
A0 ={};
A1 = A ={a,b};
A2 = ={a,b}.{a,b}={aa,ab,ba,bb};
A3 = ={a,b}.{aa,ab,ba,bb}
={aaa,aab,aba,abb,baa,bab,bba,bbb};
…
∴ A* = { x | x=(a|b)n ,n≥0 }
符号串集合运算示例(续):
推论:若 A为任一字母表,则 A* 就是该字母
表上的所有符号串(包括空串)的集合。