编译原理

编译原理的复习大纲，包括算符文法、LR分析器、LR(0)文法、属性的分类、语法制导翻译过程、符号表的查找方法等内容。

编译原理

• 第一章
  • 翻译程序：是指这样一个程序，他把一种语言所写的程序，翻译成与之等价的另一种语言
  • 编译程序：源语言是高级语言，目标语言是低级语言，那么这样的程序叫编译程序
  • 解释程序：将源程序输入并执行之，即边解释边执行
  • 编译过程划分的阶段和每阶段完成的功能
    • 词法分析：对源程序的字符串进行扫描和分解，根据语言的语法规则，识别出一个具有独立意义的单词
    • 词法分析：检查各种语法单位在语法结构上的正确性
    • 语义分析及中间代码生成：对每种语法进行静态的语义审查，分析其含义，并用另一种语言形式来描述这种语义
    • 代码优化：对前阶段产生的中间代码进行等价变换，以期获得更高效的目标代码
    • 目标代码生成：将中间代码变化成特定机器上绝对指令代码或可重定位的指令代码或汇编指令代码。
• 第二章
  • 1
    • 字母表：元素的非空有穷集合
    • 符号：字母表中的元素
    • 符号串：符号的有穷序列
  • 符号串的运算
  • 3
    • 文法：规则的非空有穷集合，通常表示成四元祖G=（Vn,Vt,P,S）
  • 4
    • 直接推导：令G是一个文法，从符号串xAy直接推导出day仅使用一次规则
    • 推导：如果存在一个直接推导序列：即表示从a0出发，经过一步或若干步或使用若干次规则可推导出an
    • 广义推导：表示从a0出发，经过0步或若干步，可推导出an.(*)
    • 直接推导的长度为1，推导的长度大于等于1，广义推导的长度大于等于0
    • 递归规则：在规则的左部和右部具有相同非终结符的规则。
    • 文法的递归性：对文法中任意一非终结符，若能建立一个推导过程，在推导所得的符号串中又出现了非终结符本身，则文法是递归性的。
    • 文法的二义性：如果一个文法存在句子对应两棵不同的语法树，则说这个文法是二义性的。
  • 5
    • 短语：子树末端结点形成的符号串是相对于子树根的短语。
    • 直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。
    • 句柄：最左简单子树末端结点的符号串。
    • 素短语：至少包含一个终结符，而且除了本身之外不含有其他素短语。
    • 最左素短语：句型中最左边的素短语。
  • 6
  • 7
    • 见notability
• 第三章
  • 词法分析程序的功能：每当语法分析程序需要一个单词符号时，就向词法分析程序发出“取下一个单词符号”的调用命令。词法分析程序就从输入字符串中，，识别出一个具有独立意义的单词符号，并传给语法分析程序。
  • 2
    • 正规集：能用正规式或正规文法表示的集合
    • 正规式：正规式可以由较小的正规式按照特定规则递归地构建。每个正规式r定义（表示）一个语言，记为L（r）
    • 正规文法：3型文法
    • 确定性有穷自动机（DFA）
    • 非确定性有穷自动机（NFA）
  • 3
    • 正规文法->有穷自动机：f(A,a)=B
    • 有穷自动机->正规文法：f(A,a)=B
    • 正规文法->正规式：解方程
    • 正规式->正规文法：一系列规则
    • 正规式->有穷自动机：画图
    • 有穷自动机->正规式：读图
    • NFA->DFA：状态矩阵
    • DFA化简：划分子集法
    • 详细解法参见notability
• 第八章
  • 程序设计语言使用的存储环境
    • 完全静态存储环境
    • 基于栈的存储环境
    • 基于堆的存储环境
• 第七章
  • 基本块：代码优化中，基本块是指程序中一顺序执行的语句序列，它有一个入口和多个出口
  • 实施循环优化包括
    • 环内的代码外提
    • 度削弱与删除归纳变量
    • …
  • 编译中的代码优化
    • 局部优化
    • 全局优化
    • 循环优化
  • 与机器无关的优化，常用的优化技术
    • 删除公共子表达式
    • 代码外提
    • 强度削弱
    • 删除归纳变量
    • 合并已知量
    • 复写传播
    • 删除无用赋值
• 第六章
  • 符号表的作用
    • 记录标识符的相关信息
    • 为上下文语义的合法性检查提供依据
    • 生成目标代码时，是编译程序分配存储地址的依据
  • 符号表的查找方法
    • 顺序查找
    • 二分查找
    • 散列查找
  • 符号表可用不同的数据结构
    • 线性表
    • 各种搜搜索树
    • 散列表
• 第五章
  • 属性文法：形式定义：三元组AG=(G,V,E)。其中G表示一个上下文无关文法，V表示属性的有穷集，E表示属性的断言或谓词的有穷集。
  • 属性的分类
    • 综合属性
      • 用于“自下而上”传递信息
    • 继承属性
      • 用于“自上而下”传递信息
  • 语法制导翻译过程
    • 在语法分析过程中，根据相应文法的每一规则所对应的语义子程序翻译的过程
  • 逆波兰式：实际上是后缀表达式：左右中
  • 三元式：(i) (op,arg1,arg2)
  • 树形表示：树
  • 四元式：(i) (op,arg1,arg2,result)
  • 三地址代码：X=a op b
• 第四章
  • 语法分析程序的功能：以词法分析器生成的单词符号的序列作为输入，根据语言的语法规则，识别出各种语法成分，并在分析的过程中进行语法检查，检查所给的单词符号序列是否是该文法的一个句子。若是，则以该剧自的某种形式的语法树作为输出。若不是，指出错误的位置和性质。
  • 自上而下的分析法：从文法的开始符号出发，根据文法规则正向推导出给定句子的一种方法。
  • 自下而上的分析法：从给定的输入串开始，根据语法规则逐步进行归约，直至归约到文法的开始符号。
  • LL(1)
    • FIRST、FOLLOW、SELECT集的构造
    • 文法的判别
    • 文法左递归消除、回溯消除
    • 非LL(1)文法到LL(1)文法的改写
    • 预测分析表的构造
    • 对输入串的分析过程
    • 递归下降分析法
    • 递归下降分析程序
  • 算符文法
    • 算符优先文法的定义
    • FIRSTVT、LASTVT集求解
    • 算符优先分析表
    • 算符优先分析法
  • LR分析器
    • 工作原理
    • 过程
    • 分析表组成部分
    • 动作、活前缀的定义
    • 项目的分类
  • LR(0)文法
    • 判别
    • 分析表构造
    • 输入串的分析过程
  • SLR(1)文法
    • 判别
    • 分析表构造
    • 输入串分析过程
  • LR(1)文法
    • 判别
    • 分析表构造
    • 输入串分析过程
  • LALR(1)文法
    • 判别
    • 分析表构造
    • 输入串分析过程