编译原理期末总复习题含答案

第八节习题1、将编译程序分成若干个“遍”是为了 d。 c．既持有左值又持有右值d．既不持有左值也不持有右值 5、d 7、词法分析器的输入是

词8、中间代码生成时所遵循的是- 9、编译程序是对d b。53种，因此不是目标代码的只能选d。则，并且语义规则可以定义一个程序的意义。因此选a。 1、编译程序各阶段的工作都涉及到 2、编译程序工作时，通常有 语义分析？c．中间代码生 1、解释程序和编译程序的区别在于是否生成目标程序（解释不产生目标程序，边翻译边执 2、编译过程通常可分为5个阶段，分别是词法分析 、语法分析语义分析中间代码生 3、编译程序工作过程中，第一段输入是源程 4、编译程序是指将源程序 是否生成目标程序2、词法分 中间代码生成3、源程序目标代码生 1、文法G：S→xSx|y所识别的语言是 a.xyx b.(xyx)* c.xnyxn(n≥0) 2、文法G描述的语言L(G)是指ab L(G)={α|S+ L(G)={α|S*L(G)={α|S*L(G)={α|S+ a.上下文无关文 b.上下文有关文 d.短语文

α, a.若f(a)>g(b)，则 c.a~b都不一定成 d.a~b一定成 a.短 c.句 d.句 a.P+T和i b.P和P+Tc.i和P+T+id.P和T 9、文法G：S→b|∧(T) a.{b,∧,(} b.{b,∧,)} a.0 b.1 c.2 d.3 a.消除左递 b.消除右递 c.消除回 d.提取公共左因 a.直接短 b.句 c.最短 d.素短 B. a.最左推导的逆过 b.最右推导的逆过c.规范推 d.最左归约的逆过f(a)<g(b)abc。左推导，则必然有二义性。故选a。EE+FE+T P2-8-1句型P+T+I a.有向图是一个状态转换 b.状态转换图是一个有向 a.多种推导过程 b.多种最左推导过程 4、有一文法G：S→AB b.c. d.e. a.句 b.句 c.以单词为单位的程d.文法的开始 e.句 a.0型文法 b.1型文法 解答1、e、a、c 7、Chomsky把文法分为 解答1、空 2型 3型 （）（）（）（）（）解答1、对 为X1,X2,…,XK，则A→X1,X2,…,XK，必然是G的一个产生式。5、推导：我们称αAβ直接推出αγβ，即αAβαγβ，A→γ存在一个从α1αn的推导，则称α1可推导出αn。推导是归约的逆过程。α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。G[S]Chomsky1型文法，即上下文有关文法。于是得到文法G[S]生成的语言L={ a的个数；也即所求上下文无关文法G[S]为：4、有文法 S Aa c

S c 5、对于文法G[S]： L→L,

L（ L，

a 句型（S,（a）的语法#，（·a···证明T*P↑（T*F）是该文法的一个句型，并直接短语和句柄。直接短语有两个，即P和T*F；句柄为P。

F↑P a.语义规 b.构词规 c.语 d.等价变换规 a.单词的种别编 b.单词在符号表中的位c.单词的种别编码和自身 d.单词自身 c.M1和M2所识别的语言集相等 4、状态转换图（见图3-6-1）接受的字集为 0 0a.以0开头的二进制数组成的集 b.以0结尾的二进制数组成的集c.含奇数个0的二进制数组成的集 d.含偶数个0的二进制数组成的集 a.词法分析器应作为独立的一 b.词法分析器作为子程序较c.词法分析器分解为多个过程，由语法分析器选择使用d.词法分析器并一个独立的阶段 a.基本 b.四元 c.运算d.逆波兰 e.常 a. b. d. e.解答1、a、c、 （）（）（）（）（）（）（）8eDFAML(G)=L(e)（） 1、2、3、错4、5、6、7、8、正 确定有限自动机，先画出NFAM相应的状态图，如图3-6-2所示。aaabXbbY I—3-6-4ab0211—2222M′=（{0,1,2},{a,b},f,0,{1,2}，其状态转换图如图3-6-5a DFAM′。ab 2、对给定正规式b*（d|ad（b|ab）+，NFAXYX123XYX123YbdbXε 2 ε5 bdbbXε 2 ε aaab 83-6-7NFAD→TLL→idRR→,idR|ε分析虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。FIRST（D）=FIRST（T）={int,real} R→ε填在输入符号#的栏目中。 ，#DTLL→idRR→,idR→2、下面文法G[S]是否为LL（1）文法？说明理由。S→AB|PQx A→xy B→bcP→dP| Q→aQ|LL（1）文法，见下面分析中的说明。分析只有三个非终结符有两个选择。1、PdP和ε2、QaQε所以该文法不是LL（1）文法。3、设有以下文法：D→Se|ε解答：（1）UFOLLOW集的过程如下：FIRST(D)∪FIRST(Ac)∪FIRST(e)∪{#}S→aAbDeB→SAc,所以FOLLOW（A）=FIRST（bDe）A→BSD，所以S→aAbDe|d、A→BSD|eB→SAc|cD因为产生式B→SAc|cD|ε中 abcde#SdAeBDεεε、将文法G[V]提取公共左因子后得到文法： FIRST(A)={[, FIRST(B)={+,ε}G′[VFOLLOW集：FOLLOW(A)=FOLLOW(V)={+,,#}FOLLOW(E)=FIRST(])\{ε}∪FOLLOW(B)=FIRST(])\{ε}∪FOLLOW(E)={]}FOLLOW(B)=FOLLOW(E)={]}可以看到，对文法G′[V]的产生式→E，有对产生式→，G[A]：→ε解答：（1）A→|ε 因该文法产生偶数（可以为0）个a，所以得到文法G′[A]：→ε此时对产生式→aa|，有FOLLOW(A)={#}∪FOLLOW(A)={#}，因而 A#A1aaaa1aaaa2#Aaaaaa3aaa4aa5#Aaaa67#8## ab()d#a⋗⋗b⋗⋗(⋖⋖⋖≖)⋗⋗d#⋖⋖⋖≖由S→a|b|(A)得：FIRSTVT(S)={a,b,();ASdFIRSTVT(A)={dASFIRSTVT(S)⊂FIRSTVT(A)由A→…dA得：LASTVT(A)={d},又由A→S得：LASTVT(S) 由#⋖FISTVT(S)得：#⋖a,#⋖b,#⋖LSTVT(S)⋗#得：d⋗⋗⋗#,⋗#。572。 ab()d#a⋗⋗⋗b⋗⋗⋗(⋖⋖⋖≖)⋗⋗⋗d⋖⋖⋖⋗⋖⋗#⋖⋖⋖≖，S，S（S简单短语（即直接短语）S

###

A→α，“A→α” a.LALR文法 a.SLR（1）⊂LR（0）bLR（1）⊂LR（0）c.SLR（1）⊂LR（1）d.无二义文法 提下，当α后跟终结符a时，才进行归约；因此选d。⊂5、选c。 4、对LR分析表的构造，有可能存在 c.移进/归约d.移进/移进e.归约/归约 a. b. c. 6、对LR分析器来说，存在 c.SLR（1）d.SLR（0）e.LR（1） 5、选a、b、c、d、e。 ，“R”表示 ，“0”表示 1、一张分析表3、规范句型4、输入串5、活前缀项目集合LR6、归约接受移进70个字符四、 →AS·和A→S·A 则是由I4中的4和8读入一个S字符后得到的下一个项目。状态全体构成了文法G′的LR（0）规范族。 3、后缀式ab+cd+/可用表达式 a. + 5、中间代码的树型表示 2、下面中间代码形式中，能正确表示算术表达式a+b+c的有

d+

b．goto语句c．条件语句 a．便于进行空间的组织b．利于目标代码的优化 6、下面的中间代码形式中，a+b*c。题*

3、当源程序中的标号出现“先后定义”时，中间代码的转移地址须持 ①a*(-②解答1、① ⑹ ⑹

第三节 . b.语义检 c.语法检 d.地址分 a.过程地 c.过程 c.名字有确切的属性 a.名字 b.类型 c.信息 d.值 b.填入新 d.杂凑技术 a.词法错 b.语法错 c.语义错d.编译错误 解答：1、a、c 标识符地址及长度2、拼写错误最小距离匹配3、词法分析语法语义分

a.动态b.栈 c.静态d.堆 a.先请先 b.先请后 c.后请先 d.任 a.递归过 b.可变体积的数据项 c.静态变 d.待定性质的名 a. b. c. a.保护 b.恢复 d.恢复 a.数 b.指针变 d.静态变 e.动态变 a.递归过 b.分程序结 c.动态变d.动态数 e.静态数 a.队 d.堆 a.定义新的活动记录的 b.保护返回地 c.传递参数d.建立DIS Y表 e.定义新的活动记录的TOP b.静态数 d.待定性质的名 e.静态变 a.局部变 b.连接数 c.形式单d.局部数组的变 e.