东北大学秦皇岛分校编译原理课件 第二篇第三篇.ppt

第三章 文法和语言 本章目的 为语言的语法描述寻求工具 工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读） 形式工具--形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述 本章知识点(内容) 引言和预备知识 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明 3.1 文法的直观概念和语言概述 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题：给出一些规则，用这些规则来说明(或者定义)句子的组成结构。 “我是大学生”。是汉语的一个句子 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷=我｜你｜他 〈名词〉∷=王明｜大学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是｜学习 〈直接宾语〉∷=〈代词〉｜〈名词〉 有了一组规则以后，按照如下方式用它们导出句子：开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成： 〈句子〉 ? 〈主语〉〈谓语〉， 然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉， 那么得到：〈主语〉〈谓语〉 ? 〈代词〉〈谓语〉， 重复做下去， 句子：“我是大学生”的全部动作过程是： 〈句子〉 ? 〈主语〉〈谓语〉 ? 〈代词〉〈谓语〉  ?我〈谓语〉 ?我〈动词〉〈直接宾语〉  ? 我是〈直接宾语〉 ?我是〈名词〉 ?我是大学生 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。 注:用于产生其他语言的语言称为元语言。 3.2 编译原理所涉及到的一些数学概念和运算 集合 笛卡儿乘积 关系 符号串 3.2.1 集合 概念 表示法：（1）枚举法：{1,2,3} （2）谓词法：{x|x-32} 特性： （1）唯一性 （2）确定性 集合间的关系：相等、不相等、子集…… 集合的运算：并集、交集、差集、幂集 3.2.2 笛卡儿乘积 序偶：由两个按一定次序排列的客体组成的序列，记为（x，y） n重序组：由n个按一定次序排列的客体组成的序列，记为（x1，x2，…，xn） 笛卡儿乘积：A、B为任意两个集合，若序偶的第一个成员是集合A的一个元素，第二个成员是集合B的一个元素，则所有这样的序偶组成的集合称为集合A和B的笛卡儿乘积。 3.2.3 关系 定义 关系矩阵和关系图 关系的基本性质 1、自反 2、非自反 3、对称 4、非对称 5、传递 关系的乘积 关系的传递闭包 自反传递闭包 3.3 有关定义和记号 符号：可以相互区别的记号（元素）。 字母表?：符号（元素）的非空有穷集合。 符号串：由字母表?中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε(没有符号的符号串)是?上的符号串 2.若x是?上的符号串,a是?的元素,则xa是?上的符号串 3. y是?上的符号串,当且仅当它可以由1和2导出。 例如： Σ={a,b} ε,a,b,aa,ab,aabba…都是?上的符号串 介绍有关符号串的一些运算 ? 符号串的头,尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。举个例子:设z=abc,那么z的头是ε,a,ab,abc,除abc外，其它都是固有头；z的尾是ε,c,bc,abc,z的固有尾是ε,c,bc。 当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，采用省略写法：z=x…； 如果只是为了强调x在符号串z中的某处出现，则可表示为：z=…x…；符号t是符号串z的第一个符号，则表示为z=t…。 符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串. 由于ε 的含义，显然有ε x=x ε =x。 例如 x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜x