当前位置：文档视界 › 05-编译原理课程测试第五套卷(附解析)-编译原理试题-中国科技大学

05-编译原理课程测试第五套卷(附解析)-编译原理试题-中国科技大学

编译原理课程测试第五套卷（附解析）

1、（10分）用子集构造法给出由下面的NFA 得到的DFA 的转换表

2、（20分）（1）通过构造识别活前缀的DFA 和构造分析表，来证明文法E → E + id | id 是SLR(1)文法。（2）下面左右两个文法都和（1）的文法等价 E → E + M id | id E → M E + id | id M → ε M → ε

请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。 3、（10分）下面是C 语言两个函数f 和g 的概略（它们不再有其它的局部变量）： int f (int x) { int i; …return i +1; … } int g (int y) {int j; … f (j +1); … }

请按照教材上例6.5中图6.13的形式，画出函数g 调用f ，f 的函数体正在执行时，活动记录栈的内容及相关信息，并按图6.12左侧箭头方式画出控制链。假定函数返回值是通过寄存器传递的。 4、（10分）C 语言函数f 的定义如下： int f (int x, int *py, int **ppz) { **ppz +=1; *py +=2; x +=3; return x + *py + **ppz; }

变量a 是指向b 的指针，变量b 是指向c 的指针，c 是整型变量并且当前值是4。那么执行f (c, b, a)的返回值是多少？ 5、（10分）Java 语言的实现通常把对象和数组都分配在堆上，把指向它们的指针分配在栈上，依靠运行时的垃圾收集器来回收堆上那些从栈不可达的空间（垃圾）。这种方式提高了语言的安全性，但是增加了运行开销。编译时能否采用一些技术，以降低垃圾收集所占运行开销？概述你的方案。 6、（5分）在面向对象语言中，编译器给每个对象分配空间的第1个域存放虚方法表的指针。是否可以把虚方法表指针作为最后1个域而不是第1个域？请简要说明理由。 7、（15分）考虑一个简单语言，其中所有的变量都是整型（不需要显式声明），并且仅包含赋值语句、读语句和写语句。下面的产生式定义了该语言的语法（其中lit 表示整型常量；OP 的产生式没有给出，因为它和下面讨论的问题无关）。 Program → StmtList StmtList → Stmt StmtList | Stmt Stmt → id := Exp; | read (id ); | write ( Exp ); Exp → id | lit | Exp OP Exp 我们把不影响write 语句输出值的赋值（包括通过read 语句来赋值）称为无用赋值，写一个语法指导定义，它确定一个程序中出现过赋予无用值的变量集合（不需要知道无用赋值的位置）和没有置初值的变

量集合（不影响write语句输出值的未置初值变量不在考虑之中）。

非终结符StmtList和Stmt用下面3个属性（你根据需要来定义其它文法符号的属性）：

（1）uses_in：在本语句表或语句入口点的引用变量集合，它们的值影响在该程序点后的输出。

（2）uses_out：在本语句表或语句出口点的引用变量集合，它们的值影响在该程序点后的输出。

（3）useless：本语句表或语句中出现的无用赋值变量集合。

8、（10分）一个C文件array.c仅有下面两行代码：

char a[ ][4] = { “123”, “456”};

char *p[ ] = { “123”, “456”};

从编译生成的下列汇编代码可以看出对数组a和指针p的存储分配是不同的。试依据这里的存储分配，为置了初值后的数组a和指针p写出类型表达式。

.file “array.c”

.globl a

.data

.type a, @object

.size a, 8

.string “123”

.string “456”

.section .rodata

.LC0:

.string “123”

.LC1:

.string “456”

.globl p

.data

.align 4

.type p, @object

.size p, 8

.long .LC0

.long .LC1

.section .note.GNU-stack, “”, @pro gbits

.ident “GCC: (GNU) 3.3.5 (Debian 1:3.3.5-13)”

9、（10分）两个C文件long.c和short.c的内容分别是

long i = 32768*2;

和

extern short i;

main() { printf(“%d\n”, i); }

在X86/Linux机器上，用cc long.c short.c命令编译这两个文件，能否得到可执行目标程序？若能得到目标程序，运行时是否报错？若不报错，则运行结果输出的值是否为65536？若不等于65536，原因是什么？

编译原理课程测试第五套卷参考答案

1、A = {0}, B = {0, 1}, C = {0, 1, 2}, D = {0, 1, 2, 3}

2、（1）先给出接受该文法活前缀的DFA如下：

表中没有多重定义的条目，因此该文法是SLR(1)的。

（2）只有文法

E → M E + id | id

M →ε

不是LR(1)文法。因为对于句子id+id+…+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。

3、

4、参数传递使得x 的值和c 的值一样，都是4；py 的值和b 的值一样，指向c ；ppz 的值和a 的值一样，指向b 。 **ppz +=1的执行使得c 的值为5。*py +=2的执行使得c 的值为7。x +=3的执行使得x 的值为7。这时x 、*py 和**ppz 的值都是7，因此返回值是21。

5、从两方面考虑。（1）减少垃圾：用程序分析技术确定数据的生存期是否超过它的静态作用域所对应的生存期，若没有超过则将这样的数据分配在栈上，而不必分配在堆上。（2）尽量静态确定垃圾：用程序分析技术把能静态确定的垃圾都标注出来，可使得运行时对它们回收开销很小。

6、不行。按书上目前的分配方式，若作为最后1个域，则难以为该对象产生它超类的视图。

7、 Exp 的属性uses 表示它引用的变量集合。Program 的useless 和no_initial 分别表示程序的无用赋值变量集合和未置初值变量集合。 Program → StmtList https://www.docsj.com/doc/c114016078.html,es_out:=?;

https://www.docsj.com/doc/c114016078.html,eless := https://www.docsj.com/doc/c114016078.html,eless;

Program.no_initial := https://www.docsj.com/doc/c114016078.html,es_in;

StmtList → Stmt StmtList 1 StmtList https://www.docsj.com/doc/c114016078.html,es_out := https://www.docsj.com/doc/c114016078.html,es_out; https://www.docsj.com/doc/c114016078.html,es_out := StmtList https://www.docsj.com/doc/c114016078.html,es_in; https://www.docsj.com/doc/c114016078.html,es_in := https://www.docsj.com/doc/c114016078.html,es_in

https://www.docsj.com/doc/c114016078.html,eless := StmtList https://www.docsj.com/doc/c114016078.html,eless ? https://www.docsj.com/doc/c114016078.html,eless; StmtList → Stmt https://www.docsj.com/doc/c114016078.html,es_out := https://www.docsj.com/doc/c114016078.html,es_out; https://www.docsj.com/doc/c114016078.html,es_in := https://www.docsj.com/doc/c114016078.html,es_in;

https://www.docsj.com/doc/c114016078.html,eless := https://www.docsj.com/doc/c114016078.html,eless

Stmt → id := Exp; https://www.docsj.com/doc/c114016078.html,eless :=if id .lexeme ∈https://www.docsj.com/doc/c114016078.html,es_out then ? else {id .lexeme}; https://www.docsj.com/doc/c114016078.html,es_in := if id .lexeme ∈https://www.docsj.com/doc/c114016078.html,es_out then (https://www.docsj.com/doc/c114016078.html,es_out –{id .lexeme})?https://www.docsj.com/doc/c114016078.html,es else https://www.docsj.com/doc/c114016078.html,es_out Stmt → read (id ); https://www.docsj.com/doc/c114016078.html,eless:=if id .lexeme ∈https://www.docsj.com/doc/c114016078.html,es_out then ? else {id .lexeme}; https://www.docsj.com/doc/c114016078.html,es_in := https://www.docsj.com/doc/c114016078.html,es_out – {id .lexeme} Stmt → write ( Exp ); https://www.docsj.com/doc/c114016078.html,eless := ?, https://www.docsj.com/doc/c114016078.html,es_in := https://www.docsj.com/doc/c114016078.html,es_out ? https://www.docsj.com/doc/c114016078.html,es

Exp → id https://www.docsj.com/doc/c114016078.html,es:= {id .lexeme}

ebp

低地址

高地址

栈

esp

Exp →lit https://www.docsj.com/doc/c114016078.html,es:= ?

Exp → Exp1 OP https://www.docsj.com/doc/c114016078.html,es:= https://www.docsj.com/doc/c114016078.html,es ? https://www.docsj.com/doc/c114016078.html,es

8、置了初值后的数组a和指针p的类型表达式分别是：

array(0..1, string)和array(0..1, pointer(string))

或者写成：

array(0..1, array(0..3, char) )和array(0..1, pointer(array(0..3, char)))

9、编译以文件为单位，不会发现文件之间的类型错误。由于数据的类型信息没有附加在目标文件中，因此连接时也不会发现两个文件中变量i的类型不一致。

运行时不会报错，但输出结果不是65536，而是0。这是由于X86机器对于整型数据来说，是低地址放整数的低位，高地址放整数的高位。在short.c文件中，short i取的是long.c文件中long i的那两个低位字节，它们都是0，因此输出结果是0。

编译原理期末考试习题及答案

一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0）项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分）（2）写出上述句型的短语，直接短语和句柄。（4分）答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分）（3）（4分）短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分）答：句子aaa对应的两颗语法树为：

因此，文法是二义文法四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分）答：对应的NFA为：（6分）状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分）六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分）（2）构造相应的first 和 follow 集合。（6分）答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T)

《编译原理》模拟期末试题汇总 6套,含答案

《编译原理》模拟试题一一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ ) 4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√) 6．递归下降法允许任一非终极符是直接左递归的。 (√) 7．算符优先关系表不一定存在对应的优先函数。 (×) 8．自底而上语法分析方法的主要问题是候选式的选择。 (×) 9．LR 法是自顶向下语法分析方法。 (×) 10．简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。

(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式三、填空题(每空1分，共10分)

编译原理期末考试题目及答案

一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式M 1 和M 2 等价是指__C_。 A．M1和M2的状态数相等 B．M1和M2的有向边条数相等 C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A．xyx B．(xyx)* C．xnyxn(n≥0) D．x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言C．编译方法D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x

编译原理测试及答案

编译原理期中测试答案三、单项选择题(每题3分，共15分) 1．设有文法G[S]: S→(AS)|(b) A→(SaA)|(a) 该文法的句型(((b)a(a))(b))有 C 个直接短语。 A.1 B. 2 C. 3 D. 4 2．如果一个文法满足 D ，则称该文法是二义性文法。 (1) 文法的某一个句子存在两个（包括两个）以上的语法树 (2) 文法的某一个句子存在两个（包括两个）以上的最左推导 (3) 文法的某一个句子存在两个（包括两个）以上的最右推导 (4) 在进行归约时，文法的某些规范句型的句柄不唯一上述描述中的所有正确描述有： A. (1) B. (1)(2) C. (1)(2)(3) D. (1)(2)(3)(4) 3．构造一个不带回溯的自顶向下语法分析器，要求文法满足 E 。 A.对每个形如A→x1|x2|…|xn的产生式，要求FIRST(xi)与FIRST(xj)的交集为空集(i≠j) B.对每个形如A→x1|x2|…|xn的产生式，若xi* ε，则要求FIRST(xj)与FOLLOW(A)的交集为空集(i≠j) C. 不含左递归 D. A和B同时满足 E. A、B和C同时满足

4、给定文法A→bA|cc，下列符号串中，是该文法的句子的是 C 。 ① cc ② bcbc ③ bcbcc ④ bccbcc ⑤ bbbcc A① B. ①③④⑤ C. ①⑤ D. ①④⑤ 5、若一个句型中出现了某一产生式的右部，则此右部 B 是该句型的句柄。 A.一定 B. 不一定 C. 一定不 D. 无法判断四、简述题(每题5分，共20分) 1、写一上下文无关文法,它能产生语言}0 n。 n a L m b , =m | {>= # S→A#B A→Aa|ε B→Bb|ε 2、将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]：S→bSAe | bA A→Ab | d 答：文法G[S] 改写为等价的不含左递归和左公共因子的 G'[S]S→bB B→SAe | A A→d A' A' →bA' | ε 3、什么是文法的二义性？下面的文法是二义的吗？为什么？

编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)

期末考试编译原理试卷及答案

一．填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为（7）。 5．文法符号的属性有综合属性和（8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。二．选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（），以及一组（）。 A ．字符串 B ．产生式 C ．开始符号 D ．文法 2.程序的基本块是指（）。 A ．一个子程序 B ．一个仅有一个入口和一个出口的语句 C ．一个没有嵌套的程序段 D ．一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。 A ．自左向右 B ．自顶向下 C ．自底向上 D ．自右向左 4．在通常的语法分析方法中，（）特别适用于表达式的分析。 A ．算符优先分析法 B ． LR 分析法 C ．递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（）。 A ．四元式序列 B ．间接三元式序列 C ．二元式序列 D ．机器语言程序或汇编语言程序 6．一个文法所描述的语言是（）；描述一个语言的文法是（）。 A ．唯一的 B ．不唯一的 C ．可能唯一，也可能不唯一 7．如果在文法G 中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。 A ．其最左推导和最右推导相同 B ．该句子有两个不同的最左推导 C ．该句子有两个不同的最右推导 D ．该句子有两棵不同的语法树

编译原理习题及答案(整理后)

第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。

一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a)

编译原理试题B及答案

编译原理试题B 一、单项选择题（每题1分，共20分） 1、对编译系统有关概念描述正确的是（ B） A．目标程序只能是机器语言 B. 编译程序处理的对象是源语言 C．解释程序属于编译程序 D. 词法分析无法自动进行 2. 设有表达式a*b-c，将其中a*b识别为表达式的编译阶段是什么（B） A．词法分析 B. 语法分析 C．语义分析 D. 代码生成 3. 下面不能用于对文法进行描述的是（A ） A．源语言 B. EBNF C．BNF D. 语法图 4. 设有文法G[S]: S→0S|1A|0，A→1|1S|0B，B→1A|0B，下列符号串中是该文法的句子的是（）？A．1010001001101 B.0101001110010010 C．1101010011110111 D.1010011101101010 (可画出DFA验证) 5. 文法G[S]: S→aA|bC|a A→aS|bB B→aC|bA|b C→aB|bS ,则不是L(G)句子的是（ B ） A．a100b50ab100 B. a1000b500aba C．a500b60aab2a D. a100b40ab10aa （画出DFA） 6. 哪个不是DFA的构成成分（B） A．有穷字母表 B. 初始状态集合 C．终止状态集合 D. 有限状态集合 7.词法分析器的输入是（ B ） A．单词符号串 B.源程序 C．语法单位 D.目标程序 8.在词法分析阶段不能识别的是（C ） A．标识符 B. 运算符 C．四元式 D. 常数 9.设有一段C语言程序 while(i&&++j)

{ c=2.19; j+=k; i++; } ,经过词法分析后可以识别的单词个数是（B ） A．19 B.20 C．21 D.23 10．自上而下语法分析的主要动作是（ B ） A．移进 B. 推导 C．规约 D. 匹配 11.下面不属于LL(1)分析器的自称部分是（ D ） A．LL(1)总控程序 B. LL(1)分析表 C．分析栈 D.源程序串 12.设有文法G[S]为 S→AB|bC， A→ε|b，B→ε|aD，C→AD|b，D→aS|c 则FOLLOW(A)为（A ） A．{a,c,#} B.{c,#} C．{a,#} D.{#} 13.设有文法G[S]: S→Ap|Bq，A→a|cA，B→b|dB ，则FIRST(Ap)为（ C ）A．{p,q} B. {b,d} C．{a,c} D. 其他 14.自下而上语法分析的主要分析动作是（D ） A．推导 B. 规约 C．匹配 D. 移进-规约 15.算法优先分析中，可规约串是（ C ） A．句柄 B．活前缀 C．最左素短语 D．素短语 16. 设有文法G={{S},{a},{S→SaS|ε},S}，该文法是（ B ） A．LL(1)文法 B．二义性文法 C．SLR(1)文法 D．算法优先文法 17、中间代码生成时所以据的是（C ） A．语法规则 B．词法规则 C．语义规则D．等价变换规则 18、给定文法G: E→E+T|T，T→T*F|F，F→i|(E) 则L(G)中的一个句子i+i+(i*i)*i的逆波兰表示为（ C ） A．iii*i++ B．ii+iii**+ C．ii+ii*i*+ D．其他

编译原理试题及答案(期末复习版).pdf

<编译原理>历年试题及答案一．（每项选择 2 分，共 20 分）选择题 1．将编译程序分成若干个“遍”是为了_b__。 a.提高程序的执行效率 b.使程序的结构更加清晰 c. 利用有限的机器内存并提高机器的执行效率 d. 利用有限的机器内存但降低了机器的执行效率 2．构造编译程序应掌握__d__。 a.源程序 b.目标语言 c.编译方法 d.以上三项都是 3．变量应当 c＿。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持有左值也不持有右值 4．编译程序绝大多数时间花在 _d___上。 a.出错处理 b.词法分析 c.目标代码生成 d.管理表格 5．词法分析器的输出结果是_c___。 a.单词的种别编码 b.单词在符号表中的位置 c.单词的种别编码和自身值 d.单词自身值 6．正规式 MI 和 M2 等价是指__c__。 a. MI 和 M2 的状态数相等 b.Ml 和 M2 的有向弧条数相等。 C.M1 和 M2 所识别的语言集相等 d. Ml 和 M2 状态数和有向弧条数相等7．中间代码生成时所依据的是—c。 a．语法规则 b．词法规则c．语义规则 d．等价变换规则 8．后缀式 ab+cd+/可用表达式__b_来表示。 a． a+b/c+d b． (a+b)/(c+d) c． a+b/(c+d) d． a+b+c/d 9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 10.堆式动态分配申请和释放存储空间遵守___d____＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意二（每小题 10 分，共 80 分）简答题 1.画出编译程序的总体结构图，简述各部分的主要功能。 2. 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.

(完整word版)编译原理期末试题(二)含答案,推荐文档

《编译原理》期末试题（二）一、是非题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。（） 3.已经证明文法的二义性是可判定的。（） 4.每个基本块可用一个DAG表示。（） 5.每个过程的活动记录的体积在编译时可静态确定。（） 6.2型文法一定是3型文法。（） 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 X ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（） 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 X ( ) 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.× 9.√10.× 11.× 12.√ 13.× 14.√ 15.√ 16.√ 17.× 18.√19.√ 20.×21.√22.√ 二、填空题： 2.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标代码生成）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。 4.从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。 5.语法分析器的输入是（单词符号），其输出是（语法单位）。 6.扫描器的任务是从（源程序中）中识别出一个个（单词符号）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如(类型、种属、所占单元大小、地址）等等。 8.一个过程相应的DISPLAY表的内容为(现行活动记录地址和所有外层最新活动记录的地址) 10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。 11.一个名字的属性包括( 类型)和(作用域 )。 12.常用的参数传递方式有(传地址），（传值），（传名） 13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。 14.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上）分析法。 15.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。 17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。 19.语法分析是依据语言的（语法）规则进行。中间代码产生是依据语言的（语义）规则进行的。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（LL(1) 文法）文法。 22.对于数据空间的存贮分配， FORTRAN采用( 静态策略， PASCAL采用( 动态)策略。

编译原理期末试题及答案

2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。 3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 4、已知文法G(S)及相应翻译方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么 5、已知文法G(S) S→bAa A→(B | a B→Aa) 写出句子b(aa)b的规范归约过程。 6、已知文法G[S] S→S*aF | aF | *aF F→+aF | +a 消除文法左递归。 1、设文法G(S): S→^ | a | (T) T→T,S | S ⑴消除左递归； ⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表 2.语句if E then S (1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 4.设某语言的for语句的形式为 for i:＝E(1) to E(2) do S 其语义解释为 i:＝E(1) LIMIT:＝E(2) again: if i＜＝LIMIT then Begin S; i:＝i＋1 goto again End; （1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S (1) 给出句子(a,(a,a))的最左推导； (2) 给出句型((T,S),a)的短语, 直接短语，句柄。 8.对于C 语言do S while E语句 (1)改写文法，使之适合语法制导翻译；

(2)写出改写后产生式的语义动作。 9.已知文法G(S) S→aAcBe A→Ab| b B→d (1)给出句子abbcde的最左推导及画出语法树； (2)给出句型aAbcde的短语、素短语。 10.设文法G(S): S→(T) | aS | a T→T,S | S ⑴消除左递归和提公共左因子； ⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i (1) 给出句型(i+i)*i+i的最左推导及画出语法树； (2) 给出句型(E+T)*i+F 的短语，素短语和最左素短语。答案： (1)消除左递，文法变为G’[S]： S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε 此文法无左公共左因子。 (2)构造相应的FIRST和FOLLOW集合： FIRST(S)={a, ^, (}，FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ，FOLLOW(T)={}} FIRST(T’)={,, ε} ，FOLLOW(F)={)} (3) C→if E then S→CS(1) (2) C→if E then {BACK, NXQ); :=} S→CS(1) {:=MERG, S(1). Chain)} 4. (1) F→for i:=E(1) to E(2) do S→FS(1) (2)F→for i:=E(1) to E(2) do {GEN(:=, E(1).place, _, entry(i)); :=entry(i);

编译原理试题及答案3

编译原理复习题一、填空题： 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、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。

编译原理期末A试卷答案

黄冈师范学院 2012—2013学年度第一学期期末试卷参考答案考试课程：编译原理考核类型：考试A卷考试形式：闭卷出卷教师：牛冀平考试专业：计算机科学与技术，软件工程考试班级：计科201001班，软件201001班一、填空（每空0.5分，共 10分） 1、编译程序的功能是是对(高级语言)进行翻译，使之生成目标代码。 2、编译程序的工作过程一般划分为5个阶段：（词法分析）、语法分析、语义分析与中间代码生成，（代码优化）及目标代码生成。另外还有表格管理和（出错处理）。 3、一个上下文无关文法所含四个组成部分是一组终结符号、一组（非终结符号）、一个开始符号、（一组产生式）。 4、设G是一个给定的文法，S是文法的开始符号，如果S=> x（其中x∈V*），则称x 是文法的一个（句型）。 5、规范归约中的可归约串是指句柄，算符优先分析中的可归约串是指（最左素短语）。 6、在编译过程中,可采用的中间代码形式有（）、（）、（）等。（三元式、间接三元式、四元式、逆波兰式、抽象语法树）（任选三个即可） 7、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。 8、表达式（a+b)*c的后缀表达式为（ab+c*）。 9、符号表的结构一般有（线性表）、（有序表）、（散列表或哈希表）等。分别使用的查找方法有（顺序查找）、（折半查找）和（哈希法查找） 10、代码优化的目的是（减少代码的时空开销）。 11、寄存器是CPU内部的（存储单元），其访问时间小于CPU对内存的访问时间。 12、如果一个句子存在两棵不同的语法树就说明该句子是（二义性）的。二、选择题（每题1分，共10分）

编译原理考试试题与答案(汇总)

《编译原理》考试试题及答案（汇总）一、是非题（请在括号，正确的划√，错误的划×）（每个2分，共20分） 1．编译程序是对高级语言程序的解释执行。(× ) 2．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 3．一个算符优先文法可能不存在算符优先函数与之对应。(√ ) 4．语法分析时必须先消除文法中的左递归。(×) 5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√) 6．逆波兰表示法表示表达式时无须使用括号。(√ ) 7．静态数组的存储空间可以在编译时确定。(×) 8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。(× ) 10．一个语义子程序描述了一个文法所对应的翻译工作。(×) 二、选择题(请在前括号选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置 C．( ) 单词的种别编码和自身值D．( ) 单词自身值 2．正规式 M 1 和 M 2 等价是指_____。 A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等

3．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。 A．( )最左推导和最右推导对应的语法树必定相同 B．( ) 最左推导和最右推导对应的语法树可能不同 C．( ) 最左推导和最右推导必定相同 D．( )可能存在两个不同的最左推导，但它们对应的语法树相同 5．构造编译程序应掌握______。 A．( )源程序B．( ) 目标语言 C．( ) 编译方法 D．( ) 以上三项都是 6．四元式之间的联系是通过_____实现的。 A．( ) 指示器B．( ) 临时变量 C．( ) 符号表 D．( ) 程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。 A. ( ) ┐AB∨∧CD∨B．( ) A┐B∨CD∨∧ C．( ) AB∨┐CD∨∧ D．( ) A┐B∨∧CD∨ 8. 优化可生成_____的目标代码。 A．( ) 运行时间较短B．( ) 占用存储空间较小C．( ) 运行时间短但占用存空间大D．( ) 运行时间短且占用存储空间小 9．下列______优化方法不是针对循环优化进行的。 A. ( ) 强度削弱 B．( ) 删除归纳变量 C．( ) 删除多余运算 D．( ) 代码外提

编译原理期末考试试卷(A卷)

编译原理期末考试试卷（A卷）一、简述编译程序的工作过程。（10）二、构造下列正规式相应的DFA（用状态转换图表示）（15）（1）1（0 | 1）*100 （2）0*10*10*10*1 （3）letter（letter | digit）* 三、给出下面语言的相应文法：（15） L1={a n b n | n≥1} L2={a n b m+n a m| n≥1，m≥0}

E→gAf | c (1)计算该文法的每一个非终结符的FIRST集和FOLLOW集； (2)试判断该文法是否为LL（1）文法。（15）六、对表达式文法G： E →E+T | T T →T*F | F F →(E) | I （1）造各非终结符的FIRSTVT和LASTVT集合；（2）构造文法的算符优先关系表。（15）

七、有定义二进制整数的文法如下： L →LB | B B →0 | 1 构造一个翻译模式，计算该二进制数的值（十进制的值）。（15）

简述编译程序的工作过程。（10）编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；②语法分析，根据语言的语法规则，把单词符号串分解成各类语法单位；③语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译；④代码优化，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。二、构造下列正规式相应的DFA （用状态转换图表示）（15）（4）（5）（6）（1）（2） (3) 三、给出下面语言的相应文法：（15） L 1={a n b n | n ≥1} L 2={a n b m+n a m | n ≥1，m ≥0} G1： A →aAb |ab G1： S →AB A →aAb | ab B →bBa | ε