文档库 最新最全的文档下载
当前位置:文档库 › 编译原理试题及答案3

编译原理试题及答案3

编译原理试题及答案3
编译原理试题及答案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、一个文法符号的综合属性是通过语法树中它的(子)结点的属性来计算的。

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 }

FIRSTVT(R)={;,(,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 (E )={ +,↑,},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=>aaabbabbb A=>aaabbabbba 最右推导:

S=>aB=>aaBB=>aaBbS=>aaBbbA=>aaBbba=>aaaBBbba=>aaaBbbba=>aaabSbbba=>aaabbAbbba=>a aabbabbba

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->E 1E 2+ E->E 1E 2* E->id

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

D->TL T->int|real L->L 1,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’ 是文法的开始符号。

S’->S

S->Aa|dAb|Bb|dBa

A->c

B->c

11、对下面的文法G:

S’->bAAB|bA

A->dSa|b

B->cAa|c

(1)判断此文法是下列文法中的哪一种?并说明理由。

LR(0)、SLR(1)、LALR(1)、LR(1)

(2)构造相应文法的项目集族和分析表。

12、对下面的文法G[S]:

S->aBc|bAB

A->aAb|b

B->b|ε

构造其LL(1)分析表,并利用符号栈分析符号串baabbb是否是该文法的句子。

13、对下面的文法G:

E->E+T|T

T->T*F|F

F->(E)|I

(1)构造其消除直接左递归后的文法G’;

(2)构造文法G’ 的LL(1)分析表,并利用符号栈分析符号串i

1*i

2

+i

3

是否是该文法

的句子。

14、对下面的文法G:

P->begind;Xend

X->d;X|sY

Y->;sY|ε

构造文法G’ 的LL(1)分析表

15、对下面的文法G:

E->TE’

E’->+E|ε

T->FT’

T’->T|ε

F->PF’

F’->*F’|ε

P->(E)|a|b|Λ

(1)计算这个文法的每个非终结符的FIRST和FOLLOW集合;

(2)证明这个文法是LL(1)的;

(3)构造它的预测分析表;

(4)构造它的递归下降分析程序。

16、对文法G(S):

S → S ∨ a T | a T | ∨ a T

T →∧ a T | ∧ a

(1) 消除该文法的左递归和提取左公因子;

(2) 构造各非终结符的FIRST和FOLLOW集合;

(3) 构造该文法的LL(1)分析表,并判断该文法是否是LL(1)的。

17、设字母表∑={ a,b},给出∑上的一个正则式b*abb*(abb*)。

(1)构造该正则式所对应的NFA(画出转换图);

(2)将所求的NFA确定化(画出DFA的转换图);

(3)将所求出的DFA最小化(画出极小化后的转换图);

(4)该正则式所表示的正则集是什么?试用自然语言描述之。

18、设字母表∑={ a,b},给出∑上的一个正则式(a *|b*)b(ba)*。

(1)构造该正则式所对应的NFA(画出转换图);

(2)将所求的NFA确定化(画出DFA的转换图);

(3)将所求出的DFA最小化(画出极小化后的转换图);

19、设有语言 L= {α | α∈ {0,1} + ,且α不以 0 开头,但以 00 结尾 } 。

⑴试写出描述 L 的正规表达式;

⑵构造识别 L 的 DFA (要求给出详细过程,并画出构造过程中的 NDFA、DFA 的状态转换图,以及 DFA 的形式化描述 ) 。

20、设字母表∑={ a,b},给出∑上的一个正则式(a|b)*(aa|bb)(a|b)*。

(1)构造该正则式所对应的NFA(画出转换图);

(2)将所求的NFA确定化(画出DFA的转换图);

(3)将所求出的DFA最小化(画出极小化后的转换图);

21、设字母表∑={ a,b},给出∑上的一个正则式(a|b)*a(a|b)。

(1)构造该正则式所对应的NFA(画出转换图);

(2)将所求的NFA确定化(画出DFA的转换图);

(3)将所求出的DFA最小化(画出极小化后的转换图);

22、设有语言L={ α | α∈ {0,1} + ,且α不以 0 开头,但以 00 结尾 } 。

⑴试写出描述 L 的正规表达式;

⑵构造识别 L 的 DFA (要求给出详细过程,并画出构造过程中的 NDFA 、 DFA 的状态转换图,以及 DFA 的形式化描述 ) 。

答:( 1 )正规表达式: 1(0|1) * 00

( 2 )第一步:将正规表达式转换为 NDFA

第二步:将 NDFA 确定化为 DFA :

状态输入I 0 I 1 t 0 1

[S] —[A,D,B] q 0 —q 1

[A,D,B] [D,B,C] [D,B] 重新命名q 1 q 2 q 3

[D,B,C] [D,B,C,Z] [D,B] q 2 q 4 q 3

[D,B] [D,B,C] [D,B] q 3 q 2 q 3

[D,B,C,Z] [D,B,C,Z] [D,B] q 4 q 4 q 3

DFA 的状态转换图

第三步:给出 DFA 的形式化描述

DFA M = ( { q 0 , q 1 , q 2 , q 3 , q 4 }, {0,1}, t, q 0 , { q 4 } )

t 的定义见 M 的状态转换表。

23、给定文法 G[S] :

S → SaA|a

A → AbS|b

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

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

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

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

答:(1)拓广文法:

G[S′]: S′→ S ⑴ S → SaA ⑵ S → a ⑶

A → AbS ⑷ A → b ⑸

该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA :⑵该文法的 LR(0) 分析表:

状态ACTION GOTO

a b # S A

0 S 2 1

1 S 3 acc

2 r

3 r 3 r 3

3 S 5 4

4 r 2 r 2 /S 6 r 2

5 r 5 r 5 r 5

6 S 2 7

7 r 4 /S 3 r 4 r 4

⑶ LR(0) 文法:该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突状态。

该文法不是 LR(0) 文法,因为存在冲突状态: I 4 和 I 7。

⑷ SLR(1) 文法:该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态,冲突可用 FOLLOW 集解决。

该文法不是 SLR(1) 文法。因为 FOLLOW(S)={a,b,#} ,所以无法解决冲突。

24、对下面的文法G:

S->aBc|bAB

A->aAb|b

B->b|ε

(1)计算这个文法的每个非终结符的FIRST和FOLLOW集合;

(2)证明这个文法是LL(1)的;

(3)构造它的预测分析表。

答:(1)first(B)={b, ε},first(A)={a,b},first(S)={a,b}

Follow(S)={#},follow(A)={b,#},follow(B)={c,#}

(2)因为只有FIRST(B)含有ε , 所以只考虑:

FOLLOW(B)=FIRST(c) ?FOLLOW(S)={c, #}

∴该文法的LL(1)表

(3)该文法的LL(1)分析表如下:

a b c #

S aBc bAB

A aAb b

B b εε

25、设字母表∑={ a,b},对于以aa或ab结尾的字的正规集。(1)请写出描述该语言的正规式。

(2)构造该正规式所对应的NFA(画出转换图);

(3)将所求的NFA确定化(画出DFA的转换图);

(4)将所求出的DFA最小化(画出极小化后的转换图);答:(1)正则式为:(a|b)*a(a|b)。(1分)(2)由正则式得到的转换系统如下图:(1分)

(3)由子集法构造的DFA如下图:

(4)DFA最小化如下图:

26、设文法G为 S → E

E→ TE | ε

T → eT | t

(1)证明它是LR(1)文法;

(2)构造它的LR(1)分析表;

(3)给出输入符号串etet的分析过程。

答:(1)拓广文法G’:(1分)

(0) S' →S (1) S → E (2) E→ TE

(3) E →ε (4) T → eT (5) T → t

FIRST(A) = {ε, e,t}

FIRST(B) = {e, t}

构造的DFA如下:

由项目集规范族看出,不存在冲突动作。

∴该文法是LR(1)文法。

(2)

LR(1)分析表

状态Action Goto e t # S E T

0 S4 S5 r3 1 2 3

1 acc

2 r1

3 S

4 S

5 r3

6 3

4 S4 S

5 7

5 r5 r5 r5

6 r2

7 r4 r4 r4

(3)输入串abab的分析过程为:

步骤状态栈符号栈当前字符剩余字符串动作

(1) 0 # e tet# 移进

(2) 04 #e t et# 移进

(3) 045 #et e t# 归约 T→t

(4) 047 #eT e t# 归约 T→et

(5) 03 #T e t# 移进

(6) 034 #Te t # 移进

(7) 0345 #TeT # 归约 T→t

(8) 0347 #TeT # 归约 T→et

(9) 033 #TT # 归约 E→ε

(10) 0336 #TTE # 归约 E→TE

27、对文法G(S):

S → S ∨ a T | a T | ∨ a T

T →∧ a T | ∧ a

(1) 消除该文法的左递归和提取左公因子;

(2) 构造各非终结符的FIRST和FOLLOW集合;

(3) 构造该文法的LL(1)分析表,并判断该文法是否是LL(1)的。

答:(1)消除左递归

S → a T S’ | ∨ a T S’

S’→∨ a T S’ | ε

T → T →∧ a T | ∧ a

提取左公因子

S → a T S’ | ∨ a T S’

S’→∨ a T S’ | ε

T →∧ a T’

T’→ T | ε

(2) 各非终结符的FIRST和FOLLOW集合:

FIRST(S)={a,∨} FIRST(S')={ ∨,ε} FIRST(T)={ ∨ }

FIRST(T')={ ∨,ε} FOLLOW(S)={#} FOLLOW(S')={#}

FOLLOW(T)={∨,#} FOLLOW(T')={∨,#}

(3) LL(1)分析表如下(3分) ,该文法是LL(1)文法。(1分)

编译原理与实践第三章答案

The exercises of Chapter Three 3.2 Given the grammar A →AA|(A)|ε a. Describe the language it generates; b. Show that it is ambiguous. [Solution]: a. Generates a string of balanced parenthesis, including the empty string. b. parse trees of ():3.3 Given the grammar exp → exp addop term | term addop → + | - term → term mulop factor| factor mulop → * factor → ( exp ) | number Write down leftmost derivations, parse trees, and abstract syntax trees for the following expression: a. 3+4*5-6 b. 3*(4-5+6) c. 3-(4+5*6) [Solution]: a.The leftmost derivations for the expression 3+4*5-6: Exp => exp addop term =>exp addop term addop term =>term addop term addop term=> factor addop term addop term =>3 addop term addop term => 3 + term addop term =>3+term mulop factor addop term =>3+factor mulop factor addop term A ()εA A A A A ()εε

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

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

编译原理课后习题答案(第三版)

精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法: E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树:/********************************

编译原理_第三版_课后答案

编译 原理 课后题答案 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法: E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导:

E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树:/******************************** E E F T E + T F F T +i i i E E F T E -T F F T -i i i E E F T +T F F T i i i *i+i+i i-i-i i+i*i *****************/ P36-9 句子iiiei 有两个语法树: S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ???????? P36-10 /************** ) (|)(|S T T TS S →→ ***************/ P36-11 /*************** L1: ε ||cC C ab aAb A AC S →→→ L2:

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

编译原理考试题及答案汇总 一、选择 1.将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2.正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3.中间代码生成时所依据的是 _C_。 A.语法规则 B.词法规则 C.语义规则 D.等价变换规则 4.后缀式 ab+cd+/可用表达式__B_来表示。 A. a+b/c+d B.(a+b)/(c+d) C. a+b/(c+d) D. a+b+c/d 6.一个编译程序中,不仅包含词法分析,_A____,中间代码生成,代码优化,目标代码生成等五个部分。 A.( ) 语法分析 B.( )文法分析 C.( )语言分析 D.( )解释分析 7.词法分析器用于识别__C___。 A.( ) 字符串 B.( )语句 C.( )单词 D.( )标识符 8.语法分析器则可以发现源程序中的___D__。 A.( ) 语义错误 B.( ) 语法和语义错误 C.( ) 错误并校正 D.( ) 语法错误 9.下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A.( ) (1)(2) B.( ) (1) C.( ) (1)(2)(3) D.( ) (2)(3) 10.解释程序处理语言时 , 大多数采用的是__B___方法。 A.( ) 源程序命令被逐个直接解释执行 B.( ) 先将源程序转化为中间代码 , 再解释执行 C.( ) 先将源程序解释转化为目标程序 , 再执行 D.( ) 以上方法都可以 11.编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A.( ) (2)(3) B.( ) (2)(3)(4)C.( ) (1)(2)(3) D.( ) (1)(2)(3)(4) 12.编译程序是一种___C__。 A. ( ) 汇编程序 B.( ) 翻译程序 C.( ) 解释程序 D.( ) 目标程序 13.文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B.( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C.( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14.文法分为四种类型,即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B.( ) 正则文法 C.( ) 上下文有关文法 D.( ) 上下文无关文法15.一个上下文无关文法 G 包括四个组成部分,它们是:一组非终结符号,一组终结符号,一个开始符号,以及一组 __D___。 A.( ) 句子 B.( ) 句型 C.( ) 单词 D.( ) 产生式 16.通常一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目标代码生成等五个部分,还应包括_C____。

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

一、填空题(每空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、什么是文法的二义性?下面的文法是二义的吗?为什么?

编译原理第3章 习题解答

第3章习题解答 1.构造正规式1(0|1)*101相应的DFA. [答案] 先构造NFA ============================================================== 2.将下图确定化:

[答案] 重新命名,令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。 ================================================================ 3.把下图最小化: [答案] (1)初始分划得Π0:终态组{0},非终态组{1,2,3,4,5}

对非终态组进行审查: {1,2,3,4,5}a {0,1,3,5} 而{0,1,3,5}既不属于{0},也不属于{1,2,3,4,5} ∵{4} a {0},所以得新分划 (2)Π1:{0},{4},{1,2,3,5} 对{1,2,3,5}进行审查: ∵{1,5} b {4} {2,3} b {1,2,3,5},故得新分划 (3)Π2:{0},{4},{1, 5},{2,3} {1, 5} a {1, 5} {2,3} a {1,3},故状态2和状态3不等价,得新分划 (3)Π3:{0},{2},{3},{4},{1, 5} 这是最后分划了 (4)最小DFA : ======================================= 4.构造一个DFA ,它接收Σ={0,1}上所有满足如下条件的字符串:每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。 [答案] 按题意相应的正规表达式是0*(100*)*0* 构造相应的DFA ,首先构造NFA 为 用子集法确定化 可最小化,终态组为G1={C, D},非终态组为G2={S, A, B} 对于G2分析:f(S,0)=A, f(A,0)=A, 后继状态均属于G2 而f(B,0)=C, 后继状态属于G1 将G2分割成G21={S ,A}, G22={B}

编译原理试题及答案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、一个文法符号的综合属性是通过语法树中它的(子)结点的属性来计算的。

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

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

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

期末考试试卷(A)卷 一、填空题(每小题2分,共20分) 1、字母表∑,用∑*表示∑上所有有穷长的串集合,∑*称为∑的①。 2、设z=abc,则z的固有头是①。 3、如何由语言基本符号组成程序中各个语法成分(包括程序)的一组规则叫 ①。 4、设∑={a,b},∑上的正规式(a|b)(a|b) 相应的正规集为① 5、NFA的映象f是从"状态×字"映射到"状态子集",f为①值函数。 6、LR分析是按规范句型的①为可归约串。 7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。 8、如果分析树中一结点的属性b依赖于属性c,那么这个结点的属性b的语义规 则的计算必须在定义属性c的语义规则的计算①。 9、对于栈式符号表,引入一个显示嵌套层次关系表- ①表,该表总是 指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。 10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk 的一条通路。如果n1=nk,则称该通路为①。 二、单项选择(每小题2分,共14分) 1、乔姆斯基把文法分成4种类型,即0型、1型、2型和3型。其中3型文法也称 为()。 A.上下无关文法 B.正规文法 C.上下文有关文法 D.无限制文法 2、生成非0开头的正偶数集的文法是()。 A. Z::=ABC B. Z::=ABC C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|ε B::=BA|B0|0 A::=1|2|3|…|9 A::=1|2|3|…|9 C. Z::=ABC|2|4|6|8 D. Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|ε A::=1|2|3|…|9 A::=1|2|3|…|9 3、简单优先分析法从左到右扫描输入串,当栈顶出现()时进归约。

编译原理试题及答案

参考答案 一、单项选择题(共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中的一条产生式。

编译原理试题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.其他

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

《编译原理》考试试题及答案(汇总) 一、是非题(请在括号,正确的划√,错误的划×)(每个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.( ) 代码外提

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

第一章 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)

编译原理期末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分)

编译原理试题及答案——加强版

编译原理试题及答案 <高级版> 一、对于文法 G[S] : S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB ⑴ (3 分 ) 请写出三个关于 G[S] 的句子; ⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型?试证明你的结论。 ⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。 二、请构造一个文法,使其产生这样的表达式 E :表达式中只含有双目运算符 + 、 * ,且 + 的优先级高于 * , + 采用右结合, * 采用左结合,运算对象只有标识符 i ,可以用括号改变运算符优先级。要求给出该文法的形式化描述。 三、设有语言 L={ α | α∈ {0,1} + ,且α不以 0 开头,但以 00 结尾 } 。 ⑴试写出描述 L 的正规表达式; ⑵构造识别 L 的 DFA (要求给出详细过程,并画出构造过程中的 NDFA 、 DFA 的状态转换图,以及 DFA 的形式化描述 ) 。 四、给定文法 G[S] : S → AB A → a B | bS | c B → AS | d ⑴ (6 分 ) 请给出每一个产生式右部的 First 集;

⑵ (3 分 ) 请给出每一个非终结符号的 Follow 集; ⑶ (8 分 ) 请构造该文法的 LL(1) 分析表; ⑷ (8 分 ) 什么是 LL(1) 文法?该文法是 LL(1) 文法吗?为什么? 五、给定文法 G[S] : S → SaA|a A → AbS|b ⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵请构造该文法的 LR(0) 分析表。 ⑶什么是 LR(0) 文法?该文法是 LR(0) 文法吗?为什么? ⑷什么是 SLR(1) 文法?该文法是 SLR(1) 文法吗?为什么? 六、给定下列语句: if a+b>c then x := a*(b-c) + (b*c-d)/e ⑴写出其等价的逆波兰表示; ⑵写出其等价的四元式序列。 七、已知下列 C 语言程序: int * f() { int a = 100; return &a; } main()

编译原理(清华大学 第2版)课后习题答案

第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题

第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12.

短语: 直接短语: 句柄: 13.(1)最左推导:S => ABS => aBS =>aSBBS => aBBS => abBS => abbS => abbAa => abbaa 最右推导:S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) 文法:S → ABS S → Aa S →ε A → a B → b (3) 短语:a1 , b1 , b2, a2 , , bb , aa , abbaa, 直接短语: a1 , b1 , b2, a2 , , 句柄:a1 14 (1) S → AB A → aAb | ε B → aBb | ε (2) S → 1S0 S → A A → 0A1 |ε 第四章 1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101 NFA (2) 1(1010*|1(010)*1)*0 NFA

相关文档