编译原理复习笔记
开始学科复习。选择编译原理作为第一门复习的课程，因为其内容不算太多，大部分计算过程可以暂时不用记录和练习，而且没什么前置知识。
选用课本是上课时用的清华大学出版社《编译原理》（其实我觉得这本书里给部分概念下定义时没有做到简洁明了，挺难理解的）。以下是记录的笔记。不求全面，只求适合自己之后再次复习使用。
编译程序与编译过程
编译程序（Compiler）
- 从功能上看，一个编译程序就是一个语言翻译程序；
- 基本任务：将源语言程序翻译成等价的目标语言程序。
- 重要性：使多数计算机用户不必考虑与机器有关的繁琐细节，使程序员独立于机器。
解释程序（Interpreter）
以语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源代码本身。
编译过程
- 词法分析：
- 功能：从左到右扫描源程序，并将该字符串转换成单词（Token）串；同时，检查词法错误、进行标识符登记——符号表管理
- 工具：正规表达式、自动机
- 语法分析：
- 功能：在词法分析的基础上将单词序列分解成各类语法短语；构造分析树，指出语法错误，指导翻译。
- 语义分析：
- 功能：审查源程序有无语义错误，为代码生成阶段收集类型信息；
- 中间代码生成：
- 功能：经过上述工作之后，将源程序变为独立于具体硬件的记号系统；
- 代码优化：
- 对前一阶段产生的中间代码进行等价变换，以获取更高的执行效率（速度、空间）；
- 分为机器有关和机器无关
- 目标代码生成：
- 功能：将中间代码转换成目标机上的机器指令代码或者汇编代码，完成最后的翻译，可以运行；
翻译程序的结构
符号表管理、错误处理：前端后端都有出现。
遍（pass）：
- 对源程序或源程序的中间结果从头到尾扫描，并做相关的加工处理，生成新的中间结果或目标程序；
- 遍可以和阶段相对应，也可无关；
- 分遍可以使编译程序的结构清晰，但增加 I/O 时间；
- 影响分遍因素：内存不够、全局优化需要、某些语言需要（如名字先引用后定义）。
词法分析
单词的形式化描工具：
- 正规文法（3 型文法）
- 正规式（正则表达式）
- 自动机（DFA、NFA）
自动机
确定的有穷自动机（DFA）和不确定的有穷自动机（NFA）的区别：确定性 => 对任何状态和输入符号，唯一地确定了下一个状态。
- NFA 转换为等价的 DFA：子集法
- DFA 的化简
文法与语言
产生式（又称规则）：a -> b 左部 -> 右部
文法：
- 阐明语法的一个工具。
- 作用：
- 严格地定义句子的结构；
- 用适当条数的规则描述语言的全部句子。
- 4 种文法类型：逐渐增加限制
- 0 型文法：对于每个产生式 A -> B，A 含至少一个非终结符
- 上下文有关的（1 型）：每个产生式均满足 |B| >= |A|（除非 B 为空）
- 上下文无关的（2 型）：每个产生式均满足 A 是一个非终结符
- 正规文法（3 型）：每个产生式的形式都是 A -> aB 或 A -> a（A、B 都是非终结符，a 是终结符）
上下文无关文法及其语法树
- 推导：不断替换文法产生式左部的非终结符号，直至全部将非终结符号替换为终结符号的过程
- 最左推导：总是优先替换产生式左部最左侧的非终结符号
- 最右推导：总是优先替换产生式左部最右侧的非终结符号（在形式语言中称为规范推导）
- 二义文法：存在某个句子对应两棵不同的语法树的文法
句型分析
自上而下的分析方法：
- 从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导；
- 通过最左推导从顶部（根结点）开始构造 AST；
- 常用的分析器有递归下降语法分析器、LL 语法分析器。
自下而上的分析方法：
- 从输入符号串开始，逐步进行“规约”，直至规约到文法的开始符号；
- 通过最右推导从底部（叶子结点）开始构造 AST；
- 常用的分析器有 LR 语法分析器、SLR 语法分析器、LALR 语法分析器。
短语：一个句型的语法树中任一子树叶节点所组成的符号串都是该句型的短语。
直接短语：当子树不包含其他更小的子树时，该子树叶节点所组成的字符串就是该句型的直接短语。
句柄：句柄是最左边的直接短语。
例子：
可得S=(Sd(T)db)为此文法的一个句型：
- 短语：
S，(T)，b，Sd(T)，Sd(T)db，(Sd(T)db) - 直接短语：
S，(T)，b - 句柄：
S
自顶向下语法分析
- 自顶向下的确定分析方法：
- 优点：实现方法简单、直观，便于手工构造或自动生成语法分析器
- 缺点：对文法有一定限制
- 自顶向下的不确定分析方法：
- 带回溯
- 实际上是一种穷举的试探方法，效率低，代价高，极少使用
- 文法不满足 LL(1) 时使用
确定的自顶向下分析思想
LL(1) 文法是能够使用确定的自顶向下分析技术的。
LL(1) 的含义：
- 第 1 个 L 表明自顶向下分析是从左向右扫描输入串；
- 第 2 个 L 表明分析过程中将用最左推导；
- 1 表明只需向右看一个符号便可决定选择哪个产生式进行推导。
LL(1) 文法的判别
具体见课本。
某些非 LL(1) 文法到 LL(1) 文法的等价变换
若文法中含有直接或间接左递归，或含有左公共因子，则该文法肯定不是 LL(1) 文法。因此，要做某些非 LL(1) 文法到 LL(1) 文法的等价变换，需要：
- 提取左公共因子；
- 消除左递归。
具体操作见课本。
自底向上语法分析
- 又称移进-归约分析
- 实现思想：对输入符号串自左向右进行扫描，并将输入符逐个移进一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或其他可归约串（对应某产生式的右部）时，就用该产生式的左部非终结符代替右部的文法符号串。这个行为称为一步归约。
LR 分析
LR 分析法是一种能根据当前分析栈中的符号串和向右顺序查看输入串的 k 个符号就可以唯一确定分析器的动作是移进还是归约、用哪个产生式归约，因而能够唯一地确定句柄。
内容太多，图太多，但是对现阶段的我不太重要，故略。如果有学弟学妹看到了，这章是重点，所有例题都要自己推一遍。
语法制导的语义计算
两种重要的语义计算模型：
- 属性文法：在文法基础上，为文法符号关联有特定意义的属性，并为产生式关联相应的语义动作或条件谓词。
- 翻译模式：在形式上类似于属性文法，但允许由
{}括起来的语义动作出现在产生式右端的任何位置，以此显式地表达属性计算的次序。
基于属性文法的语义计算
综合属性：产生式左部的非终结符的某个属性。计算时自底向上传递信息。
继承属性：产生式右部某个文法符号的某个属性。计算时自顶向下传递信息。
遍历分析树进行语义计算
- 可以通过标注来表示属性的计算结果
- 在语法分析遍之后进行，不能体现语法制导方法的优势
- 实际的编译程序中，语法制导的语义计算大都采用单遍的过程（语法分析过程中完成语义动作） => 不是所有属性文法都适合单遍的处理过程 => 受限的属性文法
受限的属性文法：
- S-属性文法：只包含综合属性的属性文法
- L-属性文法：既可以包含综合属性，也可以包含继承属性，但要求产生式右端某文法符号的继承属性的计算只取决于该符号左边符号的属性（对于产生式左部的符号，只能是继承属性）
- S-属性文法是 L-属性文法的一个特例。