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

《东北大学秦皇岛分校编译原理课件第二章第三章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章文法和语言本章目的为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具--形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述1本章知识点(内容)引言和预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明23.1文法的直观概念和语言概述当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存

2、在着如何给出它的有穷表示的问题：给出一些规则，用这些规则来说明(或者定义)句子的组成结构。3“我是大学生”。是汉语的一个句子〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉4有了一组规则以后，按照如下方式用它们导出句子：开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成：〈句子〉〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓

3、语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去，句子：“我是大学生”的全部动作过程是：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生5“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一

4、种描述元语言称为文法。注:用于产生其他语言的语言称为元语言。63.2编译原理所涉及到的一些数学概念和运算集合笛卡儿乘积关系符号串73.2.1集合概念表示法：（1）枚举法：{1,2,3}（2）谓词法：{x

5、x-3>2}特性：（1）唯一性（2）确定性集合间的关系：相等、不相等、子集……集合的运算：并集、交集、差集、幂集83.2.2笛卡儿乘积序偶：由两个按一定次序排列的客体组成的序列，记为（x，y）n重序组：由n个按一定次序排列的客体组成的序列，记为（x1，x2，…，xn）笛卡儿乘积：A、B为任意两个集合，若序偶的第一个成员是集合A的一

6、个元素，第二个成员是集合B的一个元素，则所有这样的序偶组成的集合称为集合A和B的笛卡儿乘积。93.2.3关系定义关系矩阵和关系图关系的基本性质1、自反2、非自反3、对称4、非对称5、传递关系的乘积关系的传递闭包自反传递闭包103.3有关定义和记号符号：可以相互区别的记号（元素）。字母表：符号（元素）的非空有穷集合。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε(没有符号的符号串)是上的符号串2.若x是上的符号串,a是的元素,则xa是上的符号串3.y是上的符号串,当且仅当它可以由1和2

7、导出。例如：Σ={a,b}ε,a,b,aa,ab,aabba…都是上的符号串11介绍有关符号串的一些运算符号串的头,尾，固有头和固有尾：如果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…

8、；符号t是符号串z的第一个符号，则表示为z=t…。12符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串.由于ε的含义，显然有εx=xε=x。例如x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5符号串的方幂：符号串自身连接n次得到的符号串an定义为aa…aan个aa1=a,a2=aa且a0=ε例；若x=AB则:x0=εx1=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(n>0)13符号串集合：若集合A中所有元素都是某字母表上的符号

9、串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy

10、xA且yB若集合A=ab,cdeB=0,1则AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭