北语20春《编译原理》作业2满分

北交《编译原理》在线作业二-0008
编译程序诸阶段的工作往往是( )。

A:顺序
B:并行
C:成批
D:穿插
答案：D
最适合动态建立数据实体的内存分
A:栈式分配
B:堆式分配
C:编译时预先分配
D:以上三种均可
答案：B
把一个高级语言程序翻译成机器可执行的目标程序的工作由下列程序之一完
成( )。

A:汇编程序
B:解释程序
C:编译程序
D:预处理程序
答案：C
高级语言编译程序常用的语法分析方法中，递归下降分析法属于( )分析方法。

A:自左至右
B:自上而下
C:自下而上
D:自右向左
答案：B
LR（1）文法都是( )。

A:无二义性且无左递归
B:可能有二义性但无左递归
C:无二义性但可能是左递归
D:可以既有二义性又有左递归
答案：C
( )是指源程序中不符合语义规则的错误，这些错误一般在语义分析时能检测出来。

A:语义错误
B:语法错误
C:短语错误
D:短句错误
答案：A
( )是指源程序中不符合语法或词法规则的错误，这些错误一般在词法分析或语法分析时能检测出来。

A:语义错误
B:语法错误
C:短语错误
D:短句错误
答案：B
如果r、s是正规式，则下面( )不一定是正规式。

A:rs。

编译原理在线作业2-0002正则式的“·”读作什么()。

选项A:并且选项B:或者选项C:连接选项D:闭包正确选项 :C巴科斯-诺尔范式(即BNF)是一种广泛采用的(什么样的工具()。

选项A:描述规则选项B:描述语言选项C:描述文法选项D:描述句子正确选项 :B设有文法G［S］:S→aAc|b，A→cAS|ε，则文法G是哪一类文法()。

选项A:LL(1)文法选项B:非LL(1)文法选项C:二义性文法选项D:无法判断正确选项 :B如果一个产生式的左部或右部含有无用符号，则此产生式称为()产生式。

选项A:非法选项B:多余选项C:非确定选项D:无用正确选项 :DDFA中定义了一个从K×Σ到K的单值映射f，指明若当前的状态为P，而输入字符为a时，则下一个状态是Q,f记为什么()。

选项A:f(P,Q)=a选项B:f(P,a)=Q选项C:f(Q,a)=P选项D:f(a,P)=Q正确选项 :B规范推导的每一步总是用产生式右边符号串替换句型中什么位置的非终结符号()。

选项A:最左选项B:最右选项C:最中选项D:任意正确选项 :B自底向上分析时，若分析成功，则分析栈中只剩下什么()。

选项A:界符#及开始符号S选项B:开始符号S选项C:界符#号选项D:当前的输入符号正确选项 :A设G是一右线性文法，并设G中的非终结符号的个数为k，则所要构造的状态转换图共有几个结点()。

选项A:k-1选项B:k选项C:k+1选项D:k+2正确选项 :C设有文法G[S]：S→11S|00S|0C|1C|ε，C→1S|0S|00C|11C，下列符号串中哪个是该文法的句子()。

选项A:00011选项B:01011选项C:001101选项D:0110正确选项 :D假设某程序语言的文法如下：S→a|b|(T)，T→TdS|S，考察该文法的句型(Sd(T)db)，其中：素短语是哪个()。

选项A:S选项B:b选项C:(T)选项D:Sd(T)正确选项 :CLL(1)分析表可用一个二维数组表示，它的每一行与文法的一个什么符号相关联()。

《编译原理》作业参考答案一、填空1．图二图一。

2．文法是无ε产生式，且任意两个终结符之间至多有一种优先关系的算符文法。

3．最右推导最右推导。

4．对于循环中的有些代码，如果它产生的结果在循环中是不变的，就把它提到循环外来。

把程序中执行时间较长的运算替换为执行时间较短的运算。

5．对于文法中的每个非终结符A的各个产生式的候选首符集两两不相交；对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST（A）∩FOLLOW（A）= ø6．控制。

7．语义分析和中间代码产生8．自上而下自下而上自上而下9．自下而上表达式10．自下而上11．源程序单词符号12． DFA初态唯一，NFA初态不唯一；DFA弧标记为Σ上的元素，NFA弧标记为Σ*上的元素；DFA的函数为单射，NFA函数不是单射13．词法，词法分析器，子程序，语法14．ε，a，ab，ab15．终结符号，非终结符号，产生式16．L(G)={a n | n≥1}17．1型，2型，3型18．二义的19．快20．终态，输入字21．单词符号，终结符22．归约23．必须24．直接25．终结符，更快26．E→E+∙T， E→E∙+T， E→∙E+T， E→E+T∙27．归约—归约28．类型检查，一致性检查29．词法分析、词法30．语法分析程序、语法31。

终结符号、产生式、开始符号、非终结符32．2、2、333．不需要避开34．符合、不符合35．推导36．包括37．Ass38．一定没有、一定没有、至多只有一个39．SLR（1）40．移进——归约41．a.控制流检查、b.一致性检查、c.相关名字检查二、判断下面语法是否正确1 ×2 ×3 √4 ×5 √6 ×三、简答题1．词法分析的任务是对输入的源程序进行单词及其属性的识别，为下一步的语法分析进行铺垫；有两种方法可以实现词法分析器：一，手工编写词法分析程序。

二，由词法分析器自动生成程序生成。

4.一个语言的文法是唯一的。 A.错误 B.正确 正确答案:A
5.根据文法等价的概念，可对文法进行等价改造，以期得到所需形式的文法。 A.错误 B.正确 正确答案:B
6.使用语法制导翻译方法的编译程序能同时进行语法分析和语义分析。 A.错误 B.正确 正确答案:B
7.状态转换矩阵的列标题表示状态图中的各个状态。
8.状态转换矩阵的行标题表示状态转换图中的什么部分()。 A.终态 B.矢线 C.输入符号 D.状态 正确答案:D
9.一个状态转换图是由一组矢线连接的有限个结点所组成的什么()。 A.有向图 B.无向图 C.无回路有向图 D.强连通的有向图 正确答案ቤተ መጻሕፍቲ ባይዱA
10.什么模式，既把语法分析与语义处理分开，又令其平行地进行，从而在同一遍扫描中同 时完成语法分析和语义处理两项工作()。 A.语法制导翻译 B.中间代码生成 C.中间代码优化
16.作为词法分析的结果，通常是把从源程序中所识别出的各个单词转换成什么，并依次进 行输出()。 A.内部表示 B.外部表示 C.类别码 D.词文 正确答案:A
17.两个有穷自动机等价是指它们的什么相等()。 A.状态数相等 B.有向弧数相等 C.所识别的语言相等 D.状态数和有向弧数相等 正确答案:C
4.若用临时变量 T1 表示 CONSTPART 部分，用临时变量 T 表示 VARPART 部分，则变址 存数四元式的形式是什么()。 A.([ ]=，X，0，T[T1]) B.(=[ ]，T[T1]，0，X) C.([ ]=，X，0，T1[T]) D.(=[ ]，T1[T]，0，X) 正确答案:C
二、 判断题 (共 20 道试题,共 40 分) 1.存在这样一些语言，它们能被确定的有穷自动机识别，但不能用正规表达式表示。 A.错误 B.正确 正确答案:A

北交《编译原理》在线作业二-0007
( )是指源程序中不符合语法或词法规则的错误，这些错误一般在词法分析或语法分析时能检测出来。

A:语义错误
B:语法错误
C:短语错误
D:短句错误
答案：B
( )是指源程序中不符合语义规则的错误，这些错误一般在语义分析时能检测出来。

A:语义错误
B:语法错误
C:短语错误
D:短句错误
答案：A
( )是为每个标识符保存一个记录的数据结构，记录的域是标识符的属性。

A:符号表
B:代码表
C:源程序
D:出错表
答案：A
下列说法中错误的是( )。

A:当一遍中包含若干阶段时，各阶段的工作是穿插进行的
B:遍数越多越好
C:遍数越多，输入/输出所消耗的时间越多
D:并非每种语言都可以用单遍编译来实现
答案：B
在LR分析法中，分析栈中存放的状态是识别规范句型( )的DFA状态。

A:句柄
B:前缀
C:活前缀
D:LR(0)项目
答案：C
在编译程序使用的表格中，最重要的是( )。

A:数据表
B:信息表
C:变量表
D:符号表
答案：D
高级语言编译程序常用的语法分析方法中，递归下降分析法属于( )分析方法。

A:自左至右
B:自上而下
C:自下而上
D:自右向左
答案：B
有限自动机( )个接受状态。

A:只能有一个
B:只能有两个。

《编译原理》考试试题及答案（汇总）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。

2.对 下 面 的 文 法 G : E → TE' F → PF' E' → +E| ε F' → *F'| ε T → FT' T' → T| ε P → (E) | a | b | ^
(1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (2) 证明这个方法是 LL(1) 的。 (3) 构造它的预测分析表。 FIRST(E')={+,ε} FIRST(P)={(,a,b,^); 解:(1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 FIRST 集合有: FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^); FIRST(T')=FIRST(T)＋{ε}={(,a,b,^,ε); FOLLOW(E)={+,},#};//不包含 ε FOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,},#}; FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含 ε FOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含 ε (2)证明这个方法是 LL(1)的。 各产生式的 SELECT 集合有: SELECT(E->TE')=FIRST(T)={(,a,b,^); SELECT(E'->+E)={+}; SELECT(E'->ε)=FOLLOW(E/)={},#} SELECT(T->FT')=FIRST(F)={(,a,b,^); SELECT(T'->T)=FIRST(T)={(,a,b,^); SELECT(T'->ε)=FOLLOW(T/)={+,},#}; SELECT(F->PF')=FIRST(P)={(,a,b,^); SELECT(F'->*F')={*}; SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#}; SELECT(P->(E))={() SELECT(P->a)={a} SELECT(P->b)={b} SELECT(P->^)={^} 可见,相同左部产生式的 SELECT 集的交集均为 空,所以文法 G[E]是 LL(1)文法。 (3)构造它的预测分析表。 文法 G[E]的预测分析表如下: FIRST(F')={*,ε};

8、规范推导是最左推导，故选 d。
9、由 T→T,…和 T→(… 得 FIRSTVT(T))={(,，)}；
由 T→S 得 FIRSTVT(S)⊂FIRSTVT(T)，而 FIRSTVT(S)={b,∧,(}；即
FIRSTVT(T)={b,∧,(,，}；
因此选 c。
10、d 11、c 12、b 13、b 14、b
标语言
第二章
一、单项选择题
1、文法 G：S→xSx|y 所识别的语言是 。
a. xyx
b. (xyx)* c. xnyxn(n≥0) d. x*yx*
2、文法 G 描述的语言 L(G)是指 。
a. L(G)={α|S⇒+ α , α∈VT*}
b. L(G)={α|S⇒* α, α∈VT*}
c. L(G)={α|S⇒* α,α∈(VT∪VN*)} d. L(G)={α|S⇒+ α, α∈(VT∪VN*)}
6、一个文法所有句型的集合形成该文法所能接受的语言。
五、简答题
1、句柄 2、素短语
3、语法树
4、归约
六、问答题
1、给出上下文无关文法的定义。
2、文法 G[S]：
（） （） （） （） （）
5、推导
S→aSPQ|abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc （1）它是 Chomsky 哪一型文法？ （2）它生成的语言是什么？ 3、按指定类型，给出语言的文法。 L={aibj|j＞i≥1}的上下文无关文法。 4、有文法 G：S→aAcB|Bd
a. 23 B. 42 c. 30 14、规范归约指 。
d. 17
a. 最左推导的逆过程
b. 最右推导的逆过程

北交《编译原理》在线作业二-0009试卷总分:100 得分:100一、单选题(共25 道试题,共50 分)1.一个结点相应的文法符号属性值是由该结点兄弟结点和/或父节点的相应的文法符号的属性值来计算，按这种情况计算的属性值叫做( )。

A.赋值属性B.自然属性C.综合属性D.继承属性答案:D2.优化所依循的原则是( )。

A.语言的语义规则B.程序的等价变换规则C.正规式D.上下文无关文法答案:B3.1型文法也称为( )。

A.短语文法B.左性性文法C.右线性文法D.上下文有关文法答案:D4.( )是指源程序中不符合语法或词法规则的错误，这些错误一般在词法分析或语法分析时能检测出来。

A.语法错误B.语义错误C.短语错误D.短句错误答案:A5.已知文法：S→aAa|aBb|bAb|bBaA→x B→x ，则( )A.都不是B.LR(1)文法LR（1）文法D.A和B答案:B6.( )是描述语言的语法结构的形式规则。

A.语法B.语义C.词法D.文法答案:D7.如果r、s是正规式，则下面( )不一定是正规式。

A.r|sB.rsC.r+sD.r*答案:C8.描述一个语言的文法是( )。

A.唯一的B.可能唯一C.可能不唯一D.不唯一的答案:A9.由于受到具体机器主存容量的限制，编译程序几个不同阶段的工作往往被组合成( )。

A.遍B.过程C.程序D.批量答案:A10.若一个文法是递归的，则它所产生的句子个数( )。

A.根据具体情况而定B.是有限个的C.必定是无穷的D.不确定答案:A11.语义分析与中间代码产生所依循的是( )。

A.语言的语义规则B.正规式C.有限自动机D.上下文无关文法答案:A12.下列选项中，不属于优化编译程序提供的对代码的各种变换必须遵循的原则的是( )。

A.等价原则B.有效原则C.最佳原则D.合算原则答案:C13.Pascal的if语句满足( )。

A.静态作用域规则B.最远匹配原则C.最近匹配原则D.动态作用域规则答案:C14.有限自动机可以有( )个初始状态。

北京语言大学网络教育学院《编译原理》模拟试卷一注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。

请监考老师负责监督。

2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。

3.本试卷满分100分，答题时间为90分钟。

4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。

一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。

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 所描述的语言是（）的集合。

编译原理答案1-2《编译原理习题精选》第一章形式语言基础1．1文法与语言的形式定义1．2推导树与二义性文法1．3综合题第二章有限状态自动机和词法分析2．1有限状态自动机2．2词法分析2．3综合题第三章自顶向下句法分析3．1下推自动机与句法分析3．2LL(1)文法及其句法分析方法3．3递归子程序句法分析方法3．4综合题第四章自底向上句法分析4．1优先文法及其句法分析方法4．2LR(0)、SLR(1)文法及其句法分析方法4．3LR(1)、LALR(1)文法4．4综合题第五章句法制导翻译方法与中间代码生成5．1中间代码5．2属性文法与句法制导翻译5．3综合题第六章运行时存储和环境管理6．1存储分配6．2环境建立与管理6．3形实参数通讯6．4综合题第七章代码优化7．1基本块内代码优化7．2全局优化7．3综合题第八章综合习题精选第一章形式语言基础§1.1文法与语言的形式定义一、要点提示1．文法G是一个四元组G=（VT,VN,P,）其中：VT是非空有限的终结符集合，VN是非空有限的非终结符集合，P是非空有限产生式集合，VN是文法G的开始符号，集合P中的产生式的一般形式是（或::=），其中''是元符号，称为产生式的左部，称为产生式的右部。

Chomky根据产生式的不同形式，将文法分为四类。

分别是：0型文法（又称短语结构文法）；1型文法（又称上下文有关文法）；2型文法（又称上下文无关文法）；3型文法（又称正则文法）；编译程序所涉及的主要是2型与3型文法，分别用于句法分析与词法分析。

2型文法的一般形式为,VN,(VN∪VT)某。

3型文法的一般形式为a或a,、VN，aVT（或a，a）。

2．文法G[]中，是文法的开始符号，对某，若(VN∪VT)某，则称是G的一个句型，若VT某，则称是G的一个句子。

文法G[]的句子的全体所组成的集合称为G[]的语言，记作L(G[])={w|某w,wVT某}。

3．从实用的角度出发，在编译原理中所讨论的文法是被简化了的文法，即：a)文法中不含形如的产生式。

___《计算机编译原理)》20春期末考
试.doc
1.编译程序有三种工作方式：解释型、编译型和汇编型。

其中，汇编型是指先将源代码编译成汇编代码，再将汇编代码翻译成机器码。

2.LL(1)文法中不包含左公共因子是必要条件。

3.在规范归约中，句柄用来刻画可归约串。

4.根据文法G[S]：S→S+U|U，U→U*V|V，V→(S)a，句型P+T+i的句柄为V，最左素短语为V+U。

5.中间代码的设计原则是容易生成和翻译为目标代码。

6.对于文法G[S]：S→S8|S9|Sa|Sc|a|b|c，符合该文法的句子有①ab9、②a9c98、③aaa和④bc89.
7.编译程序工作的后端包含的阶段有中间代码生成、代码优化和代码生成。

8.一个句型中称为句柄的是该句型的最左直接短语。

9.对于文法G[S]：S→SB|B，B→0|b，句子0b0的规范推导为SSBS0SB0Sb0Bb00b0.
10.文法G[E]：E→3EXY|34Y，YX→XY，4X→44，
4Y→45，5Y→55是Chomsky文法类型中的1型文法。

11.一个LR分析器由三部分组成，分别是总控程序、分析表和分析栈。

12.由文法G[S]的开始符S经n步(n≥0)推导产生的文法符号序列α是句型。

(单选题)1: ( )是指源程序中不符合语法或词法规则的错误，这些错误一般在词法分析或语法分析时能检测出来。

A: 语义错误
B: 语法错误
C: 短语错误
D: 短句错误
正确答案: B
(单选题)2: ( )是指源程序中不符合语义规则的错误，这些错误一般在语义分析时能检测出来。

A: 语义错误
B: 语法错误
C: 短语错误
D: 短句错误
正确答案: A
(单选题)3: ( )是为每个标识符保存一个记录的数据结构，记录的域是标识符的属性。

A: 符号表
B: 代码表
C: 源程序
D: 出错表
正确答案: A
(单选题)4: 下列说法中错误的是( )。

A: 当一遍中包含若干阶段时，各阶段的工作是穿插进行的
B: 遍数越多越好
C: 遍数越多，输入/输出所消耗的时间越多
D: 并非每种语言都可以用单遍编译来实现
正确答案: B
(单选题)5: 在LR分析法中，分析栈中存放的状态是识别规范句型( )的DFA状态。

A: 句柄
B: 前缀
C: 活前缀
D: LR(0)项目
正确答案: C
(单选题)6: 在编译程序使用的表格中，最重要的是( )。

A: 数据表
B: 信息表
C: 变量表
D: 符号表
正确答案: D。

【奥鹏】-[东北师范大学]编译原理20春在线作业2试卷总分:100 得分:100第1题,词法分析器用于识别什么()。

A、句柄B、句型C、单词D、产生式正确答案:C第2题,把用一组数学符号和规则来描述语言的方式称为什么()。

A、推演B、推导C、形式描述D、形式语言正确答案:C第3题,逆波兰式ab+c+d*e-所对应的表达式是什么()。

A、(a+b+c)*d-eB、a+b+c*d-eC、a+(b+c)*d-eD、(a-b+c)*d+e正确答案:A第4题,设有文法G[I]：I::=I1|I0|Ia|Ic|a|b|c,下列符号串中是该文法的句子的是哪个()。

A、ab0B、a0c01C、1abaD、0bc10正确答案:B第5题,由右线性文法构造状态转换图时，要令G的开始符号S所标记的结点是什么结点()。

A、初态B、终态C、既非初态亦非终态D、任意正确答案:A第6题,赋值语句X:=-(a+b)/(c-d)-(a+b*c)的逆波兰表示是什么()。

A、Xab+cd-/-bc*a+-:=B、Xab+/cd--bc*a+--:=C、Xab+-cd-/abc*+-:=D、Xab+cd-/abc*+--:=正确答案:A第7题,文法S→aAa|aBb|bAb|bBa，A→x，B→x是哪一类文法()。

A、LR(0)文法B、SLR(1)文法C、LR(1)文法D、都不是正确答案:C第8题,NFA的要素中不包含哪个成分()。

A、有穷字母表B、初始状态集合C、终止状态集合D、有限状态集合正确答案:B第9题,Σ={0，1}上的正规式(0|1)*表示什么()。

A、0开头的串B、1开头的串C、有一个0和一个1的串D、由0、1组成的任意串正确答案:D第10题,算符优先分析法每次都是对什么进行归约()。

A、最左短语B、简单短语C、最左素短浯D、素短语正确答案:C第11题,一个状态转换图是由一组矢线连接的有限个结点所组成的什么()。

A、有向图B、无向图C、无回路有向图D、强连通的有向图正确答案:A第12题,数组的存储通常有几种方式()。

2树的根结点以文法G[S]的开始符S标记；
3若一结点至少有一个直接后继，则此结点上的标记为Vn中的一个符号；
4若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为
Xi,X2,…，准则A^Xi,X2,…，冶 必然是G的一个产生式。
4.归约：（**）
解答：我们称 仏丫直接归约出aA0仅当A^y是一个产生式，且a（VnUVt）*。归约过程就是从输
出错处理程序对出现在源程序中的错误进行处理。此外，编译的各个阶段都可能出现错误。出错处理 程序对发现的错误都及时进行处理。
第二章
多项选择题：
1.ABC 2. ACE 3. BCD 4. AC 5. BC
填空题：
1•文法中的终结符和非终结符的交集是（空集）。词法分析器交给语法分析器的文法符号一定是（终结
(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；
(2)写出句子acabcbbdcc的最左推导过程。(***)
解答：
(1)分别画出对应两句型的语法树，如下图所示
句柄:AaB Bd
(2)句子acabcbbdcc的最左推导如下：
ST二aAcB二aAaBcB二acaBcB=acabcB二acabcbScA二acabcbBdcA二acabcbbdcA二acabcbbdcc
S二：aSPQ二aaSPQPg aaabQPQPQ：aaabPQQPQ：aaabPQPQQ aaaPPQQQ aaabbPqqq二aaabbQQg aaabbbcQQ二aaabbbccQ二aaabbbccc
于是得到文法G[S]生成的语言L={anbncn|n>1}
3.按指定类型，给出语言的文法。
L={aibj|j>i>1}的上下文无关文法。(**)

(单选题)1: 下列关于语法树的描述中，错误的是( )。

A: 语法树的根结由开始符号所标记
B: 一棵语法树表示了一个句型所有的不同推导过程
C: 一棵语法树是不同推导过程的共性抽象，是它们的代表
D: 一个句型不是只有唯一的一棵语法树
正确答案: B
(单选题)2: ( )的任务是把中间代码（或经过优化处理之后）变换成特定机器上的低级语言代码。

A: 词法分析
B: 语法分析
C: 优化
D: 目标代码生成
正确答案: D
(单选题)3: 最适合动态建立数据实体的内存分
A: 栈式分配
B: 堆式分配
C: 编译时预先分配
D: 以上三种均可
正确答案: B
(单选题)4: 在编译的各阶段中，和目标机器关系最为密切的是( )。

A: 词法分析
B: 语法分析
C: 语义分析
D: 目标代码生成
正确答案: D
(单选题)5: ( )是描述语言的语法结构的形式规则。

A: 文法
B: 语义
C: 词法
D: 语法
正确答案: A
(单选题)6: 表达式(a+b)*(c+d)的后缀式表示为( )。

A: a+b*c+d
B: +ab*+cd
C: ab+cd+*
D: 无法表示
正确答案: C
(单选题)7: 语义分析与中间代码产生所依循的是( )。

20春《编译原理》作业_1一、单选题( 每题4分, 共10道小题, 总分值40分)1.正规式MI和M2等价是指_____。

A. MI和M2的状态数相等B. Ml和M2的有向弧条数相等C. M1和M2所识别的语言集相等D. Ml和M2状态数和有向弧条数相等答：C call：【131】【9666】【2906】2.编译程序是将高级语言程序翻译成( )。

A. 高级语言程序B. 机器语言程序C. 汇编语言程序D. 汇编语言或机器语言程序答：D3.文法G[N]= （{b} ，{N ，B} ，N ，{N→b│bB ，B→bN} ），该文法所描述的语言是A. L(G[N])={bi│i≥0}B. L(G[N])={b2i│i≥0}C. L(G[N])={b2i+1│i≥0}D. L(G[N])={b2i+1│i≥1}答：C4.一个句型中的最左_____称为该句型的句柄。

A. 短语B. 简单短语C. 素短语D. 终结符号答：B5.用高级语言编写的程序经编译后产生的程序叫_____。

A. 源程序B. 目标程序C. 连接程序D. 解释程序答：B6.文法分为四种类型，即0型、1型、2型、3型。

其中2型文法是_____。

A. 短语文法B. 正则文法C. 上下文有关文法D. 上下文无关文法答：D7.编译程序使用_____区别标识符的作用域。

A. 说明标识符的过程或函数名B. 说明标识符的过程或函数的静态层次C. 说明标识符的过程或函数的动态层次D. 标识符的行号答：B8.编译程序前三个阶段完成的工作是（）。

A. 词法分析、语法分析和代码优化B. 代码生成、代码优化和词法分析C. 词法分析、语法分析、语义分析和中间代码生成D. 词法分析、语法分析和代码优化答：C9.四种形式语言文法中，1型文法又称为_____文法。

A. 短语结构文法B. 前后文无关文法C. 前后文有关文法D. 正规文法答：C10.把汇编语言程序翻译成机器可执行的目标程序的工作是由_____完成的。