山东大学2025-2026-2编译原理期末回忆版
计算机学院，郑艳伟老师
小题，每题5分
画图展示编译器原理
后缀式
二义文法
文法 E→E∨T | T ;T→T∧F | F; F→¬F | (E)| i ，句子 a∧¬(b∨c) ，语法树、短语、直接短语、句柄
文法代表什么语言
提取左公因子
FA转正规式
大题，每题13分
给定正规式(i|r)v(v,)*
①构造NFA；
②确定化；
③最小化。
LL(1)分析，文法
①消除左递归；
②构造First集合；
③构造Follow集合；
④构造LL(1)分析表（可能涉及消除二义文法冲突）；
⑤识别句子。
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条
