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

痛定思痛。 2023-09-30 19:49 11阅读 0赞

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

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

## 一、编译器结构 ##

题目如下

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

![ca39aa5c0e3e4dffb678b2edd3e7fe1a.png][]

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

答案如下

A: Scanner

![3c2806e6c84341db9fbc1acc52975c4f.png][]

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)文法不能分析带有左公因子和左递归的语法，所有要先进行消除*

![e220370db0704e8f8203ae6338ec0228.png][]

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

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*

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

![7d0f970f469f42dc92811a761d626988.png][]

## 五、找出句型的句柄 ##

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

> 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**

**该句型句柄如下**

![4786b26e28bf40499f01f52b32f19997.png][]

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

[ca39aa5c0e3e4dffb678b2edd3e7fe1a.png]: https://img-blog.csdnimg.cn/ca39aa5c0e3e4dffb678b2edd3e7fe1a.png
[3c2806e6c84341db9fbc1acc52975c4f.png]: https://img-blog.csdnimg.cn/3c2806e6c84341db9fbc1acc52975c4f.png
[e220370db0704e8f8203ae6338ec0228.png]: https://img-blog.csdnimg.cn/e220370db0704e8f8203ae6338ec0228.png
[7d0f970f469f42dc92811a761d626988.png]: https://img-blog.csdnimg.cn/7d0f970f469f42dc92811a761d626988.png
[4786b26e28bf40499f01f52b32f19997.png]: https://img-blog.csdnimg.cn/4786b26e28bf40499f01f52b32f19997.png