当前位置：文档之家› 编译原理期末复习题(包含上一份N多答案)

编译原理期末复习题(包含上一份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、编译过程中扫描器所完成的任务是从（源程序）中识别出一个个具有（独

立语法意义的单词）。

23、确定的有穷自动机是一个（五元组），通常表示为（DFA=（K，∑，M，S，Z））。

24、已知文法G(E):

E->T|E+T|E-T

T->F|T*F|T/F

F->(E)|i

该文法的开始符号是（E ），终结符号集合VT是（{ +,-,*./,(,),i }），非终结符号集合VN是（{ E,T,F }），句型T+T*F+i的短语有（T+T*F+I ，T*F 第一个T，i）。

25、已知文法G(E):

E->T|E+T|E-T

T->F|T*F|T/F

F->(E)|i

改写该文法以消除直接左递归，改写后的文法为：E->（+TE‘|-TE‘|ε），T->（FT‘），（T‘-> *FT‘|ε），F->（（E）| i）。

26、已知文法G(Z):

Z->U0|V1

U->Z1|1

V->Z0|0

请写出全部由此文法描述的只含四个符号的句子：（0101，1010，1001，0110 ）。该文法是Chomsky（ 3 ）型文法。

27、Chomsky定义的四种形式语言文法分别为：（0型）文法--又称（短语文法）文法，（1型）文法--又称（上下文有关）文法，（2型）文法--又称（上下文无关）文法，（3型）文法--又称（正则）文法。

28、文法G(S):

S->AB

A->aAb|ab

B->Bc|ε

其描述的语言L(G[S])=（a n b n c m,n≥1，m≥0 ）。

29、文法G(S):

S->SAS|b|c

A->aaA|a

其描述的语言L(G[S])=（b,C,或者是以b开头、以c结尾的、中间是任意个由b或c间隔开的奇数个a组成的符号串）。

30、过程与过程引用中信息交换的方法是（全局变量的使用）和（参数传递）。

31、形式参数和实在参数之间的对应关系通常按（它们在源程序中的位置）来确定。

32、按传结果的方式进行形实参数结合，是一种把（传地址）和（传值）的特点相结合的参数传递方式。

33、在PASCAL中，由于允许用户动态申请与释放内存空间，所以必须采用（堆）存储分配方式。

34、编译程序进行数据流分析的目的是（为了进行全局优化）。

35、根据所涉及程序的范围，优化可分为（局部优化）、（循环优化）和（全

局优化）三种。

36、局部优化是局限于一个（基本块）范围内的一种优化。

37、词法分析阶段的错误主要是（拼写错误），可通过（最小距离匹配）的办法去纠正错误。

38、对错误的处理方法一般有（校正法）和（局部优化法）。

39、源程序中的错误一般有（词法错误）、（语法错误）、（语义错误）和（违反环境限制的错误）四种。

40、翻译程序是这样一种程序，它能够将（用甲语言书写的程序）转换成与其等价的（用乙语言书写的程序）。

41、编译程序的工作过程一般可以划分成（词法分析、语法分析、语义分析、中间代码生成、代码优化）等五个基本阶段。

42、编译程序的工作过程还会伴有（表格处理）和（出错处理）。

二、选择题：

1、在使用高级语言编程时，首先可通过编译程序发现源程序的全部（ A ）错误和部分（ B ）错误。

A、语法

B、语义

C、语用

D、运行

2、程序语言的处理程序是一种（ A ）。

A、系统软件

B、应用软件

C、实时系统

D、分布式系统

3、（ B ）是两类程序语言处理程序，它们的主要区别在于是否生成目标代码。

A、高级语言和低级语言

B、解释程序和编译程序

C、编译程序和操作

系统D、系统程序和应用程序

4、汇编语言是将（ A ）翻译成（ B ）；编译程序是将（ C ）翻译成（ D ）。

A、汇编语言程序

B、机器语言程序

C、高级语言程序

D、汇编或机器语言程序e、汇编或高级语言程序F、机器或高级语言程序

5、编译程序与具体的机器（ A ），与具体的语言（ B ）。

A、有关

B、无关

6、编译程序生成的目标程序（ B ）是可执行的程序。

A、一定

B、不一定

7、编译程序生成的目标程序（ B ）是机器语言程序。

A、一定

B、不一定

8、把汇编语言程序翻译成机器可执行的目标程序的工作是由（ B ）完成的。

A、编译器

B、汇编器

C、解释器

D、预处理器

9、编译过程中，语法分析器的任务是（ B ）。

(1)分析单词是怎样构成的；(2)分析单词串是如何构成语句和说明的；(3)分析语句和说明是如何构成程序的；(4)分析程序的结构

A、(2)(3)

B、(2)(3)(4)

C、(1)(2)(3)

D、(1)(2)(3)(4)

10、文法G所描述的语言是（ D ）的集合

A、文法G的字母表V中所有符号组成的符号串；

B、文法G的字母表V的闭包V*中的所有符号串；

C、由文法的识别符号推出的所有符号串；

D、由文法的识别符

号推出的所有终结符符号串；

11、描述语言L={a m b n|n>m>1}的文法为（ D ）。

A、Z->Abb, A->aA|a, B->bB|b

B、Z->ABb, A->Aa|a,B->aBb|b

C、Z->Ab, A->aAb|a

D、Z->aAb, A->Ab|aAb|@

12、一个句型中的最左（ B ）称为该句型的句柄。

A、短语

B、简单短语

C、素短语

D、终结符号

13、文法的二义性和语言的二义性是两个（A）的概念。

A、不同

B、相同

C、无法判断

14、上下文无关文法（A）产生语言L={a m b n c i|i>1,n>1}

A、可以

B、不可以

15、（B）正规文法能产生下面的语言：L={a m b n|n>1}

A、存在一个

B、不存在任何c、无法判断

16、编译程序中的语法分析器接受以（C）为单位的输入，并产生有关信息供以后各阶段使用。

A、表达式

B、产生式

C、单词

D、语句

17、高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ B ）分析方法。

A、自左至右

B、自顶向下

C、自底向上

D、自右至左

18、算符优先分析法每次都是对（ E ）进行归约，简单优先分析法每次都是对（ C ）进行归约。

A、最左短语

B、简单短语

C、句柄

D、素短语

E、最左素短语

19、文法G(S)：S—>aTb|,，T->R，R—>R/S|S的句型aR/aSb/aTb,b的最左素

短语为（ B ）。

A、aTb

B、aSb

C、S

D、R/

E、,

20、LR语法分析栈中存放的状态是识别（ B ）的DFA状态。

A、前缀

B、可归前缀

C、项目

D、句柄

21、已知文法G[S]：s->LaR|R，L->bR|c，R->L 该文法是（ B ）。

(1)LR(0)文法；(2)SLR(1)文法；(3)LR(1)文法；(4)LALR(1)文法；(5)都不是

A、(1)(2)

B、(3)(4)

C、(1)(2)(3)(4)

D、(5)

E、(6)

22、若一个句型中出现了某一产生式的右部，则此右部（ B ）是该句型的句柄。

A、一定

B、不一定

23、LR(K)方法是（ D ）。

A、从左到右分析，每次走K步的一种编译方法

B、从左到右分析，共经过K步的一种编译方法

C、从左到右分析，每次向前预测K步的一种编译方法

D、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法

24、文法G[S]：S->AA，A->Aa|a 不是LR(1)文法的理由是（ D ）

A、FIRST(S)NFIRST(A)≠ф

B、FIRST(A)NFOLLLOW(A) ≠ф

C、FIRST(Aa)NFIRST(a) ≠ф

D、都不是

25、下列关于标识符和名字的叙述中，正确的是（ C ）。

A、标识符有一定的含义

B、名字是一个没有意义的字符序列

C、名字有确切的属性

D、都不对

26、编译程序在其工作过程中使用最多的数据结构是（ C ）。它记录着源

程序中的各种信息，以便查询或修改。

A、线性表

B、链表

C、表

D、符号表

27、在编译程序在其工作过程中使用的各种表中，以（ D ）最重要，其生存期最长，使用也最频繁。

A、线性表

B、链表

C、表

D、符号表

28、编译程序使用（ B ）区别标识符的作用域。

A、说明标识符的过程或函数名

B、说明标识符的过程或函数的静态层次

C、说明标识符的过程或函数的动态层次

D、标识符的行号

29、动态存储分配时，可以采用的分配方法有（ C ）。

(1)以过程为单位的栈式动态存储分配；(2)堆存储分配；(3)最佳分配方法

A、(1)

B、(2)

C、(1)(2)

D、(1)(2)(3)

30、过程调用时，参数的传递方法通常有（ D ）。

(1)传值；(2)传地址；(3)传结果；(4)传名

A、(1)(2)

B、(1)(2)(3)

C、(1)(2)(4)

D、(1)(2)(3)(4)

31、在编译方法中，动态存储分配的含义是（ A ）。

A、在运行阶段对源程序中的量进行分配

B、在编译阶段对源程序中的量进行分配

C、在编译阶段对源程序中的量进行分配，在运行时这些量的地址可以根据需要改变

D、以上都不对

32、PASCAL中过程说明的局部量地址分配在（ B ）。

A、调用者的数据区中

B、被调用者的数据区

C、主程序的数据区

D、公共数据区

33、表达式-a+b*c+d+(e*f)/d*e，如果优先级由高到低依次为-、+、*、/，且均为左结合，则其后缀式为（ D ）。

A、abc*+d+ef*d/e*+-

B、a-bc*def*d/e*+++

C、a-bc*+def*d/e*++

D、a-b+cd+ef*+*de*/

34、表达式a*b-c-d$e$f-g-h*i中，运算符的优先级由高到低依次为-、*、$，且均为右结合，则其后缀式为（ D ）。

A、ab*c-d-e$fg-h-i*$

B、$*a-b-cd$e*-f-ghi

C、bcd--a*efgh--i*$$

D、abcd--*efgh--i*$$

E、ab*c-d-e$fg-h-i*$

35、a:= a+b*c↑(d/e)/f的逆波兰记号表示是（C ）。

A、aabc*+↑de/f/:=

B、aabcde↑/*f/:=

C、aabcde/↑*f/+:=

D、以上都不对。

三、简答题：

1、什么是语法制导翻译？

答：所谓语法制导翻译，是指在语法规则的制导下，通过计算语义规则，完成对输入符号的翻译。

由于使用属性文法时把语法规则和语义规则分开，但在使用语法规则进行推导或归约的同时又使用这些语义规则来指导翻译与最终产生目标代码，所以称为语法制导翻译。

2、写出算术表达式A+B*(C-D)+E/(C-D)**N 的三元式、四元式序列。

答：四元式：三元式：

（-，C，D，T1）（1）（-，C，D）

（*，B，T1，T2）（2）（*，B，（1））

（+，A，T2，T3）（3）（+，A，（2））

（-，C，D，T4）（4）（-，C，D）

（**，T4，N，T5）（5）（**，（4），N）

（/，E，T5，T6）（6）（/，E，（5））

（+，T3，T6，T7）（7）（+，（3），（6））

3、写出条件语句IF a<0 THEN x:=x+1 ELSE x:=4*（x-1）的四元式形式。

答：

（1）（>，a，0，T1）

（2）（BMZ，T1，，（6））

（3）（+，x，1，T2）

（4）（：=，T2，，x）

（5）（BR，，，（9））

（6）（-，x，1，T3）

（7）（*，4，T3，T4）

（8）（：=，T4，，x）

（9）

4、把语句IF A∨B

答：（1）（《，B，D，T1》

（2）（∨，A，T1 ，T2）

（3）（BMZ，T2，，（6））

（4）S1的四元式序列

（5）（JMP，，，（7））

（6）S2的四元式序列

（7）

5、给出表达式A+B*(C-D)-E/F↑G 的三元式、逆波兰和四元式表示。

答：A、三元式B、四元式

（1）（-，C，D）（1）（-。C。D。T1）

（2）（*，B，（1））（2）（*，B，T1，T2）

（3）（+，A，（2））（3）（+，A，T2，T3）

（4）（↑，F，G）（4）（↑，F，G，T4）

（5）（/，E，（4））（5）（/，E，T4，T5）

（6）（-，（3），（5））（6）（-，T3，T5，T6）

C、逆波兰：ABCD-*+EFG↑/-

6、给出算术表达式-(a+b)*(c+d)-(a+b+c)的四元式序列。

答：（1）（+，a，b，T1）

（2）（neg，T1，，T2）

（3）（+，c，d，T3）

（4）（*，T2，T3，T4）

（5）（+，a，b，T5）

（6）（+，T5，c，T6）

（7）（-，T4，T6，T7）

7、写出当型语句

while x+y>3 do

begin

a:=a+3*b;

b:=a+e-f*e;

end;

的四元式序列。

答：（1）（+，x，y，T1）

（2）（>，T1，3，T2）

（3）（BMZ，T2，,(12)）

（4）（*，3，b，T3）

（5）（+，a ，T3，T4）

（6）（：=，T4，，a）

（7）（+，a，e，T5）

（8）（*，f，e，T6）

（9）（-，T5，T6，T7）

（10）（：=，T7，，b）

（11）（BR，，，（1））

（12）

8、将语句

if A V B>0 then while C>0 do C:=C+D 翻译成四元式。

答：

100 (jnz，A，-，104)

101 (j，-，-，102)

102 (j>，B，0，104)

103 (j，-，-，109)

104 (j>，C，0，106)

105 (j，-，-，109)

106 (+，C，D，T1)

107 (:=，T1，-，C)

108 (j，-，-，104)

109

9、对下列文法G:

S'->#S#

S->D(R)

R->R;P|P

P->S|i

D->i

（1）计算文法G中每个非终结符的FIRSTVT集；

（2）计算文法G中每个非终结符的LASTVT集；答：（1）各非终结符的FIRSTVT集合为：

FIRSTVT（S’）={ #} FIRSTVT（P）={（，i）

FIRSTVT（S）={（，i）FIRSTVT（D）={i }

（2）各非终结符的LASTVT集合为：

LASTVT（S’）={#} LASTVT（P）={ }，i}

LASTVT（S）={} }

LASTVT（D）={ i}

LASTVT（R）={；，），i}

10、对下列文法G:

S'->#S#

S->fStS

S->i=E

E->E+T|T

T->P↑T|P

P->(E)|i

（1）计算文法G中每个非终结符的FIRSTVT集；

（2）计算文法G中每个非终结符的LASTVT集；

答：（1）各非终结符的FIRSTVT集合为：

FIRSTVT（S’）={ #} FIRSTVT（T）={ ↑，（，i）

FIRSTVT（S）={f，i} FIRSTVT（E）={+，↑，（，i ）

FIRSTVT（P）={（，i ）

（2）各非终结符的LASTVT集合为：

LASTVT（S’）={#} LASTVT（T）={ ↑，}，i}

LASTVT（S）={ t，=，+，↑，)，i}

LASTVT（P）={ }，i}

11、文法G1：P->PaP|PbP|cP|Pe|f

证明文法G1是二义文法。

答：因为文法存在句型：fbfbf ，此句型有两棵不同的语法树，所以文法是二义的。

或存在2种最右推导：

A、P=>PbP=>PbPbP=>PbPbf=>Pbfbf=>fbfbf

B、P=>PbP=>Pbf=>PbPbf=>Pbfbf=>fbfbf

12、有文法G[N]：

N->SE|E

S->SD|D

E->0|2|4|6|8|10

D->0|1|2|3|4|5|6|7|8|9

证明该文法是二义的；此文法描述的语言是什么？并试写出另一文法，使L （G‘）=L（G），且G‘是无二义的。

答：对于该文法，存在句型110，有两棵不同的语法树或两种不同的最右推导，因此文法具有二义性。

A、N=>SE=>S10=>D10=>110

B、N=>SE=>S0=>SD0=>S10=>D10=>110

该文法描述的语言是偶数集合。

等价的无二义文法是：

G‘[N]：

N->SE|E

S->SD|D

E->0|2|4|6|8

D->0|1|2|3|4|5|6|7|8|9

13、写出不能被5整除的偶整数的文法。

答：G[Z]:

Z->(+|-)AB

A->0|1|2|3|4|5|6|7|8|9|AA

B->1|2|3|4|5|6|7|8|9

14、对于文法G=（V N，V T，S，P）：

V N={ S，A，B，}；V T={a，b}，开始符号为S

P：

S->aB|bA

A->aS|bAA|a

B->bS|aBB|b

给出串aaabbabbba的

（1）最左推导；（2）最右推导；（3）推导树。

答：最左推导：

S=>aB=>aaBB=>aaaBBB=>aaabSBB=>aaabbABB=>aaabbaBB=>aaabbabB =>aaabbabbS=>aaabbabbbA=>aaabbabbba

最右推导：

S=>aB=>aaBB=>aaBbS=>aaBbbA=>aaBbba=>aaaBBbba=>aaaBbbba=>aaa bSbbba=>aaabbAbbba=>aaabbabbba

15、什么是句柄？

答：一个句型德最左直接短语称为句柄。

16、什么是最左素短语？

17、上下文无关文法

答：若一个形式文法G = (N, Σ, P, S) 的产生式规则都取如下的形式：V -> w，则称之为上下文无关的，其中V∈N ，w∈(N∪Σ)*。上下文无关文法取名为“上下文无关”的原因就是因为字符V 总可以被字串w 自由替换，而无需考虑字符V 出现的上下文。上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；

四、问答题：

1、给出将赋值语句翻译成四元式的语法制导定义，允许右部表达式含有加法、乘法、取负、括号运算。生成赋值语句x:=b*(c+d)+a的四元式。

2、出条件赋值语句i:=if b then e1 else e2 的语义子程序。其中b是布尔表达式，e1和e2 是算术表达式，I代表与e1和e2类型相同的左部变量。按写出的语义子程序生成条件赋值语句z:=if a>c then x+y else x-y+0.5 的四元式序列。

3、试写出PASCAL循环语句for I:=1 to n do s的语义子程序，假定该语句的

文法为：

F1:=for i:=1 to n

S:= F1 do S1

4、给出做为条件控制的布尔表达式翻译为四元式的语法制导定义，允许布尔表达式中有与、或、非及括弧运算。（如在翻译过程中使用了自定义的函数，可以不写函数过程，但请注明函数的功能和出入口的参数）。

5、按语法制导的定义将下面的后缀表达式翻译成中缀表达式。注意：不允许出现冗余括号。

E->E1E2+

E->E1E2*

E->id

6、某程序设计语言说明部分的语法制导定义如下所示：

D->TL

T->int|real

L->L1,id|id

给出其语法制导定义及自底向上的翻译方案，并比较两者的不同。

7、设有文法G[S]：

S->E(1)

E->Aa(2)|Bb(3)

A->cA(4)|d(5)

B->cB(6)|d(7)

构造其LR（0）分析表并利用此分析表判断符号串acccd是否是该文法的句

子。

8、对下列文法：

S’->S

S->bRST

S->bR

R->dSa

R->e

T->fRa

T->f

(1)出非终结符的FIRST和FOLLOW的集合。

（2）构造该文法的SLR（1）分析表。

9、给定文法G[S] ：

S → SaA | a

A → AbS | b

⑴请构造该文法的以LR(0) 项目集为状态的识别规范句型活前缀的DFA 。

⑵请构造该文法的LR(0) 分析表。

⑶什么是LR(0) 文法？该文法是LR(0) 文法吗？为什么？

⑷什么是SLR(1) 文法？该文法是SLR(1) 文法吗？为什么？

10、构造下列文法的LR（1）分析表，其中S’ 是文法的开始符号。

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

一、填空题|（每题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)

编译原理复习题--有答案版

1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 答案： S→ AB|B A→ a|aA B→ bBc|bc 2．给出下面语言的相应文法 L1={a n b n c m d m| m,n≥1，n为奇数，m为偶数}。答案：文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc 3、构造一个DFA，它接受={a，b}上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化） (一)相应的正规式为(a|b)*ab(a|b)* (二)①与此正规式对应的NFA为答案；在自己写的纸上 4、对下面的文法G: E→TE’ E’→+E|ε T→FT’ T’→T|ε F→PF’ F’→*F’|ε P→(E)|a|b|∧（1）证明这个文法是LL(1)的。考虑下列产生式: 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)文法. 计算这个文法的每个非终结符的FIRST和FOLLOW。（8分）答案：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,^,+,),#} （3）构造它的预测分析表。（6分）答案；在手机上写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2)

四川大学编译原理期末复习总结

一、简答题 1.什么是编译程序答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 2.请写出文法的形式定义答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S） –其中Vn表示非终结符号 –Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ –S是开始符号， –P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*) 3.语法分析阶段的功能是什么答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。 4.局部优化有哪些常用的技术答：优化技术1—删除公共子表达式优化技术2—复写传播优化技术3—删除无用代码优化技术4—对程序进行代数恒等变换（降低运算强度）优化技术5—代码外提优化技术6—强度削弱优化技术7—删除归纳变量优化技术简介——对程序进行代数恒等变换（代数简化）优化技术简介——对程序进行代数恒等变换（合并已知量） 5．编译过程分哪几个阶段答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。 6. 什么是文法答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。 7. 语义分析阶段的功能是什么答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。 8.代码优化须遵循哪些原则答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果 9.词法分析阶段的功能是什么答：

编译原理期末复习

编译原理期末复习鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 1、简答题（或者名词解释）下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。（1）简述编译程序的概念及其构成答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。 2)构成：（2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序 (3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合）答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序 3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。 4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。 6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序：对出错进行处理。 (4) 说明编译和解释的区别： 1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。（5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V T，V N，S，P)，其中V T：终结符集合(非空) V N：非终结符集合(非空)，且V T ?V N=? S：文法的开始符号，S?V N P：产生式集合(有限)。

王汝传编译原理习题答案

《编译原理》习题答案：第一次： P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？答：被翻译的程序称为源程序；翻译出来的程序称为目标程序或目标代码；将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；编译程序是将高级语言写的源程序翻译成目标语言的程序。关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。 P14 3、编译程序是由哪些部分组成？试述各部分的功能？答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。 P14 4、语法分析和语义分析有什么不同？试举例说明。答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。 P15 5、编译程序分遍由哪些因素决定？答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。补充： 1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。补充： 2、赋值语句：A：= 5 * C的语法和语义指的是什么？答：语法分析将检查该语句是否符合赋值语句规则，语义是指将 5 * C 的结果赋值为 A 。第二次作业： P38 1、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1*，T2+。 T2T1＝{011，0010，0111，01010，100111，1001010} T1*＝{ε，11，010，1111，11010，01011，010010……} T2+＝{0，01，1001，00，001，01001，010，0101……}

《编译原理》模拟期末试题汇总 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

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

一．填空题（每空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 ．该句子有两棵不同的语法树

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

编译原理期末复习题

3.2是非判断，对下面的述，正确的在述后的括号写T，否则写F。 (1)有穷自动机接受的语言是正则语言。（） (2)若r1和r2是Σ上的正规式，则r1|r2也是。（） (3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。（） (4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b*(a|b)*。（） (5)对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。（） (6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（）答案 (1) T (2) T (3) F (4) F (5) T (6) T 3.3描述下列各正规表达式所表示的语言。 (1) 0(0|1)*0 (2) ((ε|0)1*)* (3) (0|1)*0(0|1)(0|1) (4) 0*10*10*10* (5) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 答案 (1) 以0开头并且以0结尾的，由0和1组成的符号串。 (2) {α|α∈{0,1}*} (3) 由0和1组成的符号串，且从右边开始数第3位为0。 (4) 含3个1的由0和1组成的符号串。{α|α∈{0,1}+，且α中含有3个1 } (5) {α|α∈{0,1}*,α中0和1为偶数} 3.4对于下列语言分别写出它们的正规表达式。 (1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。 (2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 (3) Σ={0,1}上的含偶数个1的所有串。 (4) Σ={0,1}上的含奇数个1的所有串。 (5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。 (6) 不包含子串011的由0和1组成的符号串的全体。 (7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。答案 (1) 令Letter表示除这五个元音外的其它字母。 ((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))* (2) A*B*....Z* (3) (0|10*1)* (4) (0|10*1)*1

《编译原理》期末考试复习题

《编译原理》期末考试复习题一、是非题（请在括号内，正确的划√，错误的划×）（每个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．简单优先文法允许任意两个产生式具有相同右部。 () 三、填空题(每空1分，共10分) 1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__ ___和 ___ _。表格管理出错处理_ 2．若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。 _目标程序_编译程序 3．编译方式与解释方式的根本区别在于__ __。是否生成目标代码_ 4．对编译程序而言,输入数据是__ __, 输出结果是__ ___。 _源程序目标程序

5．产生式是用于定义__ __的一种书写规则。 _语法成分 6．语法分析最常用的两类方法是___ __和__ __分析法。自上而下_自下而上四、简答题（20分） 1. 什么是句子？什么是语言 ? 答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。() ×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3．递归下降分析法是自顶向上分析方法。() ×4．产生式是用于定义词法成分的一种书写规则。() √5．LR 法是自顶向下语法分析方法。() √6．在SLR （1 ）分析法的名称中，S的含义是简单的。() ×7．综合属性是用于“ 自上而下” 传递信息。() ×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。() ×9．程序语言的语言处理程序是一种应用软件。() ×10．解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。

编译原理复习题及答案

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

(2020年整理)编译原理期末总复习题(含答案).doc

第八节习题一、单项选择题 1、将编译程序分成若干个“遍”是为了 b 。 a．提高程序的执行效率 b．使程序的结构更加清晰 c．利用有限的机器内存并提高机器的执行效率 d．利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握 d 。 a．源程序b．目标语言 c．编译方法d．以上三项都是 3、变量应当 c 。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在 b 上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、 d 不可能是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用 a 可以定义一个程序的意义。 a．语义规则b．词法规则 c．产生规则d．词法规则 7、词法分析器的输入是 a 。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- d 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对 d 。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循 b 。 a．语义规则b．语法规则 c．构词规则d．等价变换规则解答 1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。 2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。 3、对编译而言，变量既持有左值又持有右值，故选c。 4、编译程序打交道最多的就是各种表格，因此选d。 5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。 6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。 7、b 8、c 9、d 10、c 二、多项选择题

编译原理考试试卷

南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷一、选择题（每题2分，共20分）得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。 A．字符串 B．运算符号 C．开始符号 D．文法 2.程序的基本块是指_____。 A．一个子程序 B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段 D．一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____分析方法。 A．自左向右 B．自顶向下 C．自底向上 D．自右向左 4．经过编译所得到的目标程序是_____。 A．四元式序列 B．间接三元式序列 C．二元式序列 D．机器语言程序或汇编语言程序 5．运行阶段的存储组织与管理的目的是_____。 ①提高编译程序的运行速度②节省编译程序的存储空间 ③提高目标程序的运行速度④为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④②6．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值 7．正规式M 1 和M 2 等价是指_____。

A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 8．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化二、名词解释（每题2分，共20分）得分 1.最左推导： 2.语法： 3.文法： 4.基本块： 5.语法制导翻译： 6.短语： 7.规范句型：

编译原理试题及答案

参考答案一、单项选择题(共10小题，每小题2分，共20分) 1．语言是 A ．句子的集合 B ．产生式的集合 C ．符号串的集合 D ．句型的集合 2．编译程序前三个阶段完成的工作是 A ．词法分析、语法分析和代码优化 B ．代码生成、代码优化和词法分析 C ．词法分析、语法分析、语义分析和中间代码生成 D ．词法分析、语法分析和代码优化 3．一个句型中称为句柄的是该句型的最左 A ．非终结符号 B ．短语 C ．句子 D ．直接短语 4．下推自动机识别的语言是 A ．0型语言 B ．1型语言 C ．2型语言 D ．3型语言 5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A ．字符 B ．单词 C ．句子 D ．句型 6．对应Chomsky 四种文法的四种语言之间的关系是 A ．L 0?L 1?L 2?L 3 B ．L 3?L 2?L 1?L 0 C ．L 3=L 2?L 1?L 0 D ．L 0?L 1?L 2=L 3 7．词法分析的任务是 A ．识别单词 B ．分析句子的含义 C ．识别句子 D ．生成目标代码 8．常用的中间代码形式不含 A ．三元式 B ．四元式 C ．逆波兰式 D ．语法树 9．代码优化的目的是 A ．节省时间 B ．节省空间 C ．节省时间和空间 D ．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A ．把高级语言翻译成汇编语言 B ．把高级语言翻译成机器语言 C ．把中间代码变换成依赖具体机器的目标代码装订线

D．把汇编语言翻译成机器语言二、填空题（本大题共5小题，每小题2分，共10分） 1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。 5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。三、名词解释题(共5小题，每小题4分，共20分) 1．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。 2．LL(1)文法若文法的任何两个产生式A →α | β都满足下面两个条件：（1）FIRST(α) ? FIRST(β ) = φ；（2）若β?* ε，那么FIRST(α) ? FOLLOW( A ) = φ。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。 3．语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征： (1)根节点的标记是开始符号S。 (2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…A R，那么A→A1A2…A R一定是P中的一条产生式。

文档之家

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

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

编译原理复习题--有答案版

四川大学编译原理期末复习总结

编译原理期末复习

王汝传编译原理习题答案

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

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

最新编译原理试题汇总+编译原理期末试题(8套含答案+大题集)

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

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

编译原理期末复习题

《编译原理》期末考试复习题

编译原理复习题及答案

(2020年整理)编译原理期末总复习题(含答案).doc

编译原理考试试卷

编译原理试题及答案