上次章节内容回顾ppt课件.ppt
24页
上次上次上次上次课课内容回想内容回想内容回想内容回想语法分析简介：语法分析简介：词法分析：字母是元素，组成字符串词法分析：字母是元素，组成字符串(记号记号)语法分析：记号是元素，组成句子语法分析：记号是元素，组成句子语法分析的作用：语法分析的作用：1：识别句子：识别句子2：语法错误：语法错误 正规式能定义一些简单的言语，能表示给定构造的固定次数的反复或者没有指定次数的反复例：a (ba)5, a (ba)*正规式不能用于描画配对或嵌套的构造例1：配对括号串的集合例2：{wcw | w是a和b的串} 3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG) 3.2 上下文无关文法上下文无关文法(CFG)FCFG的定的定义与表示与表示F上下文无关文法，上下文无关文法，Context Free Grammar，，CFGF定定义3.1 CFG是一个四元是一个四元组：：FG =〔〔N，，T，，P，，S〕，其中〕，其中F〔〔1〕〕 N是非是非终结符〔符〔Nonterminals〕的有限集合；〕的有限集合；F〔〔2〕〕 T是是终结符〔符〔Terminals〕的有限集合，且〕的有限集合，且N∩T=Φ；；F〔〔3〕〕 P是是产生式〔生式〔Productions〕的有限集合，形〕的有限集合，形如：如：FA→α，其中，其中A∈∈N〔左部〕，〔左部〕，α∈∈(N∪∪T)*〔〔右部〕，右部〕，F假假设α=ε，那么称，那么称A→ε为空空产生式〔也可以生式〔也可以记为A →〕；〕；F〔〔4〕〕 S(非非终结符符)称称为文法的开文法的开场符号〔符号〔Start symbol〕。
〕 3.2 上下文无关文法上下文无关文法(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〕 产生式的普通读法记号 → 读作“定义为〞或者“可导出〞 “E → E + E〞 表述为“算术表达式定义为两个算术表达式相加〞；或者“一个算术表达式加上另一个算术表达式，依然是一个算术表达式〞 3.2 上下文无关文法上下文无关文法(CFG) 2.产生式表示也被称为巴克斯范式〔Backus-Naur Form，BNF〕，其中→用::=表示 E ::=E + E | E * E | (E) | -E | id 3.2 上下文无关文法上下文无关文法(CFG)3.终结符与非终结符书写上的区分(a) 用大小写区分： E → id(b) 用" "区分： E → "id" E → E "+" E(c) 用< >区分：
新的产生式的左部是此非终结符，右部是一切原来右部的或运算〔并集合〕6.[例3.3] G3.1可以重写为如下方式：7.E → E + E 〔1〕8.| E * E〔2〕9.|〔E〕〔3〕10.| -E〔4〕11.| id〔5〕12.用“|〞衔接的每个右部称为一个候选项，具有平等的权益13.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开开场，，对产生式左部的非生式左部的非终结符反复地运用符反复地运用产生式：将生式：将产生式生式左部的非左部的非终结符交符交换为右部的文法符号序列〔展开右部的文法符号序列〔展开产生生式，用式，用标志志=>表示〕，直到得到一个表示〕，直到得到一个终结符序列 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)定定义3.2 利用利用产生式生式产生句子的生句子的过程中，将程中，将产生式生式A→γ的右部的右部替代文法符号序列替代文法符号序列αAβ中的中的A得到得到αγβ的的过程，称从程，称从αAβ直接直接推推导出出αγβ，，记作：作：αAβ=>αγβ。
假假设对于恣意文法符号序列于恣意文法符号序列α1，，α2，，...αn，均有，均有α1=>α2=>...=>αn，那么称此，那么称此过程程为零步或多步推零步或多步推导，，记为：：α1=>*αn，其中，其中α1=αn的情况的情况为零步推零步推导假假设α1≠αn，即推，即推导过程中至少运用一次程中至少运用一次产生式，那么称此生式，那么称此过程程为至少一步推至少一步推导，，记为：：α1=>+αn 两点留意：两点留意： α，有，有α=>*α，即推，即推导具有自反性；具有自反性； 假假设α=>*β，，β=>*γ，那么，那么α=>*γ，即推，即推导具有具有传送性 3.2 上下文无关文法上下文无关文法(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)均是句型均是句型 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 E rm (E) rm (E + E)F rm (E + id) rm (id + id)3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG) 3.2 上下文无关文法上下文无关文法(CFG)F推推导、分析、分析树与与语法法树FE => -E => -(E) => -(E+E) => -(id+E) => -E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) (id+id) F推推导产生句子的方式不直生句子的方式不直观。
分析分析树是推是推导的的图形直形直观表示，同表示，同时反映言反映言语构造的本构造的本质和推和推导过程 F定定义3.5 3.5 对CFG GCFG G的句型，分析的句型，分析树被定被定义为具有下述性具有下述性质的一棵的一棵树F〔〔1 1〕根由开〕根由开场符号所符号所标志；志；F 〔〔2 2〕非叶子〕非叶子节点〔内部点〔内部节点〕由非点〕由非终结符符标志；志；F〔〔3 3〕叶子由一个〕叶子由一个终结符或符或εε标志；志；F〔〔4 4〕假〕假设A A是某内部是某内部节点的点的标志，且志，且X1X1，，X2X2，，......，，XnXn是是该节点从左到右一切孩子的点从左到右一切孩子的标志，那么志，那么A→X1X2...XnA→X1X2...Xn是一个是一个产生式假设A→εA→ε，那么，那么标志志为A A的的结点可以点可以仅有一个有一个标志志为εε的孩子 3.2 上下文无关文法上下文无关文法(CFG)分析树与言语和文法的关系：每不断接推导(每个产生式)，对应一棵仅有父子关系的子树，即产生式左部非终结符“长出〞右部的孩子；分析树的节点，从左到右构成G的一个句型假设节点仅由终结符标志，那么构成一个句子。
F例 –(id+id) 的分析树EE ()EEE+ididE E + E | E E | (E ) | E | id 3.2 上下文无关文法上下文无关文法(CFG)[例3.5] 再调查-(id+id)的推导过程E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) 最左推导和最右推导的中间过程对应的分析树能够不同，但最终的分析树一样，由于最终是同一个句子 3.2 上下文无关文法上下文无关文法(CFG)分析树既反映了产生句型的推导过程，又反映了句型的构造在更多的情况下，仅关注句型构造，而忽略推导过程定义3.6 对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树:〔1〕 根与内部节点由表达式中的操作符标志；〔2〕 叶子由表达式中的操作数标志；〔3〕用于改动运算优先级和结合性的括弧，被隐含在语法树的构造中语法树与分析树的最根本区别在于内部节点〔包括根节点〕： 分析树的内部节点是非终结符； 语法树的内部节点是操作符〔运算符〕； 或者说语法树中省略了反映分析过程的非终结符 3.2 上下文无关文法上下文无关文法(CFG)[例3.6] 句子-(id+id)和句型if C then s1 else s2分析树：左部非终结符“产生〞右部文法符号序列；语法树：操作符(运算)作用于操作数(运算对象)；习惯上它们分别被称为详细语法树和笼统语法树。
3.2 上下文无关文法上下文无关文法(CFG)F二二义性的存在性的存在F二二义性性问题：一个句子能：一个句子能够对应多于一棵分析多于一棵分析树F[例例3.7] 文法文法G3.2为E→E+E | E*E |〔〔E〕〕| -E | idF句子句子id+id*id和和id+id+id能能够的分析的分析树有：有： 3.2 上下文无关文法上下文无关文法(CFG)定定义3.7 假假设文法文法G对同一句子同一句子产生不止一棵分析生不止一棵分析树，那么称，那么称G是二是二义的 缘由：在由：在产生句子的生句子的过程中某些直接推程中某些直接推导有多于一种有多于一种选择留意：留意：一个句子有多于一棵分析一个句子有多于一棵分析树，，仅与文法和句子有关，与采用的与文法和句子有关，与采用的推推导方法无关；方法无关；文法中短少文法中短少对文法符号文法符号优先先级和和结合性的合性的规定悬空〔空〔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) 3.2 上下文无关文法上下文无关文法(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匹配 文法具有二义性文法具有二义性F在任何一个程序设计言语中，假设出现了二义性，那么表示同一段程序在确定的、一样的环境下反复执行，会得到不同的结果，这在程序设计中是不允许的。
F也就是说任何程序设计言语不应该有二义性F文法二义不能阐明它所产生的言语一定是二义的F只需当产生一个言语的一切文法都是二义的时候，这个言语才被以为是二义的 3.2.1 正规式和上下文无关文法的比较〔初步思索〕正规式(a|b)*ab文法A0 a A0 | b A0 | a A1A1 b A2A2 12开场开场a0abb3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG) 为什么要用正规式定义词法 〔为什么不用上下文无关文法？〕词法规那么非常简单，不用用上下文无关文法对于词法记号，正规式描画简约且易于了解从正规式构造出的词法分析器效率高3.2 3.2 上下文无关文法上下文无关文法上下文无关文法上下文无关文法(CFG)(CFG) 本次课内容总结本次课内容总结CFG的定义与表示推导(最左、最右推导)、句子、句型分析树，语法树文法歧义的存在性CFG与正规式的关系 作业作业FP 3.2, 3.4 。
