语法分析-自底向上分析-编译原理-05-(二)课件
71页1、第五章 语法分析自底向上分析,5.1基本问题 方法 从句子出发,反复利用产生式做归约 (用产生式的左部替代右部),逐步构造语法分析树,最后得到文法的开始符号 核心 寻找句型与句柄的匹配,分析方法,例 5-1: S a A c B e A A bb B d 分析过程: abbcde aAbcde aAcde aAcBe S,语法分析树的生成,a b b c d e,A,A,B,S,A b,A A b,B d,S a A c B e,句柄:最左直接短语,短语: 设文法T,N, 若 =* 且 =+ , 则称是句型相对于非终结符的短语 若=* 且=,则称是直接短语。,规范归约的定义,设 为文法 G 的句子,称序列 n,.,1,0 为 的规范归约,其中 1) n = 2) 0 = (开始符号) 3) 对每个 i (1 = i = n),i-1 是将i 中的句柄归约后得到的,规范归约,规范归约是规范推导(最右推导)的逆过程 中心问题是如何寻找和确定一个句型中的句柄 各种自底向上分析采用不同的方法确定句柄,移进归约分析器,id id #, #,移进归约 控制程序,产生式序列,栈内容 + 输入缓冲区内
2、容 # 句型 #,栈,输入缓冲区,分析器的四种动作,1) 移进:将下一输入符号移入栈 2) 归约:用产生式左侧的非终结符替换栈顶的句柄 3) 接受:分析成功 4) 出错:出错处理 各种自底向上分析方法的控制方法不同,例5-2:id+id*id 的分析,动作 栈 输入缓冲区 1) # id1+id2*id3# 2) 移进 #id1 +id2*id3# 3) 归约 Eid #E +id2*id3# 4) 移进 #E+ id2*id3# 5) 移进 #E+id2 *id3# 6) 归约 Eid #E+E *id3# 7) 移进 #E+E* id3# 8) 移进 #E+E*id3 # 9) 归约 Eid #E+E*E # 10) 归约 EE*E #E+E # 11) 归约 EE+E #E # 12) 接受,产生式序列表示语法分析树,E id E id E id E E * E E E + E,id + id * id,E,E,E,E,E,移进归约分析中的冲突,文法复杂时出现: 1) 移进归约冲突 例中的 6) 可以移进 id 或 归约 EE+E 2) 归约归约冲突 存在两个可用的产生式 各种分
3、析方法处理冲突的方法不同,5.2 算符优先分析,方法: 利用终结符之间的优先关系确定句柄。 算符优先关系的定义 (终结符之间) a b a 的优先级低于 b a b a 的优先级等于 b a b a 的优先级高于 b,算符优先文法,如果文法 中不存在具有相邻非终结符的产生式,则称为算符文法。 如果无产生式的算符文法 中,且任意两个终结符之间至多有一种优先关系,则称为算符优先文法。 算符优先分析仅适用于算符优先文法。,例5-3:表达式文法的算符优先关系,E E + E E - E E * E E / E E E ( E ) id,存在优先级 + * + id +id * + id* id id # id,算符优先关系的使用,分析例:id + id * id 在输入符号串中插入优先符,形成一组以 为左端,以为中缀,以为右端的短语。 # id + id * id # 对短语进行归约后再次插入优先符 # E + E * E # # E + E # # E #,算符优先分析的实现,组成结构 移进归约分析器 + 优先关系表 工作框架 输入、输出、初态、终态不变 分析算法 P93 参照输入串、优先关
4、系表,完成一组产生式归约,产生语法分析树。,id+id*id 的分析过程,id + id * id #,算符优先分析 控制器,E id,E id,E id,E E * E,E E + E,算符优先关系表,#,id #,E #,+ E #,id + E #,E + E #,* E + E #,id * E + E #,E * E + E #,E + E #,E #,算符优先关系表的构造,对于任何符号 X 和 Y: 若 X 的运算优先级高于 Y, 则设 X Y 和 Y X 若 X 和 Y 运算优先级相同, 且具有左结合性,则设 X Y 和 Y X; 否则设 X Y 和 Y X 设 X id, id X, X (, ( X, ) X, X ),( ), X # 和 # X,算符优先分析小结,优点 简单、效率高 能够处理部分二义性文法 缺点 文法书写限制大 占用内存空间大 不规范、存在查不到的语法错误,习题:,P133 2. (2) 补充题 给出布尔表达式的文法 bexpr bexpr OR bexpr bexpr bexpr AND bexpr bexpr NOT bexpr bexpr (
《语法分析-自底向上分析-编译原理-05-(二)课件》由会员我***分享,可在线阅读,更多相关《语法分析-自底向上分析-编译原理-05-(二)课件》请在金锄头文库上搜索。
2020届中考英语备考复习-作文课件
2019年中考英语复习-专题十五-交际运用(试卷部分)课件
2019届二轮复习-高中英语-情态动词和虚拟语气课件
2019届一轮复习苏教版物质的跨膜运输课件
2019年北师大版英语单元复习课件::Unit17Laughter课件北师大版选修6
2021届新中考物理冲刺备考复习-力-弹力-重力课件
2019届一轮复习人教版种群的特征和数量变化课件
2020年高考地理一轮复习--等高线地形图-课件
2019版高考英语一轮复习-Unit-1-Living-well课件
2019届一轮复习人教版孟德尔的遗传定律——基因分离定律课件
2019届高三第二轮复习专题二万有引力定律及其应用课件
2020最新部编版语文五年级上册23-鸟的天堂课件含课后练习
2020版高考(浙江)一轮复习:第7讲-细胞呼吸课件
2020年新教材高中英语UNIT4HISTORYANDTRADITIONSSectionⅢDiscoveringUsefulStructures课件必修第二册
2019届高考历史二轮复习阶段三专题十三罗斯福新政与当代资本主义的新变化课件2
2019版高考生物二轮复习-专题三-细胞的生命历程-考点9-细胞分裂过程图像和坐标曲线的识别课件
(通史版)2021版高考历史一轮复习第4部分高考讲座(三)2高考非选择题(12分开放探究题)规范答题讲练课件
2019届高三地理复习第五讲--《区际联系与区域协调发展》课件
2021人教部编版历史九年级上册习题课件:第18课美国的独立
2020学年新教材高中英语Unit1FoodforthoughtPeriodTwoStartingout课件
2024-04-18 25页
2024-04-18 29页
2024-04-18 38页
2024-04-18 16页
2024-04-09 21页
2024-04-09 26页
2024-04-09 28页
2024-04-09 19页
2024-04-09 26页
2024-04-09 23页