- 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年7月修订).pptx
- 论我国国土防御的重点.pdf
- 我国国土防御要点.pptx
- 鲁教版高中地理选择性必修第一册全册同步教学课件(2025年7月修订).pptx
- 2025年秋新人教版化学九年级上册全册同步课件.pptx
- 2024年秋季学期新冀教版7年级上册英语课件 Unit 3 All about me (第4课时)Lesson 4.pptx
- 2024年秋新湘教版地理7年级上册课件 第2章 认识地球 2.1.2 经纬线 经纬度 经纬网.pptx
- 2024年秋季学期新冀教版7年级上册英语课件 Unit 2 Learning English is fun! (第3课时) Lesson 3.pptx
- 2025年新译林版英语七年级上册全册同步教学课件.pptx
- 2025年秋季苏科版物理九年级上册全册同步课件.pptx
最近下载
- 意大利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)