编译原理考点

编译原理题库
1. 什么是编译原理？
编译原理是研究将高级程序语言翻译成为机器语言的原理和方法的学科。

2. 编译器的主要功能是什么？
编译器的主要功能包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等。

3. 什么是词法分析？
词法分析是将输入的字符流转化为标记流的过程。

4. 什么是语法分析？
语法分析是将词法分析得到的标记流转化为语法树的过程。

5. 什么是语义分析？
语义分析是对语法树进行解析，检查程序中是否存在语义错误或不符合语言规范的地方。

6. 什么是中间代码生成？
中间代码生成是将语义分析得到的语法树转化为中间表示形式，以便进行后续的代码优化和目标代码生成。

7. 什么是代码优化？
代码优化是对中间代码进行优化，以提高程序的执行效率和空间利用率。

8. 什么是目标代码生成？
目标代码生成是将优化后的中间代码转化为机器语言的过程。

9. 什么是语法制导翻译？
语法制导翻译是一种以语法规则为基础，通过对语法树的遍历和语义规则的应用来进行翻译的方法。

10. 什么是LL(1)文法？
LL(1)文法是一种上下文无关文法，它具有左递归和左因子的特点，并且在进行预测分析时每个非终结符的每个可能产生式都有唯一的选择。

编译原理知识点
1.1 翻译程序的三种方式
1.编译：将高级语言编写的源程序翻译成等价的机器语言或汇编语言。

2.解释：将高级语言编写的源程序翻译一句执行一句，不生成目标文件，直接执行源代码文件。

3.汇编：用汇编语言编写的源程序翻译成与之等价的机器语言。

1.2 编译程序的五个阶段
1.词法分析：对源程序的字符串进行扫描和分解，识别出每个单词符号。

2.语法分析：根据语言的语法规则，把单词符号分解成各类语法单位。

3.语义分析与中间代码生成：对各种语法范畴进行静态语义检查，若正确则进行中间代码翻译。

4.代码优化：遵循程序的等价变换规则。

5.目标代码生成：将中间代码变换成特定机器上的低级语言代码。

2.1.1 字母表
1.定义：字母表是有穷非空的符号集合。

2.表示：通常用字母表大写字母A，B，…Z和希腊字母Σ表示。

eg：A={0,1}，Σ={a,b,c,d}
3.说明
1）字母表包含了语言中所允许出现的一切符号。

2）字母表中的符号也称字符。

2.1.2 符号串
1.定义：由字母表中的符号组成的有穷序列。

2.表示：通常由t，u，v，w，x，y，z等小写英文字母来表示。

3.说明
1）符号串由构成的符号的种类、数量、顺序共同决定。

2）不包含任何符号的符号串称为空符号串，简称空串，用ε表示。

4.对于给定的字母表Σ，符号串的递归定义如下：
1）ε是Σ上的一个符号串。

2）若x是Σ上的符号串，a是Σ的符号，则xa是Σ上的符号串。

并规定。

编译原理重点第一章1.编译程序是计算机系统经典、核心的系统软件2.计算机需要把高级编程语言的程序翻译成机器语言代码或汇编语言才能运行3.如果源语言是高级编程语言，目标语言是机器代码和汇编语言这样的低级语言，这类翻译程序就叫做编译程序或编译器4.运行高级语言程序的另一种方式是解释执行，它需要的翻译程序不是编译程序，而是解释程序5.解释程序不产生源程序的目标代码，而是对源程序逐条语句进行分析6.Basic和多数脚本语言都是按照解释方式运行的7.解释方式的主要优点是便于对源程序进行调试和修改，但是其加工过程降低了程序的运行效率8.Java语言同时具有编译执行方式和解释执行方式9.9．计算机程序的编译过程类似，一般分为五个阶段：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成10.词法分析的任务是逐步地扫描和分解构成源程序的字符串，识别出一个一个的单词符号或符号11.语法分析的任务是在词法分析的基础上12.语法分析不考虑语义，形式上构成13.语义分析的任务是检查程序语义的正确性，解释程序结构的含义14.语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。

15.语义分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。

所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序16.代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码17.编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序18.编译程序结构包括五个基本功能模块和两个辅助模块19.编译划分成前端和后端。

20.编译前端只依赖于源程序，独立于目标计算机。

编译前端的工作包括词法分析、语法分析、语义分析、中间代码生成、及其优化，文法错误的处理和符号表的组织也在编译前端完成。

编译原理要点整理//红色字体标注的是重点中的重点，大题的归宿第一章引论1.翻译器，编译器的定义2.编译器工作步骤和流程3.编译器前端后端的概念，理解为什么要有前端后端4.“遍”的概念第二章词法分析1.词法分析器的定义2.词法分析器所要完成的任务3.记号，模式，词法单元概念区分4.串的运算（和，连接，指数，闭包，正闭包）5.正规定义6.转换图（注意开始状态和结束状态以及需要将指针回退的状态）7.不确定的有限自动机（NFA）定义8.确定的有限自动机（DFA）定义9.从正规式到NFA（明确通过正规式如何构造连接运算，和运算，闭包运算的NFA）10.此方法产生的NFA的性质11.从NFA到DFA（子集构造法）12.DFA的化简（合并不可区别状态）13.从语言描述直接到DFA14.了解Lex学完本章：能语言描述改写成正规定义，能将正规定义转化为语言描述，给出一个正规式，能转换成相应的NFA，DFA并化简。

第三章语法分析1.上下文无关文法定义2.区分句子和句型3.最左推导&& 最右推导4.分析树5.文法二义性6.消除左递归&& 提左因子7.了解语言鸟瞰（0型文法：短语文法；1型文法：上下文有关文法；2型文法：上下文无关文法；3型文法：正规式）8.FIRST集合&& FOLLOW集合定义及计算方法9.LL（1）文法定义10.了解自上而下的递归下降的预测分析11.自上而下非递归的预测分析（详细明确预测分析器接受某一输入串时的具体过程，明确栈如何变化，输入输出如何变化）12.预测分析表的构造13.句柄的概念14.自下而上的分析方法：用栈实现移近-归约分析（详细明确预测分析器接受某一输入串时的具体过程，明确栈如何变化，输入输出如何变化）15.LR文法和LR分析算法16.构造SLR分析表（从文法构造识别活前缀的DFA（LR（0）项目集规范族），从DFA构造SLR分析表）17.构造规范的LR分析表（从文法构造识别活前缀的DFA（LR（1）项目集规范族），从DFA构造规范的LR分析表）18.构造LALR分析表（从文法构造识别活前缀的DFA（合并同心的LR（1）项目集），从DFA构造规范的LR分析表）（合并同心项目集可能会引起归约-归约冲突，不会引起新的移进-归约冲突）学完本章：能计算FIRST集合和FOLLOW集合；给定一个文法，能判断是否是LL(1)文法，并为其构造分析表；能构造LR(1)文法的三种预测分析表；明确移近归约分析中的每一个步骤，明确栈如何变化。

第一章1. 程序设计语言是人与计算机联系的工具，通过程序设计语言指挥计算机按照自己的意志进行运算和操作显示信息和输出运算结果。

2. 最早的计算机程序设计语言是机器语言(指令系统)。

机器语言中的指令都是用二进制代码直接表示的。

3. 机器语言和符号语言以及汇编语言都是低级程序设计语言。

4. 1954年FORTRAN I语言的问世标志计算机高级程序设计语言的诞生。

5. 计算机高级程序设计语言独立于机器，比较接近于自然语言，容易学习掌握,编写程序效率高,编写的程序易读易理解易移植。

6. 翻译程序：将高级语言编写的程序翻译成机器语言。

7. 编译程序的工作过程：编译程序这要功能是将源程序翻译成等价的目标程序，这个翻译过程分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

8. 编译程序的重要意义在于它使高级语言独立于机器语言，使程序员用高级语言编写程序时不必考虑那些直接与机器有关的琐碎的环节，这些细节由编译程序区处理。

9. 编译程序包括：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序以及表格处理程序和出错处理程序。

10.编译程序的组织方式：编译过程分为六个阶段,改划分是编译程序的逻辑组织方式。

编译过程分为前端和后端。

前端包括词法分析、语法分析、语义分析、中间代码生成、代码优化。

后端包括目标代码生成,依赖于计算机的硬件系统和机器指令系统。

这种组织方式便于编译程序的移植，如果移植到不同类型的机器上只需修改编译程序的后端即可。

11.翻译方式：编译方式和解释方式。

12.源程序：用高级语言编写的程序。

源程序是编译程序加工的对象。

13.编译方式：先将源程序翻译成汇编语言程序或机器语言程序（目标程序），然后再执行。

这个翻译程序为编译程序.14.编译方式中源程序的编译和目标程序的运行时分成两个阶段完成的。

编译所的目标程序计算机暂时不能执行,必须由连接装配程序将目标程序和编译程序及系统子程序连接成一个可执行程序,这个可执行程序可直接被计算机执行。

《编译原理》知识点总结目录第一章引论第二章高级语言及其语法描述第三章语法分析——自上而下分析第四章属性文法和语法制导翻译第五章语义分析和中间代码产生第六章优化第一章引论一．编译程序(compiler):把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序二．编译程序的工作的五个阶段:词法分析、语法分析、中间代码产生、优化、目标代码产生1.词法分析任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。

依循的原则：构词规则描述工具：有限自动机FOR I := 1 TO 100 DO保留字标识符等符整常数保留字整常数保留字2.语法分析任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。

依循的原则：语法规则述工具：上下文无关文法3.语义分析与中间代码产生任务:对各类不同语法范畴按语言的语义进行初步翻译。

（变量是否定义、类型是否正确等）依循的原则：语义规则中间代码:三元式，四元式，逆波兰记号，树形结构等。

是一种独立于具体硬件的记号系统。

例：将Z:=X + 0.618 * Y 翻译成四元式为(1) * 0.618 Y T1(2) + X T1 T2(3) := T2 _ Z4. 优化任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。

依循的原则：程序的等价变换规则FOR K:=1 TO 100 DOBEGINM := I + 10 * K;N := J + 10 * K;END4.目标代码产生任务: 把中间代码变换成特定机器上的目标代码。

依赖于硬件系统结构和机器指令的含义目标代码三种形式:a)绝对指令代码: 可直接运行b)可重新定位指令代码: 需要连接装配c)汇编指令代码: 需要进行汇编第二章高级语言及其语法描述2.1.1语法词法规则：单词符号的形成规则。

a)单词符号是语言中具有独立意义的最基本结构。

编译原理知识点(总7页) -CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除1.解释程序：不生成目标代码编译程序：生成目标代码2.编译程序组成：8个分析< 前端 >：(词法分析程序、语法分析程序、语义分析程序、中间代码生成程序)综合< 后端 >：（代码优化程序、目标代码生成程序）贯穿始末：表格管理程序、出错处理程序3.文法四元组：终结符号集合Vt 、非终结符号集合Vn、产生式集合P、识别符号(开始符号)SV T∩V N＝Φ文法 -> 语言（推导、规约）唯一；语言 -> 文法（凑规则）不唯一。

4.文法分类：0型文法(短语结构文法)：左侧至少含有一个非终结符1型文法(上下文有关文法)：左侧长度 <= 右侧长度 S->ε除外， S不能出现在右侧2型文法(上下文无关文法)：左侧只能有一个非终结符 ( 语法分析 )3型文法(正规文法)：A-> aB A->a 右线性； ( 词法分析 )A->Ba 或A->a 左线性（看非终结符位置）5.A*＝ A0 ∪A+ A0 ＝{ε} != { } ＝Φ空集A+ ＝ AA* ＝ A*A6.句型：符号串x是从识别符号S推导出来的，x称为一个句型句子：x仅由终结符号组成，仅含终结符号的句型是一个句子短语：子树的末端（叶子）从左至右连成的串（包括整棵语法树）简单子树：只含有单层分枝的子树直接短语( 简单短语 )：由简单子树的叶子组成句柄：最左边的直接短语（不一定含终结符）素短语：至少含有一个终结符的短语，并且除它自身之外不再含任何更小的素短语最左素短语：最左边的素短语短语：P（相对于T、E）、 P+T（相对于E）、i（相对于P、F）、P+T+i（相对于E）直接短语：P、i 句柄：P (最左边的直接短语)素短语：P+T 、i （至少含有一个终结符的短语）最左素短语：P+T7.二义性文法：有两个不同的最左推导或有两个不同的最右推导或能产生两棵语法树8.文法产生式正规式规则1 A xB B y A = xy规则2 A xA|y A = x*y 右线性A Ax|y A = yx* 左线性规则3 A x A y A = x|y9.DFA 初态唯一，转换函数为单值映射表示方式：转移矩阵、状态转换图状态转换图上若存在一条从初态到某一终态的道路，且这条路上所有弧的标记符连成的字符串为t，则称t被DFA接受。

编译原理重点第⼀章1. 机器语⾔：计算机能执⾏的语⾔。

2. 翻译器：能够完成⼀种语⾔到另⼀种语⾔的转换的软件。

3. 源语⾔：需要翻译的语⾔。

4.⽬标语⾔：被翻译成的语⾔。

编译的各阶段：每个阶段的输⼊输出（注意顺序）字符流第⼆章1. 词法分析：词法分析是编译的第⼀阶段，它的主要任务是扫描输⼊字符流，产⽣⽤于词法分析的词法记号序列。

源程序2. 词法记号：由记号名和属性值构成的⼆元组，属性值有时不必要。

记号名是代表⼀类词法单元的抽象名字，如标识符、某个特定的关键字。

3. 模式：记号的模式描述属于该记号的词法单元的形式。

在⼀个关键字作为⼀个记号的情况下，它的模式就是构成该关键字的字符序列。

4.词法单元：单词，是源程序中匹配⼀个记号模式的字符序列，它有词法分析器标识为该记号的实例。

5.例2.1Position = initial + rate * 60 的记号⽤⼆元组序列表⽰：-------唯⼀的，所以可以省略属性值6.字母表：表⽰符号的有限集合。

7.串：字母表中符号的⼜穷序列。

8.串的长度：串s的长度是出现在s中的符号的个数，写为|s|；空串长度为0 记为ε。

9.语⾔：表⽰字母表上的⼀个串集，属于该语⾔的串称为该语⾔的句⼦或字。

10.P17：表2.2语⾔运算的定义，例2.2、例2.3、表2.3正规式的代数定理11.P23:不确定的有限⾃动机(NFA)、P24：确定的有限⾃动机(DFA)-------NFA—DFA转化、DFA 化简。

12.P36—37: 习题2.3、2.7、2.8、2.11、2.12.● 2.3叙述由下列正规式描述的语⾔0（0|1）*0—以0开头和结尾的，长度⾄少是2的01串。

（（ε|0）1*）*—所有的01串。

（0|1）*0（0|1）（0|1）—倒数第3位是0的01串。

0*10*10*10*—含有3个1的01串。

（00|11）*（（01|10）（00|11）*（01|10）（00|11）*）* —含有偶数个0和偶数个1的01串。

复习汇总一、第一章概述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)工作过程中的每个阶段均采用了符号表管理器，出错处理器。