编译器原则语法和语言.ppt

第二章 文法和语言;第2章 文法和语言;2.1 文法的直观表示;形式语言：只考虑语法而不考虑语义的符号语言。 每种语言具有两个可识别的特性 语言的形式 与该形式相关联的意义 “形式”指语言的所有规则，描述出现什么符号串 语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。 形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。;表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述 例：汉语句子的构成规则：　　〈句子〉∷=〈主语〉〈谓语〉　　〈主语〉∷=〈代词〉|〈名词〉　　〈代词〉∷= 我 | 你 | 他　　〈名词〉∷= 王明 | 大学生 | 工人 | 英语　　〈谓语〉∷=〈动词〉〈直接宾语〉　　〈动词〉∷= 是 | 学习　　〈直接宾语〉∷=〈代词〉|〈名词〉;推导：“我是大学生” 是汉语的一个句子〈句子〉? 〈主语〉 〈谓语〉 ? 〈代词〉〈谓语〉 ?我〈谓语〉 ?我〈动词〉〈直接宾语〉 ? 我是〈直接宾语〉 ?我是〈名词〉 ?我是大学生 ;2.2 符号与符号串;符号串：由字母表中的符号构成的任何有穷序列称为符号串。符号串中的符号是有顺序的。;符号串s的头（前缀）和尾（后缀） ： 如果s=xy是一符号串，那么x是s的头，y是s的尾。若x是非空，则y是固有尾；若y非空，则x是固有头。 前缀：移走符号串s尾部的零个或多个符号得到的串。 如：设s=abc,那么s的前缀是ε，a，ab，abc 后缀：移走符号串s头部的零个或多个符号得到的串。 如：s =abc的后缀是ε，c，bc，abc，s的固有尾是ε，c，bc。 ;符号串s的子串： 从s中删去任何前缀或后缀得到的串. 如:bc是符号串abc的一个子串. 对符号串s， s和ε两者都是符号串s的前缀、后缀和子串。 符号串s的真前缀，真后缀，真子串： 任何非空符号串 x，是s的前缀，后缀或子串，并且 s ? x ;2.符号串的运算 (1)符号串相等： 符号串x，y，如果两者诸符号依次相等，则两符号串相等。 (2)符号串的长度：符号串中包含符号的个数。 |abc|=3；| ? |=0； (3)符号串的连结： x=abc，y=def 则xy=abcdef；yx=defabc； xy yx ? x=x ? =x； ;(4)符号串集合的乘积： 设A、B为两个符号串集合，其乘积为AB={xy|x ?A，y?B}； 例：A={aa，bb}，B={cc，dd}，则 AB={aacc，aadd，bbcc，bbdd} {? }A=A {? }=A； (5)空集： 不含任何元素的集合称为空集。记为?； 对任何集合A：A ?= ?A= ?; 注意： ?? ? ;(6)符号串的方幂： x是字母表上的符号串，则x的幂运算为： x0= ? ; x1= x; x2= xx;… xn= xn-1x=x xn-1 (n0) xn表示n个x相连结。 eg：x=ok；则 x0= ? ; x1= ok; x2= okok; … (7)符号串集合的方幂： A为符号串集合，则A的幂运算为： A0={?}; A1=A; A2=AA;... An= An-1A=AAn-1;(n0) A={aa，bb}，则A0={?}； A1={aa，bb}； A2=AA={aaaa，aabb，bbaa，bbbb};...;(8)符号串集合的闭包和正闭包 集合A的闭包表示为A*（亦称为自反闭包或星闭包）定义为： A*=A0? A1? A2? A3? …=?Ak， k?0 正闭包表示为A+具体定义为 A+=A1? A2? A3? …=?Ak， k?1 由定义可以看到A*= A0 ? A+ ;3、语言 (1)由一组符号所构成的集合。即： 字母表?上的每个语言是?*的一个子集。 例如：字母表Σ={a,b}，Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…} 集合{ab,aabb,aaabbb,…,anbn,…} 或表示为{w|w∈Σ*且w=anbn,n≥1}为字母表?上的一个语言。 集合{a,aa,aaa,…} 或表示为{w|w∈Σ*，且w=an，n≥1} 为字母表?上的一个语言。 (2) ?ε?是一个语言。 (3) ?即? ?是一个语言。;2.3 文法和语言的形式定义;一、规则（重写规则、产生