上次章节内容回顾ppt课件

1、上次课内容回顾上次课内容回顾语法分析简介：语法分析简介：词法分析：字母是元素，组成字符串词法分析：字母是元素，组成字符串(记号记号)语法分析：记号是元素，组成句子语法分析：记号是元素，组成句子语法分析的作用：语法分析的作用：1：识别句子：识别句子2：语法错误：语法错误正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复例：a (ba)5, a (ba)*正规式不能用于描述配对或嵌套的结构例1：配对括号串的集合例2：wcw | w是a和b的串 3.2 上下文无关文法上下文无关文法(CFG)3.2 上下文无关文法上下文无关文法(CFG)FCFG的定义与表示的定义与表示F

2、上下文无关文法，上下文无关文法，Context Free Grammar，CFGF定义定义3.1 CFG是一个四元组：是一个四元组：FG =（N，T，P，S），其中），其中F（1） N是非终结符是非终结符Nonterminals的有限集合；的有限集合；F（2） T是终结符是终结符Terminals的有限集合，且的有限集合，且NT=；F（3） P是产生式是产生式Productions的有限集合，形的有限集合，形如：如：FA，其中，其中AN左部），左部），(NT)*（右部），（右部），F若若=，则称，则称A为空产生式也可以记为为空产生式也可以记为A ）；）；F（4） S(非终结符非终结符)称为文法

3、的开始符号称为文法的开始符号Start symbol）。）。 3.2 上下文无关文法上下文无关文法(CFG)例3.1 简单算术表达式的上下文无关文法可表示如下：N = ET = +，*，(，)，-，idS = EP: E E + E（1） E E * E（2）E （E）（3）E -E（4）E id（5） 产生式的一般读法记号 读作“定义为或者“可导出”。 “E E + E” 表述为“算术表达式定义为两个算术表达式相加”；或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。3.2 上下文无关文法上下文无关文法(CFG) 2.产生式表示也被称为巴克斯范式Backus-Naur For

4、m，BNF），其中用:=表示 E :=E + E | E * E | (E) | -E | id3.2 上下文无关文法上下文无关文法(CFG)3.终结符与非终结符书写上的区分(a) 用大小写区分： E id(b) 用 区分： E id E E + E(c) 用区分： + 教材约定：大写英文字母A、B、C表示非终结符； 小写英文字母a、b、c表示终结符； 小写希腊字母、表示任意文法符号序列3.2 上下文无关文法上下文无关文法(CFG)产生式的缩写形式当多个产生式的左部非终结符相同时，可合并为一个产生式。新的产生式的左部是此非终结符，右部是所有原来右部的或运算并集合）。例3.3 G3.1可以重写为

5、如下形式：E E + E （1）| E * E（2）|（E）（3）| -E（4）| id（5）用“|”连接的每个右部称为一个候选项，具有平等的权利。P: E E + E (1) E E * E (2) E (E)(3) E -E(4) E id(5)3.2 上下文无关文法上下文无关文法(CFG)FCFG产生语言的基本方法推导产生语言的基本方法推导F CFG产生式通过推导的方法产生语言。产生式通过推导的方法产生语言。F通俗地讲，产生式产生语言的过程是从开始符号通俗地讲，产生式产生语言的过程是从开始符号S开始，开始，对产生式左部的非终结符反复地使用产生式：将产生式对产生式左部的非终结符反复地使用产

6、生式：将产生式左部的非终结符替换为右部的文法符号序列展开产生左部的非终结符替换为右部的文法符号序列展开产生式，用标记式，用标记=表示），直到得到一个终结符序列。表示），直到得到一个终结符序列。 F例例3.4 用算术表达式的上下文无关文法产生终结符序列用算术表达式的上下文无关文法产生终结符序列-(id+id)可如下：可如下：FE E + E（1）F | E * E（2）F|（E）（3） F| -E（4）F| id（5）E = -E (4) = -(E) (3) = -(E+E) (1) = -(id+E) (5) = -(id+id) (5)3.2 上下文无关文法上下文无关文法(CFG)定义定义

7、3.2 利用产生式产生句子的过程中，将产生式利用产生式产生句子的过程中，将产生式A的右部的右部代替文法符号序列代替文法符号序列A中的中的A得到得到的过程，称从的过程，称从A直接直接推导出推导出，记作：，记作：A=。若对于任意文法符号序列若对于任意文法符号序列1，2，.n，均有，均有1=2=.=n，则称此过程为零步或多步推导，记为：，则称此过程为零步或多步推导，记为：1=*n，其中，其中1=n的情况为零步推导。的情况为零步推导。若若1n，即推导过程中至少使用一次产生式，则称此过程为，即推导过程中至少使用一次产生式，则称此过程为至少一步推导，记为：至少一步推导，记为：1=+n。 两点注意：两点注意

8、： ，有，有=*，即推导具有自反性；，即推导具有自反性； 若若=*，=*，则，则=*，即推导具有传递性。，即推导具有传递性。3.2 上下文无关文法上下文无关文法(CFG)定义定义3.3 由由CFG G所产生的语言所产生的语言L(G)被定义为被定义为: L(G) = S= + and T* ， L(G)称为上下文无关语言称为上下文无关语言(Context Free Language, CFL)，称为句子。称为句子。若若S=*，(NT)*，则称，则称为为G的一个句型。的一个句型。定义定义3.4 在推导过程中，若每次直接推导均替换句型中最左边在推导过程中，若每次直接推导均替换句型中最左边的非终结符，

9、则称为最左推导，由最左推导产生的句型被的非终结符，则称为最左推导，由最左推导产生的句型被称为左句型。称为左句型。类似可定义最右推导与右句型，最右推导也被称为规范推导。类似可定义最右推导与右句型，最右推导也被称为规范推导。E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 12 3 4 5 66是句子，所有是句子，所有i (i=1.6)均是句型。均是句型。F例 E E + E | E E | (E ) | E | id F最左推导FE lm E lm (E) lm (E + E)F lm (id + E) lm (id + id)F最右推导规范推导）FE rm

10、 E rm (E) rm (E + E)F rm (E + id) rm (id + id)3.2 上下文无关文法上下文无关文法(CFG)3.2 上下文无关文法上下文无关文法(CFG)F推导、分析树与语法树推导、分析树与语法树FE = -E = -(E) = -(E+E) = -(id+E) = -(id+id) E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) F推导产生句子的方式不直观。分析树是推导的图形直推导产生句子的方式不直观。分析树是推导的图形直观表示，同时反映语言结构的实质和推导过程。观表示，同时反映语言结构的实质和推导过程。 F定义定义3.5

11、 3.5 对对CFG GCFG G的句型，分析树被定义为具有下述的句型，分析树被定义为具有下述性质的一棵树。性质的一棵树。F（1 1根由开始符号所标记；根由开始符号所标记；F （2 2非叶子节点内部节点由非终结符标记；非叶子节点内部节点由非终结符标记；F（3 3叶子由一个终结符或叶子由一个终结符或 标记；标记；F（4 4若若A A是某内部节点的标记，且是某内部节点的标记，且X1X1，X2X2，.，XnXn是该节点从左到右所有孩子的标记，则是该节点从左到右所有孩子的标记，则AX1X2.XnAX1X2.Xn是一个产生式。若是一个产生式。若AA，则标记为，则标记为A A的的结点可以仅有一个标记为结点

12、可以仅有一个标记为 的孩子。的孩子。3.2 上下文无关文法上下文无关文法(CFG)分析树与语言和文法的关系：每一直接推导(每个产生式)，对应一棵仅有父子关系的子树，即产生式左部非终结符“长出右部的孩子；分析树的节点，从左到右构成G的一个句型。若节点仅由终结符标记，则构成一个句子。F例 (id+id) 的分析树EE ()EEE+ididE E + E | E E | (E ) | E | id3.2 上下文无关文法上下文无关文法(CFG)例3.5 再考察-(id+id)的推导过程。E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 最左推导和最右推导的中间过程

13、对应的分析树可能不同，但最终的分析树相同，因为最终是同一个句子3.2 上下文无关文法上下文无关文法(CFG)分析树既反映了产生句型的推导过程，又反映了句型的结构。在更多的情况下，仅关注句型结构，而忽略推导过程。定义3.6 对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树:（1） 根与内部节点由表达式中的操作符标记；（2） 叶子由表达式中的操作数标记；（3用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。语法树与分析树的最根本区别在于内部节点包括根节点）： 分析树的内部节点是非终结符； 语法树的内部节点是操作符运算符）； 或者说语法树中省略了反映分析过程的非终结符。3.2

14、上下文无关文法上下文无关文法(CFG)例3.6 句子-(id+id)和句型if C then s1 else s2分析树：左部非终结符“产生右部文法符号序列；语法树：操作符(运算)作用于操作数(运算对象)；习惯上它们分别被称为具体语法树和抽象语法树。 3.2 上下文无关文法上下文无关文法(CFG)F二义性的存在二义性的存在F二义性问题：一个句子可能对应多于一棵分析树二义性问题：一个句子可能对应多于一棵分析树F例例3.7 文法文法G3.2为为EE+E | E*E |（E）| -E | idF句子句子id+id*id和和id+id+id可能的分析树有：可能的分析树有：3.2 上下文无关文法上下文无

15、关文法(CFG)定义定义3.7 若文法若文法G对同一句子产生不止一棵分析树，则称对同一句子产生不止一棵分析树，则称G是二是二义的。义的。 原因：在产生句子的过程中某些直接推导有多于一种选择原因：在产生句子的过程中某些直接推导有多于一种选择注意：注意：一个句子有多于一棵分析树，仅与文法和句子有关，与采用的一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关；推导方法无关；文法中缺少对文法符号优先级和结合性的规定。文法中缺少对文法符号优先级和结合性的规定。“悬空悬空danglingelse问题问题S if C then S(1)| if C then S else S(2)| id

16、:= E(3)(G3.3)C E = E | E E(4).(6)E E + E | - E | id | n(7).(10)3.2 上下文无关文法上下文无关文法(CFG)例3.8 条件语句 if x0 then x:=5 else x:=-5if x0 then x:=5 else x:=-5else与离它远的then匹配if x0 then x:=5 else x:=-5else与离它近的then匹配文法具有二义性文法具有二义性F在任何一个程序设计语言中，如果出现了二义性，则表示同一段程序在确定的、相同的环境下反复执行，会得到不同的结果，这在程序设计中是不允许的。F也就是说任何程序设计语言不应该有二义性。F文法二义不能说明它所产生的语言一定是二义的。F只有当产生一个语言的所有文法都是二义的时候，这个语言才被认为是二义的。3.2.1 正规式和上下文无关文法的比较初步思考）正规式(a|b)*