未雨绸缪很重要，所以现在就把编译原理这门传说中很变态的课的复习提纲先搜集一份来。

来自：Google → 玉山天空论坛 → 校园学术 → 趣味学堂 → 【计算机科学与技术】【编译原理】复习提纲

一.编译原理引论

1.1 基本概念

翻译程序,编译程序,解释程序,源语言,目标语言,诊断编译程序,优化编译程序,交叉编译程序,可变目标编译程序

1.2.编译过程概述

词法分析的任务,语法分析的任务,语义分析和中间代码生成的任务,优化的任务和主要方面(方法)目标代码生成的任务,目标代码的形式

1.3.编译程序的结构 编译程序的总体结构,符号表的作用,语法错误和语义错误的概念,遍的概念,编译前端和编译后端的概念

1.5.编译程序的生成

自编译方式和交叉编译方式生成编译程序的方法

二.高级语言及其语法描述

2.1程序语言的定义

2.1.1语法

词法规则,单词符号,语法规则,语法单位

2.1.2语义

语义规则

2.2 高级语言的一般特性

2.2.1高级语言的分类

过程式语言,函数式语言,基于规则的语言,面向对象的语言

2.2.3数据类型和操作

标识符和名字的区别,名字的值和属性(类型和作用域),数组的内情向量必需包括的内容,左值和右值

2.3程序语言的语法描述

符号串,空集,连接,闭包,正则闭包.

上下文无关文法的四个组成部分,推导,最左推导,最右推导,句子,句型,语言.

文法的二义性是不可以判定的.要求会画语法树

2.3.3形式语言鸟瞰

短语文法,上下文相关文法,上下文无关文法,正规文法

三. 词法分析

程序语言的单词符号的分类:关键字,标识符,常数,运算符,界符

预处理子程序与扫描缓冲区

超前搜索思想,状态转换图及其实现

3.3正规表达式与有限自动机

正规集,正规式,等价的正规式

NFA,DFA的定义

根据正规式,写出对应的自动机的方法,NFA化为等价的DFA的方法

四. 语法分析-自上而下分析

自上而下的分析的主旨是,对于任何输入串,试图用一切可能的办法,从文法开始符号(根节点)出发,自上而下的为输入串建立一棵语法树.或者说,为输入串寻找一个最左推导.这种分析过程本质上是一种试探过程,是反复使用不同的产生式谋求匹配输入串的过程.

自上而下的带有回溯的试探法的一种简单的实现方案为让每个非终结符对应一个递归子程序.每个这种子程序作为一个布尔过程.一旦发现它的某个候选式与输入串匹配,就用这个候选式去扩展语法树,并返回”真”否则,保持原来的语法树并且保持指向输入串中当前分析的符号的位置的指针不变.

存在的问题:左递归,虚假匹配-回溯,难于找出输入串中出错的确切位置,是穷尽一切可能的试探法-效率低下

4.3.1 左递归的消除

对于给定的一个文法,消除其左递归的方法

4.3.2 消除回溯,提左因子

终结首符集FIRST()的定义,也就是FIRST(a)是从a可能推导出的所有的开头的终结符或者空串.

4.3.3 LL(1)分析的条件

FOLLOW(A)的定义,也就是所有句型中出现在紧接在A之后的终结符或者’#’

LL(1)文法的定义和条件

4.5 预测分析程序

4.5.1预测分析程序的工作过程

给定文法和其对应的分析表,写出对一个输入串进行预测分析的步骤

4.5.2预测分析表的构造

给定文法,构造出其对应的预测分析表的方法

五.语法分析-自下而上分析

5.1自下而上分析的基本问题

5.1.1规约

移进-规约方法是用一个寄存符号的栈,把输入符号一个一个的移进栈里,当栈顶形成某个产生式的一个候选式时,把栈顶的这一部分替换(规约)成该产生式的左部符号.关键的问题是判断”当栈顶形成某个产生式的一个候选式时”,是否可以”把栈顶的这一部分替换(规约)成该产生式的左部符号”,即判断”可规约串”的问题.

不同的判断”可规约串”的方法,形成了不同的自下而上的分析法.

5.1.2规范规约简述

短语,直接短语,句柄,规范规约,规范推导,规范句型

规范规约的实质是,在移进过程中,当发现栈顶呈现句柄时,就用相应的产生式的左部符号进行替换.

给定文法,求一个句型的短语,直接短语,句柄.

5.1.3 符号栈的使用和语法树的表示

规定:用一个不属于文法符号的特殊符号#作为符号栈的栈底符号,即在分析开始时,就预先把#放入符号栈中.同时,也使用这个符号作为输入串的结束符号.

语法分析对符号栈的使用有4类操作:移进,规约,接受,出错处理.

5.2 算符优先分析

给定一个算符优先文法及其优先表,写出算符优先算法对一个输入串的分析过程.

给定一个算符优先文法,构造其的优先表的方法.

5.3 LR分析法

5.3.1 LR分析器

LR方法的基本思想是,在规范规约的过程中,一方面记住已经移进和规约出来的整个符号串,即记住”历史”另一方面根据所用的产生式推测将来可能遇到到的输入符号,即对未来进行”展望”.当一串看起来象句柄的符号串出现在分析栈的顶部时,根据记载的”历史”(当前是哪个状态)和”展望”(分析表表明了在当前状态下对于当前可能输入的不同符号进行如何的处理),以及”现实”(实际上当前的输入符号),确定当前栈顶的符号串是否为一个句柄.

一个LR分析器实质上是一个带有栈的确定性有限状态自动机.任何时候,栈顶的状态都代表里整个的历史和已经推测出来的展望.LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一确定的.

LR分析器由栈,LR分析程序和分析表构成.文法确定了LR分析表的内容.分析表分为动作表(ACTION)和状态转换表(GOTO)两部分构成.

给定一个文法及其LR分析表,对一个输入串写出LR分析器的工作过程.

5.3.2LR(0)项目集族和LR(0)分析表的构造

活前缀是规范句型的前缀.LR(0)项目,一个识别文法活前缀的DFA的项目集合 (即DFA的状态)的全体称为这个LR(0)文法的LR(0)项目集规范族.凡是圆点在最右端的项目,称为一个规约项目.文法开始符号的规约项目,称为接受项目.对于圆点之后是终结符的项目,称为移进项目.对于圆点之后是非终结符的项目称为待约(等待规约)项目.

给定一个文法,求其LR(0)分析表的过程和方法.

六.属性文法和语法制导翻译

6.1属性文法

综合属性,继承属性

七.语义分析和中间代码产生

后缀式,四元式的概念

算术表达式的四元式表示,条件语句和循环语句的四元式表示

把条件语句和循环语句翻译成四元式序列的方法.

十.优化

10.1概述

优化的原则:等价原则,有效原则,合算原则

常用的优化技术:删除公共子表达式,复写传播,删除无用代码.代码外提.强度削弱,删除归纳变量

十一.目标代码生成

11.6 窥孔优化

窥孔优化方法是通过考察一小段目标指令(称为窥孔)并把这些指令替换为更短和更快的一段指令,从而提高目标代码的质量.这里的窥孔指目标程序中的一个可以移动的小窗口.

典型的窥孔优化技术包括:对冗余存取,对可到达代码的删除,对控制流的优化,强度削弱,删除无用操作等.

另外还找到一个编译原理的在线学习的网站。