- 1、本文档共71页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
语法分析自底向上分析.ppt
第五章 语法分析——自底向上分析 5.1 基本问题 方法 从句子出发,反复利用产生式做归约 (用产生式的左部替代右部),逐步构造语法分析树,最后得到文法的开始符号 核心 寻找句型与句柄的匹配 分析方法 例 5-1: S → a A c B e A → A b|b B → d 分析过程: abbcde → aAbcde → aAcde → aAcBe → S 语法分析树的生成 a b b c d e 句柄:最左直接短语 短语: 设文法G={VT,VN,P,S} 若 S =* αAδ 且 A =+ β, 则称β是句型αβδ相对于非终结符A的短语 若S=*αAδ 且A=β,则称β是直接短语。 规范归约的定义 设 α为文法 G 的句子,称序列 αn,...,α1,α0 为 α的规范归约,其中 1) αn = α 2) α0 = S (开始符号) 3) 对每个 i (1 = i = n),αi-1 是将αi 中的句柄归约后得到的 规范归约 规范归约是规范推导(最右推导)的逆过程 中心问题是如何寻找和确定一个句型中的句柄 各种自底向上分析采用不同的方法确定句柄 移进归约分析器 分析器的四种动作 1) 移进:将下一输入符号移入栈 2) 归约:用产生式左侧的非终结符替换栈顶的句柄 3) 接受:分析成功 4) 出错:出错处理 各种自底向上分析方法的控制方法不同 例5-2:id+id*id 的分析 动作 栈 输入缓冲区 1) # id1+id2*id3# 2) 移进 #id1 +id2*id3# 3) 归约 E→id #E +id2*id3# 4) 移进 #E+ id2*id3# 5) 移进 #E+id2 *id3# 6) 归约 E→id #E+E *id3# 7) 移进 #E+E* id3# 8) 移进 #E+E*id3 # 9) 归约 E→id #E+E*E # 10) 归约 E→E*E #E+E # 11) 归约 E→E+E #E # 12) 接受 产生式序列表示语法分析树 E → id E → id E → id E → E * E E → E + E 移进归约分析中的冲突 文法复杂时出现: 1) 移进归约冲突 例中的 6) 可以移进 id 或 归约 E→E+E 2) 归约归约冲突 存在两个可用的产生式 各种分析方法处理冲突的方法不同 5.2 算符优先分析 方法: 利用终结符之间的优先关系确定句柄。 算符优先关系的定义 (终结符之间) a ≮ b a 的优先级低于 b a ≡ b a 的优先级等于 b a ≯ b a 的优先级高于 b 算符优先文法 如果文法 G 中不存在具有相邻非终结符的产生式,则称为算符文法。 如果无ε产生式的算符文法 G中,且任意两个终结符之间至多有一种优先关系,则称为算符优先文法。 算符优先分析仅适用于算符优先文法。 例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 参照输入串、优先关系表,完成一组产生式归约,产生语法分析树。 id+id*id 的分析过程 算符优先关系表的构造 对于任何符号 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,
您可能关注的文档
最近下载
- 意大利cemb(赛博)er60动平衡仪中文操作手册.pdf VIP
- 粮油供货保障方案.docx VIP
- 负压引流器产品技术要求标准2023版.pdf VIP
- 初中英语课外阅读黑布林版渔夫和他的灵魂中文译文.docx VIP
- Oasis montaj7.5 操作手册-Oasis montaj Mapping and Processing软件平台.pdf VIP
- 机械精度设计与检测技术基础第2版杨沿平第七章滚动轴承配合1课件教学.ppt VIP
- 云南省昆明市盘龙区2023-2024学年七年级上学期期末英语试卷.pdf VIP
- 硬膜下血肿的护理常规.pptx
- 2020年牛津译林版7A英语七年级上册Unit2-单元检测卷(含答案).docx VIP
- 机械精度设计与检测技术基础第2版杨沿平第八章键与花键连接1课件教学.ppt VIP
文档评论(0)