一．（每项选择2分，共20分）选择题1．将编译程序分成若干个“遍”是为了_b__。a.提高程序的执行效率b.使程序的结构更加清晰
c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率2．构造编译程序应掌握__d__。a.源程序b.目标语言c.编译方法d.以上三项都是3．变量应当c＿。a.持有左值b.持有右值
c.既持有左值又持有右值d.既不持有左值也不持有右值4．编译程序绝大多数时间花在_d___上。a.出错处理b.词法分析c.目标代码生成d.管理表格
5．词法分析器的输出结果是_c___。a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值6．正规式MI和M2等价是指__c__。a.MI和M2的状态数相等b.Ml和M2的有向弧条数相等。
C.M1和M2所识别的语言集相等d.Ml和M2状态数和有向弧条数相等7．中间代码生成时所依据的是—c。
a．语法规则b．词法规则c．语义规则d．等价变换规则8．后缀式ab+cd+/可用表达式__b_来表示。
a．a+b/c+db．(a+b)/(c+d)c．a+b/(c+d)d．a+b+c/d
9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。
a.动态存储b.栈式存储c.静态存储d.堆式存储10.堆式动态分配申请和释放存储空间遵守___d____＿原则。
a.先请先放b.先请后放c.后请先放d.任意二（每小题10分，共80分）简答题
1.画出编译程序的总体结构图，简述各部分的主要功能。2.已知文法G[E]:
E→ET+|TT→TF*|FF→F^|a
试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.3．为正规式(a|b)*a(a|b)构造一个确定的有限自动机。4．设文法G(S)：
S→(L)|aS|aL→L，S|S
(1)消除左递归和回溯；
(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。
5．已知文法A->aAd|aAb|ε
判断该文法是否SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。6．构造算符文法G[H]的算符优先关系（含＃）。
G[H]：H→H;M|MM→d|aHb
7．已构造出文法G（S）（1）SBB（2）BaB（3）Bb1）。给出DFA图2）.给出LR分析表
3）．假定输入串为abaab，请给出LR分析过程（即状态，符号，输入串的变化过程）。8．将下面的语句翻译成四元式序列：
whileA (1)求出流图中各结点N的必经结点集D(n)，(2)求出流图中的回边，(3)求出流图中的循环。 参考答案一．单项选择题1.将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。2..构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。3.对编译而言，变量既持有左值又持有右值，故选c。4.5.6.7.8.9.10. 编译程序打交道最多的就是各种表格，因此选d。 词法分析器输出的结果是单词的种别编码和自身值，选C。正规式M1和M2所识别的语言集相等，故选C。选c。选b。选C 堆式动态分配申请和释放存储空间不一定遵守先请后放和后请先放的原则，故选d 二．简答题 1．【解答】 编译程序的总体结构图如图1.2所示。 词法分析器：输入源程序，进行词法分析，输出单词符号。 语法分析器：在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号串分解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。 中间代码生成器：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码，比如说四元式。优化：对中间代码进行优化处理。 目标代码生成器：把中间代码翻译成目标语言程序。 表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编译程序各阶段所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编译过程都在不断地和表格打交道。 出错处理程序对出现在源程序中的错误进行处理。此外，编译的各阶段都可能出现错误，出错处理程序对发现的错误都及时进行处理。 2．【解答】 该句型对应的语法树如下：该句型相对于E的短语有FF^^*；相对于T的短语有FF^^*,F;相对于F的短语有F^;F^^;简单短语有F;F^;句柄为F.3．【解答】 最简DFA如图2.66所示。4．(1) 【解答】 S→(L)|aS’S’→S|εL→SL’L’→SL’|ε 评分细则：消除左递归2分，提公共因子2分。(2)FIRST和FOLLOW FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)}FIRST(L)＝{(，a}FOLLOW(L)＝{)}FIRST(L’)＝{，，ε}FOLLOW(L’〕＝{)} 5．【解答】 (1)拓广文法 (0)S->A(1)A->aAd(2)A->aAb(3)A->ε(2)构造识别活前缀的DFA FOLLOW(A)={d,b,#} 对于状态I0：FOLLOW(A)∩{a}=Ф对于状态I1：FOLLOW(A)∩{a}=Ф 因为，在DFA中无冲突的现象，所以该文法是SLR(1)文法。(3)SLR(1)分析表状态ACTIONGOTO aBd#A 012345 S2S2 S5r1r2 r3r3 r3 accr3S4r1r2 r1r2 r3r3 13 (4)串ab#的分析过程步骤状态栈符号栈当前字符剩余字符串10#ab#移进202#ab#归约A->ε3023#aAb#移进40235#aAb#归约A->aAb501#A#接受6． 动作 【解答】 由M→d和M→a…得：FIRSTVT(M)=｛d,a｝；由H-H;…得：FIRSTVT(H)=｛；｝ 由H→M得：FIRSTVT(M)cFIRSTVT(H)，即FIRSTVT(H)={;,d,a}由M→d和M→…b得：LASTVT(M)={d,b}；由H---，；m得：LASTVT(H)=｛；｝； 由H→M得：LASTVT（M）cLASTVT(H），即LASTVT(H)=｛;,d,b} 对文法开始符H,有#H#存在，即有＃=＃，# 对形如P→…ab…，或P→…aQb…，有a=b，由M→a|b得：a=b；对形如P→…aR…，而b∈FIRSTVT(R)，有a 由H→…；M得：； ACTIONabs3s4S3s3 S4s4 GOTO S1 #acc B256 456r3R1R2r3R1R2 r1R2 (3)句子abaab的分析过程表:句子abaab的分析过程步骤状态符号栈输入串0#0#abaad#1#03#abaad#2#034#abaab#B→b3#036#aBaab#B→aB4#02#Baab#5#023#Baab#6#0233#Baab#78910111213 #02334#Baab##02336#BaaB##0236#BaBad##025#BBad##01#Sd###d#识别成功 所得产生式 8．【解答】 该语句的四元式序列如下（其中E1、E2和E3分别对应：A 9．【解答】 (1)流图中各结点N的必经结点集D(n)， D(l)＝{1}，D(2)＝{1,2}，D(3)＝{1,2,3}，D(4)={1,2,3,4}，D(5)＝{1,2,5}，D(6)＝{1,2,5,6} (2)求出流图中的回边， 5->2，4->3 (3)求出流图中的循环: 回边5->2对应的循环：2、5、3、4；回边4->3对应的循环：3、4 《编译原理》模拟试题一 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(√) 4．正则文法其产生式为A->a，A->Bb,A,B∈VN，a、b∈VT。(×)5．每个文法都能改写为LL(1)文法。(√) 6．递归下降法允许任一非终极符是直接左递归的。(√)7．算符优先关系表不一定存在对应的优先函数。(×) 8．自底而上语法分析方法的主要问题是候选式的选择。(×)9．LR法是自顶向下语法分析方法。(×) 10．简单优先文法允许任意两个产生式具有相同右部。(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 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所描述的语言是_____的集合。 A.()文法G的字母表V中所有符号组成的符号串B．()文法G的字母表V的闭包V*中的所有符号串C．()由文法的开始符号推出的所有终极符串D.()由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。A.()短语文法B．()正则文法C．()上下文有关文法D．()上下文无关文法 10．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组_____。A．()句子B．()句型C．()单词D．()产生式三、填空题(每空1分，共10分)1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和___出错处理__。2．若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程序称为___编译程序__。 3．编译方式与解释方式的根本区别在于__是否生成目标代码___。 4．对编译程序而言,输入数据是___源程序__,输出结果是__目标程序___。5．产生式是用于定义___语法成分__的一种书写规则。 6．语法分析最常用的两类方法是___自上而下__和___自下而上__分析法。四、简答题（20分） 1.什么是句子？什么是语言? 答：(1)设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx,x∈VT*}。 2.写一文法，使其语言是偶正整数的集合,要求：(1)允许0打头；(2)不允许0打头。 解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P: S->PD|D P->NP|ND->0|2|4|6|8 N->0|1|2|3|4|5|6|7|8|9 (2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)P: S->PD|P0|DP->NR|NR->QR|QD->2|4|6|8 N->1|2|3|4|5|6|7|8|9Q->0|1|2|3|4|5|6|7|8|93.已知文法G[E]为： E→T|E+T|E-TT→F|T*F|T/FF→（E）|i ①该文法的开始符号（识别符号）是什么？ ②请给出该文法的终结符号集合VT和非终结符号集合VN。③找出句型T+T*F+i的所有短语、简单短语和句柄。解：①该文法的开始符号（识别符号）是E。②该文法的终结符号集合VT={+、-、*、/、（、）、i}。非终结符号集合VN={E、T、F}。③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;简单短语为i、T*F、第一个T;句柄为第一个T。 4.构造正规式相应的NFA:1(0|1)*101解1(0|1)*101对应的NFA为 5.写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示和三元式序列。逆波兰表示：abc*＋ab＋/d－三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d)五.计算题（10分） 构造下述文法G[S]的自动机：S->A0A->A0|S1|0该自动机是确定的吗？若不确定，则对它确定化。 解：由于该文法的产生式S->A0，A->A0|S1中没有字符集VT的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。代入S->A0有该文法的正规式：0(0|01)*0，所以，改 写该文法为确定的自动机为： 由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：下表由子集法将NFA转换DFA: 为 由上表可知DFA为： 《编译原理》模拟试题二 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。(×) 2．若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。(×)3．一个句型的句柄一定是文法某产生式的右部。(√)4．在程序中标识符的出现仅为使用性的。(×) 5．仅考虑一个基本块，不能确定一个赋值是否真是无用的。(√) 6．削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。(√) 7．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。(×)8．算符优先关系表不一定存在对应的优先函数。(×)9．数组元素的地址计算与数组的存储方式有关。(×) 10．编译程序与具体的机器有关,与具体的语言无关。(×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目 标代码生成等五个部分，还应包括_____。A．()模拟执行器B．()解释器C．()表格处理和出错处理D．()符号执行器 2．文法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}3．一个句型中的最左_____称为该句型的句柄。A．()短语B．()简单短语C．()素短语D．()终结符号 4．设G是一个给定的文法，S是文法的开始符号，如果S->x(其中x∈V*),则称x是 文法G的一个_____。A．()候选式B．()句型C．()单词D．()产生式5．文法G[E]：E→T∣E＋TT→F∣T﹡FF→a∣（E） 该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的_____。①（E＋T）②E＋T③F④F﹡(E＋T)A．()①和③B．()②和③C．()③和④ D．()③ 6．若一个文法是递归的，则它所产生的语言的句子_____。 A．()是无穷多个C．()是可枚举的 B．()是有穷多个D．()个数是常量 7．词法分析器用于识别_____。 A．()句子A.()非终极符集A.()寻找句柄 B．()句型 C．()单词 D．()产生式 D.()状态集D.()选择候选式 8．在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是_____。 B．()终极符集B.()寻找句型 C．()字母表C.()消除递归 9．在自底向上的语法分析方法中，分析的关键是_____。 10．在LR分析法中，分析栈中存放的状态是识别规范句型_____的DFA状态。 A.()句柄B.()前缀C.()活前缀D.()LR(0)项目三、填空题(每空1分，共10分) 1．设G是一个给定的文法，S是文法的开始符号，如果S->x(其中x∈VT*),则称x是文法的一个__句子___。 2．递归下降法不允许任一非终极符是直接__左___递归的。 3．自顶向下的语法分析方法的基本思想是：从文法的__开始符号____开始，根据给定的输 入串并按照文法的产生式一步一步的向下进行__直接推导____，试图推导出文法的__句子____，使之与给定的输入串___匹配___。 4．自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行___直接归约__，力求归约到文法的__开始符号___。 5．常用的参数传递方式有___传地址__，传值和传名。 6．在使用高级语言编程时,首先可通过编译程序发现源程序的全部__语法___错误和语义部 分错误。 四、简答题（20分） 1.已知文法G[S]为： S→dABA→aA|aB→Bb|ε G[S]产生的语言是什么？ 答：G[S]产生的语言是L(G[S])={danbm│n≥1,m≥0}。 2.简述DFA与NFA有何区别? 答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。3.构造正规式相应的DFA:1(1010*|1(010)*1)*0。解 ： 1(1010 * | 1(010) * 1) * 0 对 应 的 NFA 为 ： 4.已知文法G(S) S→a|∧|(T)T→T，S|S 写出句子((a，a)，a)的规范归约过程及每一步的句柄。解：句型 ((a，a)，a)((S，a)，a)((T，a)，a)((T，S)，a)((S)，a)((T)，a)(S，a)(T，a)(T，S)(T)S 归约规则S→aT→SS→aT→T，ST→SS→S(T)T→SS→aT→T，SS→(T) 句柄aSaT，SS(T)SaT，S(T) 5.何谓优化？按所涉及的程序范围可分为哪几级优化？ 1)优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。(2)三种级别：局部优化、循环优化、全局优化。五.计算题（10分） 对下面的文法G：E->TE'E'->+E|εT->FT'T'->T|ε F->PF'F'->*F'|εP->(E)|a|b|^ (1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。(4分)(2)证明这个方法是LL(1)的。(4分)(3)构造它的预测分析表。(2分)解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(E')={+,ε} FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε}; FIRST(F)=FIRST(P)={(,a,b,^};FIRST(F')=FIRST(P)={*,ε};FIRST(P)={(,a,b,^};FOLLOW集合有： FOLLOW(E)={),#}; FOLLOW(E')=FOLLOW(E)={),#}; FOLLOW(T)=FIRST(E')∪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]的预测分析表如下： 《编译原理》模拟试题三 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×) 2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(×) 3．递归下降分析法是自顶向上分析方法。(√) 4．产生式是用于定义词法成分的一种书写规则。(×)5．LR法是自顶向下语法分析方法。(√) 6．在SLR（1）分析法的名称中，S的含义是简单的。(√) 7．综合属性是用于“自上而下”传递信息。(×) 8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(×) 9．程序语言的语言处理程序是一种应用软件。(×) 10．解释程序适用于COBOL和FORTRAN语言。(×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．文法G产生的_____的全体是该文法描述的语言。A．()句型B．()终结符集C．()非终结符集D．()句子2．若文法G定义的语言是无限集，则文法必然是_____。 A．()递归的B．()前后文无关的C．()二义性的D．()无二义性的 3．四种形式语言文法中，1型文法又称为_____文法。A．()短语结构文法B．()前后文无关文法C．()前后文有关文法D．()正规文法4．一个文法所描述的语言是_____。A．()唯一的B．()不唯一的C．()可能唯一，好可能不唯一D．()都不对5．_____和代码优化部分不是每个编译程序都必需的。A．()语法分析B．()中间代码生成C．()词法分析D．()目标代码生成6．_____是两类程序语言处理程序。A．()高级语言程序和低级语言程序B．()解释程序和编译程序C．()编译程序和操作系统D．()系统程序和应用程序7．数组的内情向量中肯定不含有数组的_____的信息。A.()维数B．()类型C．()维上下界D．()各维的界差 8.一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组_____。 A．()句子B．()句型C．()单词D．()产生式 9．文法分为四种类型，即0型、1型、2型、3型。其中2型文法是_____。A.()短语文法B．()正则文法C．()上下文有关文法D．()上下文无关文法10．文法G所描述的语言是_____的集合。 A.()文法G的字母表V中所有符号组成的符号串B．()文法G的字母表V的闭包V*中的所有符号串C．()由文法的开始符号推出的所有终极符串D.()由文法的开始符号推出的所有符号串三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。 2．对于文法的每个产生式都配备了一组属性的计算规则，称为__语义规则___。3．一个典型的编译程序中，不仅包括__词法分析___、__语法分析___、__中间代码生成___、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。 4．从功能上说，程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。5．扫描器的任务是从__源程序___中识别出一个个___单词符号__。6．产生式是用于定义__语法范畴___的一种书写规则。四、简答题（20分） 1.写一个文法，使其语言是奇数集，且每个奇数不以0开头。解：文法G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D 2.设文法G(S)： S→(L)|aS|aL→L，S|S (1)消除左递归和回溯； (2)计算每个非终结符的FIRST和FOLLOW。解：(1)S→(L)|aS'S'→S|εL→SL'L'→SL'|ε(2) FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S')＝{，a,ε}FOLLOW(S')＝{#，，，)}FIRST(L)＝{(，a}FOLLOW(L)＝{)}FIRST(L')＝{，，ε}FOLLOW(L'〕＝{)}3.已知文法G(E) E→T|E＋TT→F|T*FF→(E)|i (1)给出句型(T*F＋i)的最右推导；(2)给出句型(T*F＋i)的短语、素短语。 解：(1)最右推导：->(T＋i)->(T*F＋i) (2)短语：(T*F＋i)，T*F＋i，T*F，i E->T->F->(E)->(E＋T)->(E＋F)->(E＋i) 素短语：T*F,i4.While a＞0∨b＜0Begin do X：＝X＋1； ifa＞0thena：＝a－1 elseb：＝b＋1 End； 翻译成四元式序列。 解： (1)(j＞，a，0，5)(2)(j，－，－，3)(3)(j＜，b，0，5)(4)(j，－，－，15)(5)(＋，×，1，T1)(6)(：＝，T1，－，×)(7)(j≥，a，0，9)(8)(j，－，－，12)(9)(－，a，1，T2)(10)(：＝，T2，－，a)(11)(j，－，－，1)(12)(＋，b，1，T3)(13)(：＝，T3，－，b)(14)(j，－，－，1)(15) 五.计算题（10分） 已知NFA=（{x,y,z},{0,1},M,{x},{z}），其中： M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x},M(y,1)=φ,M(z,1)={y},构造相应的DFA并最小化。 解：根据题意有NFA图:下 表 由 子 集 法 将 NFA 转 换 为 DFA ： 下面将该DFA最小化： (1)首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F} (2)区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。 (3)区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。 (4)由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。 (5)综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下： 《编译原理》模拟试题四 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．一个LL(l)文法一定是无二义的。(×) 2．正规文法产生的语言都可以用上下文无关文法来描述。(×) 3．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。(√)4．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(×) 5．逆波兰法表示的表达式亦称前缀式。(√) 6．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。(√)7．LR法是自顶向下语法分析方法。(×) 8．数组元素的地址计算与数组的存储方式有关。(×) 9．算符优先关系表不一定存在对应的优先函数。(×) 10．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器用于识别_____。A．()字符串B．()语句C．()单词D．()标识符 2．文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_____。A.()短语文法B．()正则文法C．()上下文有关文法D．()上下文无关文法3．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组_____。A．()句子B．()句型C．()单词D．()产生式4．_____是一种典型的解释型语言。A．()BASICB．()CC．()FORTRAND．()PASCAL5．与编译系统相比，解释系统_____。 A．()比较简单,可移植性好,执行速度快B．()比较复杂,可移植性好,执行速度快C．()比较简单,可移植性差,执行速度慢D．()比较简单,可移植性好,执行速度慢 6．用高级语言编写的程序经编译后产生的程序叫_____。A．()源程序B．()目标程序C．()连接程序D．()解释程序7．词法分析器用于识别_____。A.()字符串B．()语句C．()单词D．()标识符 8．编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过_____这几步:(1)编辑(2)编译(3)连接(4)运行A.()(1)(2)(3)(4)B．()(1)(2)(3)C．()(1)(3)D．()(1)(4) 9．把汇编语言程序翻译成机器可执行的目标程序的工作是由_____完成的。 A．()编译器B．()汇编器C．()解释器D．()预处理器 10．文法G所描述的语言是_____的集合。 A.()文法G的字母表V中所有符号组成的符号串B．()文法G的字母表V的闭包V*中的所有符号串C．()由文法的开始符号推出的所有终极符串D.()由文法的开始符号推出的所有符号串三、填空题(每空1分，共10分) 1．语法分析是依据语言的__语法___规则进行的，中间代码产生是依据语言的__语义___规进行的。 2．语法分析器的输入是__单词符号串___，其输出是__语法单位___。3．一个名字的属性包括__类型___和__作用域___。 4．产生式是用于定义___语法成分__的一种书写规则。 5．逆波兰式ab+c+d*e-所表达的表达式为__(a+b+c)*d-e___。 6．语法分析最常用的两类方法是__自上而下___和__自下而上___分析法。四、简答题（20分） 1.写出下列表达式的三地址形式的中间表示。(1)5+6*(a+b); (2)forj:=1to10doa[j+j]:=0。答：(1)100:t1:=a+b101:t2:=6*t1102:t3:=5+t2(2)100:j:=1 101:ifj>10gotoNEXT102:i:=j+j103:a[i]:=0 2.设基本块p由如下语句构成：T0:=3.14;T1:=2*T0;T2:=R+r; A:=Tl*T2；B:=A; T3:=2*T0;T4:=R+r; T5:=T3*T4;T6:=R-r；B:=T5*T6； 试给出基本块p的DAG。 解：基本块p的DAG图: 3.写出表达式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。解：（1）三元式：①（＋，a，b）②（－，a，b）③（/，①，②）④（*，b，c）⑤（＋，a，④） ⑥（－，③，⑤）（2）四元式： ①（＋，a，b，T1）②（－，a，b，T2）③（/，T1，T2，T3）④（*，b，c，T4）⑤（＋，a，T4，T5）⑥（－，T3，T5，T6） 4.写一个文法使其语言为偶数集，且每个偶数不以0开头。解：文法G（S）：S→AB|B|A0A→AD|CB→2|4|6|8C→1|3|5|7|9|BD→0|C 5.设文法G（S）：S→S＋aF|aF|＋aFF→*aF|*a （1）消除左递归和回溯； （2）构造相应的FIRST和Follow集合。1） S->aFS'|＋aFS'S'->＋aFS'|εF->*aF'F'->F|ε（2） FIRST（S）＝｛a，+｝FOLLOW（S）＝｛＃｝FIRST（S'）＝｛+，ε｝FOLLOW（S'）＝｛＃｝FIRST（F）＝｛*｝FOLLoW（F）＝（+，＃｝FIRST（F'）＝｛*，ε｝FOLLOW（+，＃｝五.计算题（10分）已知文法为：S->a|^|(T)T->T,S|S 构造它的LR(0)分析表。 解：加入非终结符S'，方法的增广文法为：S'->SS->aS->^S->(T)T->T,S T->S下面构造它的LR(0)项目集规范族为： 从上表可看出,不存在移进-归约冲突以及归约归约冲突，该文法是LR(0)文法。从而有下面的LR(0)分析表： 《编译原理》模拟试题五 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。(×) 2．一个有限状态自动机中，有且仅有一个唯一的终态。(×)3．一个算符优先文法可能不存在算符优先函数与之对应。(√)4．语法分析时必须先消除文法中的左递归。(×) 5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√)6．逆波兰表示法表示表达式时无须使用括号。(√)7．静态数组的存储空间可以在编译时确定。(×) 8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。(×)10．一个语义子程序描述了一个文法所对应的翻译工作。(×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。A．()单词的种别编码B．()单词在符号表中的位置C．()单词的种别编码和自身值D．()单词自身值2．正规式M1和M2等价是指_____。A．()M1和M2的状态数相等B．()M1和M2的有向边条数相等C．()M1和M2所识别的语言集相等D．()M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。A．()xyxB．()(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．()代码外提 10．编译程序使用_____区别标识符的作用域。A.()说明标识符的过程或函数名 B．()说明标识符的过程或函数的静态层次C．()说明标识符的过程或函数的动态层次 D.()标识符的行号 三、填空题(每空1分，共10分) 1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。 2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。5．后缀式abc-/所代表的表达式是___a/(b-c)__。 6．局部优化是在__基本块___范围内进行的一种优化。四、简答题（20分） 1.简要说明语义分析的基本功能。 答：语义分析的基本功能包括:确定类型、类型检查、语义处理和某些静态语义检查。2.考虑文法G[S]:S→(T)|a+S|aT→T,S|S 消除文法的左递归及提取公共左因子。解：消除文法G[S]的左递归：S→(T)|a+S|aT→ST′T′→,ST′|ε 提取公共左因子：S→(T)|aS′S′→+S|εT→ST′T′→,ST′|ε 3.试为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。解：wab+cde10-/+8+*+ 4.按照三种基本控制结构文法将下面的语句翻译成四元式序列：while(A 解：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)：100(j<,A,C,102)101(j,_,_,113)102(j<,B,D,104) 103(j,_,_,113)104(j=,A,1,106)105(j,_,_,108)106(+,C,1,C) 107(j,_,_,112) 108(j≤,A,D,110)109(j,_,_,112)110(+,A,2,A)111(j,_,_,108)112(j,_,_,100)1135.已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。证明： 由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为： 因此，文法G[S]为二义文法。 五.计算题（10分）已知文法A->aAd|aAb|ε 判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有：S'->AA->aAd|aAb|ε下面构造它的LR(0)项目集规范族为： 从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。其SLR(1)分析表为： 对输入串ab#给出分析过程为： 《编译原理》模拟试题六 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×) 2．确定的自动机以及不确定的自动机都能正确地识别正规集。(√)3．词法分析作为单独的一遍来处理较好。(×) 4．构造LR分析器的任务就是产生LR分析表。(√) 5．规范归约和规范推导是互逆的两个过程。(×) 6．同心集的合并有可能产生新的“移进”/“归约”冲突。(×)7．LR分析技术无法适用二义文法。(×) 8．树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。(×)9．程序中的表达式语句在语义翻译时不需要回填技术。(√)10．对中间代码的优化依赖于具体的计算机。(×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．编译程序绝大多数时间花在_____上。A．()出错处理B．()词法分析C．()目标代码生成D．()表格管理2．编译程序是对_____。A．()汇编程序的翻译B．()高级语言程序的解释执行C．()机器语言的执行D．()高级语言的翻译3．采用自上而下分析，必须_____。A．()消除左递归B．()消除右递归C．()消除回溯D．()提取公共左因子4．在规范归约中，用_____来刻画可归约串。A．()直接短语B．()句柄C．()最左素短语D．()素短语5．若a为终结符，则A->α·aβ为_____项目。 A．()归约B．()移进C．()接受D．()待约6．间接三元式表示法的优点为_____。A．()采用间接码表，便于优化处理B．()节省存储空间，不便于表的修改C．()便于优化处理，节省存储空间D．()节省存储空间，不便于优化处理7．基本块内的优化为_____。A.()代码外提，删除归纳变量B．()删除多余运算，删除无用赋值C．()强度削弱，代码外提D．()循环展开，循环合并8.在目标代码生成阶段，符号表用_____。A．()目标代码生成B．()语义检查C．()语法检查D．()地址分配9．若项目集Ik含有A->α · ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才 采取“A->α·”动作的一定是_____。 A.()LALR文法B．()LR(0)文法C．()LR(1)文法D．()SLR(1)文法 10．堆式动态分配申请和释放存储空间遵守_____原则。 A.()先请先放B．()先请后放C．()后请先放D.()任意三、填空题(每空1分，共10分) 1．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。 2．语法分析基于__上下文无关___文法进行，即识别的是该类文法的句子。语法分析的有效工具是__语法树___。 3．分析句型时，应用算符优先分析技术时，每步被直接归约的是__最左素短语___，而应用LR分析技术时，每步被直接归约的是___句柄__。 4．语义分析阶段所生成的与源程序等价的中间表示形式可以有__逆波兰___、___四无式表示__与___三元式表示__等。 5．按Chomsky分类法，文法按照___规则定义的形式__进行分类。 6．一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有___递归__定义的规则。 四、简答题（20分）1.文法G[S]为：S->Ac|aBA->abB->bc 写出L(G[S])的全部元素。解：S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc} 2.构造正规式1(0|1)*101相应的DFA。解：先构造NFA： 确定化： 重新命名，令AB为B、AC为C、ABY为D得： 所以，可得DFA为： 3.文法S->a|^|(T)T->T,S|S 对(a,(a,a)和(((a,a),^,(a)),a)的最左推导。解：对(a,(a,a)的最左推导为： S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a)) 对(((a,a),^,(a)),a)的最左推导为：S=>(T)=>(T,S)=>(S,S)=>((T),S) =>((T,S),S)=>((T,S,S),S)=>((S,S,S),S) =>(((T),S,S),S)=>(((T,S),S,S),S)=>(((S,S),S,S),S)=>(((a,S),S,S),S)=>(((a,a),S,S),S)=>(((a,a),^,S),S)=>(((a,a),^,(T)),S)=>(((a,a),^,(S)),S)=>(((a,a),^,(a)),S)=>(((a,a),^,(a)),a) 4.文法：S->MH|aH->LSo|εK->dML|εL->eHfM->K|bLM 判断G是否为LL(1)文法，如果是，构造LL(1)分析表。解：各符号的FIRST集和FOLLOW集为： 预测分析表为： 由于预测分析表中无多重入口，所以可判定文法是LL(1)的。五.计算题（10分）已知文法G[S]为：S->a|^|(T)T->T,S|S (1)计算G[S]的FIRSTVT和LASTVT。 (2)构造G[S]的算符优先关系表并说明G[S]是否未算符优先文法。(3)计算G[S]的优先函数。 (4)给出输入串(a,a)#的算符优先分析过程。解：（1）各符号的FIRSTVT和LASTVT： （2）算符优先关系表： （3）对应的算符优先函数为： （4）句子(a,a)#分析过程如下： 因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- yule263.com 版权所有 湘ICP备2023023988号-1
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务