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

2.3 程序语言的语法描述,2.3.1 上下文无关文法 2.3.2 语法分析树与二义性2.3.3 形式语言鸟瞰,2.3.1 上下文无关文法,一、文法引入二、符号和符号串 三、文法的直观概念 四、文法和语言的形式定义,二、符号和符号串 p25,英语 句子 单词 字母程序设计语言 程序 单词 基本符号基本符号集合:构成一个语言的一切基本符号组成一个集合,1.字母表(基本符号集合、符号集)字母表是元素的 非空有穷 集合 2.元素(符号)例:汉语的字母表 汉字,数字及标点符号 C语言的字母表字母,数字,符号,文法和语言的形式定义的预备知识,3.符号串：上的有穷序列,例:=a,b,c,则_是上的符号串空串:不包含任何符号的符号串 符号串中符号的顺序很重要 可以使用字母表示符号串 x=abc和 不同,4.符号串的运算,(a)符号串的长度|x|(b)符号串的头（前缀）、尾（后缀）、固有头（真前缀）、固有尾（真后缀）定义：如果z=xy是一符号串，(x,y都是符号串),那么：x是z的头，y是z的尾，如果x非空，那么y是固有尾；如果y非空，那么x是固有头。,补充练习,设z=abc,那么z的头是_，z的尾是_,固有头是_,固有尾是_,(c)符号串的连接 xy,xy把y的符号写在x的符号之后得到的符号串x=x=x(d)符号串的方幂 z=xn把x自身连接n次得到的符号串例 x=AB,x3=_ x0=对于n0,有xn=xxn-1=xn-1 x,5.符号串的集合:由字母表上的符号串组成的集合 假设:U和 V是符号串集合(a)U和V的乘积(连接)UV=|U且V(b)V自身的n次乘积 Vn=VVVV0=例:若 集合A=ab,cde,B=0,1 则 AB=_,6.字母表的闭包*(Closure Set)上的一切符号串组成的集合 例如:=0,则*=_=a,b,则*=_,7.字母表的正闭包+(Positive Closure Set)上的除外的所有符号串组成的集合,8.闭包与正闭包,*=0 1 2 n=1 2 n*=0=*-=*=*对所有的,有*,多项选择题,*的元素的数量是A.可数的B.不可数的C.无穷多的D.有穷多的,9.辨析,连线练习,字母表 元素符号串符号串的集合,构成语言的基本符号语言的基本符号集某种语言程序，句子,英语 句子 单词 字母程序设计语言 程序 单词 基本符号,10.语言,语言是由句子组成的集合字母表上的一个语言是上的一些 符号串的集合字母表的闭包*是上的一切符号串组成的集合 字母表上的每个语言是*的一个子集,例：以下是字母表=a,b上的语言,A=ab,aabb,aaabbb,an bn,w|w*且w=an bn,n1B=a,aa,aaa,w|w*且w=an,n1,关于语言,是一个语言。是一个语言。有关语言的运算：既然将语言定义为一个集合，那么有关集合的运算也适合语言设L是(上的)一个语言,M是(上的)一个语言，则语言L和M的并，交，差，补是一个语言,