编译原理复习

编译原理复习

一、选择

1、构造编译程序应掌握（）

A.源程序

B.目标文件

C.编译方法

D.以上三项2、编译程序绝大多数时间花在（）上

A.出错处理

B.词法分析

C.目标代码生成

D.表格管理3、编译程序是对（）

A.汇编程序的翻译

B.高级语言程序的解释执行

C.机器语言的执行

D.高级语言的翻译4、词法分析器的输出结果是（）

A.单词的种别编码

B.单词在符号表中的位置

C.单词的种别编码和自身值

D.单词自身值5、正规式M1和M2等价是指（）A.M1和M2的状态数相等B.M1和M22的有向变条数相等C.M1和M2所识别的语言集相等D.M1和M2状态数和有向边条数6、DFAM接受的字集为（）A.以0开头的二进制数组成的集合B.以0结尾的二进制数组成的集合C.含奇数个0的二进制数组成的集合D.含偶数个0的二进制数组成的集合7、文法G[S]:S→某S某|y所识别的语言是（）

A.某y某

B.（某y某）某

C.某ny某n（n≥0）

D.某ny某n8、如果文法G[S]是无二义的，则它的任何句子α（）A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同

D.可能存在两个不同的最左推导，但它们对应的语法树相同9、采用自顶向下分析，必须（）

A.消除左递归

B.消除右递归

C.消除回溯

D.提取公共左因子10、设a、b、c是文法的终结符，且满足有限关系a〓b和b〓c，则（）A.必有a〓cB.必有c〓aC.必有b〓aD.a~c都不一定成立11、在规范规约中，用（）

开刻画可归约串A.直接短语B.句柄C.最左素短语D.素短语12、若a为

终结符，则A→α·aβ为（）项目A.规约B.移近C.接受D.待约

13、若项目集合Ik含有A→α·，则在状态k时，仅当面临的输入

符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是（）

https://www.sodocs.net/doc/ae19220515.html,LR文法

B.LR(0)文法

C.LR(1)文法

D.SLR(1)文法14、同心集合

并有可能产生新的（）冲突

A.指示器

B.临时变量

C.符号表

D.程序变量16、间接三元式表示法的

优点为（）

A.采用间接码表，便于优化处理

B.节省存储空间，不便于表的修改

C.便于优化处理，节省存储空间

D.节省存储空间，不便于优化处理17、表

达式（┐A∨B）∧（C∨D）的逆波兰表示为（）

A.┐AB∨∧CD∨

B.A┐B∨CD∨∧

C.AB∨┐CD∨∧

D.A┐B∨∧CD∨18、过程

的DISPLAY表中记录了（）

A.过程的连接数据

B.过程的嵌套层次

C.过程的返回地址

D.过程的入

口地址19、过程P1调用P2是，连接数据不包含（）

A.嵌套层次显示表

B.老SP值

C.返回地址

D.全局DISPLAY表地址

20、堆式动态分配申请和释放存储空间遵守（）原则

A.先请先放

B.先请后放

C.后请先放

D.任意21、.栈式动态分配与管

理在过程返回时应做的工作有（）

A.保护SP

B.恢复SP

C.保护TOP

D.恢复TOP22、如果活动记录中没有DISPLAY表，则说明（）

A.程序中不允许有递归定义的过程

B.程序中不允许有嵌套定义的过

程

C.程序中不允许有嵌套定义的过程，也不允许有递归定义的过程

D.

程序中允许有递归定义的过程，也允许有嵌套定义的过程23、优化可生

成（）的目标代码

A.运行时间较短

B.占用存储空间较小

C.运行时间短但占用内存空间大

D.运行时间短且占用存储空间小24、下列（）优化方法不是针对循环优化进行的

A.强度削弱

B.删除归纳变量

C.删除多余运算

D.代码外提25、基本块

内的优化为（）

A.代码外提，删除归纳变量

B.删除多余运算，删除无用赋值

C.强度

削弱，代码外提D.循环展开，循环合并

26、在程序流图中，我们称具有下述性质（）的节点序列为一个循环

A.它们是非连通的且只有一个入口结点

B.它们是强连通的但有多个入口

结点C.它们是非连通的但有多个入口结点D.它们是强联通的且只有一个

入口结点27、关于必经结点的二元关系，下列叙述中不正确的是（）

A.满足自反性

B.满足传递性

C.满足反对称性

D.满足对称性28、有一

语法制导翻译如下：

S→bAb{print“1”}A→(B{print“2”}A→a{print“3”}B→Aa){pr int“4”}

若输入序列为b(((aa)a)a)b,且采用自底向上的分析方法，则输出序

列为（）A.32224441B.34242421C.12424243D.3444221229、错误的局部化

是（）A．把错误理解成局部的错误B.对错误在局部范围内进行纠结C．当发现错误时，跳过错误所在的语法单位继续分析下去D．当发

现错误时立即停止编译，待用户改正错误后再继续编译二、填空

1、编译程序划分的类型_________

2、编译程序是对__高级语言的翻

译_

3、若文法是无二义的，则规范推导与规范归纳的关系_________

4、

词法分析程序输出的单词符号通常表示成二元式的形式5、语言的目标是

_______，是一个特殊的非终结符6、描述语言L={ab|n≥m≥1}的文法为

__________

7、程序语言的生成系统是_________，而识别系统则是___________8、语法分析器的功能是输入_____________输出_____________9、两个自动

机等价是指DFA和NFA

10、文法四元组G[S]={VTV TSξ}______________11、词法分析器的

输出结果是__________________12、语法分析的方法种类

_________________13、文法符号的属性种类____________________14、

文法G所描述的语言是__________的集合

15、为使编译程序能正确翻译，对程序设计语言必须使用

___________的定义方法

16、LR语法分析法是指_____________扫描输入串和________进行规

范归纳17、首节点是指从它开始到控制流程图中任何一个结点都有一条

通路的结点。18、生成中间代码时所依据的是_____________________19、划分基本块的关键问题是准确定义入口和出口语句

20、错误的局部化是指当发现错误时，跳过错误所在的语法单位继续

分析下去21、基本块是指_____________________

22、基本块的优化方法________，循环优化的方法

______________________________23、优化可生成_____________的目标

代码

24、优化对象所涉及的范围____________________，优化的分类

_______________________

25、一个好的编译程序应具有较强的________或________能力。26、

代码优化所遵循的原则是程序的等价变换原则。

27、动态语义检查需要生成相应的目标代码，它是在运行时进行的。

28、编译生成的目标代码不可能是________。

29、语法制导翻译_________________________________。30、编译

程序是将源程序__________成目标程序后再执行。

31、中间代码

___________________________________________________。32、编译模

型的最后一个阶段是代码生成。

33、在编译程序的全过程中，都需对___________进行频繁地访问，

耗费的时间占很大比例三、简答

1.四类文法的关系与区别

答：由四类文法的定义可知，从0型文法到3型文法逐渐增加限制。

1~3型文法都属于0型文法，2、3型文法不一定属于1型文法（如果存在

形如A→§的产生式，则不属于1型文法），3型文法属于2型文法。

四类文法的区别如下：（1）1型文法中不允许有形如“A→§”的产

生式存在，而2、3型文法则允许形如“A→§”的产生式存在。（2）0、

1型文法的产生式左部

存在含有终结符号的符号串或两个以上的非终结符，而2型和3型文

法的产生式左部只允许是单个的非终结符号。2.中间代码的优化原则答：

等价原则：

有效原则：合算原则：

源程序表格管理目标程序语义分析与中间代码生成器出词法分析器语

法分析器错处优化目标代码生成器理3.编译程序的结构（图）

4.解释程序与编译程序的区别

答：编译程序是将源程序翻译成目标程序后再执行该目标程序；而解

释程序则逐条读出源程序中的语句并解释执行，即在解释程序的执行过程

中并不产生目标程序。典型的解释型高级语言是BASIC语言。5.构造编译

程序应掌握的内容。

答：构造一个编译程序必须掌握下述三方面的内容：

⑴对被编译的源语言（如C、PASCAL等），要深刻理解其结构（语法）和含义。

⑵必须对目标机器的硬件和指令系统有深刻的了解。

⑶必须熟练掌握编译方法，编译方法掌握的如何将直接影响到编译程

序的成败，一个好的编译方法可能得到事半功倍的效果。6.编译程序的工

作过程。

答：编译程序的工作过程是指从输入源程序开始到输出目标程序为止

的整个过程。此过程是非常复杂的。一般来说，整个编译过程可以划分成

五个阶段：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、优化阶段和目标代码生成阶段。

7.堆式存储分配中需解决的问题。

答：对于堆式存储分配来说，需要解决两个问题：一是堆空间的分配，即当运行程序需要一块空间时应分配哪一块给它；另一个问题是分配空间

的回收，由于返回堆的不同空间是按任意次序进行的，所以需要研究专门

的回收分配策略。

8.NFA和DFA的区别。

答：NFA和DFA的区别主要有两点：其一是NFA可以有若干个初始状态，而DFA仅有一个初始状态；其二是NFA的状态转换函数f不是单值函数，而是一个多值函数，即f(i,a)={某些状态的集合}（i∈S），它表示

不能由当前状态和当前输入字符唯一地确定下一个要转换的状态，也即允

许同一个状态对同一个输入字符可以有不同的输出边。四、计算

1.文件G[S]：S→aS|bS|a

构造LR（0）项目集规范族；给出识别活前缀的DFA；构造SLR（1）

分析表，判断是否为SLR(1)文法。

2.表达式（A+B某(C-D)）+E(C-D)^N翻译成：逆波兰式、四元式、三

元式、间

接三元式。

3.程序：I=400J=200L1：J=J+1readI

ifI<5000gotoL2writeJhaltL2:I=I某1

gotoL1

画控制流程图：求各个结点的必经结点集；求回边：求循环。

4.文件G[S]：

S→(L)|aS|aL→L,S|S(1)(S,(a))最右推导，画语法树。

（2）该句型中所有的短语，直接短语、句柄和最左素短语。

5.文件G[S]：

S→S+aT|aT|+aT

T→某aT|某a

(1)aT+a某a某a最右推导，画语法树；

(2)该句型中所有的短语、直接短语、句柄和最左素短语。

6.正规表达式（a|b）某(aa|bb)（a|b）某,(a|b)某aa,求出等价的简化版DFAM.

7.设有基本块：应用DAG进行优化，画出DAG图；假定变量L,M,N在出口之后是活跃的，写出优化后的四元式序列。

编译原理全复习(完整版)

1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？ 答 编译程序总框架 （1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。 （2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。 （3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。 （4）优化器，对中间代码进行优化处理。 （5）目标代码生成器，把中间代码翻译成目标程序。 （6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。 （7）出错管理，把错误信息报告给用户。 编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。 （2）。语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。 （3）语义分析与中间代码产生。任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。 （4）优化。任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。 （5）目标代码生成。任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。 2》．重要概念： a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。 b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等 c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。 d. 遍：就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。

编译原理期末复习题(包含上一份N多答案)

编译原理复习题 一、填空题： 1、编译方式与解释方式的根本区别在于（是否生成目标代码）。 2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。 3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。 4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。 5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。 6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。 7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。 9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。

10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。 11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。 14、在编译程序中安排中间代码生成的目的是（便于代码优化）和（便于目标程序的移植）。 15、表达式-a+b*(-c+d)的逆波兰表示为（a-bc-d+*+ ）。 16、表达式a+b*(c+d/e)的逆波兰表示为（abcde/+*+ ）。 17、表达式a:=a+b*c↑(d/e)/f的逆波兰表示为（aabcde/↑*f/+:= ）。 18、文法符号的属性有（继承属性）和（综合属性）两种。 19、一个文法符号的继承属性是通过语法树中它的（兄弟结点与父）结点的相应文法符号的属性来计算的。 20、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。 21、语法制导的编译程序能同时进行（语法）分析和（语义）分析。 22、编译过程中扫描器所完成的任务是从（源程序）中识别出一个个具有（独

编译原理 复习资料

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一定是上下文无关文法。（√） 8.正则文法、正则式和有限自动机三者都是描述正则集的有力工具，它们的描述能力是等价的。（√） 9.LL（1）分析法必须要求原文法不含左公因子和左递归。（√） 10.对于LR(0)文法，我们可直接从它的项目集规范族和活前缀识别自动机的状态转换函数GO构造了LR分析表。（√） 1.BNF是一种广泛采用的描述（文法）的工具。 2.无符号常数的识别和拼数工作通常在（词法分析）阶段完成。 3.“运算符与运算对象类型不匹配”属于（语义错误） 4.将汇编语言程序翻译成机器可以执行的目标程序的工作由（汇编程序）完成。 5.在汇编过程中，汇编程序能够找到的错误包括（全部语法错误和部分语义错位） 6.由“非终结符→符号串”形式的规则构成的文法是（2型文法） 7.关于短语和句柄，正确的叙述为（直接短评才可能是句柄） 8.同正则式a*b*等价的文法是（G3:S→aS|Sb|ε） 9.文法G[S]:S→xSy|y所描述的语言是（x^nyx^n(n>=0)） 10.若G为一文法，Vt是该文法的终结符号集合，L(G)和Vt^*之间的关系是（L(G)是Vt^* 的子集） 11.有限自动机能够识别（正则文法）

编译原理简单复习

1、画出编译程序的总体结构图，简述其部分的主要功能。 [答案] 编译程序的总框图见下图。 图编译程序的总体结构图 其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号。 语法分析器对单词符号串进行语法分析（根据语法规则进行推导或归纳），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序语句”。 语义分析及中间代码产生器，按照语义规则对语法分析器归纳出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。 优化器对中间代码进行优化处理。其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。 目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件相关的机器能识别的语言，即目标程序，才能在机器上运行。 表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息

也大多从表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断地和表格打交道。 出错处理程序对出现在源程序中的错误进行处理。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户。 2.已知文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 试给出下述表达式的推导及分析树 (1)i; (2)i*i+i (3)i+i*i (4)i+(i+i) [答案] (1)E=>T=>F=>i (2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i (4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i)

编译原理复习汇总

复习汇总 一、第一章概述 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)工作过程中的每个阶段均采用了符号表管理器，出错处理器。10.编译器各阶段的工作过程（结合第二章6小点红色部分理解） 1)源程序通过词法分析器翻译成记号流，记号流通过语法分析产生语 法树，然后根据语法树来进行适当的语义处理，语义分析产生符号 表和中间代码。 2)符号表的格式：标识符，类型，分配的地址。 3)中间代码的格式：操作符，左操作数，右操作数，结果。 4)中间代码的优化：传值的代码可以省略。

编译原理复习

一、选择 1、构造编译程序应掌握（） A.源程序 B.目标文件 C.编译方法 D.以上三项 2、编译程序绝大多数时间花在（）上 A.出错处理 B.词法分析 C.目标代码生成 D.表格管理 3、编译程序是对（） A.汇编程序的翻译 B.高级语言程序的解释执行 C.机器语言的执行 D.高级语言的翻译 4、词法分析器的输出结果是（） A.单词的种别编码 B.单词在符号表中的位置 C.单词的种别编码和自身值 D.单词自身值 5、正规式M1和M2等价是指（） A. M1和M2的状态数相等 B. M1和M22的有向变条数相等 C. M1和M2所识别的语言集相等 D. M1和M2状态数和有向边条数 6、DFA M接受的字集为（） A.以0开头的二进制数组成的集合 B.以0结尾的二进制数组成的集合 C.含奇数个0的二进制数组成的集合 D.含偶数个0的二进制数组成的集合 7、文法G[S]:S→xSx|y所识别的语言是（）

A.xyx B.（xyx）* C.x n yx n（n≥0） D.x n yx n 8、如果文法G[S]是无二义的，则它的任何句子α（） A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能不同 C.最左推导和最右推导必定相同 D.可能存在两个不同的最左推导，但它们对应的语法树相同 9、采用自顶向下分析，必须（） A.消除左递归 B.消除右递归 C.消除回溯 D.提取公共左因子 10、设a、b、c是文法的终结符，且满足有限关系a〓b和b〓c，则（） A.必有a〓c B.必有c〓a C.必有b〓a D.a~c都不一定成立 11、在规范规约中，用（）开刻画可归约串 A.直接短语 B.句柄 C.最左素短语 D.素短语 12、若a为终结符，则A→α·aβ为（）项目 A.规约 B.移近 C.接受 D.待约 13、若项目集合Ik含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是（） https://www.sodocs.net/doc/ae19220515.html,LR文法 B.LR(0)文法 C.LR(1)文法 D.SLR(1)文法 14、同心集合并有可能产生新的（）冲突 A.归约 B.“移进”/“移进” C.“移进”/“归约” D.“归约”/“归约” 15、四元式之间的联系时通过（）实现的 A.指示器 B.临时变量 C.符号表 D.程序变量 16、间接三元式表示法的优点为（）

编译原理课程复习

《编译原理》课程复习 五、计算题： 1、考虑下面程序 ………… V ar a：integer； Procedure S(X)； V ar X：integer； Begin a：＝a＋1； X：＝a＋X End； Begin a：＝5； S(a)； Print(a) End． 试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？ 答：传名：a＝12 传值：a＝6 2、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。 逆波兰表示： abc*＋ab＋/d－ 三元式序列： ①(*，b，c) ②(＋，a，①) ③(＋，a，b) ④(/，②，③) ⑤(－，④，d) 3、已知文法G(S) S→a|∧|(T) T→T，S|S 写出句子((a，a)，a)的规范归约过程及每一步的句柄。 句型归约规则句柄 ((a，a)，a)S→a a ((S，a)，a)T→S S ((T，a)，a)S→a a ((T，S)，a)T→T，S T，S ((S)，a)T→S S ((T)，a)S→S(T)(T) (S，a)T→S S (T，a)S→a a

(T，S)T→T，S T，S (T)S→(T)(T) S 4、写一个文法，使其语言是奇数集，且每个奇数不以0开头。 解：文法G(N)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D 5、设文法G(S)： S→(L)|a S|a L→L，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。 解：S→(L)|aS’ S’→S|ε L→SL’ L’→SL’|ε FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)} FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)} FIRST(L)＝{(，a}FOLLOW(L)＝{ )} FIRST(L’)＝{，，ε}FOLLOW(L’)＝{ }} 6、While a＞0 ∨b＜0do Begin X：＝X＋1； if a＞0 then a：＝a－1 else b：＝b＋1 End； 翻译成四元式序列。 解： (1) (j＞，a，0，5) (2) (j，－，－，3) (3) (j＜，b，0，5) (4) (j，－，－，15) (5) (＋，×，1，T1) (6) (：＝，T1，－，×) (7) (j＞，a，0，9) (8) (j，－，－，12) (9) (－，a，1，T2) (10) (：＝，T2，－，a) (11) (j，－，－，1) (12) (＋，b，1，T3)

计算机编译原理_知识点复习考点归纳总结

三一 文库 （https://www.sodocs.net/doc/ae19220515.html, ）*电大考试* 编译原理名词解释 1.局部优化：局限于基本块范围的优化称。 2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。 3.DISPLAY 表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display 表就是用于登记每个外层过程的最新活动记录起始地址。 5.最左推导：任何一步α=>β都是对α中的最右非终结符替换。 6.语法：一组规则，用它可形成和产生一组合式的程序。 7.文法：描述语言的语法结构的形式规则。 8.基本块：指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。 9.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。 10.短语：令G 是一个文法，S 划文法的开始符号，假定αβδ是文法G 的一个句型，如果有S αAδ且A β，则称β是句型αβδ相对非终结符A 的短语。 11.待用信息：如果在一个基本块中，四元式i 对A 定值，四元式j 要引用A 值，而从i 到j 之间没有A 的其它定值，则称j 是四元式i 的变量A 的待用信息。 12.规范句型：由规范推导所得到的句型。 13.扫描器：执行词法分析的程序。 14.超前搜索：在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。 15.句柄：一个句型的最左直接短语。 16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。 17.规范句型：由规范推导所得到的句型。 18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。 19.语法：是组规则，用它可形成和产生一个合式的程序。 20.语义：定义程序的意义的一组规则。 21.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化 21．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。 22．LL(1)文法 若文法的任何两个产生式A → α | β都满足下面两个条件：（1）FIRST(α ) ⋂ FIRST(β ) = φ；（2）若β ⇒* ε ，那么FIRST(α ) ⋂ FOLLOW( A ) = φ。我们把满足 这两个条件的文法叫做LL(1)文法，其中 的第一个L 代表从左向右扫描输入，第二个L 表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。 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 所产生的句子。 24．LR(0)分析器 所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 25．语言和文法 文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G 定义为四元组的形式：G=(V N ，V T ，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合(非空)；S 是开始符号(或识别符号)。这里，V N ∩V T =∅，S ∈ V N 。V=V N ∪V T ，称为文法G 的字母表，它是出现文法产生式中的一切符号的集合。文法G 所描述的语言用L(G)表示，它由文法G 所产生的全部句子组成，即L(G)={x| S ⇒*x ，其中S 为文法开始符 号，且+ ∈T V x }简单的说，文法描述的语言是该文法一切句子的集合。 26．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。 27．LL(1)文法 若文法的任何两个产生式A → α | β都满足下面两个条件：（1）FIRST(α ) ⋂ FIRST(β ) = φ；（2）若β ⇒* ε ，那么FIRST(α ) ⋂ FOLLOW( A ) = φ。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L 代表从左向右扫描输入，第二个L 表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。 28．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法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 所产生的句子。 29．LR(0)分析器 所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 30．语言和文法 文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G 定义为四元组的形式：G=(V N ，V T ，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合(非空)；S 是开始符号(或识别符号)。这里，V N ∩V T =∅，S ∈ V N 。V=V N ∪V T ，称为文法G 的字母表，它是出现文法产生式中的一切符号的集合。文法G 所描述的语言用L(G)表示，它由文法G 所产生的全部句子组成，即L(G)={x| S ⇒*x ，其中S 为文法开始符 号，且+ ∈T V x }简单的说，文法描述的语言是该文法一切句子的集合。 31.编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成 32.解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。 33.编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 34.解释程序和编译程序的根本区别：是否生成目标代码 35.句子的二义性（这里的二义性是指语法结构上的。）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 36文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 37.LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归)第1个L ：从左到右扫描输入串。第2个L ：生成的是最左推导。1 ：向右看1个输入符号便可决定选择哪个产生式 38．某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 39.文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。 40.一个属性文法(attribute grammar)是一个三元组A=(G, V, F) G ：上下文无关文法。V ：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。F ：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。 41.综合属性:若产生式左部的单非终结符A 的属性值由右部各非终结符的属性值决定,则A 的属性称为综合属。 42.继承属性:若产生式右部符号B 的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B 的属性为继承属性。(1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。(2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。在计算时： 综合属性沿属性语法树向上传递（即传递信息的方向是自下而上）；继承属性沿属性语法树向下传递（即传递信息的方向是自上而下）。 43.语法制导翻译：是指在语法分析过程 中，完成附加在所使用的产生式上的语义规则描述的动作。 44.语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。 45.中间代码（中间语言）：1、是复杂性介于源程序语言和机器语言的一种表示形式。2、一般，快速编译程序直接生成目标代码。3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。 46.何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。 47.为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。(2)便于移植，便于修改，便于进行与机器无关的优化。 48.中间代码的几种形式：逆波兰式（后缀式） ，三地址码（三元式、四元式、间接三元式 ） 49.符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word ）。 50.符号表的功能：（1）收集符号属性 (2) 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据 51.符号的主要属性及作用：1. 符号名 2. 符号的类型 （整型、实型、字符串型等））3. 符号的存储类别（公共、私有）4. 符号的作用域及可视性 （全局、局部） 5. 符号变量的存储分配信息 （静态存储区、动态存储区） 52.存储分配方案策略：静态存储分配；动态存储分配：栈式、 堆式。 53.静态存储分配：1、基本策略：在编译时就安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。2、适用的分配对象：子程序的目标代码段；全局数据目标（全局变量）3、静态存储分配的要求：不允许递归调用，不含有可变数组。FORTRAN 程序是段结构，不允许递归，数据名大小、性质固定。 是典型的静态分配 54.动态存储分配 ：1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。2、两种动态存储分配方式：栈式，堆式栈式动态存储分配策略：将整个程序的数据空间设计为一个栈。【例】在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。 55.过程所需的数据空间包括两部分：一部分是生存期在本过程这次活动中的数据对象。如局部变量、参数单元、临时变量等；另一部分则是用以管理过程活动的记录信息(连接数据)。 56.活动记录（AR ）：一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 (块)叫做一个活动记录。构成：1、临时工作单元；2、局部变量；3、机器状态信息；4、存取链；5、控制链；6、实参；7、返回地址 57.什么是代码优化 所谓优化，就是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少。 58.优化原则：等价原则：经过优化后不应改变程序运行的结果。

编译原理复习资料

编译原理复习资料 一、填空题. 1.编译程序是一种程序，能够将某一种高级语言编写的源程序改造成另一种低级语言编写 的目标程序，它们在逻辑上等价，完成相同的工作。 2.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是_二义性的__。 3.词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单 词符号，并以__单词符号或单词符号表示的源程序_的形式输出。 4.编译程序一般划分为词法分析、语法分析、语义分析、中间代码生成、和代码优化目标 代码生成六个阶段；除此以外,还有两个重要的基本工作,它们是表格管理和出错处理。 5.目前，语法分析方法有两大类，分别为自上向下的分析方法和__自下而上_分析方法。 自上而下的分析方法是从___文法的开始符号__出发，根据文法规则正向推导出给定句子的方法。 6.属性文法是编译技术中用来说明程序设计语言的___语义__的工具。 7.若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程 序称为 ____编译程序___。 8.扫描器（程序）的任务是从_字符串__中识别出一个个_单词符号_。 9.一个LR分析器包括三部分：总控程序、_分析表_和分析栈。 10.自顶向下的语法分析方法的基本思想是：从文法的_开始符号_出发，根据给定的输入串 并按照文法的产生式一步一步的向下进行__正向推导_，试图推导出文法的给力句子__，使之与给定的输入串匹配。 11.按Chomsky分类法，文法被分成___4（0~3型文法）__类。 12.局部优化是在__基本块___范围内进行的一种优化。 13.编译程序是一种＿翻译＿程序，它将某一种高级语言编写的源程序改造成另一种低级语 言编写的目标程序，源程序和目标程序在逻辑上等价，完成相同的工作。 14.编译程序与解释程序的根本区别为__解释程序在执行中不产生目标程序_。 15.语法分析的任务是识别给定的终结符号串是否为给定文法的___句子__。 16.编译程序一般划分为＿词法＿分析、语法分析、＿语义＿分析、中间代码生成、＿代码 优化＿和目标代码生成六个阶段；除此以外,还有两个重要的基本工作,它们是＿表格

编译原理复习题附标准答案

编译原理复习题及答案 一、选择题 1．一个正规语言只能对应( B ) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A] ：A→ε A→aB B→Ab B→a是( A ) A 正规文法 B 二型文法 3．下面说法正确的是( A ) A 一个SLR( 1)文法一定也是LALR ( 1)文法 B 一个LR (1)文法一定也是LALR ( 1)文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL (1)文法的( A ) A 必要条件 B 充分必要条件 5．下面说法正确的是( B ) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是( A ) A 归约速度快 B 对文法限制少 7．一个LR( 1)文法合并同心集后若不是LALR ( 1)文法( B ) A 则可能存在移进/归约冲突 B 则可能存在归约/ 归约冲突 C 则可能存在移进/归约冲突和归约/ 归约冲突 8．下面说法正确的是( A ) A Lex 是一个词法分析器的生成器 B Yacc 是一个语法分析器 9．下面说法正确的是( A ) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C) 。 A 、机器语言的执行 B 、汇编语言的翻译 C 、高级语言的翻译D、高级语言程序的解释执行11．(A) 是一种典型的解释型语言。 A ．BASIC B ．CC．FORTRAND ．PASCAL

把汇编语言程序翻译成机器可执行的目标程序的工作12． 13．14．15．16．17．18．19．20．21． 22．23．24．25． A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 用高级语言编写的程序经编译后产生的程序叫(B) A ．源程序B．目标程序C．连接程序D．解释程序 (C)不是编译程序的组成部分。 A. 词法分析程序 B. 代码生成程序 C.设备管理程序 D.语法分析程序 通常一个编译程序中，不仅包含词法分析，语法分析，语义分析， 中间代码生成，代码优化， 目标代码生成等六个部分，还应包括(C)。矚慫润厲钐瘗睞枥庑赖。 A ．模拟执行器B．解释器C．表格处理和出错处理D．符号执行器 编译程序绝大多数时间花在(D) 上。 A ．出错处理B．词法分析C．目标代码生成D．表格管理 源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 词法分析器的输出结果是(D)。 A 、单词自身值B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 文法：G：S→ xSx | y 所识别的语言是(D)。 A 、xyx B 、(xyx)* C 、x*yx* D、x n yx n (n≥0) 如果文法G 是无二义的，则它的任何句子α(A) A ．最左推导和最右推导对应的语法树必定相同 B ．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D ．可能存在两个不同的最左推导，但它们对应的语法树相同 正则文法(A) 二义性的。 A. 可以是 B. 一定不是 C. 定是 (B) 这样一些语言，它们能被确定的有穷自动机识别， 但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 给定文法 A → bA|ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba 设有文法G[S] ：S S1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有(D) (B)完成的。

编译原理期末考试复习知识点

1.Chomsky把文法分为几种类型？什么是文法的二义性？ 1）分成四种类型，即0型、1型、2型和3型。（1）0型文法：设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。（2）1型文法：若P中的每一个产生式α→β均满足|β|>=|α|，仅仅S->ε除外，则文法G是1型。（3）若P中的每一个产生式α→β满足：α是非终结符，β∈(VN∪VT)*，则此文法称为2型的。（4）若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a∈VT*，则G是3型文法。 2）如果文法G中的某个句子存在不只一棵语法树，则称该句子是二义性的。如果文法含有二义性的句子，则称该文法是二义性的 2. 简述DFA与NFA的区别：DFA每次输入只对应一个结果，而NFA的依次输入可能对应多个结果，形成一个结果集。 3.什么是算符文法？并举例说明 设有文法G，如果G中没有形如A->…BC…的产生式，其中B,C为非终结符，则称G为算符文法。 例如：对于表达式的二义性文法E->E|E-E|E*E|E/E|E↑E|(E)|i 其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法为算符文法。 4.什么是3型文法？什么是文法的语言？ （1）若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a ∈VT*，则G是3型文法。 （2）文法的语言：文法是用于描述语言的语法结构的形式规则。文法描述的语言是该文法一切句子的集合。一个文法所描述的语言是唯一的。 5. 什么是文法的二义性？给出一个二义性文法实例 （1）如果文法G中的某个句子存在不只一棵语法树，则称该句子是二义性的。如果文法含有二义性的句子，则称该文法是二义性的 书上：若一个文法中存在某个句子，有两个不同的最左（最右）推导，则该文法是二义的。（2）文法G=（{E},{+, * , i , (,) }, P, E），其中P为：E->i ; E->E+E ; E->E*E ; E->(E) ; 这里的非终结符E表示一类算术表达式，i表示程序设计语言中的变量。该文法定义了由变量，+，*，（和）组成的算术表达式的语法结构。 6.常见的代码优化技术有哪些？依据优化所涉及的范围分为那些级别？ 删除多余运算、代码外提、强度削弱、变换控制条件、合并已知量和复写传播、删除无用赋值。局部优化、循环优化、全局优化

编译原理复习(有答案)

第一章引论 1.编译过程的阶段 由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段 2.编译程序的概念 3.编译程序的结构 例：（B）不是编译程序的组成部分。 A. 词法分析器； B. 设备管理程序 C. 语法分析程序； D. 代码生成程序 4.遍的概念 对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 5.编译程序与解释程序的区别 例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（D）。 A. 单用户与多用户的差别 B. 对用户程序的差错能力 C. 机器执行效率 D. 是否生成目标代码 第三章文法和语言 文法的概念 字母表、符号串和集合的概念及运算 例：(ab|b)*c 与下面的那些串匹配？（ACD） A. ababbc； B. abab； C. c； D. babc； E. aaabc 例：ab*c*(a|b)c 与后面的那些串匹配？（BC） A.acbbc B.abbcac C.abc D.acc 例：(a|b)a+(ba)*与后面的那些串匹配? （ADE） A.ba B.bba C.ababa D.aa E.baa 文法的定义（四元组表示） 文法G定义为四元组（V N，V T，P，S） V N：非终结符集 V T：终结符集 P：产生式（规则）集合 S：开始符号（或识别符号） 例：给定文法，A::= bA | cc，下面哪些符号串可由其推导出（①② ⑤）。 ①cc ②b*cc ③b*cbcc ④bccbcc ⑤bbbcc 什么是推导 例：已知文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 试给出下述表达式的推导：i*i+i 推导过程：E->E+T ->T+T ->T*F+T ->F*F+T ->i*F+T ->i*i+T ->i*i+F ->i*i+i ●句型、句子的概念 例：假设G一个文法，S是文法的开始符 号，如果S=>*x，则称x是句型。 例：对于文法G，仅含终结符号的句型称 为句子。 ●语言的形式定义 例：设r=(a|b|c)(x|y|z)，则L(r)中元素为9 个。 例：文法G产生式为S→AB，A→aAb|ε， B→cBd|cd，则B∈L(G)。 A. ababcd； B. ccdd； C. ab； D. aabb ●等价文法 例：如果两个文法描述了同一个语言，则这两个文法是等价文法。 ●文法的类型 0型：左边至少有一个非终结符 1型：右边长度>=左边长度 2型：左边有且仅有一个非终结符 3型：形如：A->aB,A->a 各类型文法都是逐级包含关系， 例：文法S→abC|c，bC→d是几型文法？0 型 例：文法S→abC，bC→ad是几型文法？1 型 例：文法G[A]：A→ε，A→aB，B→Ab，B→a 是几型文法？2型 例：文法S→a|bC，C→d是几型文法？3 型 ●最左（右）推导

编译原理复习整理(重点含答案)

1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb|ab后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：G1(S):S→AB；A→aAb|ab；B→cB|ε 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化）

4、对下面的文法G: E →TE ’ E ’→+E|ε T →FT ’ T ’→T|ε F →PF ’ F ’ →*F ’|ε P →(E)|a|b|∧ （1）证明这个文法是LL(1)的。 （2）构造它的预测分析表。 (1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)} FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#} (2)考虑下列产生式: '→+'→'→'→E E T T F F P E a b ||*|()|^||εεε FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. (3) + * ( ) a b ^ # E E TE →' E TE →' E TE →' E TE →' E' '→+E E '→E ε '→E ε T T F T →' T F T →' T F T →' T F T →' T' '→T ε '→T T '→T ε '→T T '→T T '→T T '→T ε F F P F →' F P F →' F P F →' F P F →' F' '→F ε '→'F F * '→F ε '→F ε '→F ε '→F ε '→F ε '→F ε P P E →() P a → P b → P →^ 5、考虑文法: S →AS|b A →SA|a （1）列出这个文法的所有LR(0) 项目。