编译原理期末不挂科指南

概念

编译器与解释器区别和联系：

1. 解释器不像编译器通过翻译来生成目标程序，而是直接执行源程序所指定的运算。
2. 编译器会保存生成的目标程序，执行速度较快；解释器不会保存生成的目标程序，执行速度较慢。
3. 编译器生成目标程序，且与平台相关；解释器不生成目标程序，与平台无关。

编译器的结构：分析部分+综合部分

编译程序的输入数据是源程序, 输出结果是目标程序

编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成等几个基本阶段,同时还会伴有符号表管理和出错管理。

词法分析：输入源程序的字符，输出词法单元流

语法分析：输入词法记号流，输出语法短语树

语义分析：检查程序的语义正确性，以保证程序各部分能有意义地结合在一起，为后面代码生成阶段收集类型信息。

中间代码表示形式：后缀表示，抽象语法树，三地址码

推导：符号串中的非终结符用其产生式右部的串来代替

最左（右）推导：每次直接推导均替换句型中最左（右）边的非终结符

**二义性：**某个句子不止一棵分析树，或者说这个句子存在不止一种最左（最右）推导

规约：若一个子串和某个产生式的右部匹配，则用该产生式的左部符号代替这个子串。

句型的句柄是和某产生式右部匹配的子串。

句柄的右边仅含终结符

移进-归约语法分析的四种动作：

• 移进：把下一个输入符号移进栈
• 归约：分析器知道句柄的右端已在栈顶，然后确定句柄的左端在栈中的位置，再决定用什么样的非终结符代替句柄
• 接受：分析器宣告分析成功
• 报错：分析器发现语法错误，调用错误恢复例程

移进-归约语法分析的冲突：

• 移进-归约冲突
• 归约-归约冲突

可行前缀：右句型的前缀，该前缀不超过最右句柄的右端

LR文法 vs LL文法

• LR(K)文法:向前看k个输入符号能够知道一个产生式的右部所能推导出的所有符号串，进而识别出这个产生式右部的出现。
• LL(K)文法：看到了产生式右部推出的前k个符号后能够识别出用于归约的产生式。
• LR文法比LL文法描述的语言更多，但手工构造分析表的工作量太大

区别	LR(1)方 法	LL(1)方 法
建立分析树的方式	自下而上	自上而下
归约还是推导	规范归约	最左推导
决定使用产生式的时机	看见产生式右部推出的整个终结符串后，才确定用哪个产生式进行归约	看见产生式右部推出的第一个终结符后，便要确定用哪个产生式推导
对文法的显式限制	对文法没有限制	无左递归、无公共左因子
分析表比较	状态×文法符号 分析表大	非终结符×终结符 分析表小
分析栈比较	状态栈，通常状态比文法符号包含更多信息	文法符号栈
确定句柄	根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式	无句柄概念
语法错误	决不会将出错点后的符号移入分析栈	和LR一样，决不会读过出错点而不报错

其余详见PDF版 编译原理-词法分析与语法分析

TODO：第五、六章