189 8069 5689
涵盖所有考点，复习绝对高效，点赞+留邮箱获取pdf版本
如果从开始符号依次推导出 A1A2A3，则按其逆序排序时得到的产生式最少。
3. 消除回溯
通过反复提取左公因子可以消除回溯。
4. 提左公因子
5. 后缀表达式中缀转后缀算法：
初始化符号栈，顺序读取中缀表达式，遇到(则将其入栈，遇到)则依次弹出栈顶元素到结果串中，直到遇到(，将其出栈但不附加到结果串；
遇到+-，弹出栈顶的所有操作符，附加到结果串中，然后自己进栈；
遇到*/，先让栈顶的*/出栈，附加到结果串中，然后自己进栈；
遇到数字，直接附加到结果串中；
最后若符号栈非空，将符号栈栈顶元素依次附加到结果串中。
// 中缀转后缀
vectorinterToPost(vectorvec)
{
vectorres;
stackop_stack;
for (int i = 0; i< vec.size(); i++) {
if (vec[i] == "(")
op_stack.push(vec[i]);
else if (vec[i] == ")") {
while (op_stack.top() != "(") {
res.push_back(op_stack.top());
op_stack.pop();
}
// 左括号出栈
op_stack.pop();
}
// 遇到+-，先让栈中的+-*/出栈
else if (vec[i] == "+" || vec[i] == "-") {
while (!op_stack.empty() && op_stack.top() != "(") {
res.push_back(op_stack.top());
op_stack.pop();
}
op_stack.push(vec[i]);
}
// 遇到*/，先让栈中的*/出栈
else if (vec[i] == "*" || vec[i] == "/") {
while (!op_stack.empty() && (op_stack.top() == "*" || op_stack.top() == "/")) {
res.push_back(op_stack.top());
op_stack.pop();
}
op_stack.push(vec[i]);
}
else
res.push_back(vec[i]);
}
while (!op_stack.empty()) {
res.push_back(op_stack.top());
op_stack.pop();
}
return res;
} 计算后缀表达式：
初始化数据栈，顺序读取后缀表达式，遇到操作符op则将栈次顶元素op栈顶元素，弹出操作数并压入运算结果；
遇到数据，则直接压入栈顶；
最终栈顶元素就是结果。
// 计算后缀表达式
double solvePostPrefix(vectorpost_prefix) {
stackdataStack;
double num1, num2, result;
for (auto x : post_prefix) {
if (x == "+" || x == "-" || x == "*" || x == "/") {
num1 = dataStack.top();
dataStack.pop();
num2 = dataStack.top();
dataStack.pop();
if (x == "+")
result = num2 + num1;
if (x == "-")
result = num2 - num1;
if (x == "*")
result = num2 * num1;
if (x == "/")
result = num2 / num1;
dataStack.push(result);
}
else {
double num = strToDouble(x);
dataStack.push(num);
}
}
return dataStack.top();
} 是一种含义明确、便于处理的记号系统，通常独立于具体的硬件但与指令形式有某种程度的接近，或者能够比较容易的转换为机器指令，常见的形式有：
把中间代码变换为特定机器上的低级语言代码，产生出足以发挥硬件效率的目标代码是一件非常不容易的事情。常见的形式有：
汇编指令代码：需要汇编才能执行；
绝对指令代码：可以立即执行；
可重定位指令代码：运行前必须借助于一个链接装配程序，把各个目标模块（包括系统提供的库模块）连接在一起，确定程序装入内存中的起始地址，使之成为一个可以运行的绝对指令代码程序。
强制式语言：面向底层和语句，每个语句的执行引起若干存储单元中值的改变；
应用式语言：更注重程序所表示的功能，每条语句都封装了复杂的功能；
基于规则的语言：检查一定的条件，当它满足值，则执行适当的动作；
面向对象的语言：主要特征是封装性、继承性、多态性。
用 Σ*表示 Σ 上所有符号串的全体，空字 ε 也在其中，称为 Σ 的闭包。
10. 二义文法如果一个文法的某个句子对应两棵不同的语法树，即其最左（ 最右）推导不唯一，称该文法为二义文法。对程序设计语言来说，常常希望它的文法是无二义的，因为我们希望对它每个语句的分析是唯一的。
消除文法二义性的关键步骤：
例子：改写二义文法
E ->E + E
E ->E * E
E ->(E) | -E | id优先级从低到高：[+]；[*]；[( ), -, id]；
结合性：
左结合：[+, *]
右结合：[-]
无结合：[id]
非终结符与运算：
E:+（E产生式，左递归）T:*（T产生式，左递归）F:-,( ),id（F产生式，右递归）
E → E + T | T
T → T * F | F
F → (E) | -E | id
**句型：**从文法开始符号推导出来的任一文法符号串；
**句子：**从文法开始符号推导出来的任一终结符号串；
**短语：**对文法G[S]，如果有S =>* αAδ且A =>+ β，则称β是句型αAδ相对于非终结符号A的短语。
短语是语法树中所有子树的边缘，是相对于子树根节点的短语。
例如：
短语是S，(T)，Sd(T)，b，Sd(T)db，(Sd(T)db)；
**直接短语：**对文法G[S]，如果有S =>* αAδ且A =>β，则称β是句型αAδ相对于非终结符号A的短语。
直接断语是所有二层子树的边缘，在上图中只有三个二层子树。
例如：上图的直接短语是S，(T)，b；
**句柄：**最左直接短语；
句柄是最左二层子树的边缘。
例如：上图的句柄是S；
**素短语：**至少包含一个终结符的短语，并且除它自身之外不再包含其他素短语；
例如：上图的素短语是(T)，b；
**最左素短语：**句型最左边的素短语，是算符优先分析法的规约对象；
例如：上图的最左素短语是(T)；
例子：
**活前缀：**是句型的一个前缀，不含句柄以后的任何符号；
例子：
15. 规范规约规范规约是最右推导的逆过程，因此也称为最左规约。
16. 根据 FA 写正规式是根据正规式构造 FA 的逆过程。
17. 符号表用于登记源程序的各类信息，如变量名、常量名、过程名等，以及编译各阶段的进展状况。当扫描器识别出一个标识符后，把该名字填入符号表，在语义分析阶段回填类型，在目标代码生成阶段回填地址。
符号表的作用和地位：（重点）
符号表的主要属性：
static、const等；符号表的组织方式：
符号表项的排列：
Hash表，跳表；运行时存储器的划分：
存储分配策略：
活动记录：
为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样的一个连续存储块称为活动记录， 一般包括：
SP指向当前过程的动态链地址（也是帧起始地址），它又指向调用该过程的上一过程的帧起始地址，用于过程结束后回收分配的帧；它和函数的嵌套定义关系无关，只与调用顺序有关；
DAG优化；DAG优化；当翻译A = B op C时：
A、B、C是否还会在基本块内被引用；
对于一个不含回溯和左递归的文法，LL(1) 方法从左到右扫描输入串，维护一个状态栈和一个符号栈，每一步只向右查看一个符号，根据状态栈顶、符号栈顶和分析表的内容来确定下一步的动作，最终分析出整个句子。
22. LR(1)分析LR(1) 分析适合大多数上下文无关文法，它从左到右扫描符号串，能记住移进和规约出的整个符号串，即 “记住历史”，还可以根据所用的产生式推测未来可能碰到的输入符号，即 “展望未来”，根据 “历史”、“展望” 和分析表的内容来确定下一步的动作，最终分析出整个句子。
23. display 表为提高访问非局部变量的速度，引入指针数组指向本过程的所有外层，成为嵌套层次显示表，display 表是一个栈，自顶向下依次指向当前层、直接外层、直接外层的直接外层，直到最外层。
24. 语法制导翻译法对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。这种有源程序的语法结构驱动的处理办法就是语法制导翻译法。
二、综合题 2.1 词法分析例题给定正规式： ①构造NFA ②确定化 ③最小化
① + ②
③
例题 前提：LL(1) 适用条件给出文法：①构造First集合 ②构造Follow集合 ③构造LL(1)分析表 ④识别句子
First(X)
②求A ->Bc
B ->ε
则 First(A) = { c }；
若 A ->B
B ->ε
则 First(A) = { ε }；
Follow(X)
给出文法：①构造拓广文法 ②求First集合 ③构造LR(1)项目集规范族 ④构造LR(1)分析表并消除二义性 ⑤识别句子
构造带向前搜索符的DFA，无归约-归约冲突则是LR(1)文法。
例题1构造文法G[S]的LR(1)项目集规范族：
S ->aCaCb
S ->aDb
C ->a
D ->aS' ->S
S ->aCaCb
S ->aDb
C ->a
D ->aFirst集合：
LR(1)项目集规范族：
LR(1)分析表并消除二义性：
⑤识别句子消除二义性需要认为定义运算优先级，发生移入-规约冲突时选择正确的项填入。
aaaab和aab：
对下列文法做 LR(1) ：
S ->AS | b
A ->SA | a
1. 过程中的说明语句给出翻译模式和高级语言程序，翻译句子，一般涉及多种类型句子的综合，也可能涉及声明语句填写符号表。
3. 布尔表达式的翻译重点：回填。
重点：if 和 while 。
例题1给出基本块代码：①构造DAG ②写出优化后的中间代码 ③写出DAG目标优化后的中间代码 ④根据变量活跃性和寄存器信息，写出目标代码。
给出基本块代码为：
(1) T6 = R - r
(2) T2 = R * r
(3) T4 = T2
(4) T1 = 6.28
(5) T3 = 6.28
(6) A = 6.28 * T2
(7) T5 = A
(8) B = A * T6
(9) T0 = 3.14假定B是基本块出口之后活跃的，有寄存器R0和R1可用，目标代码为：
DAG 优化中，不活跃变量，目标代码依然要生成计算其值的代码，只是不生成存储到主存的代码。计算代码被优化是后续优化完成的，不是 DAG 完成的。
LD R0, R
SUB R0, r R0: T6 R1: \
LD R1, R
MUL R1, r R0: T6 R1: T2
ST R0, T6
LD R0, 6.28 R0: 6.28 R1: T2
MUL R0, R1 R0: A R1: T2
MUL R0, T6 R0: B R1: T2
ST R0, B
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MmUNQHdO-1655768860486)(https://s2.loli.net/2022/06/21/kX5Cfm2ILzv4ibW.png)]
一、简答（30 分）
1.给了一个文法（具体忘了），让证明二义性。
2.写出文法，表示{0、1}集上的所有正规式
3.解释 S-属性文法
4.说出传地址和传质这两种参数传递方式的异同
5.结合具体例子谈一谈回填思想
二、（babbb）* 画 NFA 转 DFA ，最小化（15 分）
三、（1）一个文法，判断是否为 LL（1）文法（10 分）
（2）上题中的文法是否为 SLR 文法，给出证明（15 分）
（与课本上例子不同之处在于有 B ——〉ε）
四、利用语法指导思想写四元式（15 分）
（比较简单，就是一个 while-do 语句）
五、给出一段中间代码，画 DAG 图；只有 R 在代码块外是活跃的，做优化；如
果有寄存器 R0 和 R1，写出目标代码。（15 分）
一、简答题
1.编译流程图及各部分的作用。⒉举例说明文法二义性。
3.什么是L属性文法?
4.写出允许过程嵌套的C活动记录结构。5.中间代码优化有哪几种?
6.符号表作用。
二、词法分析
RE NFA DFA最小化DFA整个流程走一遍
三、自上而下文法分析
给了一个文法，证明文法是LL1的，画表。
四、自下而上文法分析
给了一个文法,证明文法是LR1的，画表。
五、中间代码生成
—段代码，四元式翻译。涉及循环和判断的嵌套。
六、代码优化和目标代码生成。
给了一个代码段，
先画DAG图，然后优化，最后输出汇编代码。
一、五个小题（25分）
1.判断一个文法是否二义
2.编译的前端，后端，什么是一遍扫描
3.什么是S属性
4.什么是语法制导翻译
5.在语法制导翻译中，空返产生式的作用（M->e）
二、自动机（15分）
一个单词表由a，b组成，请写出代表偶数个a的正规式，NFA，并确定化、最小化
三、判断一个文法是不是LL（1）的，如果是就写出预测分析表，不是就说明原因（15分）
四、判断一个文法是不是SLR（1）的，如果是就写出预测分析表，不是就说明原因（15分）
五、中间代码生成程序（15分）
while a 六、代码优化（15分） DAG优化，最后写出四元式的形式（这个是一个坑，四元式是目标代码，也就是此时要做目标代码生成） 同时目标代码生成要列表（Rvalue 寄存器描述，Avalue地址描述） 一、简答题 二、计算题 整体比较简单，高分应该挺多。把本文涉及到的知识点全部搞清楚，应付考试游刃有余 后续同学们考完试，可以把回忆版私发给我，我在此文中持续更新。 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
while a< b do if c >d then x = y * z，会给出翻译规则。
分享名称：【编译原理】山东大学编译原理复习提纲-创新互联
文章链接：http://cdxtjz.com/article/djpipg.html