《编译原理符号与符号串》由会员分享，可在线阅读，更多相关《编译原理符号与符号串（18页珍藏版）》请在金锄头文库上搜索。
1、2.3 程序语言的语法描述2.3.1 上下文无关文法 2.3.2 语法分析树与二义性 2.3.3 形式语言鸟瞰2.3.1 上下文无关文法一、文法引入 二、符号和符号串 三、文法的直观概念 四、文法和语言的形式定义 二、符号和符号串 p25 英语 句子 单词 字母 程序设计语言 程序 单词 基本符号基本符号集合: 构成一个语言的一切基 本符号组成一个集合1. 字母表 (基本符号集合、符号集) 字母表是元素的 非空有穷 集合 2. 元素(符号) 例: 汉语的字母表 汉字,数字及标点符号 C语言的字母表 字母,数字,符号 文法和语言的形式定义的预备知识 3. 符号串 ： 上的有穷序列 例: =a,
2、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
3、(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 =VVV V0= 例: 若 集合A=ab,cde, B = 0,1 则 AB =_6. 字母表的闭包 * (Closure Set) 上的一切符号串组成的集合 例如: =0 , 则*=_=a, b , 则*=_7. 字母表的正闭包 + (Positive Closure Set) 上的除外
4、的所有符号串组成的集合 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的并，交，差，补是一 个语言
