在当今数字时代，编译原理作为计算机科学领域中的重要支柱之一，扮演着将高级程序语言转换为底层机器代码的关键角色。对于每一位计算机科学专业的学子而言，深刻理解编译原理不仅是学科进阶的必经之路，更是培养解决实际问题和开发高效程序的关键一环。
随着学期即将尾声，期末考试已然迫在眉睫，为了助力你在编译原理的考场上大显身手，我们将深入解析该学科的核心概念，回顾关键算法，剖析实际项目经验，为你奠定牢固的基础。欢迎踏上这场关于编译原理的深度复习之旅，让我们共同迎接考试挑战，掌握这门学科的精髓，为未来的编程征途赢得坚实的起步。
思维导图
引论
编译程序的过程：
词法分析——>语法分析——>语义分析——>中间代码生成——>代码优化——>目标代码生成
其中中间代码生成和代码优化不是必要的。
文法和语言
描述文法的两种方式：生成方式、识别方式
什么是文法：
文法的等价：文法所生成语言的等价。
句型和句子的区别：句型>句子,句子是终结符串，句型可以包含非终结符。
推导：直接推导、星推导、加推导
最右推导：每次对最右边的非终结符进行替换（规范推导）
最左推导：每次替换最左边的非终结符。
推导和规约：推导：产生式右边代替产生式左边，规约：产生式左边代替产生式右边。
推导是自顶向下，右边代替左边；规约是自底向上，左边代替右边。
文法的分类和对应的自动机：
0型文法：所有的文法都是0型文法
1型文法：产生式右边长度大于产生式的左边
2型文法：产生式左边只有一个非终结符
3型文法：产生式右边只有一个终结符或者一个终结符号和一个非终结符。
1型文法为什么是上下文有关的（context-sensitive）：
上下文：非终结符前后的终结符号，想要用产生式的右边代替左边的时候必须考虑非终结符的前后位置（上下文）
语法树：描述上下文无关文法的句型推导的直观表示，是句型分析的工具。
什么样的文法是二义的：某个文法对应两棵不同的语法树，注意文法的二义性和语言的二义性是不同的。很可能文法是二义的但是语言是相同的，文法的二义只是影响我们对语言的分析。判断一个文法是不是二义的是一个递归不可解的问题，但是我们可以给出一个文法不是二义文法的充分条件。
分析程序：完成句型分析的程序
概念：句子，句型，句柄，短语
短语：短语是句型的一部分，这一部分是由某个非终结符加推导（经过一次或者多次推导）出来的，在语法树中，短语是以非终结符为根，其叶子节点按顺序排列的结果（事实上我们并不关心是由哪个非终结符推导得到的，只关心短语本身）
直接短语：直接由某个非终结符号推导出的短语
句柄：最左直接短语（一个非常重要的概念）
给出语言写文法，给出文法写语言
句型分析要解决的问题：
自顶向下：多候选式时如何选择；
自底向上：选择要进行规约的子串（可规约串）
词法分析
词法分析程序的任务：从左至右逐个字符地对源程序扫描，产生单词序列，用于语法分析
讨论范畴：3型文法
正规文法，正规式，自动机都是3型文法的讨论范畴
正规文法、正规式概念
正规式、正规文法，自动机的的相互转换（以NFA为桥梁转换）：
正规式↔NFA
正规文法↔NFA
DFA和NFA的区别：DFA的变换函数f是一对一映射，NFA是一对多映射，也就是NFA一个状态遇到一个字母，下一个状态是不唯一的、不确定的。
NFA的确定化：
思路：用状态集代替状态。
ε-closure：某个状态经过若干条ε弧到达的状态集合。
行表头是字母表里面的字母，列表头是状态集合。利用Ia规则更新状态，新的状态依据宽度优先搜索进入到列表头，不断递归，直到无新状态集产生。然后用状态代替状态集。
DFA的最小化：
消除无用状态：不可到达（任何输入串不能到达该状态：没有出现在产生式的右边）和不可终止（该状态没有通路到达终态：无限递归）
合并等价状态：
证明正规文法/正规式等价：
写出对应的NFA——>确定化NFA——>最小化DFA——>画出最后的自动机，判断自动机是否等价。
零碎知识点：
正规式的等价、正规集的等价、自动机的等价是等价的
状态转换图：初态双箭头表示，终态双括号表示
自动机到正规式的时候只要形成循环就是闭包
正规式到自动机的时候想要表示闭包不仅要形成循环，还有前后两条空
正规文法到自动机需要新增一个终态。
自顶向下的语法分析
LL（1）文法原理
first集 ：首终结符集合
follow集：向后看一个符号，后面跟着的终结符集合
select集 ：
判断是否为LL（1）文法：同一个非终结符的产生式右边的select集没有交集
LL（1）分析：步骤，分析栈，符号串
消除左公因子、左递归
补充：自顶向下的语法分析包括递归子程序和LL（1）分析表，两种功能相同
自底向上的语法分析
补充：自底向上的语法分析包括优先分析和LR分析，两者功能相同
移进、规约、待约、接受项目
移进、规约、接受，出错动作
LR（0），SLR（1），LALR（1），LR（1）文法判断
LR（0）文法：没有移进-规约，规约-规约冲突
SLR（0） 面向follow集规约，没有移进-规约，规约-规约冲突
LALR(1):LR(1)文法合并同心集之后没有新的冲突产生
LR（1）文法：没有规约规约冲突
SLR（1）文法写分析表的时候小技巧：先写普通的action和动作，最后再补充的状态内既有移进又有规约的规约动作。
语义分析
继承属性
综合属性
语义子程序
逆波兰式，三元式，四元式
语义分析依赖于上下文分析
抽象语法树一定是符合语法的，不会存在语法错误，语义分析器会分析语义是否满足。
在编译原理的期末复习中，我们深入研究了编译过程的各个环节，从词法分析到语法分析，再到语义分析和代码生成，每个环节都如同编译过程中的一个关键拼图，构成了理解和实现编译器的完整图景。我们将带着对编译原理的深刻理解和扎实掌握，迎接未来更高级的编程语言和编译技术的挑战。
发表评论