上次课内容回顾.ppt
24页
上次课内容回顾上次课内容回顾上次课内容回顾上次课内容回顾语法分析简介：语法分析简介：词法分析词法分析：字母是元素，组成字符串(记号)语法分析语法分析：记号是元素，组成句子语法分析的作用：语法分析的作用：1：识别句子：识别句子2：语法错误：语法错误1 ¯正规式能定义一些简单的语言正规式能定义一些简单的语言，，能表示给定结构的固定次能表示给定结构的固定次数的重复或者没有指定次数的重复数的重复或者没有指定次数的重复例：例：a (ba)5, a (ba)*¯正规式不能用于描述配对或嵌套的结构正规式不能用于描述配对或嵌套的结构例例1：：配对括号串的集合配对括号串的集合例例2：：{wcw | w是是a和和b的串的串} 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)2 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)FCFG的定义与表示的定义与表示上下文无关文法，Context Free Grammar，CFG定义定义3.1 CFG是一个四元组：G =（N，T，P，S），其中（1） N是非终结符非终结符（Nonterminals）的有限集合；（2） T是终结符终结符（Terminals）的有限集合，且N∩T=Φ；（3） P是产生式产生式（Productions）的有限集合，形如：A→α，其中A∈N（左部），α∈(N∪T)*（右部），若α=ε，则称A→ε为空产生式（也可以记为A →）；（4） S(非终结符)称为文法的开始符号开始符号（Start symbol）。
3 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)[例3.1] 简单算术表达式的上下文无关文法可表示如下：N = {E}T = {+，*，(，)，-，id}S = EP: E → E + E（1） E → E * E（2）E →（E）（3）E → -E（4）E → id（5） 1.产生式的一般读法记号 → 读作“定义为定义为”或者“可导出可导出” “E → E + E” 表述为“算术表达式定义为两个算术表达式相加”；或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”4 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG) 2.产生式表示也被称为巴克斯范式巴克斯范式（Backus-Naur Form，BNF），其中→用::=表示 E ::=E + E | E * E | (E) | -E | id5 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)3.终结符与非终结符书写上的区分(a) 用大小写大小写区分： E → id(b) 用" "区分： E → "id" E → E "+" E(c) 用< >区分：
新的产生式的左部是此非终结符，右部是所有原来右部的或运算或运算（并集合）[例3.3] G3.1可以重写为如下形式：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)7 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)FCFG产生语言的基本方法－推导产生语言的基本方法－推导 CFG（产生式）通过推导推导的方法产生语言通俗地讲，产生式产生语言的过程是从开始符号S开始，对产生式左部的非终结符反复地使用产生式：将产生式左部的非终结符替换为右部的文法符号序列（展开产生式，用标记=>表示），直到得到一个终结符序列终结符序列 [例3.4] 用算术表达式的上下文无关文法产生终结符序列-(id+id)可如下：E → E + E （1） | E * E （2）|（E）（3） | -E（4）| id（5）E => -E (4) => -(E) (3) => -(E+E) (1) => -(id+E) (5) => -(id+id) (5)8 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)定义定义3.2 利用产生式产生句子的过程中，将产生式A→γ的右部代替文法符号序列αAβ中的A得到αγβ的过程，称从αAβ直接直接推导推导出αγβ，记作：αAβ=>αγβ。
若对于任意文法符号序列α1，α2，...αn，均有α1=>α2=>...=>αn，则称此过程为零步零步或多步推导多步推导，记为：α1=>*αn，其中α1=αn的情况为零步推导零步推导若α1≠αn，即推导过程中至少使用一次产生式，则称此过程为至少一步推导至少一步推导，记为：α1=>+αn 两点注意：¯ α，有α=>*α，即推导具有自反性；¯ 若α=>*β，β=>*γ，则α=>*γ，即推导具有传递性9 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)定义定义3.3 由CFG G所产生的语言L(G)被定义为: L(G) = { ω┃S=> + ω and ω∈T* }， L(G)称为上下文无关语言上下文无关语言(Context Free Language, CFL)，ω称为句子句子若S=>α*，α∈(N∪T)*，则称α为G的一个句型句型定义定义3.4 在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导最左推导，由最左推导产生的句型被称为左句型左句型类似可定义最右推导最右推导与右句型右句型，最右推导也被称为规范推导规范推导。
E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) α1α2 α3 α4 α5 α6α6是句子，所有αi (i=1...6)均是句型10 F例 E E + E | E E | (E ) | E | id F最左推导E lm E lm (E) lm (E + E) lm (id + E) lm (id + id)F最右推导（规范推导）E rm E rm (E) rm (E + E) rm (E + id) rm (id + id)3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)11 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)F推导、分析树与语法树推导、分析树与语法树E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) 推导产生句子的方式不直观分析树分析树是推导的图形直观表示图形直观表示，同时反映语言结构的实质和推导过程 定义定义3.5 对CFG G的句型，分析树被定义为具有下述性质的一棵树。
1）根由开始符号所标记； （2）非叶子节点（内部节点）由非终结符标记；（3）叶子由一个终结符或ε标记；（4）若A是某内部节点的标记，且X1，X2，...，Xn是该节点从左到右所有孩子的标记，则A→X1X2...Xn是一个产生式若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子12 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)分析树与语言和文法的关系：F每一直接推导(每个产生式)，对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子；F分析树的节点，从左到右构成G的一个句型若节点仅由终结符标记，则构成一个句子F例 –(id+id) 的分析树EE ()EEE+ididE E + E | E E | (E ) | E | id13 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)[例3.5] 再考察-(id+id)的推导过程E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) 最左推导和最右推导的中间过程对应的分析树可能不同分析树可能不同，但但最终的分析树相同最终的分析树相同，因为最终是同一个句子14 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)分析树既反映了产生句型的推导过程，又反映了句型的结构。
在更多的情况下，仅关注句型结构，而忽略推导过程定义定义3.6 对CFG G的句型，表达式的语法树语法树被定义为具有下述性质的一棵树:（1） 根与内部节点由表达式中的操作符标记；（2） 叶子由表达式中的操作数标记；（3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中语法树与分析树的最根本区别最根本区别在于内部节点（包括根节点）：¯ 分析树的内部节点是非终结符；¯ 语法树的内部节点是操作符（运算符）；¯ 或者说语法树中省略了反映分析过程的非终结符15 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)[例3.6] 句子-(id+id)和句型if C then s1 else s2分析树：左部非终结符“产生”右部文法符号序列；语法树：操作符(运算)作用于操作数(运算对象)；习惯上它们分别被称为具体语法树具体语法树和抽象语法树抽象语法树 16 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)F二义性的存在二义性的存在二义性问题：一个句子可能对应多于一棵分析树[例3.7] 文法G3.2为E→E+E | E*E |（E）| -E | id句子id+id*id和id+id+id可能的分析树有：17 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)定义定义3.7 若文法G对同一句子产生不止一棵分析树，则称G是二二义义的。
原因原因：在产生句子的过程中某些直接推导有多于一种选择注意注意：1.一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关；2.文法中缺少对文法符号优先级和结合性的规定悬空（悬空（dangling））else”问题S → if C then S(1)| if C then S else S(2)| id := E(3)(G3.3)C →E = E | E < E | E > E(4)...(6)E →E + E | - E | id | n(7)...(10)18 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)[例3.8] 条件语句 if x<3 then if x>0 then x:=5 else x:=-5if x<3 then if x>0 then x:=5 else x:=-5else与离它远的与离它远的then匹配匹配if x<3 then if x>0 then x:=5 else x:=-5else与离它近的与离它近的then匹配匹配19 文法具有二义性文法具有二义性文法具有二义性文法具有二义性F在任何一个程序设计语言中，如果出现了二义性，则表示同一段程序在确定的、相同的环境下反复执行，会得到不同的结果，这在程序设计中是不允许的。
F也就是说任何程序设计语言不应该有二义性F文法二义不能说明它所产生的语言一定是二义的F只有当产生一个语言的所有文法都是二义的时候，这个语言才被认为是二义的20 3.2.1 正规式和上下文无关文法的比较（初步思考）F正规式(a|b)*abF文法A0 a A0 | b A0 | a A1A1 b A2A2 12开始开始a0abb3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)21 F为什么要用正规式定义词法 （为什么不用上下文无关文法？）¯词法规则非常简单，不必用上下文无关文法词法规则非常简单，不必用上下文无关文法¯对于词法记号，正规式描述简洁且易于理解对于词法记号，正规式描述简洁且易于理解¯从正规式构造出的词法分析器效率高从正规式构造出的词法分析器效率高3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG)22 本次课内容总结本次课内容总结本次课内容总结本次课内容总结FCFG的定义与表示F推导(最左、最右推导)、句子、句型F分析树，语法树F文法歧义的存在性FCFG与正规式的关系23 作业作业作业作业FP136 3.2, 3.424 。
