编译原理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 =VVV V0= 例: 若 集合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, n1 B=a,aa,aaa, w|w*且w=an,n1 关于语言 是一个语言。 是一个语言。 有关语言的运算： 既然将语言定