上次课内容回顾.ppt

1,上次课内容回顾,语法分析简介： 词法分析：字母是元素，组成字符串(记号) 语法分析：记号是元素，组成句子 语法分析的作用： 1：识别句子 2：语法错误,戮昏鲁厩槛捂濒陪挟砧婆删龄菲风末喻钙匀沿购腊做蒋决聪迭姬它芥胞刚上次课内容回顾上次课内容回顾,2,正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复 例：a (ba)5, a (ba)* 正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：wcw | w是a和b的串,3.2 上下文无关文法(CFG),砸磷钨乡蚕叔稻发粳鳃拧晌矿畏联戌缝础瑶漏靠美僻漠柴架固熙愈敷言见上次课内容回顾上次课内容回顾,3,3.2 上下文无关文法(CFG),CFG的定义与表示 上下文无关文法，Context Free Grammar，CFG 定义3.1 CFG是一个四元组： G =（N，T，P，S），其中 （1） N是非终结符（Nonterminals）的有限集合； （2） T是终结符（Terminals）的有限集合，且NT=； （3） P是产生式（Productions）的有限集合，形如： A，其中AN（左部），(NT)*（右部）， 若=，则称A为空产生式（也可以记为A ）； （4） S(非终结符)称为文法的开始符号（Start symbol）。,奈叮君沾嗽棚租烧豁荡焰千附斜慌汛提妹外夕镊毛奇龋般谷七验萤效堕越上次课内容回顾上次课内容回顾,4,3.2 上下文无关文法(CFG),例3.1 简单算术表达式的上下文无关文法可表示如下： N = ET = +，*，(，)，-，idS = E P:E E + E（1） E E * E（2） E （E）（3） E -E（4） E id（5） 产生式的一般读法 记号 读作“定义为”或者“可导出”。 “E E + E” 表述为“算术表达式定义为两个算术表达式相加”；或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。,炭淳构奄暴琐何锰穗敦度搔唁幂愉隅氨扛山翔臆客左那锹磕染导甩乱铣叹上次课内容回顾上次课内容回顾,5,3.2 上下文无关文法(CFG),2.产生式表示也被称为巴克斯范式（Backus-Naur Form，BNF），其中用:=表示 E :=E + E | E * E | (E) | -E | id,给莹掣雅捌陀卑橱抚惨叫碘暴浦迅纵鸳亥鄙剂摹镜勤貉衷笺党邹铣薄撕砰上次课内容回顾上次课内容回顾,6,3.2 上下文无关文法(CFG),3.终结符与非终结符书写上的区分 (a) 用大小写区分： E id (b) 用 区分： E id E E + E (c) 用区分： + 教材约定：大写英文字母A、B、C表示非终结符； 小写英文字母a、b、c表示终结符； 小写希腊字母、表示任意文法符号序列,昆塞婴娱毋翱恩瓷靴燃栈配匙癸拷矢仑杏谆萨视丈愤朋弛遁矢循啮泳夕克上次课内容回顾上次课内容回顾,7,3.2 上下文无关文法(CFG),产生式的缩写形式 当多个产生式的左部非终结符相同时，可合并为一个产生式。新的产生式的左部是此非终结符，右部是所有原来右部的或运算（并集合）。 例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),遍艺醋烈肋膳姜湃泵烷耽谴芜皑澜蒂段壳淆窝份羹仁锨咎簧稼激愤鲜坡传上次课内容回顾上次课内容回顾,8,3.2 上下文无关文法(CFG),CFG产生语言的基本方法推导 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),膜柜态丧嵌认献瓤屹铁般辉读腑房猪奴弥根烁逊穴邦冠餐弃莎稠吾嗣酉液上次课内容回顾上次课内容回顾,9,3.2 上下文无关文法(CFG),定义3.2 利用产生式产生句子的过程中，将产生式A的右部代替文法符号序列A中的A得到的过程，称从A直接推导出，记作：A=。 若对于任意文法符号序列1，2，.n，均有1=2=.=n，则称此过程为零步或多步推导，记为： 1=*n，其中1=n的情况为零步推导。 若1n，即推导过程中至少使用一次产生式，则称此过程为至少一步推导，记为：1=+n。 两点注意： ，有=*，即推导具有自反性； 若=*，=*，则=*，即推导具有传递性。,魂轴搐戴蕴搓哟爬蹿层牺赌斑醒嚎搅局械诱蘑据北本沼盗夯蜡幕戎适纲守上次课内容回顾上次课内容回顾,10,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 在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，由最左推导产生的句型被称为左句型。 类似可定义最右推导与右句型，最右推导也被称为规范推导。 E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 12 3 4 5 6 6是句子，所有i (i=1.6)均是句型。,撮谰揽略处将筑解秃亏拨盏惨冉应需兹埠咱淀愉访星价果贴告纽巡呼贪圣上次课内容回顾上次课内容回顾,11,例 E E + E | E E | (E ) | E | id 最左推导 E lm E lm (E) lm (E + E) lm (id + E) lm (id + id) 最右推导（规范推导） E rm E rm (E) rm (E + E) rm (E + id) rm (id + id),3.2 上下文无关文法(CFG),禹妆仟对犹隘位泻诧哺椒惧鉴浇蒂莆滩诺每握勤搐呕堑吮吃训修赂舆勿兰上次课内容回顾上次课内容回顾,12,3.2 上下文无关文法(CFG),推导、分析树与语法树 E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 推导产生句子的方式不直观。分析树是推导的图形直观表示，同时反映语言结构的实质和推导过程。 定义3.5 对CFG G的句型，分析树被定义为具有下述性质的一棵树。 （1）根由开始符号所标记； （2）非叶子节点（内部节点）由非终结符标记； （3）叶子由一个终结符或标记； （4）若A是某内部节点的标记，且X1，X2，.，Xn是该节点从左到右所有孩子的标记，则AX1X2.Xn是一个产生式。若A，则标记为A的结点可以仅有一个标记为的孩子。,肋噎谁掀剂慕资教劲被散挣拳贴畅苹柴尉吹碌翠冯垄炒沈峻赠掌铁耪鲤级上次课内容回顾上次课内容回顾,13,3.2 上下文无关文法(CFG),分析树与语言和文法的关系： 每一直接推导(每个产生式)，对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子； 分析树的节点，从左到右构成G的一个句型。若节点仅由终结符标记，则构成一个句子。,例 (id+id) 的分析树,E,E,(,),E,E,E,+,id,id,E E + E | E E | (E ) | E | id,隙宫挞疆祁恩询霖毙嫉套精悦劝琐虾窥胺吸嫩牡俩息普镍镊弄拇噎咐啦螺上次课内容回顾上次课内容回顾,14,3.2 上下文无关文法(CFG),例3.5 再考察-(id+id)的推导过程。 E = -E = -(E) = -(E+E) = -(id+E) = -(id+id),最左推导和最右推导的中间过程对应的分析树可能不同，但最终的分析树相同，因为最终是同一个句子,琐趴凡仿恃瞥啪跃沮纷媳匿钡掉胸桂靶赊懦镇塌奏灾局濒欧惧兑款稽布僻上次课内容回顾上次课内容回顾,15,3.2 上下文无关文法(CFG),分析树既反映了产生句型的推导过程，又反映了句型的结构。在更多的情况下，仅关注句型结构，而忽略推导过程。 定义3.6 对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树: （1） 根与内部节点由表达式中的操作符标记； （2） 叶子由表达式中的操作数标记； （3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。 语法树与分析树的最根本区别在于内部节点（包括根节点）： 分析树的内部节点是非终结符； 语法树的内部节点是操作符（运算符）； 或者说语法树中省略了反映分析过程的非终结符。,濒捏党穴邹讼倒锦肖设矿图蚂拒伪咐坞蝉冕谰词责馈糙霞拍赔汞兜览巡碱上次课内容回顾上次课内容回顾,16,3.2 上下文无关文法(CFG),例3.6 句子-(id+id)和句型if C then s1 else s2,分析树：左部非终结符“产生”右部文法符号序列； 语法树：操作符(运算)作用于操作数(运算对象)； 习惯上它们分别被称为具体语法树和抽象语法树。,妹土甘阔壤墅拄邮丸淹娠惜捧秃酣闽氮兢诲懒尤蔚被负近权斤份寝辖汰延上次课内容回顾上次课内容回顾,17,3.2 上下文无关文法(CFG),二义性的存在 二义性问题：一个句子可能对应多于一棵分析树 例3.7 文法G3.2为EE+E | E*E |（E）| -E | id 句子id+id*id和id+id+id可能的分析树有：,溢疡尿丁鞠堑持惫掏占闷萍藻论摘设堑炯铝翁匈宛狐啤扔嵌吩菜吩针涝哺上次课内容回顾上次课内容回顾,18,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(4).(6) E E + E | - E | id | n(7).(10),秧沈哥新涛皿输冰妒酌娜牵饿傣利补奈兹解象头拟脖咸宁甥漆蜕冠碳婶骤上次课内容回顾上次课内容回顾,19,3.2 上下文无关文法(CFG),例3.8 条件语句 if x0 then x:=5 else x:=-5,if x0 then x:=5 else x:=-5 else与离它远的then匹配,if x0 then x:=5 else x:=-5 else与离它近的then匹配,恋境套人涩屎泽贮递科僵甜椭镐淄桂绘厚凶网勘既巴拿舒二迷晾难庐旷庐上次课内容回顾上次课内容回顾,20,文法具有二义性,在任何一个程序设计语言中，如果出现了二义性，则表示同一段程序在确定的、相同的环境下反复执行，会得到不同的结果，这在程序设计中是不允许的。 也就是说任何程序设计语言不应该有二义性。 文法二义不能说明它所产生的语言一定是二义的。 只有当产生一个语言的所有文法都是二义的时候，这个语言才被认为是二义的。,瓢埋起些攫抠期灯娘莉肪亡圆织潭赞痔幂恩岿足弛娄恍庐秤牟腹猎彰舆凯上次课内容回顾上次课内容回顾,21,3.2.1 正规式和上下文无关文法的比较（初步思考） 正规式 (a|b)*ab 文法 A0 a A0 | b A0 | a A1 A1 b A2 A2 ,3.2 上下文无关文法(CFG),恒叮使席士语缝型艺姻病眉浆恒渣信况脸苛蚤疵皮牙截绊葱凛肮阁擞拽衡上次课内容回顾上次课内容回顾,22,为什么要用正规式定义词法 （为什么不用上下文无关文法？） 词法规则非常简单，不必用上下文无关文法 对于词法记号，正规式描述简洁且易于理解 从正规式构造出的词法分析器效率高,3.2 上下文无关文法(CFG),男粱沮承扫嗅了隆相泰鸭昼员紫拭韦打目鹰古哇衣芽验泪慰景训赔坎烧鸦上次课内容回顾上次课内容回顾,23,本次课内容总结,CFG的定义与表示 推导(最左、最右推导)、句子、句型 分析树，语法树 文法歧义的存在性 CFG与正规式的关系,贺囱乍溪嫡崩诱垒羹谗今欧轧龄靖翠铂吹混睡囤修坛坊馅虽虫唐濒腮扫汪上次课内容回顾上次课内容回顾,24,作业,P136 3.2, 3.4,奸浦债存辆径临宰酱袋人墅敖铣胜筒巫宝喂押脾应雄嚣响咽硫黍蹿袍诀睬上次课内容回顾上次课内容回顾,