《西北工业大学编译原理所有课件第三章上下文无关文法》由会员分享，可在线阅读，更多相关《西北工业大学编译原理所有课件第三章上下文无关文法（78页珍藏版）》请在金锄头文库上搜索。
1、machunyan,西北工业大学软件与微电子学院,1,课程内容 第一章 概论 第二章 词法分析 第三章上下文无关文法 第四章自上而下的语法分析 第五章自下而上的语法分析 第六章语义分析 第七章运行时环境 第八章代码生成 第九章 代码优化,machunyan,西北工业大学软件与微电子学院,2,第三章 上下文无关文法,本章的目的： 为语言的语法描述寻求形式工具，要求该工具对程序设计语言给出精确无二义的语法描述。 基于语法的形式化描述，语法分析算法见第四章和第五章。,machunyan,西北工业大学软件与微电子学院,3,形式工具,作业,第三章 上下文无关文法及分析,3.1 语言的表示 3.2 上下文
2、无关文法的形式定义 3.3 分析树与抽象语法树 3.4 二义性文法,machunyan,西北工业大学软件与微电子学院,4,3.1 语言的表示(续),如何描述一种语言(符号串的集合)？ 如果语言是有穷的(仅包含有穷个句子) 可以将句子逐一枚举进行表示。 如果语言是无穷的，找出语言的有穷表示 生成方式(文法)：语言的每个句子可以用定义的规则构造。 识别方式(自动机)：用一个过程模型，输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。,machunyan,西北工业大学软件与微电子学院,5,3.1 语言的表示(续),Noam Ch
3、omsky研究了自然语言的结构，提出了一种描述语言的数学系统(Chomsky文法)，并以此定义了四类性质不同的文法(0型，1型，2型和3型文法)，称为语言（文法）的Chomsky分类。 其中2型文法（或上下文无关文法）对程序设计语言是最有用的，它可以作为程序设计语言语法结构描述的标准方式。,machunyan,西北工业大学软件与微电子学院,6,3.1 语言的表示(续),Chomsky文法用生成方式(规则)描述语言，语言中的每个句子用严格定义的规则构造。 文法示例，简单句子的语法结构表示规则: 把上述两个字符串中间用一箭头分隔构成的有序对称为产生式。其中， “ ”表示“由组成”, “ ”也可以用
4、=，:=，:来代替。,machunyan,西北工业大学软件与微电子学院,7,例如：包含加法、减法和乘法的简单整型算术表达式的语法结构可由下面的上下文无关文法(2型文法)给出： exp exp op exp exp (exp) exp number op +|-|*,3.1 语言的表示(续),machunyan,西北工业大学软件与微电子学院,8,形式工具,作业,第三章 上下文无关文法及分析,3.1 语言的表示 3.2 上下文无关文法的形式定义 3.3 分析树与抽象语法树 3.4 二义性文法,machunyan,西北工业大学软件与微电子学院,9,3.2 上下文无关文法的形式定义,上下文无关文法(即
5、2型文法)的形式定义 推导和规约的定义 句型和句子的定义 最左和最右推导 文法定义的语言 递归产生式和递归文法 chomsky文法的分类-了解 文法和语言-了解,machunyan,西北工业大学软件与微电子学院,10,上下文无关文法G是一个四元组，即G=(VT ， VN ， P，S)： 终结符集合VT 非终结符集合VN(与VT不相交) 产生式或文法规则A形成的集合P, 其中AVN，(VTVN)* 开始符号S，其中SVN,产生式的左部,产生式的右部,上下文无关文法(即2型文法)的形式定义：,注：终结符和非终结符可以用单个 字符表示，也可以用字符串表示。,machunyan,西北工业大学软件与微电
6、子学院,11,例 G1 =(N , 0，1,其中:非终结符集合：VN =N,终结符集合： VT =0，1,产生式的集合： P=N0N，N1N，N0，N1,开始符号为：N,文法举例,N0N, N1N, N0, N1, N）,machunyan,西北工业大学软件与微电子学院,12,通常情况下，文法仅用产生式的集合表示：,G1N: N0N N1N N0 N1,G1N: N0N | 1N | 0 | 1,也可写成：,文法举例,表示文法的开始符号,machunyan,西北工业大学软件与微电子学院,13,文法Gexp exp exp op exp exp ( exp ) exp number op + |
7、 - | * 的终结符、非终结符、开始符号分别为？,文法举例,machunyan,西北工业大学软件与微电子学院,14,3.2 上下文无关文法的形式定义(续),上下文无关文法(即2型文法)的形式定义 推导和规约的定义 句型和句子的定义 最左和最右推导 文法定义的语言 递归产生式和递归文法 chomsky文法的分类-了解 文法和语言-了解,machunyan,西北工业大学软件与微电子学院,15,2.推导和规约的定义,包含加法、减法和乘法的简单整型算术表达式的语法结构： exp exp op exp exp ( exp ) exp number op +|-|* number number是否是一个
8、合法的句子？,machunyan,西北工业大学软件与微电子学院,16,2.推导和规约的定义(续),直接推导或一步推导 直接推导就是产生式规则的一次运用，即用产生式的右部替换左部，记为“” 。 直接推导的定义：若有v,w满足： v=, w= 其中：是文法G的产生式， (VT VN)*, (VT VN)* 则称v直接推导到w，记作 v w，也称w直接归约到v。,machunyan,西北工业大学软件与微电子学院,17,例：GS：S0S1，S01 直接推导：,S 0S1,0S1 00S11,00S11 000S111,000S111 00001111,2.推导和规约的定义(续),machunyan,西
9、北工业大学软件与微电子学院,18,推导的定义： 若存在w0w1 . wn (n0), 用 w0 =+ wn表示w0到wn经历一步或多步推导，称w0推导出wn ，或wn归约到w0 ； 若有w0 =+ wn ，或w0 = wn ，则记为 w0 =* wn ，表示表示w0到wn零步或多步推导。,2.推导和规约的定义(续),machunyan,西北工业大学软件与微电子学院,19,例：GS： S0S1， S01,S0S100S11000S11100001111,S +00001111,给出字符串00001111的一个推导：,2.推导和规约的定义(续),machunyan,西北工业大学软件与微电子学院,2
10、0,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法)的形式定义 推导和规约的定义 句型和句子的定义 最左和最右推导 文法定义的语言 递归产生式和递归文法 chomsky文法的分类-了解 文法和语言-了解,machunyan,西北工业大学软件与微电子学院,21,3.句型和句子的定义,句型和句子 设G=(VN , VT , P , S)是一文法,且 V=VNVT 若S =*，V*，则称为文法G的句型； 若S=+，VT*，则称为文法G的句子；,machunyan,西北工业大学软件与微电子学院,22,简单整型算术表达式文法： exp exp op exp|(exp)|number op
11、+|-|* 给出算术表达式（34-3）*42的一个推导，请列出推导过程中出现的句型和句子。,3.句型和句子的定义(续),machunyan,西北工业大学软件与微电子学院,23,算术表达式（34-3）*42的推导： exp exp op exp exp op number exp * number (exp) * number (exp op exp) * number (exp op number) * number (exp - number) * number (number - number) * number,machunyan,西北工业大学软件与微电子学院,24,3.2 上下文无关文
12、法的形式定义,上下文无关文法(即2型文法)的形式定义 推导和规约的定义 句型和句子的定义 最左和最右推导 文法定义的语言 递归产生式和递归文法 chomsky文法的分类-了解 文法和语言-了解,machunyan,西北工业大学软件与微电子学院,25,4.最左和最右推导,最左推导 对于文法GS，S * 是一个最左推导是指：在由S推导的过程中，任何一步直接推导，都是用字符串中的最左非终结符对应的产生式规则进行推导，其中、是句型。 简单整型算术表达式文法： exp exp op exp|(exp)|number op +|-|*,machunyan,西北工业大学软件与微电子学院,26,exp exp
13、 op exp (exp)op exp (exp op exp)op exp (number op exp)op exp (number - exp)op exp (number - number) op exp (number - number) * exp (number - number) * number,算术表达式（34-3）*42的最左推导：,machunyan,西北工业大学软件与微电子学院,27,最右推导 S * 是一个最右推导是指：在由S推导的过程中，任何一步直接推导，都是用字符串中的最右非终结符对应的产生式规则进行推导，其中、是句型。 最右推导也被称为规范推导，由规范推导所得
14、的句型称为规范句型。,4 .最左和最右推导(续),machunyan,西北工业大学软件与微电子学院,28,算术表达式（34-3）*42的最右推导： exp exp op exp exp op number exp * number (exp) * number (exp op exp) * number (exp op number) * number (exp - number) * number (number - number) * number,4.最左和最右推导(续),machunyan,西北工业大学软件与微电子学院,29,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法
15、)的形式定义 推导和规约的定义 句型和句子的定义 最左和最右推导 文法定义的语言 递归产生式和递归文法 chomsky文法的分类-了解 文法和语言-了解,machunyan,西北工业大学软件与微电子学院,30,5.文法定义的语言,文法GS定义的语言L(G) 为： L(G)=x | S =+x,其中S为开始符号,x VT* ，即语言是所有句子构成的集合； 上下文无关文法定义的语言称作上下文无关语言。,machunyan,西北工业大学软件与微电子学院,31,文法定义的语言举例 例5.1：有文法GZ: (1)Z aZb (2)Z ab 它定义的语言是什么？,由(2)知: Zab 故ab是文法的一个句子,5.文法定义的语言(续),machunyan,西北工业大学软件与微电子学院,32,由(1)(2)知: ZaZba2b2 故a2b2是文法的一个句子 反复使用产生式(1)： ZaZba2Zb2 an-1Zbn-1 anbn 所以上述文法所定义的语言为： L(GZ)=anbn | n1,5.文法定义的语言(续),machunyan,西北工业大学软件与微电子学院,33,例5.2：已知语言为 L(G)=abna | n1
