编译原理
2014—2015学年第二学期第四单元测试试卷（闭卷考试）时间：45分钟满分：100分
姓名班级出题人班级软件12-4
题目一二三四五总分
得分
一、选择题（5*2分）（每题1分，共10分）
1. 下列文法中，_______是LL(1)文法。
A. S→aSb|ab
B. S→ab|Sab
C. S→aS|b
D. S→aS|a
2. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于分析法。
A. 自左至右
B. 自顶向下
C. 自底向上
D. 自右向左
3. 自上而下分析面临的四个问题中，不包括。
A. 需消除左递归；
B. 存在回朔；
C. 虚假匹配；
D. 寻找可归约串
4. 语法分析器接收以________为单位的输入，并产生有关信息供以后各阶段使用。
A. 表达式；
B. 产生式； C 单词；D. 语句；
5. 自上而下分析的主旨是，对任何单词符号串，试图用一切可能的办法，从文法开始符号（根结点）出发，________。
A. 为输入串寻找最右推导；
B. 为输入串寻找最左直接子树；
C. 为输入串建立最右直接子树；
D. 为输入串寻找最左推导；
二、简答题（2*10分）（每题10分，共20分）
6. 词法分析和语法分析都是对字符串进行识别的，二者有何区别？
7. 为什么要消除回溯？
三、分析题（4题共70分）
8.设有文法G[S]：
S→AB
A→bB|Aa
B→Sb|a
试消除该文法的左递归。（15分）
9.已知文法G[E]：
G[E]：E→E+T|T
T→T*F|F
F→i|(E)
请按递归子程序法为其构造语法分析程序。（20分）
10．文法G[M]是否是LL(1)文法，说明理由。（15分）G[M]：M→TB
T→Ba|ε
B→Db|eT|ε
D→d|ε
11. 已知文法G[S]：
S → uBDz
B → Br | w
D → EF
E → y | ?
F → x | ?
(1) 求每个非终结符的FIRST和Follow集。
(2) 构造这个文法的LL(1)分析表
(3) 说明这个文法不是LL(1)的;
(3) 尽可能少地修改此文法,使其成为能产生相同语言的LL(1)文法.（20分）
第四章答案
1-5
B D D
C D
6. 答：词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子。词法分析的一个输入符号串是由单个符号组成的单词；语法分析的输入符号串是由词法分析得来的单词组成的句子。
7. 假定当前轮到非终结符A去执行匹配任务，A共有n个候选?1、?2、……?n，这时候该用哪一个候选去替换A，原始的办法是采用对所有候选采取“试探”的方法。如果某个候选不成功就需要“回退”。这个回退的过程会导致前次匹配的许多工作推到重来，效率低。而且，最终匹配不成功的时候，难以直到输入串中出错的确切位置。
8.解：本题考查消除左递归的方法。
应用消除文法左递归的算法对文法G[S]消除左递归的过程如下：
（1）将非终结符排序为：U1=S，U2=A，U3=B
（2）进入算法排序：
i=1时，对文法无影响
i=2，j=1时：A→Aa有直接左递归，消去该直接左递归，得
A→bBA’
A’→aA’|ε
i=3，j=1时：改写文法，有
B→ABb|a
j=2时：改写文法，有
B→bBA’Bb|a无左递归。
（3）所以文法G[S]消除左递归后变为：
G’[S]：S→AB
A→bBA’
A’→aA’|ε
B→bBA’Bb|a
9.解：本题考查递归子程序的构造方法。
本题所给文法存在左递归，不满足递归子程序法对文法的要求，必须首先消除文法左递归，然后再构造分析程序。
因为文法只有左递归，采用扩充的BNF范式消除文法左递归得到：
G[E]：E→T{+T}
T→F{*F}
F→i|(E)
然后再应用书中介绍的方法即可求解。
假定用“ADVANCE;”表示对读取下一个单词的过程的调用。
相应的递归子程序为：
PROCEDURE P(E);
BEGIN
P(T);
WHILE SYM=’+’DO
BEGIN
ADVANCE;
P(T)
END
END;
PROCEDURE P(T);
BEGIN
P(F);
WHILE SYM=’*’DO
BEGIN
ADVANCE;
P(F)
END
END;
PROCEDURE P(F);
BEGIN
IF SYM=’i’THEN ADVANCE
ELSE IF SYM=’(’THEN
BEGIN
ADVANCE;
P(E);
IF SYM=’)’THEN ADVANCE
ELSE ERROR
END
ELSE ERROR
END;
主程序中的主要内容为：
ADVANCE;
P(E);
IF WORD=”#”
THEN WRITE(“RIGHT!”)
ELSE WRITE(“ERROR!”)
10.解：本题考查LL(1)方法对文法的要求，涉及到FIRST集、FOLLOW集的求法。
首先求出文法的每一个非终结符号的FIRST集、FOLLOW集：
FIRST(D)=FIRST(d)∩FIRST(ε)={d, ε}
FIRST(B)=FIRST(Db)∩FIRST(eT)∩FIRST(ε)
=FIRST(db)∩FIRST(b)∩FIRST(eT)∩FIRST(ε)
={d，b，e，ε}
FIRST(T)=FIRST(Ba)∩FIRST(ε)={d，b，e，a，ε}
FIRST(M)=FIRST(Tb)= {d，b，e，a，ε}
FOLLOW(M)={#}
FOLLOW(B)=FOLLOW(M)∪FIRST(a)\{ε}={a，#}
FOLLOW(T)=FOLLOW(B)\{ε}∪FOLLOW(M) ∪FOLLOW(B)={d，b，e，#，a}
FOLLOW(D)=FIRST(b)\{ε}={b}
可以看出，对文法G[M]的产生式T→Ba|ε，有
FIRST(Ba)∩FOLLOW(T)={d，b，e，a}∩{d，b，e，#，a}={d，b，e，a}≠?仅此一条就会导致在自上而下的语法分析过程中出现回朔。
所以文法G[M]不是LL(1)文法。
11. 答案：
(1) FIRST(S) = { u } FOLLOW(S) = {#} FIRST(B) = {w } FOLLOW(B) = { r, z } FIRST(D) = { x, y, ?} FOLLOW(D) = { z } FIRST(E) = { y, ?} FOLLOW(E) = { x, z } FIRST(F) = { x, ? } FOLLOW(F) = { z }
(2) 该文法的LL(1)分析表为：
(3) 因为M[B, w]有两个产生式 B→Bv, B→w 且FIRST(Bv)=FIRST(w) = { w }
所以不是LL(1)的。
(4) 消除左递归即可。
S→uBDz
B→wB′
B′→rB′ | ?
D → EF
E = y | ?
F = x | ?
编译原理第4章作业 答案 本页仅作为文档封面，使用时可以删除 This document is for reference only-rar21year.March
第四章 习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a* (3)给出这个串的一棵语法分析树 习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆： rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 1)对这个文法提取公因子 2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？ 3)提取公因子之后，原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗？ 解
1)提取左公因子之后的文法变为 rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法 3)消除左递归后的文法
rexpr -> rterm rexpr’ rexpr’-> + rterm rexpr’|ε rterm-> rfactor rterm’ rterm’-> rfactor rterm’|ε rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|ε rprimary-> a | b 4)该文法无左递归，适合于自顶向下的语法分析 习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归 (3)S->S(S)S|ε (5)S->(L)|a L->L,S|S 解 (3) ①消除该文法的左递归后得到文法 S->S’ S’->(S)SS’|ε ②计算FIRST和FOLLOW集合 FIRST(S)={(,ε} FOLLOW(S)={),$} FIRST(S’)={(,ε} FOLLOW(S’)={),$} ③构建预测分析表
一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0） 项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分） 答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分） （3）（4分） 短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分） 答：句子aaa对应的两颗语法树为：
因此，文法是二义文法 四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分） 答：对应的NFA为：（6分） 状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分） 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分） （2）构造相应的first 和 follow 集合。（6分） 答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T)
第一章 1．典型的编译程序在逻辑功能上由哪几部分组成？ 答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？ 答：编译法、解释法。 4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。
第二章 1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？ 答：1）0型文法、1型文法、2型文法、3型文法。 2） 2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。 答： Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为： N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。 答：N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。 答：对于句型iiSeS存在两个不同的最左推导： S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。 （1）L1={a n b n c i |n>=1,i>=0 } （2）L2={a i b j|j>=i>=1} （3）L3={a n b m c m d n |m,n>=0} 答： （1）S→AB A→aAb | ab B→cB | ε （2）S→ASb |ab
精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************
一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式M 1 和M 2 等价是指__C_。 A．M1和M2的状态数相等 B．M1和M2的有向边条数相等 C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A．xyx B．(xyx)* C．xnyxn(n≥0) D．x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言C．编译方法D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x
第七章目标代码生成 7.1 对下列四元式序列生成目标代码： T=A-B S=C+D W=E-F U=W/T V=U*S 其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。 【解答】简单代码生成算法依次对四元式进行翻译。我们以四元式T=a+b为例来说明其翻译过程。 汇编语言的加法指令代码形式为 ADD R, X 其中，ADD为加法指令；R为第一操作数，第一操作数必须为寄存器类型；X为第二操作数，它可以是寄存器类型，也可以是内存型的变量。ADD R,X指令的含意是：将第一操作数R与第二操作数相加后，再将累加结果存放到第一操作数所在的寄存器中。要完整地翻译出四元式T=a+b，则可能需要下面三条汇编指令： MOV R, a ADD R, b MOV T, R 第一条指令是将第一操作数a由内存取到寄存器R中；第二条指令完成加法运算；第三条指令将累加后的结果送回内存中的变量T。是否在翻译成目标代码时都必须生成这三条汇编指令呢？从目标代码生成的优化角度考虑，即为了使生成的目标代码更短以及充分利用寄存器，上面的三条指令中，第一条和第三条指令在某些情况下是不必要的。这是因为，如果下一个四元式紧接着需要引用操作数T，则第三条指令就不急于生成，可以推迟到以后适当的时机再生成。 此外，如果必须使用第一条指令，即第一操作数不在寄存器而是在内存中，且此时所有可用寄存器都已分配完毕，这时就要根据寄存器中所有变量的待用信息(也即引用点)来决定淘汰哪一个寄存器留给当前的四元式使用。寄存器的淘汰策略如下： (1) 如果某寄存器中的变量已无后续引用点且该变量是非活跃的，则可直接将该寄存器作为空闲寄存器使用。 (2) 如果所有寄存器中的变量在基本块内仍有引用点且都是活跃的，则将引用点最远的变量所占用寄存器中的值存放到内存与该变量对应的单元中，然后再将此寄存器分配给当前的指令使用。 因此，本题所给四元式序列生成的目标代码如下： MOV R0, A SUB R0, C /*R0=T*/ MOV R1, C ADD R1, D /*R1=S*/ MOV S, R1 /*S引用点较T引用点远，故将R1的值送内存单元S*/ MOV R1, E SUB R1, F /*R1=W*/ SUB R1, R0 /*R1=U*/ MUL R1, S /*R1=V*/ 7.2 假设可用的寄存器为R0和R1，且所有临时单元都是非活跃的，试将以下四元式基本
编译 原理 课后题答案 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导:
E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/******************************** E E F T E + T F F T +i i i E E F T E -T F F T -i i i E E F T +T F F T i i i *i+i+i i-i-i i+i*i *****************/ P36-9 句子iiiei 有两个语法树： S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ???????? P36-10 /************** ) (|)(|S T T TS S →→ ***************/ P36-11 /*************** L1: ε ||cC C ab aAb A AC S →→→ L2:
编译原理期中测试答案 三、单项选择题(每题3分，共15分) 1．设有文法G[S]: S→(AS)|(b) A→(SaA)|(a) 该文法的句型(((b)a(a))(b))有 C 个直接短语。 A.1 B. 2 C. 3 D. 4 2．如果一个文法满足 D ，则称该文法是二义性文法。 (1) 文法的某一个句子存在两个（包括两个）以上的语法树 (2) 文法的某一个句子存在两个（包括两个）以上的最左推导 (3) 文法的某一个句子存在两个（包括两个）以上的最右推导 (4) 在进行归约时，文法的某些规范句型的句柄不唯一 上述描述中的所有正确描述有： A. (1) B. (1)(2) C. (1)(2)(3) D. (1)(2)(3)(4) 3．构造一个不带回溯的自顶向下语法分析器，要求文法满足 E 。 A.对每个形如A→x1|x2|…|xn的产生式，要求FIRST(xi)与FIRST(xj)的交集为空集(i≠j) B.对每个形如A→x1|x2|…|xn的产生式，若xi* ε，则要求FIRST(xj)与FOLLOW(A)的交集为空集(i≠j) C. 不含左递归 D. A和B同时满足 E. A、B和C同时满足
4、给定文法A→bA|cc，下列符号串中，是该文法的句子的是 C 。 ① cc ② bcbc ③ bcbcc ④ bccbcc ⑤ bbbcc A① B. ①③④⑤ C. ①⑤ D. ①④⑤ 5、若一个句型中出现了某一产生式的右部，则此右部 B 是该句型的句柄。 A.一定 B. 不一定 C. 一定不 D. 无法判断 四、简述题(每题5分，共20分) 1、写一上下文无关文法,它能产生语言}0 n。 n a L m b , =m | {>= # S→A#B A→Aa|ε B→Bb|ε 2、将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]：S→bSAe | bA A→Ab | d 答：文法G[S] 改写为等价的不含左递归和左公共因子的 G'[S]S→bB B→SAe | A A→d A' A' →bA' | ε 3、什么是文法的二义性？下面的文法是二义的吗？为什么？
第八章 语法制导翻译和中间代码生成 1．给出下面表达式的逆波兰表示(后缀式)： (1) a*(-b+c) (4) (A ∧B) ∨(?C ∨ D) (7) if(x+y)*z=0 then s ∶=(a+b)*c else s ∶=a*b*c 解(1) ab-c+* (4) AB ∧C ?D ∨∨ (7) xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else 运算） 2. 请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。 答案：三元式 (1) (+ a, b) (2) (+ c, d) (3) (* (1), (2)) (4) (- (3), /) (5) (+ a, b) (6) (+,(5),c) (7) (- (4), (6)) 间接三元式 间接三元式序列 间接码表 (1) (+ a, b) (1) (2) (+ c, d) (2) (3) (* (1), (2)) (3) (4) (- (3), /) (4) ￥ = := * := + x y z s + c x a b s * c * a b
(5) (- (4), (1)) (1) (6) (- (4), (5)) (5) (6) 四元式 (1) (+, a, b, t1) (2) (+, c, d, t2) (3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5) (6) (+, t5, c, t6) (6) (-, t4, t6, t7) 3. 采用语法制导翻译思想，表达式E 的"值"的描述如下： 产生式 语义动作 (0) S ′→E {print E.VAL} (1) E →E1+E2 {E.VAL ∶=E1.VAL+E2.VAL} (2) E →E1*E2 {E.VAL ∶=E1.VAL*E2.VAL} (3) E →(E1) {E.VAL ∶=E1.VAL} (4) E →n {E.VAL ∶=n.LEXVAL} 如果采用LR 分析法，给出表达式(5 * 4 + 8) * 2的语法树并在各结点注明语义值VAL 。 4. 假如习题3中表达式E 的“值”有两种类型：整型和实型。语义处理增加"类型匹配检查"，请给出相应的语义描述。 S ’ * E1 E2 E0 E3 2 E5.V AL=5 8 5 * E5 E6 + E4 4 E6.V AL=4 E4.V AL=8 E3.V AL=20 E1.V AL=28 E2.V AL=2 E0.V AL=56 Print(56)
第四章 词法分析 1．构造下列正规式相应的DFA ： (1) 1(0|1)* 101 (2) 1(1010* | 1(010)* 1)* (3) a((a|b)*|ab *a)* b (4) b((ab)* | bb)* ab 解： (1)1(0|1)* 101对应的NFA 为 下表由子集法将NFA 转换为DFA ： (2)1(1010* | 1(010)* 1)* 0对应的NFA 为 下表由子集法将 NFA 转换为DFA ：
(3)a((a|b)*|ab*a)* b (略) (4)b((ab)* | bb)* ab (略) 2．已知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图如下
0，1 下表由子集法将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如下： 3.将图 4.16确定化： 图4.16 解：下表由子集法将NFA转换为DFA： 1
一． 填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静 态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址 计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一 7． 如果在文法G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。 A ． 其最左推导和最右推导相同 B ． 该句子有两个不同的最左推导 C ． 该句子有两个不同的最右推导 D ． 该句子有两棵不同的语法树
第一章 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所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a) 第1章引论 第1题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2） 源程序：源语言编写的程序称为源程序。 （3） 目标程序：目标语言书写的程序称为目标程序。 （4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。 第3题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 答案： 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功 编译原理试题B 一、单项选择题（每题1分，共20分） 1、对编译系统有关概念描述正确的是（ B） A．目标程序只能是机器语言 B. 编译程序处理的对象是源语言 C．解释程序属于编译程序 D. 词法分析无法自动进行 2. 设有表达式a*b-c，将其中a*b识别为表达式的编译阶段是什么 （B） A．词法分析 B. 语法分析 C．语义分析 D. 代码生成 3. 下面不能用于对文法进行描述的是（A ） A．源语言 B. EBNF C．BNF D. 语法图 4. 设有文法G[S]: S→0S|1A|0，A→1|1S|0B，B→1A|0B，下列符号串中是该文法的句子的是 （）？A．1010001001101 B.0101001110010010 C．1101010011110111 D.1010011101101010 (可画出DFA验证) 5. 文法G[S]: S→aA|bC|a A→aS|bB B→aC|bA|b C→aB|bS ,则不是L(G)句子的是（ B ） A．a100b50ab100 B. a1000b500aba C．a500b60aab2a D. a100b40ab10aa （画出DFA） 6. 哪个不是DFA的构成成分（B） A．有穷字母表 B. 初始状态集合 C．终止状态集合 D. 有限状态集合 7.词法分析器的输入是（ B ） A．单词符号串 B.源程序 C．语法单位 D.目标程序 8.在词法分析阶段不能识别的是（C ） A．标识符 B. 运算符 C．四元式 D. 常数 9.设有一段C语言程序 while(i&&++j) { c=2.19; j+=k; i++; } ,经过词法分析后可以识别的单词个数是（B ） A．19 B.20 C．21 D.23 10．自上而下语法分析的主要动作是（ B ） A．移进 B. 推导 C．规约 D. 匹配 11.下面不属于LL(1)分析器的自称部分是（ D ） A．LL(1)总控程序 B. LL(1)分析表 C．分析栈 D.源程序串 12.设有文法G[S]为 S→AB|bC， A→ε|b，B→ε|aD，C→AD|b，D→aS|c 则FOLLOW(A)为（A ） A．{a,c,#} B.{c,#} C．{a,#} D.{#} 13.设有文法G[S]: S→Ap|Bq，A→a|cA，B→b|dB ，则FIRST(Ap)为（ C ）A．{p,q} B. {b,d} C．{a,c} D. 其他 14.自下而上语法分析的主要分析动作是（D ） A．推导 B. 规约 C．匹配 D. 移进-规约 15.算法优先分析中，可规约串是（ C ） A．句柄 B．活前缀 C．最左素短语 D．素短语 16. 设有文法G={{S},{a},{S→SaS|ε},S}，该文法是（ B ） A．LL(1)文法 B．二义性文法 C．SLR(1)文法 D．算法优先文法 17、中间代码生成时所以据的是（C ） A．语法规则 B．词法规则 C．语义规则D．等价变换规则 18、给定文法G: E→E+T|T，T→T*F|F，F→i|(E) 则L(G)中的一个句子i+i+(i*i)*i的逆波兰表示为（ C ） A．iii*i++ B．ii+iii**+ C．ii+ii*i*+ D．其他 <编译原理>历年试题及答案 一．（每项选择 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+d b． (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+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 《编译原理》第一次作业参考答案 一、下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？ 1.b*(ab*ab*)* 所有含有偶数个a的由a和b组成的字符串. 2.c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一：所有至少含有1个a和1个b的由a，b和c组成的字符串. 答案二：所有含有子序列ab或子序列ba的由a，b和c组成的字符串. 说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更“自然”. 二、设字母表∑={a,b}，用正则表达式（只使用a，b， ，|，*，+，？）描述下列语言： 1.不包含子串ab的所有字符串. b*a* 2.不包含子串abb的所有字符串. b*(ab?)* 3.不包含子序列abb的所有字符串. b*a*b?a* 注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容. ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ 《编译原理》第二次作业参考答案 一、考虑以下NFA： 1.这一NFA接受什么语言（用自然语言描述）？ 所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串. 2.构造接受同一语言的DFA. 答案一（直接构造通常得到这一答案）： 答案二（由NFA构造DFA得到这一答案）： 二、正则语言补运算 3.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串. 1.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串. 第四章 习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a* (3)给出这个串的一棵语法分析树 习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆： rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 1)对这个文法提取公因子 2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？ 3)提取公因子之后，原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗？ 解 1)提取左公因子之后的文法变为 rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法 3)消除左递归后的文法 rexpr -> rterm rexpr’ rexpr’-> + rterm rexpr’|ε rterm-> rfactor rterm’ rterm’-> rfactor rterm’|ε rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|ε rprimary-> a | b 4)该文法无左递归，适合于自顶向下的语法分析 习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归 (3)S->S(S)S|ε (5)S->(L)|a L->L,S|S 解 (3) ①消除该文法的左递归后得到文法 S->S’ S’->(S)SS’|ε ②计算FIRST和FOLLOW集合 FIRST(S)={(,ε} FOLLOW(S)={),$} FIRST(S’)={(,ε} FOLLOW(S’)={),$} ③ (5) ①消除该文法的左递归得到文法 S->(L)|a 《编译原理》期末试题（二） 一、是非题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。（） 3.已经证明文法的二义性是可判定的。（） 4.每个基本块可用一个DAG表示。（） 5.每个过程的活动记录的体积在编译时可静态确定。（） 6.2型文法一定是3型文法。（） 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 X ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（） 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 X ( ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 答案：1.× 2.× 3.× 4.√ 5.√ 6.×7.×8.× 9.√10.× 11.× 12.√ 13.× 14.√ 15.√ 16.√ 17.× 18.√19.√ 20.×21.√22.√ 二、填空题： 2.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标 代码生成）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。 4.从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。 5.语法分析器的输入是（单词符号），其输出是（语法单位）。 6.扫描器的任务是从（源程序中）中识别出一个个（单词符号）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如(类型、种属、所占单元大小、地址）等等。 8.一个过程相应的DISPLAY表的内容为(现行活动记录地址和所有外层最新活动记录的地址) 10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。 11.一个名字的属性包括( 类型)和(作用域 )。 12.常用的参数传递方式有(传地址），（传值），（传名） 13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。 14.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上） 分析法。 15.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。 17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。 19.语法分析是依据语言的（语法）规则进行。中间代码产生是依据语言的（语义）规则进行的。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（LL(1) 文法）文法。 22.对于数据空间的存贮分配， FORTRAN采用( 静态策略， PASCAL采用( 动态)策略。编译原理课后习题答案-清华大学-第二版
编译原理试题B及答案
编译原理试题及答案(期末复习版).pdf
编译原理 作业答案
编译原理第4章作业答案
(完整word版)编译原理期末试题(二)含答案,推荐文档
相关主题
文本预览