下载此文档

编译原理第2章(刘磊 机械工业出版社).ppt


文档分类:IT计算机 | 页数:约114页 举报非法文档有奖
1/114
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/114 下载此文档
文档列表 文档介绍
第二章形式语言与自动机理论基础
基本概念
形式化语言:具有语法严格、结构正规、便于计算机处理的特点。
一个程序设计语言是一种形式化语言。其核心是语法和语义。
语法:一组规则,是语言的形式。
语义:是语言的内容。
静态语义:一系列规则,确定哪些合乎语法的程序是合适的。
动态语义:表明程序要做什么,要计算什么。
定义 字母表
字母表:元素的非空有穷集合.
符号:字母表中的元素.
符号表:字母表.
字母表的表示符号:
符号串
符号串:.
例如:字母表∑={0,1},00,11,10,01,100 是它上的符号串.
注意:01和10是不同的两个符号串.
符号串的表示:=100
符号串的长度:符号串X中字符的个数m,用|X|=m表示.
空符号串:用ε表示, | ε|=0.

连接:符号串x和y,他们的连接是把y的字符写在x的字符之后.
例如:x=101,y=010
他们的连接xy=101010
|xy|=|x|+|y|=3+3=6
符号串的方幂
方幂:符号串x,把自身连接n次得到的符号串z,
z=xxxx…;记为xn
X0=
X1=X
例如:X=101
X0=
X1=101
X2=101101
X3=101101101
前缀和后缀
设z=xy是字符串.
.
如果 y <>, x是z的真前缀.
如果 x<>, y是z的真后缀
例如: z =101
z的前缀有: ,1,10,101, z的真前缀有: ,1,10,
z的后缀有: ,1, 01,101, z的真后缀有,1, 01,
子字符串
子字符串:一个非空字符串x,.
如果删去的前缀和后缀不同时为,称该子串为真子串.
例如:x=101
子串有:101,10,1,01,0, 
真子串有: 10,1,01,0, 
符号串集合
字符串集合:若集合A中的一切元素是某字母表上的符号串.
例如:={1,0},A={0,1,10,00}
符号串集合的乘积
设A、B是两个符号串的集合, AB表示A与B的乘积,定义为:
AB={xy|xA  yB}
例如 A={a,bc}, B={de,f}
AB={ade,af,bcde,bcf}
注意:{}A=A{}=A
A=A = 
符号串集合的方幂
设A是符号串集合,则称 Ai是符号串集合A的方幂,其中i〉=0。具体定义为:
A0={}
A1=A
A2=AA
……
An=AAA……A(n 个A)

编译原理第2章(刘磊 机械工业出版社) 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数114
  • 收藏数0 收藏
  • 顶次数0
  • 上传人分享精品
  • 文件大小763 KB
  • 时间2017-08-20