01_编译原理复习总结(修订版)new

《01_编译原理复习总结(修订版)new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译的各个阶段完成的工作1、词法分析根据词法规则识别出源程序中的各个记号，每个记号代表一类单词。2、语法分析根据语法规则识别出记号流中的结构，并构造一棵能够正确反映该结构的语法树。3、语义分析根据语义规则对语法树中的语法单元进行静态语义检查，其目的在于保证语法正确的结构在语义上也是合法的。4、中间代码生成根据语义分析器的输出产生中间代码。5、中间代码优化中间代码往往在时间和空间上有很大浪费，因此需进行优化。6、目标代码生成编译器的最后一个阶段，生成目标代码。7、符号表管理记录源程序中符号的必要信息，并加以合理组织，从而在编译器的各个阶段能对它们进行快速、准确的

2、查找和操作。8、出错处理在编译的不同阶段检错，并采用适当的策略修复它们。解释器及其优缺点优点：1、具有较好的动态特性。2、具有较好的可移植性。缺点：在运行时间和空间上的损失较大，运行效率低。编译的遍数编译器工作的每个阶段都对以某种形式表示的完整程序进行一遍分析。我们把每个阶段将程序完整分析一遍的工作模式称为一遍扫描。确定扫描遍数的因素：1、软硬件条件2、语言结构3、编译技术LEX、YACC分别生成什么LEX：词法分析器生成器YACC：语法分析器生成器符号表的处理，贯穿整个过程正规式的构造：文字描述→正规式（以abb结束的ab串）看P23例题2.7计算

3、题：由正规式→NFA→DFA→最小化看作业，很多。。。DFA与NFA的区别DFA是NFA的一个特例，与NFA相比，DFA的特点就是它的确定性，即在当前状态下，对同一个字符ch，最多有一个下一状态转移，而NFA有多个下一状态转移。简述从正规式到构造词法分析器的过程1、用正规式对模式进行描述2、为每个正规式构造一个NFA，它识别正规式所表示的正规集3、将构造出的NFA转换成DFA（确定化）4、优化DFA，使其状态数最少（最小化）5、根据优化后的DFA构造词法分析器0、1、2、3型文法与自动机若文法G=（N,T,P,S）的每个产生式α→β中，均有α∈（N∪T）*

4、，且至少含有一个非终结符，β∈（N∪T）*，则称G为0型文法。对0型文法施加以下第i条限制，即可得到i型文法。1、G的任何产生式α→β（S→ε除外）均满足

5、α

6、≤

7、β

8、（

9、x

10、表示x中文法符号的个数）2、G的任何产生式A→β，其中A∈N，β∈（N∪T）*3、G的任何产生式A→α或者A→aB（或者A→Ba），其中A,B∈N，a∈T0型文法→图灵机、1型文法→线性界限自动机、2型文法→下推自动机、3型文法→有限自动机CFG的定义、构成上下文无关文法CFG是一个四元组G=（N,T,P,S）N：非终结符有限集合T：终结符有限集合P：产生式有限集合S：是非终结符，被称为

11、文法的开始符号文法的二义性：原因（缺少文法符号优先级，结核性的规定）如何进行自下而上语法分析自下而上分析的基本思路是，从左到右分析输入序列ω，经过一系列的步骤，最终将ω归约为文法的开始符号，或者发现一个语法错误。归约是推导的逆过程，是一个反复用产生式的左部替换右部、谋求对输入序列进行匹配的过程。句柄的概念设αβδ是文法G的一个句型，若存在S，A，则称β是句型αβδ相对于A的短语。特别的，若有A→β，则称β是句型αβδ相对于产生式A→β的直接短语。一个句型的最左直接短语被称为句柄。大题：给出一个文法（结合制导翻译）画分析树，给出识别活前缀的DFA，是不是L

12、R(1)，分析树上给出值，计算结果P85或者看作业语义规则放在产生式右部符号后，执行规约时翻译（LR分析）P143语义规则的两种形式（基本概念）1、用抽象的属性和运算符号表示的语义规则称为语法制导定义。2、用具体属性和运算表示的语义规则称为翻译方案语法制导定义语法分析，计算属性继承属性在分析树上的计算次序和语法分析形式分析树是否一致继承属性：自上而下。语法分析树：自下而上。中间代码简介特性，生成原因生成原因：源代码与目标代码逻辑结构差别大，用语法制导翻译方法机械生成的代码往往是繁琐、重复和低效的。因此需要中间代码，目的是便于编译器的开发移植和代码的优化

13、。特性：1、便于语法制导翻译。2、既与机器指令的结构相近，又与具体机器无关。写后缀式（P165-166）这是根据11班划的重点整理的，我只挑了个人感觉比较重要的部分。我比较务实你们懂的，只挑出了分比较重的，容易考的。答案是我看了两天书的结果，肯定有不全面的地方，很多地方我只把关键句子和关键字敲出来（方便大家做小抄）。我一学期一节课都没上过，一页书都没看，希望大家能发现错误帮我纠正，我可不想考试的时候写错^_^编译原理有很多逻辑性的，这里无法给出，大家还是要看看书的。建议看两天书把记住的删掉，剩下的留下做成小抄（大题一定要看书看作业）。真心不希望任何一个同学挂科

14、，大家加油。（我也装逼挂