需要原卷和答案请点赞关注收藏后评论区留言私信~~~
下面对编译原理中一些常见的概念以及算法小题的讲解，这部分可能单独出题考试，也有可能混在大题中出现
一、编译器结构
题目如下
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
该句型句柄如下
创作不易 觉得有帮助请点赞关注收藏~~~
