编译原理期末不挂科指南

概念

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

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

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

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

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

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

语法分析:输入词法记号流,输出语法短语树

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

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

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

最左(右)推导:每次直接推导均替换句型中最左(右)边的非终结符

**二义性:**某个句子不止一棵分析树,或者说这个句子存在不止一种最左(最右)推导

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

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

句柄的右边仅含终结符

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

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

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

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

可行前缀:右句型的前缀,该前缀不超过最右句柄的右端

LR文法 vs LL文法

  • LR(K)文法:向前看k个输入符号能够知道一个产生式的右部所能推导出的所有符号串,进而识别出这个产生式右部的出现。
  • LL(K)文法:看到了产生式右部推出的前k个符号后能够识别出用于归约的产生式。
  • LR文法比LL文法描述的语言更多,但手工构造分析表的工作量太大
区别 LR(1)方 法 LL(1)方 法
建立分析树的方式 自下而上 自上而下
归约还是推导 规范归约 最左推导
决定使用产生式的时机 看见产生式右部推出的整个终结符串后,才确定用哪个产生式进行归约 看见产生式右部推出的第一个终结符后,便要确定用哪个产生式推导
对文法的显式限制 对文法没有限制 无左递归、无公共左因子
分析表比较 状态×文法符号
分析表大
非终结符×终结符
分析表小
分析栈比较 状态栈,通常状态比文法符号包含更多信息 文法符号栈
确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念
语法错误 决不会将出错点后的符号移入分析栈 和LR一样,决不会读过出错点而不报错

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

TODO:第五、六章