完整版编译原理名词解释

编译程序是一种程序，它把高级语言编写的源程序翻译成与之在逻辑上等价的机器语言或汇编语言的目标程序。

一个高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段。

如果编译生成的目标程序是汇编语言形式，那么在编译与运行阶段之间还要添加一个汇编阶段。

解释程序也是一种翻译程序，它将源程序作为输入，一条语句一条语句地读入并解释执行。

解释程序与编译程序的主要区别是：编译程序是将源程序翻译成目标程序后再执行该目标程序，而解释程序则是逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不源程序产生目标程序。

析阶段、语义分析和中间代码生成阶段、优化阶段和目标代码生成阶段。

词法分析的任务是对构成源程序的字符串进行扫描和分解，根据语言的词法规则识别出一个个具有独立意义的单词；语法分析的任务是在词法分析的基础上，根据语言的语法规则（文法规则）从单词符号串中识别出各种语法单位并进行语法检查；语义分析和中间代码生成阶段的任务是首先对每种语法单位进行静态语义检查，然后分析其含义，并用另一种语言形式来描述这种语义即生成中间代码；优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效（节省时间和空间）的目标代码；的任务是把中间代码（或经优化处、理之后）变换成特编译程序结构示意图定机器上的机器语言程序或汇编语言程序，实现最终的翻译工作。

形式化的方法：用一整套带有严格规定的符号体系来描述问题的方法。

标识符：以字母打头的字母数字串字母表：是元素的非空有穷集合。

字符：字母表中的元素称为符号，或称为字符。

可以是字母、数字和其他符号。

符号串的运算：符号串的连接、集合的乘积、符号串的幂运算、集合的幂运算、集合A的正闭包A+与闭包A*形式语言：字母表上所有的字符按照某种规则所组成的集合。

句子：均对应与字母表中的符号串。

文法：是规则的非空有穷集合（描述语言的文法不唯一）文法四元组：G[S]=(V N，V T，P，S) V N ：非终结符集V T：终结符集（V N ^ V T=空集）P：产生式集S：文法的开始符号直接推导：在推导过程中只使用了一个产生式。

第7 题证明下述文法G[〈表达式〉]是二义的。

〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/答案：可为句子a+a*a 构造两个不同的最右推导:最右推导1 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉a=>〈表达式〉* a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a最右推导2 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a第8 题文法G[S]为：S→Ac|aB A→ab B→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc (2)S=>aB=>abc即存在两不同的最右推导。

所以，该文法是二义的。

或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。

第9 题考虑下面上下文无关文法：S→SS*|SS+|a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。

(2)G[S]的语言是什么？答案：(1)此文法生成串aa+a*的最右推导如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。

第10 题文法S→S(S)S|ε(1) 生成的语言是什么？(2) 该文法是二义的吗？说明理由。

答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。

第11 题令文法G[E]为：E→T|E+T|E-T T→F|T*F|T/F F→(E)|i证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。

5.最左推导：任何一步α=>β都是对α中的最右非终结符替换。

6.语法：一组规则，用它可形成和产生一组合式的程序。

7.文法：描述语言的语法结构的形式规则。

8.基本块：指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。

10.短语：令G 是一个文法，S 划文法的开始符号，假定αβδ是文法G 的一个句型，如果有S αAδ且A β，则称β是句型αβδ相对非终结符A 的短语。

12.规范句型：由规范推导所得到的句型。

13.扫描器：执行词法分析的程序。

15.句柄：一个句型的最左直接短语。

16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。

18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。

20.语义：定义程序的意义的一组规则。

三种级别：局部优化、循环优化、全局优化21．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。

23．语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。

给定文法G=(V N ，V T ，P ，S)，对于G 的任何句型都能构造与之关联的语法树。

这棵树具有下列特征：(1)根节点的标记是开始符号S 。

(2)每个节点的标记都是V 中的一个符号。

(3)若一棵子树的根节点为A ，且其所有直接子孙的标记从左向右的排列次序为A 1A 2…A R ，那么A →A 1A 2…A R 一定是P 中的一条产生式。

(4)若一标记为A 的节点至少有一个除它以外的子孙，则A ∈V N 。

(5)若树的所有叶节点上的标记从左到右排列为字符串w ，则w 是文法G 的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。

第一章引论主要内容：编译原理的基本概念、定义、编译原理的应用发展和现状。

重点：编译程序工作的基本构成及各阶段的基本任务，具体要求：理解什么是编译程序，了解各编译程序的基本构成及各阶段的基本任务，编译程序总框，了解编译程序生成过程和构造工具。

一、名词解释1、编译程序：能够把用各种高级语言书写的源程序翻译成某种等价的目标程序的翻译程序。

2、遍：指编译程序对源程序或中间代码程序从头到尾扫描一次。

3、静态分配：在编译时就能够安排好目标程序运行时的全部数据空间。

二、问答题1、简述编译程序的结构？答：编译程序包括词法分析、语法分析、中间代码生成、优化，目标代码产生五个阶段，上述各阶段中还要进行表格处理和出错处理的工作。

2、编译程序可分成哪几个阶段？它们之间的关系如何？答：编译程序可分为五个阶段：词法分析、语法分析、中间代码生成、优化、目标代码生成。

上述五个阶段之间每个阶段输出为作下一阶段的输入，第一阶段的输入是源程序，最后阶段的输出是目标代码程序。

注意：编译过程中，阶段的划分和遍的划分不一定相同第二章高级程序语言概述主要内容：程序语言定义、初等数据类型、数据结构、表达式、语句、高级语言的一般特征及程序语言的语法描述。

重点：程序语言定义具体要求：理解程序语言的词法、语法和语义等概念；熟悉高级程序语言的一般结构和主要共同特征。

一、填空题1、程序语言是由（语法）和（语义）两方面定义的。

2、一个名字的属性包括（类型）和（作用域）3、目标代码一般有三种形式：能够立即执行的机器语言代码，（待装配的机器语言模块）和（汇编语言代码）4、语义：定义一个程序的意义的（一组规则）5、2型文法又称为（上下文无关文法），3型文法又为（正规文法）二、是非题1、虽然名字都是用标识符表示的，但名字和标识符有着本质的区别（对）2、各种名字都是用标识符表示的，所以名字和标识没有本质的区别（错）3、数组元素的地址计算与数组的存储方式没有关系（错）4、语法是指程序的含义（错）5、因名字都是用标识符表示的，故名字与标识符没有区别（错）第三章词法分析主要内容：词法分析器的任务、词法分析器的设计、正规表达式与有限自动机、词法分析器的自动生成。

《编译原理》复习题集1．名词解释短语句柄文法上下文无关文法LL（1）文法LR（1）文法语法分析无环路有向图(DAG)后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言（中间表示）2．简答题(1)编译程序和高级语言有什么区别?(2)编译程序的工作分为那几个阶段?(3)简述自下而上的分析方法。

(4)目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？(5)何谓优化？按所涉及的程序范围可分为哪几级优化？(6)简述代码优化的目的和意义。

3．叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。

( 1 | 01 )* 0*4．Pascal语言无符号数的正规定义如下：num→digit+ (.digit+)? (E(+|-)? digit+)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。

5．画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。

6．用状态转换图表示接收(a|b)*aa的确定的有限自动机。

7．处于/* 和 */之间的串构成注解，注解中间没有*/。

画出接受这种注解的DFA的状态转换图。

8．某操作系统下合法的文件名为device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。

9．构造一个DFA，它接受∑={0, 1}上0和1的个数都是偶数的字符串。

10．设有非确定的有自限动机 NFA M=({A，B，C}，{0，1}，δ，{A}，{C})，其中：δ(A，0)={C} δ (A，1)={A，B} δ (B，1)={C} δ (C，1)={C}。

请画出状态转换距阵和状态转换图。

11．设L⊆ {a,b,c}* 是满足下述条件的符号串构成的语言：(1)若出现a ，则其后至少紧跟两个c ；(2)若出现b ，其后至少紧跟一个c 。

《编译原理》复习题集1．名词解释短语句柄文法上下文无关文法LL（1）文法LR（1）文法语法分析无环路有向图(DAG)后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言（中间表示）2．简答题(1)编译程序和高级语言有什么区别?(2)编译程序的工作分为那几个阶段?(3)简述自下而上的分析方法。

(4)目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？(5)何谓优化？按所涉及的程序范围可分为哪几级优化？(6)简述代码优化的目的和意义。

3．叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。

( 1 | 01 )* 0*4．Pascal语言无符号数的正规定义如下：num→digit+ (.digit+)? (E(+|-)? digit+)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。

5．画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。

6．用状态转换图表示接收(a|b)*aa的确定的有限自动机。

7．处于/* 和 */之间的串构成注解，注解中间没有*/。

画出接受这种注解的DFA的状态转换图。

8．某操作系统下合法的文件名为device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。

9．构造一个DFA，它接受∑={0, 1}上0和1的个数都是偶数的字符串。

10．设有非确定的有自限动机 NFA M=({A，B，C}，{0，1}，δ，{A}，{C})，其中：δ(A，0)={C} δ (A，1)={A，B} δ (B，1)={C} δ (C，1)={C}。

请画出状态转换距阵和状态转换图。

11．设L⊆ {a,b,c}* 是满足下述条件的符号串构成的语言：(1)若出现a ，则其后至少紧跟两个c ；(2)若出现b ，其后至少紧跟一个c 。

1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。

（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。

（4）优化器，对中间代码进行优化处理。

（5）目标代码生成器，把中间代码翻译成目标程序。

（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。

（7）出错管理，把错误信息报告给用户。

编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。

（2）。

语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。

（3）语义分析与中间代码产生。

任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

（4）优化。

任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

（5）目标代码生成。

任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。

2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。

b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。

编译原理编译原理编译器是什么？知识树基本过程词法分析语言正则语言正则定义如何让计算机识别用正则表达式定义的语言NFA 非确定有限自动机DFA 确定有限自动机正则表达式转 NFA直接用 NFA 识别语言直接从正则表达式转 DFA最小化 DFA 的算法语法分析语法的形式化：上下文无关文法推导推导 derivation字符串符号文法语法分析树文法的二义性文法二义性的消除消除左递归消除直接的左递归消除间接的左递归计算 first() 集合计算 follow(A) 集合LL(1) 文法的分析表自底向上的文法分析SLR 文法LR(0) 项扩充文法自动机的过程Closure of Item SetsSLR 分析表的构建（重点）LR(1) 文法构造 LR(1) 分析表缺点LALR 文法语法制导定义基本思想举例语法制导定义继承属性翻译模式再次举例：中缀转后缀扩展文法扩展语法树通过自顶向下的分析来实现先序遍历实现先序遍历Evaluation Order and Dependency Graphs 显式的语法分析树S-属性制导定义L-属性制导定义需要满足三条规则：语义分析和中间代码生成Introduction3 地址代码1. 类型和声明举例来说明翻译过程2. 赋值和表达式类型检查3. 布尔表达式和流控制流控制的语法制导定义布尔表达式的语法制导定义运行时环境内存管理stack 和活动记录活动树活动记录（帧）进程内通信堆管理多线程垃圾回收代码生成指令选择寄存器分配和赋值指令调度抽象目标状态机指令集基本块流图生存期和后续使用信息简单代码生成器代码优化窥孔优化局部优化控制流分析和循环优化消除共同子表达式✔编译器是什么？编译器是一个程序，主要是用来把源程序转换成另外一种计算机语言的程序。

语言编译的全过程：✔知识树编译原理正则语言识别 T oken上下文无关文法CFG 构建语法分析树语法制导翻译生成中间代码代码优化代码生成编译原理是一种语言处理器，它完成了很多工作。

《编译原理》课程复习资料一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。

[ ]2.一个句型的直接短语是唯一的。

[ ]3.已经证明文法的二义性是可判定的。

[ ]4.每个基本块可用一个DAG表示。

[ ]5.每个过程的活动记录的体积在编译时可静态确定。

[ ]6.2型文法一定是3 型文法。

[ ]7.一个句型一定句子。

[ ]8.算符优先分析法每次都是对句柄进行归约。

[ ]9.采用三元式实现三地址代码时，不利于对中间代码进行优化。

[ ]10.编译过程中，语法分析器的任务是分析单词是怎样构成的。

[ ]11.一个优先表一定存在相应的优先函数。

[ ]12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

[ ]13.递归下降分析法是一种自下而上分析法。

[ ]14.并不是每个文法都能改写成 LL(1)文法。

[ ]15.每个基本块只有一个入口和一个出口。

[ ]16.一个 LL(1)文法一定是无二义的。

[ ]17.逆波兰法表示的表达试亦称前缀式。

[ ]18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

[ ]19.正规文法产生的语言都可以用上下文无关文法来描述。

[ ]20.一个优先表一定存在相应的优先函数。

[ ]21.3型文法一定是2 型文法。

[ ]22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。

[ ]二、填空题：1. 称为规范推导。

2.编译过程可分为，，，和五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。

4.从功能上说，程序语言的语句大体可分为语句和语句两大类。

5.语法分析器的输入是，其输出是。

6.扫描器的任务是从中识别出一个个。

7.符号表中的信息栏中登记了每个名字的有关的性质，如等等。

8.一个过程相应的DISPLAY表的内容为。

9.一个句型的最左直接短语称为句型的。

10.常用的两种动态存贮分配办法是动态分配和动态分配。