编译原理2.3.1-2-符号与符号串

《编译原理2.3.1-2-符号与符号串》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.3程序语言的语法描述2.3.1上下文无关文法2.3.2语法分析树与二义性2.3.3形式语言鸟瞰2.3.1上下文无关文法一、文法引入二、符号和符号串三、文法的直观概念四、文法和语言的形式定义二、符号和符号串p25英语－>句子－>单词－>字母程序设计语言－>程序－>单词－>基本符号基本符号集合:构成一个语言的一切基本符号组成一个集合1.字母表(基本符号集合、符号集)∑－字母表是元素的非空有穷集合2.元素(符号)例:汉语的字母表－汉字,数字及标点符号C语言的字母表－字母,数字,符号…文法和语言的形式定义的预备知识3.符号串：∑上的有穷序列例:∑={a,b,c},则_______

2、_是∑上的符号串空串ε:不包含任何符号的符号串符号串中符号的顺序很重要可以使用字母表示符号串x=abcε和Ø不同4.符号串的运算(a)符号串的长度

3、x

4、(b)符号串的头（前缀）、尾（后缀）、固有头（真前缀）、固有尾（真后缀）定义：如果z=xy是一符号串，(x,y都是符号串),那么：x是z的头，y是z的尾，如果x非空，那么y是固有尾；如果y非空，那么x是固有头。补充练习设z=abc,那么z的头是____________，z的尾是____________,固有头是___________,固有尾是___________(c)符号串的连接x•y,xy把y的符号写在x的符号之后得到的符

5、号串εx=xε=x(d)符号串的方幂z=xn把x自身连接n次得到的符号串例x=AB,x3=____________x0=ε对于n>0,有xn=xxn-1=xn-1x5.符号串的集合:由字母表上的符号串组成的集合假设:U和V是符号串集合(a)U和V的乘积(连接)UV=αβ

6、αU且βV(b)V自身的n次乘积Vn=VV…VV0={ε}例:若集合A=ab,cde,B=0,1则AB=______________________6.字母表的闭包∑*(ClosureSet)∑上的一切符号串组成的集合例如:∑={0},则∑*=____∑={a,b},则∑*=____7.字母表

7、的正闭包∑+(PositiveClosureSet)∑上的除ε外的所有符号串组成的集合8.闭包与正闭包∑*=∑0∑1∑2…∑n…∑＋=∑1∑2…∑n…∑*=∑0∑＋∑＋=∑*-{ε}∑＋=∑∑*=∑*∑对所有的∑,有ε∑*多项选择题∑*的元素的数量是A.可数的B.不可数的C.无穷多的D.有穷多的√√9.辨析φε{ε}连线练习字母表元素符号串符号串的集合构成语言的基本符号语言的基本符号集某种语言程序，句子英语－>句子－>单词－>字母程序设计语言－>程序－>单词－>基本符号10.语言语言是由句子组成的集合字母表∑上的一个语言是∑上的一些符号串的集合字母表的闭包∑*是

8、∑上的一切符号串组成的集合字母表∑上的每个语言是∑*的一个子集例：以下是字母表Σ={a,b}上的语言A={ab,aabb,aaabbb,…,anbn,…}{w

9、w∈∑*且w=anbn,n≥1}B={a,aa,aaa,…}{w

10、w∈∑*且w=an,n≥1}关于语言{ε}是一个语言。Φ是一个语言。有关语言的运算：既然将语言定义为一个集合，那么有关集合的运算也适合语言设L是(∑上的)一个语言,M是(∑上的)一个语言，则语言L和M的并，交，差，补是一个语言