下载文档原格式
(1) 简述规范归约的基本思想。
（第五章课件第5张）用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。
(2) 阐述编译程序各个组成部分主要完成的工作。
（课本P2~P4）词法分析的任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。
语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位。
语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译。
优化：在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。
目标代码生成：把中间代码变换成特定机器上的低级语言代码。
(3) 什么是编译器的前端和后端，这样划分有何意义？（课本P7）编译器粗略分为词法分析，语法分析，类型检查，中间代码生成，代码优化，目标代码生成，目标代码优化。
把中间代码生成及之前阶段划分问编译器的前端，那么后端与前端是独立的。
后端只需要一种中间代码表示，可以是三地址代码或四元式等，而这些都与前端生成的方式无关。
也就是不论你前端是用fortran 还是c/c++,只要生成了中间代码表示就可以了，后端是不管你是用哪种语言生成的。
(4) 乔姆斯基把文法分为哪几种类型？对这几种类型文法作简要说明。
（课本P34）把文法分成四种类型：0，1，2，3型。
与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。
0型(短语文法，图灵机)：产生式形如：α→β其中：∈α (VT ⋃ VN)*且至少含有一个非终结符；∈β (VT ⋃ VN)*1型(上下文有关文法，线性界限自动机)：产生式形如：α→β其中：|α| ≤ |β|。
仅Sε→例外，但此时S不得出现在任何产生式的右部。
2型(上下文无关文法，非确定下推自动机)：产生式形如： A →β其中：A∈ VN；∈β (VT ⋃ VN)*。
1．翻译器：能够完成从一种语言到另一种语言的变化软件。
编译器：一种翻译器，它进行语言变换的特点是目标语言比源语言低级。
编译的各个阶段：P2词法分析器——》语法分析器——》语义分析器——》中间代码生成器——》独立于机器的代码优化器——》代码生成器——》依赖于机器的代码优化器2．词法记号：由记号名和属性值构成的二元组，属性值有时不必要。
记号名是代表一类词法单元的抽象名字，如标识符、某个特定的关键字。
记号名是语法分析的输入符号。
通常直接用记号名来引用记号。
模式：记号的模式描述属于该记号的词法单元的形式。
在一个关键字作为一个记号的情况下，它的模式就是构成该关键字的字符序列。
对于标识符和其他一些记号，它们的模式有更复杂的结构并且有很多字符串可以匹配它们。
词法单元：又称单词，是源程序中匹配一个记号模式的字符序列，它由词法分析器标识为该记号的实例。
在大多数编程语言中，关键字、算符、标识符、常数、文字串（字符串）和标点符号都处理为记号。
P16词法错误（概念）P18正规式的定义不确定的有限自动机：P231.一个有限的状态集合S；2.一个输入符号的集合∑（也称输入符号字母表，空串ε绝不会出现在∑中）；3.一个转换函数move：S*(∑∪{ε})→P(S),它把状态和符号（可以是ε）两组映射到一个状态集合。
4.状态s。
是一个唯一的开始状态；5.状态集合F是接受（或终止）状态集合，并且F包含于S；3上下文无关文法定义：P39（1）V T 是一个非空有限集合，其元素称为终结符。
（2）VN是一个非空有限集合，其元素称为非终结符，并有V T∩VN=非空（3）S是一个非终结符，称为开始符号。
（4）P是产生式的有限集合。
概念：句子; 推导；语言；句型P41文法的优点：（1）文法为语言给出了精确的、易于理解的语法说明。
（2）对于某些文法类，可以自动产生高效的分析器。
（3）如果文法设计得当，则它赋予语言的结构对于把源程序翻译成为正确的目标代码和对于错误诊断都是有用的。
编译原理总复习考点1编译程序的流程及其各自的功能词法分析：输入源程序，对源程序构成的字符串进行扫描和分析，识别出一个个的单词，如保留字、标识符、常数、特殊符号等。
如保留字(if、for、while等)、标识符、常数、特殊符号(标点符号、左右括号、运算符等)。
语法分析：根据语言语法规则，把词法分析后的单词合成各类语法单位（语法范畴），“短语”，“句子”，“程序段”，“程序”。
语义分析及中间代码的生成：根据语法结构，分析其含义，并进行初步翻译（生成中间代码），或直接生成目标代码。
“中间代码”是一种含义明确、便于处理的记号系统。
代码优化：优化的任务在于对前阶段产生的中间代码进行加工变换，以期在最后阶段产生出更为高效(节省时间和空间)的目标代码。
目标代码的生成：把中间代码变成特定机器上的机器代码。
这部分涉及到硬件,如各种数据类型变量的存储空间分配，寄存器的调度等。
考点21.了解形式语言的基本概念2.熟悉文法和语言的形式定义3.熟悉语法树和二义性4.熟悉文法的实用限制重点：（1）掌握最左最右推导（2）掌握语法树及其基本概念（3）掌握判断文法是否存在二义性考题形式（1）给出文法句型，画出出语法树，指出句柄，短语，简单......（2）短语。
（3）判断文法是否存在二义性，画出语法树，推导最左和最右推导。
考点3（不建议复习，跳过此考点）1.掌握NFA，DFA2.NFA到DFA的转换3.4.掌握DFA的化简5.掌握正则表达式形式定义考题形式：（1）由正则表达式（2）画出NFA的状态转化图（3）将NFA转换成DFA（4）化简考点4（1）掌握LL（1）分析方法考题形式：（1）判断是否为LL（1）文法（2）消除左递归（3）求select集合（4）如果是LL（1）文法，则画出LL（1）分析表，分析字符串；否则说明不是LL（1）文法的原因 5.9 5.11考点51.掌握LR（0）分析方法2.掌握SLR（1）分析方法考题形式：（1）画出题目文法的LR（0）的DFA，LR（0）分析表（2）判断是否有移进-归约和归约-归约的冲突（3）如果有，则求SLR（1）分析表，分析给出的字符串；否则给出LR（0）的分析表，分析给出的字符串考点6掌握四元式考题形式：给出一段C语言代码，该代码由for循环嵌套if语句，将其翻译成顺序执行的四元式。
1.给出语言{a n b n a m b m | n,m≥0}的一个上下文无关文法。
(6分)解：G[S]：S—>ABA—>aAb |εB—>aBb |ε2.给出语言{1 n 0 m 1 m0 n | n,m≥0}的一个上下文无关文法。
解：G[S]：S—>1S0 | AA—>0A1 |ε3.P48 第6题（5）、（6）.画语法树6、已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i（５）i+(i+i) （６）i+i*i解：(5)语法树：（6）语法树：4.P48第13题直接短语等13、一个上下文无关文法生成句子abbaa的推导树如下：(3)求直接短语解：直接短语有：a ε bP102例题6.1及其分析.( 后加画语法树)例6.1 设文法G[S]为：(1)S—>aAcBe(2)A—>b(3)A—>Ab(4)B—>d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。
步骤符号栈输入符号串动作（1）# abbcde# 移进（2）#a bbcde# 移进（3）#ab bcde# 归约（A—>b）（4）#aA bcde#移进（5）#aAb cde# 归约（A—>Ab）（6）#aA cde# 移进（7）#aAc de# 移进（8）#aAcd e# 归约（B—>d）（9）#aAcB e# 移进（10）#aAcBe # 归约（S—>aAcBe）（11）#S # 接受一、计算分析题（60%）1、正规式→ NFA→ DFA→最简DFAP72第1题（1）、（4）；第一题1、构造下列正规式相应的DFA.（1）1(0|1)*101解：先构造NFA0 1S AA A ABAB AC ABAC A ABZABZ AC AB除S，A外，重新命名其他状态，令AB为B、AC为C、ABZ为D，因为D含有Z（NFA的终态），所以0 1S AA A BB C BC A DD C B(4) b((ab)*|bb)*ab解：先构造NFA得到DFA如下所示：P72第4题（a）4、把下图确定化和最小化解：确定化：a b0 01 101 01 11 0、{1}，其中A为初态，A，B为终态，因此有：a bA B CB B CC A最小化：：初始分划得终态组{A,B}，非终态组{C}Π0：{A,B}，{C}，对终态组进行审查，判断A和B是等价的，故这是最后的划分。
1.简要说明语义分析的基本功能。
答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检查。
2.考虑文法G[S]: S → (T) | a+S | a T → T,S | S 消除文法的左递归及提取公共左因子。
解：消除文法G[S]的左递归：S→(T) | a+S | a T→ST′ T′→,ST′| ε 提取公共左因子：S→(T) | aS′ S′→+S | ε T→ST′T′→,ST′| ε3.按照三种基本控制结构文法将下面的语句翻译成四元式序列：while (A<C ∧B<D) { if(A ≥ 1) C=C+1;else while (A ≤ D)A=A+2;}。
解：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)：100 (j<,A,C,102) 101 (j,_,_,113)102(j<,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j≤,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 11310.短语------令G是一个文法，S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。
15.句柄------一个句型的最左直接短语。
18.素短语------素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。
3．语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。
给定文法G=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的语法树。
这棵树具有下列特征：(1)根节点的标记是开始符号S。
编译原理期末总结复习（经典版）编制人：__________________审核人：__________________审批人：__________________编制单位：__________________编制时间：____年____月____日序言下载提示：该文档是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。
文档下载后可定制修改，请根据实际需要进行调整和使用，谢谢!并且，本店铺为大家提供各种类型的经典范文，如公文写作、报告体会、演讲致辞、党团资料、合同协议、条据文书、诗词歌赋、教学资料、作文大全、其他范文等等，想了解不同范文格式和写法，敬请关注!Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you!In addition, this shop provides you with various types of classic sample essays, such as official document writing, report experience, speeches, party and group materials, contracts and agreements, articles and documents, poems and songs, teaching materials, essay collections, other sample essays, etc. Learn about the different formats and writing styles of sample essays, so stay tuned!编译原理期末总结复习编译原理期末总结复习（精选3篇）编译原理期末总结复习篇1一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。
1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。
（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。
（4）优化器，对中间代码进行优化处理。
（5）目标代码生成器，把中间代码翻译成目标程序。
（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。
（7）出错管理，把错误信息报告给用户。
编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。
（2）。
语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。
（3）语义分析与中间代码产生。
任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
（4）优化。
任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
（5）目标代码生成。
任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。
2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。
b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。
1.编译程序的工作过程一般可包括词法分析、语法分析、语义分析、中间代码产生与优化和目标代码生成等几个阶段，同时还有表格管理和出错处理。
2.LEX是用于词法分析的工具，Y ACC是用于语法分析的工具。
3.解释程序和编译程序的区别在于是否生成目标代码。
4.任一文法终结符集合和非终结符集合的交集是空集。
5.描述程序设计语言语法的BNF方法中，“：：=”表示定义为，“|”表示或，[W]表示W可出现0或1次，｛W｝表示W可出现n（n≥0）次。
6.已知文法G[G]: S→aSb|ab|ε，该文法描述的语言L(G)=｛a n b n|n≥0｝。
7.单词的描述工具有正规文法、正规式和有穷自动机，他们之间存在等价性。
8.高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符和界符。
9.正则式中的“|“表示或，“*”表示闭包。
10.自顶向下语法分析方法会遇到的主要问题有回溯，以及左递归带来的无限循环。
11.算符优先分析法每次归约当前句型的最左素短语，规范归约中每次归约的是当前句型的句柄。
12.对文法G[G]: S→a|b|cTc，T→S|TdS而言，FIRSTVT(T)=｛a,b,c,d｝。
13.活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
14.对文法G[G]: E→E*T|T, T→T+i|i的句子1+2*8+6进行归约后的结果为42（23，42）。
15.在LR(0),SLR(1),LR(1),LALR(1),四种文法中，描述能力最强的是LR(1)。
1.0型文法中每条规则左部至少包含一非终结符（√）。
2.3型文法一定是2型、1型、0型文法（√）。
3.对无二义性文法而言，无论最左推导还是最右推导，同一个句子的语法树是一样的。
4.若一个文法是递归的，则其语言中句子的个数必定是无穷个。
（√）5.文法规则右部的符号一定是终结符。
（×）6.语法树描述的是一个文法。
（×）7.若G是正则文法，则G一定是上下文无关文法。
复习汇总一、第一章概述1.文法与自动机的等价1)0型文法—图灵机2)1型文法—线性有界非确定图灵机3)2型文法—非确定下推自动机4)3型文法—有限状态自动机2.编译技术的应用1)语法制导的结构化编辑器2)程序格式化工具3)软件测试工具4)程序理解工具5)高级语言的翻译工具6)等等3.从面向机器的语言到面向人类的语言（结合第二章第9小点理解）1)面向机器的语言：机器指令，汇编语言2)面向人类的语言：通用程序设计语言，数据查询语言，形式化描述语言（正规式,产生式）等等。
4.各语言的分类（结合第二章第9小点理解）1)过程式语言，面向对象语言：通用程序设计语言。
2)函数语言：面向特点领域的，递归特性。
例如LISP语言3)说明性，非算法式语言：LEX/YACC,SQL。
4)脚本式语言：Shell语言5.语言之间的转换（李静PPT41）1)高级语言之间的转换一般称为预处理或转换。
2)高级语言翻译成汇编语言或机器语言称之为编译。
3)把汇编语言翻译成机器语言称之为汇编。
4)将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之为交叉汇编。
5)把机器语言翻译成汇编语言称之为反汇编。
6)把汇编语言翻译成高级语言称之为反编译。
6.编译器和解释器1)编译器●源程序的翻译和翻译后的程序的运行是两个不同的阶段。
◆编译阶段：用户输入源程序，经过编译器的处理，生成目标程序。
◆目标程序的运行阶段：根据要求输入数据，得出结果。
2)解释器（凡是可以采用编译器的地方均可以采用解释器）●解释器把翻译和运行结合到一起，编译一段源程序，紧接着就执行它。
这种方式称为解释。
7.解释器的优点（对比与编译器）1)具有较好的动态特性。
2)具有较好的移植特性。
8.解释器的缺点（对比于编译器）1)相比于编译器需花费大量的时间。
2)占用更多的内存空间。
9.编译器的工作阶段（结合第二章6小点红色部分理解）1)源程序->词法分析器->语法分析器->语义分析器->中间代码生成器->代码优化器->目标代码生成器->目标代码2)工作过程中的每个阶段均采用了符号表管理器，出错处理器。
