编译原理复习提纲整理
说明
1.这份资料的最初来源是王金伟老师给大家发的复习提纲，我在下面会给大家附一份原版，后面的21面资料是在那个的基础上整理和细化得到的。最初做这份资料的目的是我本人作为班长为了帮助我们班的同学顺利通过考试而整理的。听王老师说有想法留给学弟学妹们用，我放假后又对一些内容进行了修正和改进，得到了大家看到的这个版本
2.这份资料加入了很多我个人的理解。与原提纲相比，我增删了一些内容，并对某些内容进行了调序与合并。
3.这份资料融入了老师平时上课的PPT以及最后复习课给的PPT，更重要的是我个人的理解和猜测。大家或许都有感受，觉得编译原理书上或者PPT上说的句子根本看不懂。针对这个问题，我把很多晦涩难懂的形式化的算法通过我的理解后用比较形象易懂的话表述了出来，表述得可能并不科学严谨，但我的目的是为了能帮助大家做题和考试 4.里面的每一个考点我都在最后用括号加了注释，方便不同起点不同准备时间的同学进行选择，这里简单说明
“了解”：代表这一部分的内容被老师列在提纲内，但其实并不太影响大家对大题的计算；并且据我的分析也并不太可能出小题所以时间很紧的同学可以略看就好，当然看看还是有好处的。
“小题”一类的字样代表这一块的知识点值得出填空选择，大家有时间应该理解性的记忆下来（在2012年的期末考试上，选择为1分*10题；填空为1分*10题，判断改错为2分*5题，小题总计30分）
“简答”：老师在最后复习课上说过编译原理是有简答题的，简答不同于计算，很可能是让你默写一些步骤。所以这一块内容大家需要背诵，即使不理解也要背下来（在2012年的期末考试上，简答题的分值为5分*4题=20分
“铺垫”“大题步骤”等代表这一块的内容对于综合大题的做题是必须了解的，或者其实就是做大题的分解步骤，这些块的内容是所有人必须看懂并且记下来的
“实际大题”：总共列出的有4道，应该每年考察的都会是这4中题型，每一道的分值都在12~15分左右，是所有人想通过考试所必须攻克的。这里通常我会标出他需要用到之前的哪些哪些知识点（2012年期末考试4道题的总分值为50分）
5.如果大家想去打印，最好在装有office2007及以上的机器上打印，否则有些符号可能会显示不出来。建议大家去生活广场找机器打，不要去景元鸿
6.由于时间仓促，这份资料做的并不完善和严谨，难免有错漏之处，希望大家谅解。大家可以一边看我的这份资料，一边看老师最后给的两套PPT，课本来不及就别看了。真心希望这份资料能对大家有用，祝大家都考得好。
PS最后说一句，我们去年编译原理考得好的人挺多的，其实也不是很难，没有人挂！本人惭愧，只有89，考得比我好的多太多了。总结原因是把时间花在了研究大题上面，小题的很多知识点都没有背熟，随便错了几个小题就基本和90无缘了。
10计1 王成正 2012/7/9
1 / 24
编译原理复习提纲整理
（老师给的提纲原版） 一、 概述
1. 编译方式与解释方式区别：是否生成目标代码 2. 编译程序总框架
二、 词法分析
1. 状态转换图的功能：识别（接受）一定的符号串（单词） 2. 状态转换图的程序实现的思路：为每个状态结点都编写一个子程序 3. 字母表的概念：一般用∑表示
4. 闭包的概念：闭包V*中的每个字都是由V中的字经过若干次连接而成的 5. 正则闭包V+的概念：是V上所有符号串的集合
6. ∑*定义：表示∑上所有字的全体，空字ε也包括在其中 7. ∑+空字ε不包含，非ε 8. ε，{ }，{ε}之间的区别 9. ε所对应的正规集为{ε}
10. 正规式与正规集的定义：知道如何用正规式表示一个正规集 11. 简述NFA和DFA的定义与区别
12. 若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的ε
通路，那么空字ε可为M所识别 13. 正规式与优先自动机的等价性
14. 定理2.对于∑上的每一个正规式V，存在一个∑上的DFA M，使得L(M)=L(V)
15. DFA M的化简的概念和方法：终态和非终态是可区别的，因为终态可以读出空字ε，而非终态
不能读出空字ε 16. 课后作业一个例题
17. 构造一个DFA，它接受∑={x，y}上所有倒数第二个字符为y的字符串
三、 语法分析
（1）基本定义
1. 上下文无关文法的定义 2. 句型、句子的概念
3. 文法和语言的对应关系，给出文法构造语言，文法G产生的句子的全体是该文法的语言 4. 语法分析树与二义性：判断文法的二义性方法：如果一个文法含有二义性的句子（对应两棵不同
的语法树），则称该文法是二义性文法 5. 3型文法是正规文法、正则文法、线性文法 6. 2型文法也称为称为上下文无关文法
7. 若一个文法是递归的，则由它产生的语言的句子个数是无限的
（2）自上而下 8. 文法左递归的定义
9. 消除文法的左递归的方法：直接左递归 10. 消除回溯的方法：提取公共左因子 11. 递归下降分析法的概念，应满足什么条件？
12. 递归下降法对文法的每个非终结符构造一个相应的子程序
13. 预测分析法：给文法构造预测分析表：消除左递归、消除回溯、First集、Follow集。举例子时，
2 / 24
编译原理复习提纲整理
便成S→a|aS|（T） （3）自下而上
14. 短语、直接短语的概念
15. 句柄的概念（一个句型的最左直接短语） 16. 规范归约（最左）、规范推导（最右）、规范句型 17. 规范归约的关键问题是寻找句柄 18. 在规范归约中，可归约串必出现在栈顶 19. 算符文法、算符优先文法的概念，如何判断
20. 构造算符优先关系表、Fisrtvt、lastvt集合，可不考虑#号 21. 素短语：算符优先归约的关键问题是寻找最左素短语 22. 算符优先法尤其适用于表达式的分析 23. 给出文法G（P） X → jYj
Y → kZ|i Z → Yid
24. 该文法是否为算符优先文法？请根据FIRSTVT、LASTVT集合构造算符优先关系表说明之（12分）
25. 优先函数的优点：便于比较，节省空间 26. 优先函数的构造方法
27. 欲构造行之有效的自上而下分析器，则必须消除文法中含有的左递归 28. LR分析法属于自底向上分析方法 29. 从文法出发构造LR（0）分析表的步骤 四、语义分析
1. 综合属性和继承属性概念
五、中间代码生成
1. 中间代码是一种面向语法，易于翻译成目标代码的代码 2. 后缀式（逆波兰式）的概念
3. 逆波兰式中各运算法出现的顺序与实际运算顺序一致 4. 后缀式与抽象语法树（表达式树）的关系 5. DAG的含义
6. 四元式表示方法，联系时通过临时变量，可以翻译各种语句 7. 将赋值语句表示成后缀式和四元式 六、代码优化
1. 简述代码优化的原则与优化的级别，并列举三种常用的优化技术 2. 基本块、流图的概念，如何画、节点对应基本块 3. 局部优化的方法，DAG是对基本块进行优化的有效工具 4. P285中间注意
5. 不变运算的代码外提的条件 6. 循环优化中的强度削弱的含义
七、目标代码生成
1. 编译程序生成的目标程序种类
3 / 24
编译原理复习提纲整理
