电子科技大学编译原理--A1答案--网络教育

1、计算机编译原理试卷 A1 参考答案一、单项选择题(每小题 1 分，共 25 分)1、语言是 AA、句子的集合B、产生式的集合C、符号串的集合 D、句型的集合2、 编译程序前三个阶段完成的工作是 CA、词法分析、语法分析和代码优化B、代码生成、代码优化和词法分析C、词法分析、语法分析、语义分析和中间代码生成D、词法分析、语法分析和代码优化3、 一个句型中称为句柄的是该句型的最左 DA、非终结符号B、短语C、句子D、直接短语4、 下推自动机识别的语言是 CA、 0 型语言 B、 1 型语言 C、 2 型语言 D、 3 型语言5、扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最

2、小语法单位即 BA、字符B、单词C、句子 D、句型6、 对应ChomSky四种文法的四种语言之间的关系是 BA、 L0L1L2L3B、 L3L2L1L0C、L3=L2 L1 L0 D、 L0 L1L2=L37、 词法分析的任务是AA、识别单词B、分析句子的含义C、识别句子D、生成目标代码8、 常用的中间代码形式不含DA、三元式B、四元式C、逆波兰式D、语法树9、 代码优化的目的是CA、节省时间B、节省空间C、节省时间和空间D、把编译程序进行等价交换10、 代码生成阶段的主要任务是CA 、把高级语言翻译成汇编语言B 、把高级语言翻译成机器语言C、把中间代码变换成依赖具体机器的目标代码D 、把汇编

3、语言翻译成机器语言11、 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组B 。A、字符串B、产生式C、数字符号D、文法12、 程序的基本块是指D 。A、一个子程序B、一个仅有一个入口和一个出口的语句C、一个没有嵌套的程序段D、一组顺序执行的程序段，仅有一个入口和一个出口13、 高级语言编译程序常用的语法分析方法中，递归下降分析法属于B 分析方 法。A、自左向右 B、自顶向下 C、自底向上D、自右向左14、 在通常的语法分析方法中，A 特别适用于表达式的分析。A、算符优先分析法B、LR分析法C、递归下降分析法D、LL (1)分析法15、 经过编译所得到的

4、目标程序是D。A、四元式序列B、间接三元式序列C、二元式序列D、机器语言程序或汇编语言程序16、 一个文法所描述的语言是 A。A、唯一的B、不唯一的C、可能唯一，也可能不唯一D、无法确定17、 描述一个语言的文法是 C。A、唯一的B、不唯一的C、可能唯一，也可能不唯一D、以上都不正确18、设有文法 GI ： I I1 |I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有 B。 ab a0c01 aaa bc1O可选项有：A、B、C、D、19、运行阶段的存储组织与管理的目的是 C。 提高编译程序的运行速度 节省编译程序的存储空间 提高目标程序的运行速度可选项有：A、 B、C、20、将编译程

5、序分成若干个“遍”是为了 为运行阶段的存储分配做准备D、B。A、提高程序的执行效率B、使程序的结构更加清晰C、利用有限的机器内存并提高机器的执行效率D、禾U用有限的机器内存但降低了机器的执行效率21、通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标 代码生成等五个部分，还应包括 C。A、模拟执行器B、解释器C、表格处理和出错处理D、符号执行器22、一个句型中的最左 B称为该句型的句柄。A、短语B、简单短语C、素短语 D、终结符号23 、 设 G 是 一 个 给 定 的 文 法 ， S 是 文 法 的 开 始 符 号 ， 如 果x（其中X V*）,则称X是文法G的一个

6、._ BA、候选式B、句型C、单词 D、产生式24、一个上下文无关文法G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 D。A、句子 B、句型C、单词D、产生式25、文法 GE ：E T E + TT F T * FF a ( E)该文法句型E + F* (E + T)的简单短语是下列符号串中的 B。( E+ T)E+ T F F* (E + T)可选项有：A、和B、和C、和 D、二、判断题(每小题 1 分，共 10分)( ) 26、对任意一个右线性文法 G,都存在一个 NFA M ,满足L(G)=L(M)。( ) 27、对任意一个右线性文法 G,都存在一个

7、DFA M ,满足L(G)=L(M)。( ) 28、对任何正规表达式 e,都存在一个 NFA M ,满足L(G)=L(e)。( ) 29、对任何正规表达式 e,都存在一个 DFA M ,满足L(G)=L(e)。( × ) 30、计算机高级语言翻译成低级语言只有解释一种方式。( × ) 31、在编译中进行语法检查的目的是为了发现程序中所有错误。( × ) 32、甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统 功能完全相同。( ) 33、正则文法其产生式为 A a, A Bb, A,B VN, a、b VTO(× ) 34、每个文法都能

8、改写为 LL(1)文法。( ) 35、递归下降法允许任一非终极符是直接左递归的。三、名词解释题(每小题4 分，共 8 分)36、归约我们称直接归约出 A ,仅当 A 是一个产生式，且>(VN U Vt)*。归约过程就是从输入串开始， 反复用产生式右部的符号替换成产生式左部符号， 直至文法开始符。37、推导我们称 A 直接推出 ,即 A ,仅当 A 是一个产生式，且> (VN U Vt)*。如果 1 2 n,则我们称这个序列是从1至 2的一个推导。若存在一个从 1 n的推导，则称 1可推导出 n。推导是归约的逆过程。四、简答题(每小题 4 分,共 8分)38、试给出非确定自动机的定义

9、。答：一个非确定的有穷自动机( NFA) M 是一个五元组： M=(K, f, S , Z)。 其中 :(1) K 是一个有穷集,它的每个元素称为一个状态；(2 )是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；(3) f 是状态转换函数,是在K× *K 的子集的映射,即, f: K×*2K ；表明在某 状态下对于某输入符号可能有多个后继状态；(4) S ( K 是- 个非空初态集；( 5) Z ( K 是一 个终态集(可空) 。39、编译程序的工作分为那几个阶段？答：词法分析、语法分析和语义分析是对源程序进行的分析 （称为编译程序的前端），而中间 代

10、码生成、代码优化和代码生成三个阶段合称为对源程序进行综合 （称为编译程序的后端）， 它们从源程序的中间表示建立起和源程序等价的目标程序。五、应用题（每小题 5分，共25分）40、对于文法 GS : SAB，A AalbB，B aSb求句型baSb的全部短语、直接短语和句 柄？句型baSb的语法树如下图所示。答：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于 A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语 和句柄。41、设有非确定的有自限动机NFA M=（A，B，C，0，1，A，C）,其中：（A，0）=C （A，1）

11、=A，B （B，1）=C （C, 1）=C。请画出状态转换距阵和状 态转换图。答：状态转换距阵为:01ACA，BBCCC状态转换图为:42、文法 GS:S aSPQabQQP PQ bP bb bQ bccQ CC（1）它是ChomSky哪一型文法？（2）它生成的语言是什么？答：（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部 的符号长度，所以文法 GS是ChOmSkyI型文法，即上下文有关文法。（2） 按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到:S abQ abcS aSPQ aabQPQ aabPQQ aabbQQ aabbcQ

12、aabbccS aSPQ aaSPQPQ aaabQPQPQ aaabPQQPQ aaabPQPQQ aaaPPQQQ aaabbPqqq aaabbQQQ aaabbbcQQ aaabbbccQ aaabbbccc于是得到文法GS生成的语言L=a nbncnn 143、下面文法GS是否为LL (1)文法？说明理由。S A BlPQXA XyB bcP d P| Q aQ| 答：该文法不是 LL ( 1)文法。只有三个非终结符有两个选择。(1) P的两个右部d P和的开始符号肯定不相交。(2) Q的两个右部a Q和的开始符号肯定不相交。(3) 对S来说，由于x FIRST(A B)，同时也有x

13、 FIRST(P Q x)(因为P和Q都可能为空)所以该文法不是 LL ( 1)文法。44、设有文法GS:S aAA AbA b求识别该文法所有活前缀的DFA。答：(1)首先拓广文法：在G中加入产生式0.S'S,然后得到新的文法 G':0.S' S1.S aA2. A Ab3. A b再求G '的识别全部活前缀的 DFA :六、综合题(每小题 8分，共24分)45、对给定正规式 b* (d|ad) (b|ab) +,构造其NFA M。答：首先用A+=AA *改造正规式得：b*(d|ad)(b|ab)(b|ab)*;其次，构造该正规式的 NFA M，如 下图所示。

14、46、将文法GV改造成为LL(I)的。GV : V NNEE VV+EN i答：对文法GV提取公共左因子后得到文法：GV : V NAA EE VBB |+EN i求出文法GV中每一个非终结符号的FIRST集：FlRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一个非终结符号的FoLLoW集：FoLLoW(V)=# U FIRST(B) U FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST() U FOLLOW(B)= FIRST() U FOLLOW(E)=FOL

15、LOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A) U FOLLOW(V)=,+,#可以看到，对文法 G ' V的产生式A |E,有FIRST(E) FOLLOW(A)= +,#= ?对产生式B | + E ,有FIRST(+E) FOLLOW(B)=+ = ?而文法的其他产生式都只有一个不为的右部，所以文法G ' V是LL(I)文法。47、 对于文法 GS : S ASIbA SAla(1) 列出所有LR (0)项目(2) 列出构成文法 LR (0)项目集规范族。答：首先将文法G拓广为GS:S' SS ASIbA SA|a(1)文法GS 的L

16、R ( 0)项目是:1、S S5、SAS 9、A S A2、S S6、S b10、A SA 3、SAS7、S b 11、 A a4、SAS8、A SA12、 Aa（ 2）列出构成文法 LR （ 0）项目集规范族。用 -CLOSURE （闭包）办法构造文法 G 的 LR （ 0）项目集规范族如下:0: 1、 S S3:9、 AS A6: 12、 A a3、 S AS8、 A SA7: 7、 Sb8、 A SA3、 S AS11 、 A a6、 S b6、 S b11、 A a1: 2、 S S4: 10、 A SA9、 AS A4、 S A S8、 A SA3、 S AS11、 A a6、 S b3、 S A