东师《编译原理》20春在线作业1答案0

【奥鹏】-[东北师范大学]编译原理20春在线作业1试卷总分:100 得分:100第1题,在一个NFA中，从某一给定的状态q出发，仅经过若干条标记为ε的矢线所能达到的状态所组成的集合记为什么()。

A、q-CLOSURE(ε)B、ε-CLOSURE(q)C、CLOSURE(ε-q)D、CLOSURE(q-ε)正确答案:B第2题,能将汇编语言翻译为机器语言的程序是什么()。

A、汇编程序B、编译程序C、解释程序D、语言程序正确答案:A第3题,NFA的要素中不包含哪个成分()。

A、有穷字母表B、初始状态集合C、终止状态集合D、有限状态集合正确答案:B第4题,文法G[N]=（{N,B}，{b}，{N→b│bB，B→bN}，N），该文法所描述的语言是什么()。

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}正确答案:C第5题,若一个文法是递归的，则它所产生的语言的句子是多少()。

A、无穷多个B、有穷多个C、可枚举的D、个数是常量正确答案:A第6题,算符优先文法的特点是文法的产生式中不含什么()。

A、不含右递归B、不含两个相邻的终结符C、不含ε-产生式D、不含左递归正确答案:C第7题,逆波兰式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第8题,赋值语句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第9题,两个有穷自动机等价是指它们的什么相等()。

A、状态数相等B、有向弧数相等C、所识别的语言相等D、状态数和有向弧数相等正确答案:C第10题,项目A→α•称为什么项目，其中A∈VN，A不是开始符()。

编译原理习题及答案（整理后）第⼀章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所识别的语⾔是。

c. x n yx n(n≥0)d. x*yx*2、⽂法G描述的语⾔L(G)是指。

a. L(G)={α|S + ?α , α∈VT*} b. L(G)={α|S*?α, α∈VT*}c. L(G)={α|S *?α,α∈(VT∪V N*)} d. L(G)={α|S+ ?α, α∈(VT∪V N*)}3、有限状态⾃动机能识别。

a. 上下⽂⽆关⽂法b. 上下⽂有关⽂法c.正规⽂法d. 短语⽂法4、设G为算符优先⽂法，G的任意终结符对a、b有以下关系成⽴。

a. 若f(a)>g(b)，则a>bb.若f(a)c. a~b都不⼀定成⽴d. a~b⼀定成⽴5、如果⽂法G是⽆⼆义的，则它的任何句⼦α。

a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由⽂法的开始符经0步或多步推导产⽣的⽂法符号序列是。

《编译原理》第一次作业参考答案一、下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？1.bR(abRabR)R所有含有偶数个a的由a和b组成的字符串.2.cRa(a|c)Rb(a|b|c)R|cRb(b|c)Ra(a|b|c)R答案一：所有至少含有1个a和1个b的由a，b和c组成的字符串.答案二：所有含有子序列ab或子序列ba的由a，b和c组成的字符串.说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更“自然”.二、设字母表∑={a,b}，用正则表达式（只使用a，b， ，|，R，+，？）描述下列语言：1.不包含子串ab的所有字符串.bRaR2.不包含子串abb的所有字符串.bR(ab?)R3.不包含子序列abb的所有字符串.bRaRb?aR注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第二次作业参考答案一、考虑以下NFA：1.这一NFA接受什么语言（用自然语言描述）？所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串.2.构造接受同一语言的DFA.答案一（直接构造通常得到这一答案）：答案二（由NFA构造DFA得到这一答案）：二、正则语言补运算3.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.1.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.规律：构造语言L的补语言L’的DFA，可以先构造出接受L的DFA，再把这一DFA的接受状态改为非接受状态，非接受状态改为接受状态，就可以得到识别L’的DFA.说明：在上述两题中的D状态，无论输入什么符号，都不可能再到达接受状态，这样的状态称为“死状态”.在画DFA时，有时为了简明起见，“死状态”及其相应的弧（上图中的绿色部分）也可不画出.2.再证明：对任一正则表达式R，一定存在另一正则表达式R'，使得L(R')是L(R)的补集.证明：根据正则表达式与DFA的等价性，一定存在识别语言L(R)的DFA.设这一DFA为M，则将M的所有接受状态改为非接受状态，所有非接受状态改为接受状态，得到新的DFAM’.易知M’识别语言L(R)的补集.再由正则表达式与DFA的等价性知必存在正则表达式R’，使得L(R’)是L(R)的补集.三、设有一门小小语言仅含z、o、/（斜杠）3个符号，该语言中的一个注释由/o开始、以o/结束，并且注释1.请给出单个正则表达式，它仅与一个完整的注释匹配，除此之外不匹配任何其他串.书写正则表达式时，要求仅使用最基本的正则表达式算子（ ，|，R，+，？）.参考答案一：/o(oRz|/)Ro+/思路：基本思路是除了最后一个o/，在注释中不能出现o后面紧跟着/的情况；还有需要考虑的是最后一个o/之前也可以出现若干个o.参考答案二（梁晓聪、梁劲、梁伟斌等人提供）：/o/R(z/R|o)Ro/2.给出识别上述正则表达式所定义语言的确定有限自动机（DFA）.你可根据问题直接构造DFA，不必运用机械的算法从上一小题的正则表达式转换得到DFA.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第三次作业参考答案一、考虑以下DFA的状态迁移表，其中0，1为输入符号，A~H代表状态：其中A为初始状态，D为接受状态，请画出与此DFA等价的最小DFA，并在新的DFA状态中标明它对应的原DFA状态的子集.说明：有些同学没有画出状态H，因为无法从初始状态到达状态H.从实用上讲，这是没有问题的.不过，如果根据算法的步骤执行，最后是应该有状态H的.二、考虑所有含有3个状态（设为p，q，r）的DFA.设只有r是接受状态.至于哪一个状态是初始状态与本问题无关.输入符号只有0和1.这样的DFA总共有729种不同的状态迁移函数，因为对于每一状态和每一输入符号，可能迁移到3个状态中的一个，所以总共有3^6=729种可能.在这729个DFA中，有多少个p和q是不可区分的（indistinguishable）？解释你的答案.解：考虑对于p和q，在输入符号为0时的情况，在这种情况下有5种可能使p和q无法区分：p和q在输入0时同时迁移到r（1种可能），或者p和q在输入0时，都迁移到p或q（4种可能）.类似地，在输入符号为1时，也有5种可能使p和q无法区分.如果再考虑r的迁移，r的任何迁移对问题没有影响.于是r在输入0和输入1时各有3种可能的迁移，总共有因此，总共有5R5R9=225个DFA，其中p和q是不可区分的.三、证明：所有仅含有字符a，且长度为素数的字符串组成的集合不是正则语言.证明：用反证法.假设含有素数个a的字符串组成的集合是正则语言，则必存在一个DFA接受这一语言，设此DFA为D.由于D 的状态数有限，而素数有无限多个，所以必存在两个不同的素数p和q（设p<q），使得从D的初始状态出发，经过p个a和q个a后到达同一状态s，且s为接受状态.由于DFA每一步的迁移都是确定的，所以从状态s 出发，经过(q-p)个a，只能到达状态s.考虑仅含有字母a，长度为p+p(q-p)的字符串T.T从初始状态出发，经过p个a到达状态s，再经过(q-p)个a 仍然到达s；同样，经过p(q-p)个a后仍然到达s.因此，从初始状态出发，经过p+p(q-p)个a后必然到达状态s.由于p+p(q-p)=p(q-p+1)是合数，而s为接受状态，因而得出矛盾.原命题得证.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~一、用上下文无关文法描述下列语言：1.定义在字母表∑={a,b}上，所有首字符和尾字符相同的非空字符串.S→aTa|bTb|a|bT→aT|bT|є说明：1.用T来产生定义在字母表∑={a,b}上的任意字符串；2.注意不要漏了单个a和单个b的情况.2.L={0i1j|i≤j≤2i且i≥0}.S→0S1|0S11|є3.定义在字母表∑={0,1}上，所有含有相同个数的0和1的字符串（包括空串）.S→0S1|1S0|SS|є思路：分两种情况考虑.1)如果首尾字母不同，那么这一字符串去掉首尾字母仍应该属于我们要定义的语言，因此有S→0S1|1S0；2)如果首尾字母相同，那么这一字符串必定可以分成两部分，每一部分都属于我们要定义的语言，因此有S→SS.二、考虑以下文法：S→aABeA→Abc|bB→d1.用最左推导（leftmostderivation）推导出句子abbcde.S==>aABe==>aAbcBe==>abbcBe==>abbcde2.用最右推导（rightmostderivation）推导出句子abbcde.S==>aABe==>aAde==>aAbcde==>abbcde3.画出句子abbcde对应的分析树（parsetree）.三、考虑以下文法：S→aSbS→aSS→1.这一文法产生什么语言（用自然语言描述）？所有n个a后紧接m个b，且n>=m的字符串.2.证明这一文法是二义的.对于输入串aab，有如下两棵不同的分析树3.写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言.答案一：S→aSb|TT→aT|ε答案二：S→TS’T→aT|εS’→aS’b|ε~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~一、考虑以下文法：S→aTUV|bVT→U|UUU→ε|bVV→ε|cV写出每个非终端符号的FIRST集和FOLLOW集.FIRST(S)={a,b}FIRST(T)={є,b}FIRST(U)={є,b}FIRST(V)={є,c}FOLLOW(S)={$}FOLLOW(T)={b,c,$}FOLLOW(U)={b,c,$}FOLLOW(V)={b,c,$}二、考虑以下文法：S→(L)|aL→L,S|S1.消除文法的左递归.S→(L)|aL→SL’L’→,SL’|ε2.构造文法的LL(1)分析表.FIRST(S)={‘(‘,‘a’}FIRST(L)={‘(‘,‘a’}FIRST(L’)={‘,’,ε}FOLLOW(S)={‘$’,‘,’,‘)’}FOLLOW(L)={‘)’}FOLLOW(L’)={‘)’}3.三、考虑以下文法：S→aSbS|bSaS|ε这一文法是否是LL(1)文法？给出理由.这一文法不是LL(1)文法，因为S有产生式S→ε，但FIRST(S)={a,b,ε}，FOLLOW(S)={a,b}，因而FIRST(S)∩FOLLOW(S)≠∅.根据LL(1)文法的定义知这一文法不是LL(1)文法.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~一、考虑以下文法：(0)E’→E(1)E→E+T(2)E→T(3)T→TF(4)T→F(5)F→FR(6)F→a(7)F→b1. 写出每个非终端符号的FIRST集和FOLLOW集.FIRST(E’)=FIRST(E)=FIRST(T)=FIRST(F)={a,b}FOLLOW(E’)={$}FOLLOW(E)={+,$}FOLLOW(T)={+,$,a,b}FOLLOW(F)={+,R,$,a,b}2. 构造识别这一文法所有活前缀（viableprefiRes）的LR(0) 自动机（参照课本4.6.2节图4.31）.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第八次作业参考答案最终答案：34二、以下文法定义了二进制浮点数常量的语法规则：S→L.L|LL→LB|BB→0|1试给出一个S属性的语法制导定义，其作用是求出该二进制浮点数的十进制值，并存放在开始符号S相关联的一个综合属性value中。

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

(单选题)1: 所谓冲突，是指在一个项目集中，出现什么并存的情况()。

A: 移进项目和归约项目
B: 移进项目和待约项目
C: 移进项目和移进项目
D: 待约项目和待约项目
正确答案: A
(单选题)2: 文法Z→Bb|c，A→Aa，B→Bc中含有什么样的非终结符号()。

A: 直接左递归
B: 直接右递归
C: 间接左递归
D: 间接右递归
正确答案: A
(单选题)3: 有下列文法：S→Pa|Pb|c，P→Pd|Se|f，该文法是哪一类文法()。

A: LL(1)文法
B: SLR(1)文法
C: A和B
D: 都不是
正确答案: B
(单选题)4: 数组的存储通常有几种方式()。

A: 1种
B: 两种
C: 3种
D: 4种
正确答案: B
(单选题)5: 下述正规表达式中与(a*|b)*(c|d)等价的是哪个()。

A: a*(c|d)|b(c|d)
B: a*(c|d)*|b(c|d)*
C: a*(c|d)|b*(c|d)
D: (a*|b)*c|(a*|b)*d
正确答案: D
(单选题)6: 在一个规范句型中，位于句柄右边的符号(如果有的话)必然是什么()。

A: 非终结符号
B: 终结符号
C: 开始符号
D: 空符号串
正确答案: B
(单选题)7: 是否存在能被确定的有穷自动机识别，但不能用正则表达式表示的语言()。

A: 存在。

C栈
D循环栈
【答案】：C栈|
3.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。
【选项】：
A不发生改变
B发生改变
C稍有改变
D不能确定
【答案】：A
4.在k叉树中，度为0的结点称为( )。
【选项】：
A根
B叶
C祖先
D子孙
【答案】：B叶|
5.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关()。
【选项】：
A空或只有一个结点
B高度等于其结点数
C任一结点无左子女
D任一结点无右子女
【答案】：B
14. n个结点的线索二叉树上含有的线索数为( )。
【选项】：
A n-1
B n
C n +1
D 2n
【答案】：C
15.广义表(( a , b , c , d ) )的表头是()。
【选项】：
A a
B ( )
C ( a , b , c , d )
东北师范大学
东师远程教育
数据结构20春在线作业1
参考答案
试读一页
数据结构20春在线作业1
1个后继，该数据结构是( )
【选项】：
A线性表
B广义表
C树形结构
D图结构
【答案】：A线性表|
2.插入、删除只能在同一端进行的线性表，称为( )。
【选项】：
A队列
B循环队列
C可以链接存储
D数据元素可以是多个字符
【答案】：B
8. head指向的带表头结点的单链表为空的判定条件是( )。
【选项】：
A head = = NULL
B head-&gt;next = = head

《编译原理》课后习题答案第 1 章引论第 1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第 2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。

第一章习题解答1.解：源程序是指以某种程序设计语言所编写的程序。

目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。

翻译程序是将某种语言翻译成另一种语言的程序的统称。

编译程序与解释程序均为翻译程序，但二者工作方法不同。

解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。

即边解释边执行，翻译所得的指令序列并不保存。

编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。

即先翻译、后执行。

2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。

3.解：C语言的关键字有：auto break case char const continuedefault do double else enum extern float for goto if int longregister return short signed sizeof static struct switch typedef union unsigned void volatile while。

上述关键字在C语言中均为保留字。

4.解：C语言中括号有三种：{}，[]，（）。

其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。

C语言中无END关键字。

逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。

5.略第二章习题解答1.（1）答：26*26=676（2）答：26*10=260（3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658个2.构造产生下列语言的文法（1）{a n b n|n≥0}解：对应文法为G(S) = ({S},{a,b},{ S→ε| aSb },S)（2）{a n b m c p|n,m,p≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)（3）{a n # b n|n≥0}∪{c n # d n|n≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c,d,#}, {S→X,S→Y,X→aXb|#,Y→cYd|# },S)（4）{w#w r# | w?{0,1}*,w r是w的逆序排列}解：G(S) = ({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S)（5）任何不是以0打头的所有奇整数所组成的集合解：G(S) = ({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e, I→J|2|4|6|8, Jà1|3|5|7|9},S)（6）所有偶数个0和偶数个1所组成的符号串集合解：对应文法为S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B3.描述语言特点（1）S→10S0S→aAA→bAA→a解：本文法构成的语言集为：L(G)={(10)n ab m a0n|n, m≥0}。

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. 最右推导的逆过程

【选项】：
A错误
B正确
【答案】：B
31.最佳二叉排序树是AVL树(平衡二叉排序树)。
【选项】：
A错误
B正确
【答案】：B
32.用链表( lchild-rchild表示法)存储的包含n个结点的二叉树，结点的2n个指针域中有n + l个空指针。
【选项】：
A错误
B正确
【答案】：B
33.程序一定是算法。
【选项】：
C不同的同义词子表结合在一起
D散列表“溢出”
【答案】：C
11.数组A[6,7]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是()。
【选项】：
A 1165
B 1170
C 1175
D 118
A图的遍历是从给定的源点出发每个顶点仅被访问一次
东北师范大学
东师远程
数据结构20春在线作业1
参考答案
试读一页
数据结构20春在线作业1
1.数据序列( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 )只能是下列排序算法中的()的两趟排序后的结果。
【选项】：
A直接选择排序
B冒泡排序
C直接插入排序
D堆排序
【答案】：C
2.下面关于算法说法错误的是（）。
【答案】：C
15.存放在外存中的数据的组织结构是()。
【选项】：
A数组
B表
C文件
D链表
【答案】：C
16.从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行( )。
【选项】：
A x = top; top = top-&gt;next;

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.把汇编语言程序翻译成机器可执行的目标程序的工作是由_____完成的。

(单选题)1: a-(b*c/(c-d)+(-b)*a)的逆波兰表示是什么()。

A: abc*cd-b-a*+/-B: abc*cd-b-a*+/-C: abc*cd-/b-a*+-D: abc*/cd-b-a*+-正确答案: C(单选题)2: 在编译程序中安排生成中间代码的目的是为了什么()。

A: 便于进行优化B: 便于进行寄存器分配C: 为了产生正确的目标代码D: 便于进行存贮空间的组织正确答案: A(单选题)3: 两个有穷自动机等价是指它们的什么相等()。

A: 状态数相等B: 有向弧数相等C: 所识别的语言相等D: 状态数和有向弧数相等正确答案: C(单选题)4: 在文法中，由于有些符号不需要进一步定义，故通常将它们称为什么()。

A: 终结符号B: 非终结符号C: 开始符号D: 基本符号正确答案: A(单选题)5: 在下述的语法分析方法中，属于自顶向下的分析方法有哪些()。

A: 简单优先分析B: 算符优先分析C: 递归下降分析D: LR(k)分析正确答案: A(单选题)6: LL(1)分析法的名字中，第一个“L”的含义是什么()。

A: 自左至右B: 自顶向下C: 自底向上D: 自右至左正确答案: A(单选题)7: 语言L={ambn|m≥0，n≥1}的正规表达式是什么()。

A: a*bb*C: aa*b*D: a*b*正确答案: A(单选题)8: LL(1)分析法的名字中，第二个“L”的含义是什么()。

A: 最右推导B: 最右归约C: 最左推导D: 最左归约正确答案: C(单选题)9: 编译过程中，语法分析器的任务是什么()。

A: 分析单词是怎样构成的B: 分析单词串是如何构成语句和说明的C: 分析各语法成分的含义和用途D: 分析各语法成分应进行的运算和操作正确答案: B(单选题)10: 一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组什么()。

D．高级语言接近人们的自然语言，但其依赖具 体机器的特性是无法改变的
2021/10/10
2
《遍”是为了 。
A．提高程序的执行效率
B．使程序的结构更加清晰
C．利用有限的机器内存并提高机器的执行效率
D．利用有限的机器内存但降低了机器的执行效
率
(3) 构造编译程序应掌握 。
表2-1 状态转换矩阵
I
Ia
Ib
{x}
{x,y}
{y}
{y}
—
{x,y}
{x,y}
{x,y}
{x,y}
将转换矩阵中的所有子集重新命名，形成表2-2所 示的状态转换矩阵，即得到
S
a
b
0
2
1
1
—
2
2
2
2
2021/10/10
21
《编译原理教程》习题解析
22
其状态转换图如图2-3所示。
图2-3 习题2.3的DFA M′
(8) 由于正则闭包R+=R*R=RR*，故 (a|b)*(a|b)=(a|b)(a|b)*。故选A。
2021/10/10
17
《编译原理教程》习题解析
18
2.2 什么是扫描器？扫描器的功能是什么？ 【解答】 扫描器就是词法分析器，它接受输 入的源程序，对源程序进行词法分析并识别出一 个个单词符号，其输出结果是单词符号，供语法 分析器使用。通常把词法分析器作为一个子程序， 每当语法分析器需要一个单词符号时就调用这个 子程序。每次调用时，词法分析器就从输入串中 识别出一个单词符号交给语法分析器。
4
《编译原理教程》习题解析
5
【解答】 (1) 编译程序可以将用高级语言编写的源程序转换成 与之在逻辑上等价的目标程序，而目标程序可以是汇编语 言程序或机器语言程序。故选A。 (2) 分多遍完成编译过程可使整个编译程序的逻辑结 构更加清晰。故选B。 (3) 构造编译程序应掌握源程序、目标语言和编译方 法这三方面内容。故选D。

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

A: 语法树的根结由开始符号所标记
B: 一棵语法树表示了一个句型所有的不同推导过程
C: 一棵语法树是不同推导过程的共性抽象，是它们的代表
D: 一个句型不是只有唯一的一棵语法树
正确答案: B
(单选题)2: 类型转换时，整数到实数的转换称为( )。

A: 截断
B: 舍入
C: 拓展
D: 收缩
正确答案: C
(单选题)3: 在自下而上的语法分析方法中，分析的关键是( )。

A: 寻找句柄
B: 寻找句型
C: 消除递归
D: 选择候选式
正确答案: D
(单选题)4: 有限自动机( )个接受状态。

A: 只能有一个
B: 只能有两个
C: 只能有三个
D: 可以有0个、一个或多个
正确答案: D
(单选题)5: ( )的任务是把中间代码（或经过优化处理之后）变换成特定机器上的低级语言代码。

A: 词法分析
B: 语法分析
C: 优化
D: 目标代码生成
正确答案: D
(单选题)6: 编译程序中语法分析器接收以( )为单位的输入。

A: 单词
B: 表达式
C: 产生式
D: 句子
正确答案: A
(单选题)7: LR（1）文法都是( )。

东北农业大学网络教育学院编译原理作业题参考答案第一章编译概述多项选择题：1.编译程序各阶段的工作都涉与到（BC）。

（﹡﹡）A.语法分析B.表格管理C.出错处理D.语义分析E.词法分析2.编译程序工作时，通常有（ABCE）阶段。

（﹡）A.词法分析B.语法分析C.中间代码生成D.语义检查E.目标代码生成填空题：1．解释程序和编译程序的区别在于（是否生成目标程序）。

（﹡）2．编译过程通常可分为5个阶段，分别是（词法分析）、（语法分析）、（中间代码生成）、（代码优化）和（目标代码）生成。

（﹡）3．编译程序工作过程中，第一段输入是（源程序），最后阶段的输出为（目标代码生成）程序。

（﹡）4．编译程序是指将（高级语言编写的）程序翻译成（目标语言）程序的程序。

（﹡）综合题：1.画出编译程序的总体结构图，简述各部分的主要功能。

（﹡﹡﹡）解答：编译程序的总体结构如下图所示：词法分析程序：输入源程序，进行词法分析，输出单词符号。

语法分析程序：在词法分析的基础上，根据语言的语法规则（方法规则）把单词符号串分解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。

中间代码生成程序：按照语义规则把语法分析程序归约（或推导）出的语法单位翻译成一定形式的中间代码，比如说四元式。

优化程序：对中间代码进行优化处理。

目标代码生成程序：把中间代码翻译成目标语言程序。

表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。

编译程序各阶段所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编译过程中都在不断地和表格打交道。

出错处理程序对出现在源程序中的错误进行处理。

此外，编译的各个阶段都可能出现错误。

出错处理程序对发现的错误都与时进行处理。

第二章文法和语言的基本知识多项选择题：1. ABC2. ACE3. BCD4. AC5. BC填空题：1．文法中的终结符和非终结符的交集是（空集）。

词法分析器交给语法分析器的文法符号一定是（终结符），它一定只出现在产生式的（右）部。