- 1、本文档共40页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
词法分析器核心算法9
2.4 词法分析器核心算法 2.4.2 DFA的“短路”计算 2.4.2.1正规式的语法树(续1) 2.4.2.1正规式的语法树(续2) 2.4.2.1正规式的语法树(续3) 2.4.2.1正规式的语法树(续4 ) 2.4.2.2 从正规式构造DFA(Short-circuit Construction) 四个函数的具体意义: 2 函数的计算规则 2 函数的计算规则(续) 3 从正规式构造DFA 3 从正规式构造DFA(续1) 3 从正规式构造DFA(续2) 3 从正规式构造DFA(续3) 3 从正规式构造DFA(续4) 3 从正规式构造DFA(续5) 2.5 语法分析器核心算法 2 LL分析与LR分析 2 LL分析与LR分析(续) 2.5.2 LR(1)与LALR(1)分析 结束(3月18日) 2.5.2.1 SLR分析器的弱点 2.5.2.1 SLR分析器的弱点(续) 2.5.2.2 LR(1)分析器 1 LR(1)项目、LR(1)项目集、LR(1)项目集族 2 lookaheads的计算 3 基于LR(1)项目集的、识别活前缀的DFA的构造算法 3 基于LR(1)项目集的、识别活前缀的DFA的构造算法(续1) 4 LR(1)项目集中判定冲突的准则 5 LR(1)DFA的状态膨胀 2.5.2.3 LALR(1)分析器 2 LALR(1)项目集DFA的构造算法 算法2.3 构造LALR(1)DFA 例2.24 2.5.2.4 LR(1)与LALR(1)的关系 2.5.2.4 LR(1)与LALR(1)的关系(续1) 2.5.2.4 LR(1)与LALR(1)的关系(续2) 2.5.2.4 LR(1)与LALR(1)的关系(续3) 2.5.2.4 LR(1)与LALR(1)的关系(续4) 2.5.2.4 LR(1)与LALR(1)的关系(续5) 根据算法2.2计算LR(1)的DFA,然后将芯相同的LR(1)项目集合并为LALR(1)项目集。(弱点是时空复杂度高); 经典“龙书”([Aho 86])方法:首先构造LR(0)DFA,然后根据lookahead的自生和传播性质计算项目的lookaheads,从而得到LALR(1)的DFA; 通过改造LR(0)DFA构造算法直接计算LALR(1)的DFA。 方法3与LR(0)算法的关键区别: 用核心项目ki代表项目集,以节省空间; 用公式2.1的规则计算闭包closure(ki),以加入各项目的lookaheads; 项目的lookaheads改变后,则此项目集被认为是一个新项目集。 输入:拓广文法G={S→S}∪G 输出:DFA=(Dstates, Dtran),其中Dstates中的状态仅由核心项目组成 方法: s0:={S’→.S,$}作为唯一未标记状态加入到Dstates; while Dstates中还有未标记的Ki -- 对每个项目集的核心 loop 标记Ki; I := closure(ki); -- 标记并计算完整的项目集I for I中每个形如[A→α.x,a]项目中的x -- 对每个字符x loop K := goto (I,x); -- 计算下一状态转移 if K非空 -- 若有下一状态转移 then end if; end loop; end loop; if K 不在Dstates中 then -- 若K是新状态 if K的core等于Dstates中某Kj的core then 合并K中lookaheads到Kj中;置Kj为未标记; -- 则合并lookaheads并取消标记 else 加入K到Dstates且未标记; -- 或加入新状态到Dstates end if; end if; Dtran[Ki, x] = K; -- 记录状态转移 为文法G1构造的LALR(1)DFA如下。可以看出此DFA空间很节省,并且I2状态中也不存在移进/归约冲突。 LR(1)与LALR(1)的关系对于移进/归约冲突的解决两者是等价的; 而对于归约/归约冲突,由于LALR(1)项目中合并了lookaheads,可能会减弱它对归约/归约冲突的解决能力。 1 LR(1)DFA中不发生的移进/归约冲突,LALR(1)DFA中也一定不会发生。 考虑下述同心的n个LR(1)项目集的合并: 根据准则2.1,LR(1)DFA中没有冲突,即{a}∩li=Φ(i=1, 2, ..., n),因此:{a}∩(l1∪l2∪... ∪ln)=Φ
您可能关注的文档
- 解一元一次方程合并同类项与移项()执教厦9.ppt
- 解一元一次方程的方法——去分母9.ppt
- 解二元一次方程组--江苏教育版7.ppt
- 解决“四风”问题既要着力治标又要注重治本9.doc
- 解决三农问题地几个关系.doc
- 解决小学生自私地团体心理辅导游戏.doc
- 解决常见光电鼠标故障的小窍门2.doc
- 解剖学 11心血管系统习题2.doc
- 解排列组合问题地十六种常用策略ppt.ppt
- 解放人类地阳光大道ppt.ppt
- 2025至2030年中国电子身份识别器行业投资前景及策略咨询研究报告.docx
- 2025至2030年中国电子实验设备行业投资前景及策略咨询研究报告.docx
- 2025至2030年中国电子文档管理系统行业投资前景及策略咨询报告.docx
- 2025至2030年中国电子硬盘行业投资前景及策略咨询研究报告.docx
- 2025至2030年中国LED用衬底材料行业市场需求分析及发展趋向分析报告.docx
- 2025至2030年中国氨基葡萄糖盐酸盐行业投资前景及策略咨询研究报告.docx
- 2025年一级建造师培训建设工程项目管理考点总结8854392902整理By阿拉蕾.doc
- 2025至2030年中国钢桶烘干生产线行业投资前景及策略咨询研究报告.docx
- 2025至2030年中国存储卡行业市场运行状况及发展前景展望报告.docx
- 2025至2030年中国甘草甜素行业投资前景及策略咨询研究报告.docx
最近下载
- 人教版(2019)高中地理选择性必修1第三章第1节常见的天气系统——锋与天气.pptx VIP
- HG-T 3732-2004 改性酚醛玻璃纤维增强塑料球阀技术条件.pdf VIP
- (选调)农村教师进城选调考试试卷及答案.docx VIP
- 首都医科大学2015毕业生就业质量报告电子版20160104.pdf VIP
- (教师选调进城考试题库)农村教师进城考试题库.docx VIP
- (高清版)T-D-T 1087-2023 主体功能区优化完善技术指南.pdf VIP
- 2025年陕西榆林市榆神煤炭榆树湾煤矿有限公司招聘笔试参考题库附带答案详解.pdf
- (教师选调进城考试练习题库)农村教师进城考试练习题库.docx VIP
- 人教版高中地理选择性必修第1册 锋与天气-常见天气系统.ppt VIP
- 重庆特顺电子有限公司单层印制电路板生产项目环评报告.docx VIP
文档评论(0)