编译原理复习四:编译器结构 消除左递归、左公因子 最右推导 寻找句柄讲解(附题目和答案)

简介: 编译原理复习四:编译器结构 消除左递归、左公因子 最右推导 寻找句柄讲解(附题目和答案)

需要原卷和答案请点赞关注收藏后评论区留言私信~~~

下面对编译原理中一些常见的概念以及算法小题的讲解,这部分可能单独出题考试,也有可能混在大题中出现

一、编译器结构

题目如下

The phases of a complier for statement “b=a+i*2” are described in the following figure 1. Please give the meanings of A, B, C, D, E in the Figure 1

一个编译器大体上有以下结构:词法分析-语法分析-语义分析-中间代码生成-中间代码优化-目标代码生成-目标代码优化等步骤

答案如下

A: Scanner

B:

C: Semantic analyzer

D: IR Generation

E: Code generator

二、正则表达式的应用

Alphabet∑={a,b}, write a regular expression that will generates the set of all strings over this alphabet that contain an even number of a’s.

答案如下

R.E.: ((ab*a)|b)*

三、消除左递归与左公因子

Rewrite the following grammar G(S) to remove left recursion and left factor.

A → bAbB | bABb | aB

B → BaA | ab | ba

上面第一条式子中明显有左公因子bA,第二条式子中有左递归B,消除后结果如下

tips:自顶向下分析的LL(1)文法不能分析带有左公因子和左递归的语法,所有要先进行消除

四、为输入串构造左右推导

Consider the following grammar for Boolean expressions:

E→T+E| T-E|T,   T→1|2|3|4|5|6|7|8|9|0

Write a rightmost derivation for the string: 2+3-4

最右推导就是每次替换最右边的非终结符,结果如下

五、找出句型的句柄

来找句柄之前,我们需要介绍以下概念

1:短语 在为输入串构造的语法树中所有子树的叶子节点为短语

2:直接短语  短语中只有父子两代节点,即高度为2的短语

3:句柄 句柄为语法树中最左的直接短语

Given grammar G[E]:

E→E+E | T

T→T*F | F

F→i | (E)

Write out the handle of the sentential form T*F+i

该句型句柄如下

创作不易 觉得有帮助请点赞关注收藏~~~

目录
打赏
0
0
0
0
193
分享
相关文章
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
935 0
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
949 0
手把手带你开发一款云开发版点餐小程序,微信扫码点餐,用户端和后厨端都有
手把手带你开发一款云开发版点餐小程序,微信扫码点餐,用户端和后厨端都有
655 0
基于QT的OCR和opencv融合框架FastOCRLearn实战
本文介绍了在Qt环境下结合OpenCV库构建OCR识别系统的实战方法,通过FastOCRLearn项目,读者可以学习Tesseract OCR的编译配置和在Windows平台下的实践步骤,文章提供了技术资源链接,帮助开发者理解并实现OCR技术。
532 9
基于QT的OCR和opencv融合框架FastOCRLearn实战
最高裁95%,只留5% 用AI的,某上市公司全面ai化。你的岗位,AI入侵指数是 多少?多久消失?
本文探讨了AI对不同岗位的冲击及未来趋势,特别提到上美股份大规模裁员以保留能使用AI的员工。文中分析了Java开发、大数据开发、架构师、产品经理等岗位的AI入侵指数,指出高风险和低风险岗位,并建议进入AI入侵指数低的领域如Java+AI+大数据架构师。此外,文章还介绍了尼恩团队的大模型学习资源和面试指导服务,帮助从业者提升技能,应对AI时代的挑战。
MySQL执行计划深度解析:如何做出最优选择
【10月更文挑战第23天】 在数据库查询性能优化中,执行计划的选择至关重要。MySQL通过查询优化器来生成执行计划,但有时不同的执行计划会导致性能差异。理解如何选择合适的执行计划,以及为什么某些计划更优,对于数据库管理员和开发者来说是一项必备技能。
613 2
使用Kivy创建“Hello World”应用并打包成APK
使用Kivy创建“Hello World”应用并打包成APK
构造LR(0)分析表和SLR(1)分析表
构造LR(0)分析表和SLR(1)分析表
537 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等