编译原理期末总结
编译原理期末总结第一章编译概述
程序的翻译：源程序：用汇编语言或高级语言编写的程序。
目标程序：用目标语言所表示的程序。（目标语言：可以是介于源语言和机器语言
之间的中间语言，可以是某种机器的机器语言，也可以是某机器的汇编语言）
翻译程序：将源程序转换为目标程序的程序称为翻译程序。它是指各种语言的翻译
器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。
汇编程序：若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这是
的翻译程序就称之为汇编程序。
编译程序：若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称为“编
译”。
编译过程：词法分析（程序）、语法分析（程序）、语义分析及生成中间代码、代码优化、
目标代码生成（生成目标程序）。符号表管理错误处理每个阶段都要有
第二章形式语言的基本知识
符号串：由字母表中的符号组成的任何有穷序列。符号串的连接运算，符号串的幂运算符号串集合的运算：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。符号串集合的乘积，符号串集合的幂运算，符号串集合的闭包运算
文法和语义的定义：文法是对语言结构的定义与描述。
规范推导：最右推导，对于一个推导序列中的每一直接推导，被替换的总是当前符号串中的最右非终结符号。
规范归约：规范推导的逆过程，最左归约。规范归约递归文法：含有递归规则的文法。文法的BNF，EBNF表示
文法的二义性：若一个文法的某句子存在两个不同的最右（最左）推导，则该文法是二义性的，否则是无二义性的。
第三章词法分析
词法分析程序的任务：编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，再由语法分析程序接下去处理。
词法分析程序的手工实现：单词的文法----状态图---流程图---伪码词法分析程序的自动构造：正规式：正规集的描述机制有穷自动机（NFADFA）：正规集的识别机制LEX的实现原理和源程序的基本组成
第四章语法分析
第五章语义分析和中间代码生成
语义分析的任务：根据语义规则对识别出的各种语法成分分析其含义，进行初步翻译，生成相应的中间代码或直接生成目标代码。1.确定数据类型；2.语义检查：动态语义检查（在运行时刻进行），静态语义检查（在编译完成时）；3.识别含义，进行真正的翻译。
属性文法：附加了一组属性和运算（语义）规则的文法。语法制导翻译的过程：将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性值，从而完成预定的翻译工作。
自低向上（语法制导定义）：在产生式规约的同时调用相应的语义子程序自顶向下（翻译方案）：将语义子程序嵌入到每个递归过程中中间代码的目的：便于优化便于移植
中间代码的几种形式：后缀式四元式三元式间接三元式
第六章符号表管理和错误处理
表：编译程序在其工作过程中使用最多的数据结构是表，在这些表中，符号表最为重要，它的生存周期最长，使用最频繁。
作用：1.收集符号的各种信息；2.语义检查的依据；3.目标代码生成阶段地址分配的依据
内容：名字栏+信息栏
符号表的总体组织：多张一张前两种折中符号表项的组织：线性组织排序组织散列组织明确错误处理的两种方法：错误校正和局部化处理
第七章运行时的存储组织与分配
静态存储分配：在编译阶段由编译程序实现对存储空间的管理，为源程序中的变量分配存储单元。在编译时能够确定变量在运行时的数据空间大小，运行时不改变。
动态存储分配：在目标程序运行阶段由目标程序实现对存储空间的组织与管理，为源程序中的变量分配存储单元。在目标程序运行时进行分配，编译时为运行阶段升级好存储组织形式，即每个数据项安排好它在数据区中的相对位置。
活动记录：连接数据单元（联系单元）：静态链，动态链，返回地址；+局部数据区PL0存储分配策略：程序存储器code，数据存储器s，程序地址存储器p，地址寄存器t，指令寄存器i，基本地址寄存器b。
三个联系单元：
SL静态链，指向定义该过程的直接外层过程的活动记录的基地址，以确保变量的正确存取
DL动态链，指向调用该过程前正在运行的那个过程的活动记录的基地址，以确保能返回到调用过程段。
RA返回地址，保存该被调过程返回后的地址，即当时程序的地址寄存器p的值，也就是调用过程指令的下一条指令的地址，用来确保返回到正确的指令地址。
第八章代码优化
代码优化的目的：提高目标代码运行效率时间效率（减少运行时间）空间效率（减少内容容量）
代码优化的分类：局部优化（在基本块内进行优化）循环优化（对循环语句所生成的中间代码进行优化）全局优化（跨越多个基本块的全局范围内的优化，复杂）基本块优化方法：合并常量，删除公共子表达式，删除无用赋值循环优化方法：代码外提，强度削弱，删除归纳变量
第九章目标代码生成
实现一个代码生成器应考虑2个问题如何使生成的目标代码尽可能的短如何充分利用计算机的寄存器，减少目标代码中访问内存的次数明确目标代码的三种不同形式的优缺点可立即执行的机器语言代码待装配的机器语言代码，又称相对目标代码汇编语言代码
扩展阅读：编译原理大总结
《编译原理》期末复习指导
本课程是计算机专业的重要专业课之一，主要介绍程序设计语言编译构造的基本原理和基本实现方法。本课程主要讲授形式语言、有限状态自动机和词法分
析、自顶而下和自底而上的语法分析、中间代码生成、存储器的动态分配与管理、符号表的组织与管理、代码生成、出错恢复等内容。通过本课程学习，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。
一、通过本课程的学习，应使学生达到以下基本要求：
1、正确理解什么是编译程序；了解编译程序工作的基本过程及其各阶段的基本任务；熟悉编译程序总框；了解编译程序的生成过程和构造工具。
2、理解程序语言词法、语法和语义等概念；熟悉高级程序语言一般结构和主要共同特征。正确理解上下文无关文法基本概念，包括：文法的定义、编写、句型、句子、语言、语法树、二义性等；理解三种参数传递方式：传值、传地址、传名的含义。
3、理解词法分析器功能及形式；熟练掌握词法分析器设计的原理，掌握运用状态转换图进行词法分析器设计。
4、正确理解自顶而下分析的基本思想；熟练掌握递归下降分析基本方法：消除左递归，消除回溯，构造递归下降子程序；掌握预测分析程序的基本原理和预测分析表构造；理解LL(1)方法的定义。
5、正确理解自下而上语法分析的基本思想，以及归约、短语、句柄、分析树等概念；掌握算符优先分析基本方法：算符优先表和和算符优先函数构造技术。6、正确理解语法制导翻译基本原理；掌握基于属性文法的处理方法，了解自上而下分析制导翻译基本思想和实现方法。
7、熟悉常见的几种中间语言：四元式、三元式、逆波兰表示；掌握各种语句到四元式的翻译方法，包括：简单算术表达式，布尔表达式，控制语句，数组引用，过程调用等。8、理解符号表的作用及符号表组织和使用方法，了解名字的作用范围，了解符号表中一般应包含的内容。
9、正确理解目标程序运行进存储空间的使用和组织管理方式；理解静态分配和动态存储分配基本思想；掌握FORTRAN存储分配的处理方式；掌握栈式动态分配中活动记录的作用、组织、内容及使用；了解嵌套过程语言程序运行时整个运行栈的内容的组织。
10、正确理解代码优化的定义和各种可能的优化概念；掌握用DAG表示进行局部优化的方法。
11、正确理解代码生成过程的基本问题，理解待用信息、寄存器描述和地址描述等概念；掌握简单代码生成算法、寄存器分配策略。二、文字教材
文字教材是教学媒体的核心，是传递教学信息及学生进行自主学习的基本依据，是整个教学媒体体系的基础。包括主教材、学习指导书和参考资料汇编、教学大纲、课程教学设计方案、复习提要等。1、《编译原理》徐国定编著，高等教育出版社。参考资料：
1、《程序设计语言编译原理（第3版）》陈火旺、刘春林等编著，国防工业出版社。
2、《程序设计语言与编译》龚天富、侯文永编，电子工业出版社。3、《编译原理习题与解析》伍春香编著，清华大学出版社。4、《编译原理》吕映芝张素琴蒋维杜，清华大学版社。
三、教学内容和教学要求第一章概论
主要内容：编译程序，编译过程概述，编译程序的结构，编译程序与程序设计环境，编译程序生成，学习构造编译程序。
重点：编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。第二章形式语言基础主要内容：程序语言定义，初等数据类型，数据结构，高级高级语言的一般特性，程序结构，语句与控制结构，上下文无关文法，语法分析树与二义性。重点：上下文无关文法，程序语言定义参数传递。第三章有限状态自动机和词法分析
主要内容：词法分析器任务，词法分析器设计，正规表达式与有限自动机，词法分析器自动生成。
重点：词法分析器的任务与设计，状态转换图。第四章自顶向下句法分析
主要内容：语法分析器的功能，自上而下语法分析（递归下降分析法，预测分析程序），LL（1）分析法，递归下降分析程序构造，预测分析程序，自上而下分析的错误诊察，语义错误诊察。
重点：递归下降子程序，预测分析表构造，LL(1)文法。第五章自底向上句法分析
主要内容：自下而上语法分析（算符优先分析法），算符优先分析，LR分析器，LR(0)项目集族和LR(0)分析表的构造，SLR分析表的构造，规范LR分析表的构造，出错处理概述，词法分析阶段的错误诊察，语法分析（自下而上）阶段的错误诊察，语法分析器自动产生工具YACC。重点：归约，算符优先表构造，LR分析法。第六章中间代码生成和符号表
主要内容：中间语言，说明语句，赋值语句的翻译，布尔表达式的翻译，控制语句的翻译，过程调用的处理各种常见中间语言形式，各种语句到四元式的翻译。符号表的组织与作用，整理与查找，名字的作用范围，符号表的内容。重点：三种中间语言：四元式、三元式、逆波兰表示；算术表达式的翻译，布尔表达式的翻译，控制语句的翻译。符号表的作用与内容。第七章运行时刻存储和环境管理
主要内容：目标程序运行时的活动，运行时存储器的划分，静态存储管理，简单的栈式存储分配的实现，嵌套过程语言的栈式实现，堆式动态存储分配。重点：静态分配策略和动态分配策略基本思想，嵌套过程语言栈式分配，活动记录、运行时栈的组织。第八章代码生成
主要内容：目标机器模型，一个简单代码生成器，寄存器分配，DAG目标代码，窥孔优化。
重点：简单代码生成器，寄存器分配策略。第九章出错恢复
主要内容：词法分析的出错恢复，LR和LL句法分析的出错恢复重点：错误的恢复方法。
四、考核方式说明
该课程的考核由形成性考核和期末课程考核两部分组成。其中形成性考核成绩由平时作业和上机实验两部分成绩组成,各占总成绩的10%，期末课程考核占总成绩的80%。
平时作业考核：要求学生认真完成平时作业，各办学点应组织作业的批改和成绩的核定。平时作业的成绩评定标准和要求按省电大有关文件执行。上机实验考核：学员必须完成规定的上机实验，并撰写实验报告，由辅导实验的老师批改并评定成绩，学员实验成绩评定单必须加盖承担实验单位的公章方能生效。
课程结业考核：该课程的结业考核在期末进行，采用笔试、闭卷，由省电大统一组织命题，试卷采用百分制，卷面成绩按80%的比例折算计入总成绩。四、考试题型
试题类型包括：选择题，判断题，填空题，简答题，应用题。模拟试题
一、单项选择题
1．把汇编语言程序翻译成机器可执行的目标程序的工作是由______完成的。A．编译器B．解释器C．汇编器D．预处理器2．编译过程中，语法分析器的任务是______。1)分析单词是怎样构成的
2)分析单词串是如何构成语句和说明的3)分析语句和说明是如何构成程序的4)分析程序的结构
A．2和3B．3和4C．2，3和4D．1，2，3和4
3．高级语言编译程序常用的语法分析方法中，递归下降分析法属于______分析方法。
A．自左至右B．自顶向下C．自底向上D．自右向左4．算符优先文法是指_______的文法。
1)没有形如U->…VW…的规则（U，V，W∈Vn）
2)终结符号集Vt中任意两个符号对之间至多有一种优先关系成立。3)没有相同的规则右部。4)没有形如U->ε的规则
A．1，2B．1，2，3C．1，2，3，4D．1，2，45．动态存储分配时，可以采用的分配方法是1)以过程为单位的栈式动态存储分配2)堆存储分配3)最佳分配方法
A．1B．2C．1，2D．1，2，3
二、填空题
1．编译方式和解释方式的根本区别在于__________________。
2．LL（1）分析法中，第一个L的含义是_________________，第二个L的含义是___________________，“1”的含义是____________________。
3．过程调用时，参数的传递方法通常有__________、__________、__________和传名。
4．一个上下文无关文法所含四个组成部分是____________集、______________集、_____________集和______________集。
三、判断题
1．算符优先关系表不一定存在对应的优先函数。…………（）2．每个文法都能改写为LL(1)文法。………………………（）3．符号表由词法分析程序建立，由语法分析程序使用……（）4．上下文无关文法规则的左部一定是非终结符号…………（）5．LL（1）文法有可能是二义性的。…………………………（）
四、简述题
1．简述词法分析阶段的任务。
2．什么是语法制导翻译？
3．什么是素短语？
4．什么是静态存储分配？
5．画图说明编译程序的组成结构。
五、综合应用题1．设文法G(S)：S→(L)|aS|aL→L，S|S
(1)消除左递归和回溯；
(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。
2．已知文法G(E)E→T|E＋TT→F|T*FF→(E)|i
(1)给出句型(T*F＋i)的最右推导及画出语法树；(2)给出句型(T*F＋i)的短语、素短语。参考答案
一、单项选择题题号1答案C二、填空题
1．是否生成目标代码
2．从左向右进行分析，每次进行最左推导，向输入串中查看一个输入符号3．传值，传地址，传结果（顺序可互换）
2C3B4D5C4．终结符、非终结符、开始符号、产生式（顺序可互换）
三、判断题1．√2．×3．×4．√5．×
四、名词解释
1、答:词法分析的基本任务是从左向右扫描每行源程序的符号，识别出单词及其属性，把单词换成统一的内部表示送给语法分析程序。同时还要完成在语法分析之前需要做的工作，如删除注解、空格、换行符等非必要信息，把标识符登录到符号表及某些预加工处理等。
2、答:语法制导翻译就是在进行语法分析的同时，完成语义的分析，即在语法分析的过程中，根据语言的语义定义随时翻译已识别的那部分语法成分的全部含义。
答:有以下特征的短语称为素短语：1)它首先是一个短语。2)它至少含一个终结符号。3)除自身外，不再包含其它素短语。
3、答:如果在编译时就能确定一个程序在运行时所需要的存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并确定每个数据项的存储单元地址，而这些数据项的存储地址在运行时始终不变，这就是静态存储分配。4、答：表格管理词法分析语法分析语义分析中间代码生成代码优化目标代码生成错误处理
五、综合应用题1．解：(1)
S→(L)|aS’S’→S|εL→SL’L’→SL’|ε(2)
FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)}FIRST(L)＝{(，a}FOLLOW(L)＝{)}FIRST(L’)＝{，，ε}FOLLOW(L’〕＝{)}(3)SS’La，()＃S→aS’S→(L)S’→SS’→εS’→SS’→εS’→εL→SL’L→SL’L’L’→εL’→ε2．答：(1)最右推导：
E→T→F→(E)→(E＋T)→(E＋F)→(E＋i)→(T＋i)→(T*F＋i)语法树：ETF(E)E+TTFT*Fi
(2)短语：(T*F＋i)，T*F＋i，T*F，素短语：T*F,i
i
友情提示：本文中关于《编译原理期末总结》给出的范例仅供您参考拓展思维使用，编译原理期末总结：该篇文章建议您自主创作。
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
公文素材库友情提示：本网站所有内容为共享上传提供，不涉及任何商业利益，本站对此不承担任何保证责任！
Copyright © www.bsmz.net Corporation, All Rights Reserved 共享时代 共享你我他 版权所有