山东大学2025-2026-2编译原理期末回忆版

计算机学院，郑艳伟老师

小题，每题5分

1. 画图展示编译器原理

2. 后缀式

3. 二义文法

4. 文法 E→E∨T | T ;T→T∧F | F; F→¬F | (E)| i ，句子 a∧¬(b∨c) ，语法树、短语、直接短语、句柄

5. 文法代表什么语言

6. 提取左公因子

7. FA转正规式

大题，每题13分

1. 给定正规式(i|r)v(v,)*

   ①构造NFA；

   ②确定化；

   ③最小化。

2. LL(1)分析，文法

   ①消除左递归；

   ②构造First集合；

   ③构造Follow集合；

   ④构造LL(1)分析表（可能涉及消除二义文法冲突）；

   ⑤识别句子。

3. LR(1)分析，

①拓广文法；

②构造拓广文法的LR(1)项目集规范族；

③构造LR(1)分析表（可能涉及消除二义文法冲突）；

④识别句子。

4. 翻译句子

int m, n; double x, y, z; while (x < y) { z = z + x * y; m = m + 1; } n = 100;

①声明语句填写符号表；

②语句翻译。

5. 给出基本块代码

①构造DAG；

②面向目标代码进行DAG优化，写出结点重排序列，并写出优化后的中间代码；

④根据变量在符号表中的偏移量和给出寄存器，写出目标代码。

（这题很诡异，试卷上的空有11个，但是按照最优解只能填满9个）

这套卷子可能是出得太急了，有两处错误，一个是考场卷子上while后面那个花括号忘记打了，所以有两种翻译方式，都算对了；以及最后一题空有11个，区别在于要不要把不活跃变量存入寄存器，存不存都算对，不存就是9条，存了就是11条