豆丁微信公众号
君，已阅读到文档的结尾了呢~~
广工历编译原理期末考试卷（精品）
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
广工历编译原理期末考试卷（精品）
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口豆丁微信公众号
君，已阅读到文档的结尾了呢~~
编译原理课程设计 编译原理 编译原理 pdf 新课程标准测试题 android 编译原理 编译原理及实践 编译原理书籍推荐 编译原理视频 编译原理 课件 c语言编译原理
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
中国科技大学编译原理课程测试八套卷合集(附解析)
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口编译原理题库――综合题-海文库
全站搜索：
您现在的位置：&>&&>&其它课程
编译原理题库――综合题
编译原理A卷已知文法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)分析表为：第1页共6页对输入串ab#给出分析过程为：
编译原理B卷构造下述文法 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，所以，改写该文法为确定的自动机为：下DFA:表由子集法
将NFA转换为由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：第2页共6页
由上表可知DFA为：
编译原理C卷6．(20分)已知上下文无关文法：S → L=R | RL → *R | idR → L(1) 请构造非终结符的FIRST和FOLLOW集合。（5分）(2) 构造该文法的LL(1)分析表。该文法是LL(1)文法吗？（15分7. （20分）考虑以下文法：S → AA → BA | εB → aB| b证明该文法是LR（1）的。(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表。7．（20分）阅读下面的LEX程序，并回答：（1）该程序完成了什么功能？（2）修改该程序，使之能够计算输入的标识符个数。（直接改在试题上） LEX程序如下：%{# include &stdio.h&int num_int = 0;int num_float = 0;int num_line = 0;int num_id = 0;
[0-9]第3页共6页
integerfltid
[+\-]?{digit}+ [+\-]?{digit}+\.{digit}+ [a-zA-z] {letter}({letter}|{digit})*{integer}
num_int++ ;{flt}\n.{id}
%%main(){yylex() ;printf(“\n%d integers, %d floating point numbers, %d lines, %d identifiers.\n”,num_int, num_float, num_line, num_id) ;}
num_float++ ; num_line++ ; ; num_id++;
C卷答案6解：(1) 根据L → *R | id，可得到FIRST(L)={*, id}；根据R → L，可得到FIRST(R)= FIRST(L)={*, id}；根据S → L=R | R，可得到FIRST(S)= FIRST(L)? FIRST(R)={*, id}；S是开始符号，所以有$?FOLLOW(S)；又根据S → L=R，可得到=?FOLLOW(L)；又根据S → L=R | R，可得到FOLLOW(S)?FOLLOW(L)；又根据L → *R，可得到FOLLOW(L)?FOLLOW(R)；又根据R → L，可得到FOLLOW(R)?FOLLOW(L)；所以有FOLLOW(S)={$}，FOLLOW{L}= FOLLOW{R}={$, =}。
(2) 构造LL(1)
7. （20分）考虑以下文法：S → AA → BA | ε第4页共6页B → aB| b证明该文法是LR（1）的。(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表；
第5页共6页7答：该程序完成的功能：计算整数、浮点数的个数，统计行数，并分别输出。 修改见程序。
编译原理D卷7、证明下面文法是SLR(1)但不是LR(0)的。
S→A A→AbObBa B→aAcOaOaAb S→AaAbOBbBa A→ε B→ε
四、（20分）设文法G[S]为S?aAcB
问：1、该文法是否为算符文法，为什么？A?Ab|b
2、构造算符优先关系表。B?d
3、该文法是否可改造为LL（1）文法，为什么？
五、（本题20分）设文法G为：
E?eAf|eBgA?aA|aB?Bb|a对于输入串eaaaf，采用LR（0）、LL（1）、SLR（1）等方法中合适的一种进行分析。六、（25分）有作控制用的布尔表达式文法G[E]及其语义动作如下：1、 构造SLR（1）分析表（若不是SLR(1)）的，则说明理由）2、 分析布尔式a∨b&c的四元式生成过程，并画出最后的真假链表。3、 给出语句IF
I:=m+n的完整四元式序列。 文法G[E]：(1)E?i?1?8、证明下面的文法是LL(1)的但不是SLR(1)的。 1.构造表达式（4*7+1）*2的附注语法树。 &i?2?
{E.TC:=NXQ;
E.FC=NXQ+1;GEN(J&,ENTRY(i?1?),ENTRY(i?2?),O);GEN(J,
,0)}?1?(2)E?AE
{E.FC:=E.FC; E.FC:=MERGE(A.TC ,E.TC)}(3)A?B∨
{BACKPATCH(B.FC ,NXQ); A.TC:=B.TC}(4)B?i
{B.TC:=NXQ;
B.FC:=NXQ+1; GEN(Jnz, ENTRY(i),
,0); GEN(J,
,0)}答案：7证明：
?1??1?求该文法的LR(0)项目集规范族如下： I0={S，A→?bBa} GO(I0，A)={S→A?，A→A?b }=I1 GO(I0，b)={A→b?Ba，B→?aAc，B→?a，B→?aAb}=I2GO(I1，b)={A→Ab?}=I3GO(I2，B)={A→bB?a}=I4GO(I2，a)={B→a?Ac，B→a?，B→a?A b，A→?Ab，A→?b Ba}=I5GO(I4，a)={ A→bBa?}= I6第6页共6页
GO(I5，A)={ B→aA?c，B→aA?b，A→A?b}= I7 GO(I5，b)={ A→b?Ba，B→?aAc，B→?a，B→?aAb }= I2 GO(I7，c)={ B→aAc?}= I8 GO(I2，b)={ B→aAb?，A→Ab?}= I9 考虑I1，I5都存在“移进―归约”冲突，所以该文法不是LR(0)的。 由于FOLLOW(S)={#}，不包含b，所以I1的冲突可以消解；由于FOLLOW(B)={a}，不包含b，所以I5的综上所述，该文法是SLR(1)的。 因为FIRST(AaAb)={a}，FIRST(BbBa)={b}
FIRST(AaAb)∩FIRST(BbBa)=? 所以该文法是LL(1)的。 求该文法的LR(0)项目集规范族如下： I0={S’→?S，S→?AaAb，S→?BbBa，A→?，B→?} I1={S→S?} I2={S→A?aAb} I3={S→B?bBa} I4={S→Aa?Ab，A→?} I5={S→Bb?Ba，B→?} I6={S→AaA?b} I7={S→BbB?a} I8={S→AaAb?} I9={S→BbBa?} 考虑I0：FOLLOW(A)=FOLLOW(B)={a，b}A→?和B→?的冲突无法消解，所以该文法不是SLR(1)的。 冲突可以消解；由于FOLLOW(B)={a}，FOLLOW(A)={c，b，#}，二者不相交，所以I9的冲突也可以消解。 8证明： 1解：第7页共6页n
)digit.lexval = 7
四 答：1、该文法是算符文法。因为其任一产生式的右部都不含相继（并列）的非终结符，即不含如下形式?QR?的产生式右部。
（4分）2、FIRST(S)={a},
LAST(S)={c},FIRST(A)={b},
LAST(A)={b},FIRST(B)={d},
LAST(B)={d}。
（3分）构造算符优先关系表如下：
第8页共6页原因：3、该文法可以改造为LL（1）文法。
（8分） ① 消除左递归：S→aAcB
A’→bA’|εB→d；
② FIRST(A)={a},
FOLLOW(A)={c}, FIRST(A’)={b, ε},
FOLLOW(A’)={c}, FIRST(B)={d},
FOLLOW(B)={#}, FIRST(S)={a},
FOLLOW(S)={#},对于每个非终结符的各个产生式的FIRST集两两不相交；③ 对于A’，FIRST（A）∩FOLLOW（A）=Φ。综上所述，原文法可以改造成LL（1）文法。 五、（20分）原文法不是LL（1）文法，故不能直接使用LL（1）分析法进行分析。 步骤如下：1、拓广文法：①E’→E
②E→eAf③E→eBg
④A→aA⑤A→a
⑥B→Bb⑦B→a
（2分） 2、项目集规范族：第9页共6页
1E’→E.0E’→.EE→.eAfE→.eBg2eE→e.AfA→.aAA→.aE→e.BgB→.BbB→.a3E→eA.f4aA→a.AA→a.A→.aAA→.aB→B.b5BE→eB.gB→B.bf6E→eAf.7A→aA.8A→a.AA→a.A→.aAA→.a9E→eBg.10B→Bb.AAaagb（6分）由此项目集规范族可判断，原文法非LR（0）文法，故不能直接使用LR（0）分析法进行分析。因此，使用SLR（1）分析法分析原文法。3、构造SLR（1）分析表如下：
FOLLOW(A)={f}；FOLLOW(B)={b,g}；FOLLOW(E)={#}。
（6分）4、分析输入串eaaaf如下：第10页共6页
六、（25分） 1、步骤：（1）拓广文法：①E’→E
②E→i(1)&i(2)
③E→AE(1)④A→B∨⑤B→i
（2分）（2）项目集规范族：
1E’→E.E’→.EE→.i(1)&i(2)26E→.AE(1)i&E→i(1)&.i(2)i8E→i(1)&i.(2)A→.B∨B→i.B→.i3A7E→A.E(1)EE→AE.(1) 4BE→.i(1)&i(2)→B.∨E→.AE(1)iA2A→.B∨5∨B→.iB4A→B∨.A
（3）SLR（1）分析表如下：FOLLOW(E)={#}；FOLLOW(A)={i}；FOLLOW(B)={ ∨}。第11页共6页
6分）6分） （（2、分析输入串
a∨b&c如下：
整理：真出口为3； 假出口为4。
（2分）第12页共6页
6分）6分）（（
3、四元式：1、（Jnz,a,_,5）2、(J,_,_,3)3、(J&,b,c,5)4、(J,_,_,8)5、(*,m,n,T1)6、(:=,T1,_,I)7、(J,_,_,10)8、(+,m,n,T2)9、(:=,T2,_,I)10、??
编译原理E卷三、应用题（共50分）1、有文法G[E]：(16分)E → T + E｜T
T → T * F｜F
F → ( E )｜i(1)证明T+T*F+i是文法的一个句型。(3分)(2)构造型T+T*F+i的语法树。(3分)(3)指出该句型的所有短语、直接短语和句柄。(7分)(4)指出该句型的所有素短语和最左素短语。(3分)
2、将下列条件语句翻译成四元式的中间代码形式：(6分)if a&b or c&d and e&f then s1 else s2
3、有正规文法G[S]： (12分)S→aA|bB
B→aS|a(1)构造对应的正规式R，使得L(R)=L(G)。 (3分)(2)构造对应的NFA状态图，使得L(M)=L(R)。
(3分)(3)将所得NFA确定化为DFA。
(3分)(4)将所得DFA最小化。
4、对表达式文法G[E]：
(16分)E → E - T｜T
T → T ^ F｜F
F → ( E )｜a(1)判断G[E]是否为LL(1)文法。若不是，改造为LL(1)文法。(8分)(2)构造预测分析表，并对输入串w=a-a^a#进行预测分析。(8分)三、应用题参考答案（共50分）1、（1）证明(3分)：因为存在推导序列：E=&T+E=&T+T+E=&T+T*F+E=&T+T*F+T =&T+T*F+F=&T+T*F+i，即有E=*&T+T*F+i成立，所以，T+T*F+i是文法的一个句型。（2）语法树（3分）：第13页共6页 3分）（（3）句型分析（7分）：该句型相对于E的短语：T+T*F+i、T*F+i和i ；相对于T的短语有：T*F和i，相对于F的短语有i。相对于T→T*F的直接短语：T*F,相对于F→i的直接短语：i。句柄：T*F。(4) 该句型的所有素短语：T*F和 I；T*F为最左素短语。(3分)
2、if a&b or c&d and e&f then s1 else s2生成的三地址代码/四元式序列如下：(6分)(1)
goto (7)(2)
goto (3)(3)
goto (5)(4)
goto (p+1)(5)
goto (7)(6)
goto (p+1)(7)
s1对应的四元式序列…(p) goto (q)(p+1) s2对应的四元式序列…(q)
3、(1)代入后有S的规则右部=a（bS|b）|b(aS|a)=ab（S|ε）|ba（S|ε）=（ab|ba）（S|ε）,故对应的正规式R=(ab|ba)(ab|ba)* 。 (3分)(2)对应的NFA状态图如下左图所示： (3分
)(3)将所得NFA确定化为DFA状态图如上右图所示： (3分)(4)将所得DFA最小化：首先根据是否终态划分为非终态集P1={S,A,B}和终态集P2={Z}；然后对P1根据a弧划分为P11={S},P12={A}，P13={B}。可见原DFA已是最小化的DFA。
4、 (1)计算G[E]的SELECT集如下：(2分)SELECT(E→ E C T )={(，a}
SELECT(E→ T )==,(，a}SELECT(T→ T ^ F)={(，a}
SELECT(T→ F)={(，a}SELECT(F → ( E ))={( }
SELECT(F → a)={a}由于SELECT(E→ E C T ) ∩ SELECT(E→ T )==,(，a-≠φ；SELECT(T→ T ^ F) ∩ SELECT(T→ F)={(，a-≠φ；SELECT (F →( E ))∩SELECT (F →a) = ,(-∩,a- =φ故 G[E]不是LL((1) 文法。(1分)对G[E]的E → E C T和T → T ^ F两条规则消除左递归后变为：(2分)E→T E’
E’→ C T E’|ε
T’→ ^ F T’｜ε
F→ ( E )｜a计算消除左递归后G[E]的SELECT集如下：(2分)SELECT(E→ T E’)=,(，a}
SELECT(E’→ C T E’)=,C }SELECT(E’→ε)=,#，)}
SELECT(T→ F T’)=,(，a}SELECT(T’→ ^ F T’)=, ^}
SELECT(T’→ε)=,C ，#，)}SELECT(F→( E ))=,(-
SELECT(F→a)=,a-第14页共6页
由于SELECT(E’→ C T E’)∩SELECT (E'→ε) =φSELECT (T'→
^ F T') ∩SELECT (T'→ε) =φSELECT (F →( E ))∩SELECT (F →a) = =φ故消除左递归后的G[E]是LL((1) 文法。(1分)（2）根据消除左递归后的G[E]的SELECT集构造预测分析表如下：(3分
对输入串w=a-a^a#的分析过程如下表所示（注意：规则右部以逆序入栈）：(5分)二、设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)三、写一个文法使其语言为L(G)={ anbmambn | m,n≥1}。(6分)四、对于文法G(E): (8分)E?T|E+TT?F|T*FF?(E)|i1. 写出句型(T*F+i)的最右推导并画出语法树。2. 写出上述句型的短语，直接短语、句柄和素短语。
第15页共6页
五、设文法G(S)：(12分)S?SiA|AA?A?B|BB?)A*|(1． 构造各非终结符的FIRSTVT和LASTVT集合；2． 构造优先关系表和优先函数。(12分)
六、设某语言的do-while语句的语法形式为 (9分)S ? do
E其语义解释为：
针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作.七、(8分)将语句if
(A&X) ? (B&0) then while C&0 do C:=C+D翻译成四元式。(8分)八、(10分) 设有基本块如下： 真 假
T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)画出DAG图；(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。九、(9分) 设已构造出文法G(S)：(1) S ? BB第16页共6页(2) B ? aB (3) B? b的LR分析表如下
假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。 E卷答案：
2答：构造相应的正规式：(0|1)*1(0|1)
(3分) NFA:
1第17页共6页
1 3答：文法G(S):S ? aSb | BB ? bBa | ba4答：1. (4分)E?T?F?(E) ?(E+T) ?(E+F)?(E+i) ?(T+i) ?(T*F+i)
(4分)短语：(T*F+i),
i直接短语：T*F, i句柄：T*F素短语：T*F, i5答：(6分)FIRSTVT(S)={ i，+，)，( }FIRSTVT(A)={ +，)，( }FIRSTVT(B)={ )，( }
LASTVT(S)={ i，+，*，( }LASTVT(A)={ +，*，( }LASTVT(B)={ *，( }
。6答：(1). 适合语法制导翻译的文法(3分)
G(S):R? do第18页共6页
E(2). (6分)R? do{
R.QUAD:=NXQ
U.QUAD:=R.QUAD;BACKPATCH(S.CHAIN, NXQ) }S?U E{
BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }答案二：(1) S ? do
M ?ε { M.QUAD := NXQ }
(6分)S ? do
E {BACKPATCH(S(1).CHAIN, M2.QUAD); BACKPATCH(E.TC, M1.QUAD);S.CHAIN:=E. FC}7答：100 (j&， A， X， 102)101 (j， -， -， 109)102 (j&， B， 0， 104)103 (j， -， -， 109)104 (j&， C， 0， 106)105 (j， -， -， 109)106 (+， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)109(控制结构3分，其他5分)
DAG如右图：(6
四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*49答：步骤 状态 符号 输入串0
0267 #Bab #7
0269 #BaB #8
编译原理F卷四、问答题：22、设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。⑴试写出描述 L 的正规表达式；⑵构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。23、给定文法 G[S] ：S → SaA|aA → AbS|b⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。⑵请构造该文法的 LR(0) 分析表。⑶什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？⑷什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？24、对下面的文法G：S-&aBc|bABA-&aAb|bB-&b|ε(1)计算这个文法的每个非终结符的FIRST和FOLLOW集合；（2）证明这个文法是LL（1）的；第20页共6页（3）构造它的预测分析表。
25、设字母表∑={ a，b}，对于以aa或ab结尾的字的正规集。 （1）请写出描述该语言的正规式。（2）构造该正规式所对应的NFA（画出转换图）； （3）将所求的NFA确定化（画出DFA的转换图）； （4）将所求出的DFA最小化（画出极小化后的转换图）；
26、设文法G为 S ? EE? TE | ε
T ? eT | t(1)证明它是LR(1)文法；
(2)构造它的LR(1)分析表；(3)给出输入符号串etet的分析过程。
27、对文法G(S)：S ?
? a(1) 消除该文法的左递归和提取左公因子； (2) 构造各非终结符的FIRST和FOLLOW集合；(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。 F答案：22答：（ 1 ）正规表达式： 1(0|1) * 00
（ 2 ）第一步：将正规表达式转换为 NDFA
第二步：将 NDFA 确定化为 DFA ：
DFA 的状态转换图第21页共6页
第三步：给出 DFA 的形式化描述DFA M = （ { q 0 , q 1 , q 2 , q 3 , q 4 }, {0,1}, t, q 0 , { q 4 } ） t 的定义见 M 的状态转换表。 2323答： （1）拓广文法：G[S′]: S′→ S ⑴
S → SaA ⑵
A → AbS ⑷
A → b ⑸该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA ：
该文法的 LR(0) 分析表：
⑵⑶ LR(0) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突第22页共6页
状态。该文法不是 LR(0) 文法，因为存在冲突状态： I 4 和 I 7。⑷ SLR(1) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态，冲突可用 FOLLOW 集解决。该文法不是 SLR(1) 文法。因为 FOLLOW(S)={a,b,#} ，所以无法解决冲突。24答：（1）first(B)={b, ε},first(A)={a,b},first(S)={a,b}Follow(S)={#},follow(A)={b,#},follow(B)={c,#}(2)因为只有FIRST(B)含有? , 所以只考虑：FOLLOW(B)=FIRST(c) ?FOLLOW(S)={c,
#}∴该文法的LL(1)表(3)
25答： （1）正则式为：（a|b）*a(a|b）。
（1分）（2）由正则式得到的转换系统如下图：
（3）由子集法构造的DFA如下图：
（4）DFA最小化如下图：
26答：(1)拓广文法G’：（1分）(0) S' ?S
(2) E? TE第23页共6页(3) E ?ε
(4) T ? eT
FIRST(A) = {ε, e,t}FIRST(B) = {e, t}构造的DFA如下
由项目集规范族看出，不存在冲突动作。 ∴该文法是LR(1)文法。(2)LR(1)分析表
(3)输入串abab的分析过程为：第24页共6页
27答：（1）消除左递归S ?
? a T S’ S’ ?
? a 提取左公因子S ?
? a T S’ S’ ?
? a T’ T’ ?
(2) 各非终结符的FIRST和FOLLOW集合：FIRST(S)={a，?}
FIRST(S')={ ?，ε}
FIRST(T)={ ? } FIRST(T')={ ?，ε}
FOLLOW(S)={#}
FOLLOW(S')={#} FOLLOW(T)={?，#}
FOLLOW(T')={?，#}
编译原理G卷六、问答题1、给出上下文无关文法的定义 2、文法G[S]：S→aSPQ|abQ
cQ→cc第25页共6页
（1）它是Chomsky哪一型文法？（2）它生成的语言是什么？3、按指定类型，给出语言的文法。L={aibj|j＞i≥1}的上下文无关文法。4、有文法G：S→aAcB|BdA→AaB|cB→bScA|b（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）写出句子acabcbbdcc的最左推导过程。S→（L）|aS|a
L→L, S|S5、对于文法G[S]：（1）画出句型（S,（a））的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。6、考虑文法G[T]：
T→T*F|F F→F↑P|P P→（T）|i 证明T*P↑（T*FG卷答案：1[解答]一个上下文无关文法G是一个四元式（VT,VN,S, P），其中：●VT是一个非空有限集，它的每个元素称为终结符号；●VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=Φ；●S是一个非终结符号，称为开始符号；●P是一个产生式集合（有限），每个产生式的形式是P→α，其中，P∈VN，α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。2[解答]（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到：S?abQ?abcS?aSPQ?aabQPQ?aabPQQ?aabbQQ?aabbcQ?aabbccS?aSPQ?aaSPQPQ?aaabQPQPQ?aaabPQQPQ?aaabPQPQQ?aaaPPQQQ?aaabbPqqq?aaabbQQQ?aaabbbcQQ?aaabbbccQ?aaabbbccc??于是得到文法G[S]生成的语言L={anbncn|n≥1}
3【解答】（1）由L={aibj|j＞i≥1}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法G[S]为：G[S]：S→aSb|Sb|b4【解答】（1）分别画出对应两句型的语法树，如图2-8-2所示第26页共6页
语法树（2）句子acabcbbdcc的最左推导如下：S?aAcB?aAaBcB?acaBcB?acabcB?acabcbScA?acabcbBdcA
?acabcbbdcA?acabcbbdcc
5【解答】（1）句型（S,（a）
（2）由图2-8-3可知：①短语：S、a、(a)、S,(a)、(S,(a))②直接短语：a、S； ③句柄：S；④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；
因此素短语为a。 6【解答】首先构造T*P↑（T*F）的语法树如图2-8-4所示。
由图2-8-4可知，T*P↑（T*F）是文法G[T]的一个句型。 直接短语有两个，即P和T*F；句柄为P。H卷 四、综合题1、对于文法G[S]： S→AS|b
（1）列出所有LR（0）项目（2）列出构成文法LR（0）项目集规范族。 解答：第27页共6页
首先将文法G拓广为G[S′]：S′→SS→AS|bA→SA|a（1）文法G[S′]的LR（0）项目是：1、S′→?S
5、S→AS?2、S′→S?
6、S→?b3、S→?AS
7、S→b?4、S→A?S
10、A→SA? 11、A→?a 12、A→a?
（2）列出构成文法LR（0）项目集规范族。用ε-CLOSURE（闭包）办法构造文法G′的LR（0）项目集规范族如下：I0：1、S′→?S
I3： 9、A→S?A
I6：12、A→a?3、S→?AS
I7：7、S→b?8、A→?SA
3、S→?AS11、A→?a
6、S→?b6、S→?b
I1：2、S′→S?
I4：10、A→SA?9、A→S?A
4、S→A?S8、A→?SA
3、S→?AS11、A→?a
6、S→?b3、S→?AS
8、A→?SA6、S→?b
11、A→?aI2：4、S→A?S
I5： 5、S→AS?3、S→?AS
9、A→S?A6、S→?b
8、A→?SA8、A→?SA
11、A→?a11、A→?a
3、S→?AS6、S→?b注意：I1中的S′→S?和A→?SA是由状态I0中的1和3读入一个S字符后得到的下一个项目；，而I4中的A→SA和A→A?S则是由I3中的9和3读入一个A字符后得到的下一个项目；I5中的S→AS?和A→S?A 则是由I4中的4和8读入一个S字符后得到的下一个项目。状态全体构成了文法G′的LR（0）规范族。
编译原理I卷四、综合题1、给出下列表达式的逆波兰表示（后缀式）：① a*(-b+c)② (A∨B)∧(C∨┑D∧E)2、写出算术表达式：A+B*(C-D)+E/(C-D)↑N的①四元式序列；②三元式序列；③间接三元式序列5. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。6已知文法A-&aAd|aAb| ε判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。 答案：解答1、① ab@c+*;② AB∨CD┑E∧∨∧第28页共6页2、
①表达式的四元式序列：
②表达式的三元式序列
③间接三元式序列 5证明：
（1）(-,C,D,T1)
（1）(-,C,D)
（1）(-,C,D)
由文法S→aSb|Sb|b G[S] ：（2）(*,B,T1，对句子,T2)
对应的两棵语法树为： （2）(*,B,(1))
（2）(*,B,(1))
（3）(+,A,T2,T3) （4）(-,C,D,T4)（3）(+,A,(2))
（3）(+,A,(2)) （4）(-,C,D)
⑷ (↑,(1),N) （5）(↑,(4),N)
⑹ (/,E,T5,T6)
(+,(3),(5))⑺
(+,T3,T6,T7)
(+,(3),(6))
⑹（5）(↑,T4,N,T5)
因此，文法G[S]为二义文法。
6解：增加一个非终结符S/后，产生原文法的增广文法有：
S'-&AA-&aAd|aAb|ε下面构造它的LR(0)项
目集规范族为：
第29页共6页
从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。其SLR(1)分析表为：
对输入串ab#给出分析过程为：
编译原理J卷
五、计算题：1.设文法G(S):S→^ | a | (T)T→T,S | S⑴ 消除左递归；⑵ 构造相应的FIRST和FOLLOW集合；⑶ 构造预测分析表2.语句 if E then S(1) 改写文法，使之适合语法制导翻译；(2) 写出改写后产生式的语义动作。3.设文法G（S）：S→(T) | aT→T+S | S(1）计算FIRSTVT 和LASTVT；（2）构造优先关系表。4.设某语言的for语句的形式为(1)(2)for i:＝E to E do S其语义解释为第30页共6页i:＝E(2)LIMIT:＝Eagain: if i＜＝LIMIT thenBeginS;i:＝i＋1goto againE（1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。5.把语句while a&10 doif c&0 then a:=a+1else a:=a*3-1;翻译成四元式序列。6.设有基本块D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假设基本块出口时只有M还被引用，请写出优化后的四元序列。7.已知文法G(S)S→a | ^ | (T)T→T,S | S(1) 给出句子(a,(a,a))的最左推导；(2) 给出句型((T,S),a)的短语, 直接短语，句柄。8.对于 C 语言do S while E语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。9.已知文法G(S)S→aAcBeA→Ab| bB→d(1)给出句子abbcde的最左推导及画出语法树；(2)给出句型aAbcde的短语、素短语。10.设文法G(S):S→(T) | aS | aT→T,S | S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。11.把语句 (1)第31页共6页if X&0 ∨ Y&0then while X&0 do X:=A*3else Y:=B+3;翻译成四元式序列。12.已知文法G(S)E→E+T | TT→T*F| FF→(E)| i(1) 给出句型 (i+i)*i+i的最左推导及画出语法树；(2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。13.设文法G（S）：S→T | S∨TT→U |T∧UU→i |-U（1）计算FIRSTVT 和LASTVT；（2）构造优先关系表。
第32页共6页答案：1(1)消除左递，文法变为G’[S]：S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε此文法无左公共左因子。(2)构造相应的FIRST和FOLLOW集合：
FIRST(S)={a, ^, (}， FOLLOW(S)={#,
,, )} FIRST(T)={a, ^, (} ，FOLLOW(T)={}} FIRST(T’)={,, ε} ，FOLLOW(F)={)}
C→if E then(1)S→CS
(2)C→if E then
{BACK(E.TC, NXQ); C.chain:=E.FC}(1)
(1)S→CS{S.chain:=MERG(C.Chain, S. Chain)} 3.
FIRSTVT(S)={a,
FIRSTVT(T)={+,
LASTVT(S)={a,
) }LASTVT(T)={+,
)}(1)S→FS(1)(2)(2) F→for i:=E to E do(1){GEN(:=, E.place, _, entry(i)); F.place:=entry(i); LIMIT:=N(2)GEN(:=, E.place, _, LIMIT); Q:=NXQ; F.QUAD:=q;GEN(j≤, entry(i), LIMIT, q+2) F.chain:=NXQ; GEN(j, _, _, 0)}(1)S→FS(1){BACKPATCH(S.chain, NXQ);
GEN(+, F.place, 1, F.place);
GEN(j, _, _, F.QUAD);
S.chain:=F.chain }5. (1)
(j&, a, ‘10’, (3))第33页共6页(2) (j,
_, (12))(3) (j&, c, ‘0’,
(5))(4) (j,
_, (8))(5) (+, a, ‘1’, T1))(6) (:=, T1, _, a)(7) (j, _,
_, (1))(8) (*, a, ‘13’, T2)(9) (-, T2, ‘1’, T3)(10) (:=, T3, _, a)(11) (j, _, _,
(1))6.优化后的四元序列D:=A-CE:=A*CF:=D*EM:=F+207. 最左推导S=(T)=&(T,S)=&(S,S)=&(a,S)=&(a,(T))=&(a,(T,S))=&(a,(S,S))=&(a,(a,S))=&(a,(a,a))短语((T,S),a)(T,S),a(T,S)T,Sa直接短语T,Sa句柄T,S8.(1)S→do M1 S1while M2 EM→ε(2)M→ε
{M.quad=}S→do M1 S1while M2 E
{backpatch(s1.nextlist, M2.quad);backpatch(E.truelist, M1.quad);S.nextlist=E.}9.(1) S=&aAcBe=&AAbcBe=&abbcBe=&abbcde(2) 短语: aAbcde, Ab, d素短语: Ab, d10.(1) S →(L) | aS’S’→S |εL→SL’L’→,SL’ |ε(2)
FIRST(S)={a, (}
FIRST(S’)={a, (, ε}FIRST(L)={a, (}
FIRST(L’)={,, ε}FOLLOW(S)={,, ), #}
FOLLOW(S’)={,, ), #}FOLLOW(L)={ )}
FOLLOW(L’)={ )}第34页共6页(3)
(j&, X, 0,
(j&, Y, 0,
(j&0, X, 0, (7))(6)
(:=, T2, _, Y)12.(1) E=&E+T=&T+T=&T*F+T=&F*F+T=&(E)*F+T=&(E+T)*F+T=&(T+T)*F+T
=&(F+T)*F+T=&(i+T)*F+T=&(i+F)*F+T=&(i+i)*F+T=&(i+i)*i+T
=&(i+i)*i+F=&(i+i)*i+i(2) 短语 i, F,
(E+T)*i+F素短语 i,
E+T最左素短语 E+T13.(1)
FIRSTVT(S)={∨,
i, - }FIRSTVT(T)={∧,
i, -}FIRSTVT(U)={i, -}LASTVT(S)={∨,
i, - }LASTVT(T)={∧,
i, -}LASTVT(U)={i, -}(2)
编译原理K卷四、对下面的文法G：S→a | b | （T）T→T，S | S(1) 消去文法的左递归，得到等价的文法G2；(2) 判断文法G2是否LL（1）文法，如果是，给出其预测分析表。（15） G2：S→a | b | （T） 第35页共6页T→ ST’T’→，S T’ | εG2是LL（1）文法。五、设有文法G[A]：A→BCc | gDBB→bCDE |εC→DaB | caD→dD |εE→gAf | c(1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集；(2) 试判断该文法是否为LL（1）文法。（15）是LL（1）文法。
六、对表达式文法G：E → E+T | TT → T*F | FF → (E) | I（1）造各非终结符的FIRSTVT和LASTVT集合；（2）构造文法的算符优先关系表。（15）
七、有定义二进制整数的文法如下：L →LB
1构造一个翻译模式，计算该二进制数的值（十进制的值）。（15）K答案
6答：第36页共6页7答：引入L、B的综合属性val，翻译模式为：
{print(L.val)}L →L1B
{L.val= L1.val*2+B.val} L →B
{L.val= B.val} B →0
{B.val=0} B →1
{B.val=1}编译原理L卷五、综合应用题(共3小题，每小题10分，共30分)1．证明下述文法G：S?aSbS|aS|d是二义性文法。2．对于文法G[S]：S?AB，A?Aa|bB，B?a|Sb求句型baSb的全部短语、直接短语和句柄？S 句型baSb的语法树如图五(2)所示。Bb B
3．设有非确定的有自限动机NFA
，B，C}，{0，1}，?，{A}，{C})，其中：? (C，1)={C}。请画出状态转换距阵和状态转换? (A，0)={C}
? (A，1)={A，B}
? (B，图。答案：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个 文法是二义性文法。句子aadbd有两棵语法树。如下图：37页共6
由此可知，S?aSbS|aS|d定义的文法是二义性文法。
状态转换图为
编译原理M卷三 有穷自动机M接受字母表?＝{0,1}上所有满足下述条件的串：每个1都有0直接跟在右边。构造一个最小的DFA M及和M等价的正规式。
四 证明正规式(ab)*a 与正规式a(ba)*等价 （用构造他们的最小的DFA方法）。 五 写一个文法，使其语言是：L ＝ { 1n0m1m0n | m,n≥0 }六 对文法G[S]
S → aSb | PP → bPc | bQcQ → Qa | a(1) 它是否是算符优先文法？请构造算符优先关系表(2) 文法G[S]消除左递归、提取左公因子后是否是LL（1）文法？请证实。七 已知文法G为:（0） S′→ S（1） S → aAd（2） S → bAc第38页共6页（3） S → aec（4） S → bed（5） A → e试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。八 已知源程序如下：prod:=0;i:=1;while i≤20 dobeginprod:=prod+a[i]*b[i];i:=i+1试按语法制导翻译法将源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。九 设有以下程序段procedure P(x,y,z)beginY:=y*3;Z:=X+z;begina:=5; b:=2;p(a*b,a,a);print(a);end若参数传递的方法分别为（1）传值、（2）传地址、（3）传名，试问结果分别什么？
答案：第39页共6页
文法G：S → 1S0 | AA → 0A1 | ε
6【答案】1.求出G[S]的FIRSTVT集和LASTVT集：FIERSTVT（S）={a,b}
LASTBVT（S）={b,c}FIERSTVT(P)={b}
LASTBVT（P）={c}FIERSTVT(Q)={a}
LASTBVT（Q）={a}，所以该文法不是算符优先文法。2. 消除左递归和提取左公因子后的文法为：S → aSb | PP → bP’P’→ Pc |QcQ → aQ’Q’→ aQ’|ε求具有相同左部的两个产生式的Select集的交集：Select(S→aSb)∩Select(S→P) = {a}∩First(P) = {a}∩{b} = ФSelect(P’→Pc)∩Select(P’→Qc) = First(P)∩First(Q)={b}∩{a}= ФSelect(Q’→aQ’)∩Select(Q’→ε) = {a}∩Follow(Q) = {a}∩{c} = Ф所以修改后的文法是LL（1）文法。
7【答案：】
九【答案】
（2）传地址
45编译原理N卷1. 设有如下文法G（S），试消除其左递归。第41页共6页G（S）：S―&Ac|cA―&Bb|bB―&Sa|a2. 试构造与下面G（S）等价的无左递归的文法。G（S）：S―&Sa|Nb|cN―&Sd|Ne|f3. 设有文法G（S）：S―&aBc|bABA―&aAb|bB―&b|ε①求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。
②构造LL(1)分析表，并分析符号串baabbb是否是。4. 已知文法G(S)：S―&a|(T)T―&T,S|S①给出句子((a,a),a)的最左推导并画出语法树；②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。5. 设文法Ｇ（Ｓ）为：Ｓ―＞ａ｜ａＡｂ
Ｓ―＞ｂ｜ｂＢａＡ―＞１Ａ０｜ε
Ｂ―＞１Ｂ０｜ε求①ＬＲ（０）项目集族；②构造识别文法Ｇ（Ｅ）的ＤＦＡ；
6. 设文法Ｇ（Ｓ）为：Ｓ―＞ａ｜ａＡｂ
Ｓ―＞ｂ｜ｂＢａＡ―＞１Ａ０｜ε
Ｂ―＞１Ｂ０｜ε求①ＬＲ（０）项目集族；②构造识别文法Ｇ（Ｅ）的ＤＦＡ；
N答案：1解：S→abcS′|bcS′|cS′,
S′→abcS′|?
2解：S→fN′bS′|cS′, S′→aS′|dN′bS′|?, N′→eN′|?
3解：（1）FIRST(aBc)={a}, FIRST(bAB)={b} FIRST(aAb)={a}, A→b: FIRST(A→b)={b}, B→b: FIRST(b) = {b}, FIRST(ε)={ε}FOLLOW(A)={b, #}, FOOLOW(B)={c, #}SELECT(S→aBc)={a}, SELECT(S→bAB) ={b}, SELECT(A→aAb)={a}, SELECT(A→b)={b}, SELECT(B→b)={b}, SELECT(B→?)={c, #}因此，所得的LL(1)分析表如表A-4所示。
第42页共6页（2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。
识别串baabbb的过程
4解：（1）FIRSTVT(S)={(, i}，FIRSTVT(D) ={i}，FIRSTVT(R)={;, (, i}，FIRSTVT(P)={i, (}，LASTVT(S)={)}，LASTVT(D)={i}，LASTVT(R) = {;, ), i}，LASTVT(P)={i, )}（2）算符优先矩阵，如表A-5所示。
5解：（1）最左推导：S?(T)?(a,S)?(a,(T))?(a,(T,S))?(a,(S,S))?(a,(a, S))?(a,(a,a))语法树：如图A-16所示。(T,S)?(S,S)第43页共6页
(a,(a,a))的语法树 （2）句型(T, a, (T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。短语：a || T,a || (T) || T , a , (T) || (T , a , (T))直接短语：a || (T)素短语：a || (T)最左素短语：a句柄：a活前缀：? || ( || (T || (T , || (T , aS(
(T,a,(T))的语法树
6解：（1）、（2）LR(0)项目集族和识别活前缀的DFA，如图A-19所示。图A-19
LR(0)第44页共6页
项目集族和DFA编译原理O卷三、应用题（共50分）1、有文法G[S]：(12分)S→aAS|a
A→SbA|SS|ba(1)证明aabbaa是文法的一个句子。(3分)
(2)构造句子aabbaa的语法树。(3分)(3)指出该句子的所有短语、直接短语和句柄。(6分)2、对文法G[E']：(15分)E'→#E#
E→E+T|T T→T*F|F
(1)计算G[E']的FIRSTVT和LASTVT。(5分)(2)构造G[E']的算符优先关系表,并说明G[E']是否为算符优先文法。(5分)
(3)给出输入串w=i+i# 的算符优先分析过程。(5分)3、对以下基本块：（8分）A：=5
X1：=T1+T2
X2：=T0*T3
（1）画出基本块的DAG图。(3分)（2）根据DAG结点原来的构造顺序重写四元式。(2分)（3）假设基本块出口后只有X1，X2还被引用，试写出优化后的四元式序列。(3分)4、对文法G[S’]： (15分)0)S’→S
6)B →b(1)试构造G[S’]的LR(0)项目集规范族DFA。(4分)(2)试构造G[S’]的SLR(1)分析表，并判断它是否为SLR(1)文法。(4分)
(3)试用SLR（1）方法分析输入串aae#。(4分)(4)G[S’]是否为LR(0)、LR(1)和LALR(1)文法？为什么？(3分)第45页共6页
答案：三、应用题参考答案（共50分）1、（1）证明(3分)：因为存在推导序列S=&aAS=&aSbAS=&aabAS=&aabbaS=&aabbaa，即有S=*&aabbaa成立，所以，是文法的一个句子。（2）语法树（3分）：
（3）句型分析（6分）：将句型改写为a1a2b1b2a3a4，则：该句型相对于S的短语：a1a2b1b2a3a4和 a4；相对于A的短语：
a2b1b2a3和b2a3；对于S→a的直接短语：a2，a4；相对于A→ba的直接短语：b2a3；句柄：a2。
2、(1)计算G[E']的FIRSTVT和LASTVT集如下：(5分
)(2)构造G[E']的算符优先关系表如下：(4分
由上表可知G[E']是算符优先文法(1分)。 (3)输入串w=i+i# 的算符优先分析过程如下：(5分)
3、（1）基本块的DAG图如下：(3分
)（2）根据DAG结点原来的构造顺序重写四元式如下：(2分)第46页共6页A：=5
B：=R+rT0：=A+B
X1：=T0+T1
X2：=T0*T1（3）假设基本块出口后只有X1，X2还被引用，则通过重新命名临时变量的基本块保结构变换，可将基本块的四元式代码进一步优化为：(3分)C：=R+r
4、0)S’→S
3)A →aAe4)A →a
6)B →b(1)G[S’]的LR(0)项目集规范族DFA如下：(4分)
(2)由于，得G[S’]的SLR(1)分析表如下：(3分
由上左表可知G[S’]是SLR(1)文法（1分）。(3)用SLR（1）方法分析输入串aae#过程如上右表所示：(4分)(4)由于G[S’]LR(0)项目集规范族DFA中I4、T5中都包含有移进―归约冲突，所以G[S’]不是LR(0)文法，由于G[S’]是SLR(1)文法故一定是LR(1)和LALR(1)文法。(3分)编译原理P卷一、综合题（30分）1、 构造下面文法的LL(1)分析表。S→aBc|bABA→aAb | bB→b |ε构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子。
2、 设有文法G（S）：S→CC
(3)求1）拓广文法，2） 文法的转移图，3） 构造规范LR语法分析表，第47页共6页4） 构造LALR语法分析表。答案： 1解：First(S)={a,b}
First(A)={a,b}
First(B)={b, ε}
2解答：1） 拓广文法S’ →SS→CC
2）第48页共6页
第49页共6页
3）文法的规范LR语法分析表
4)LALR语法分析表
编译原理Q卷五、请给对文法G[S]进行改写成LL（1）文法，并给出改写后文法的预测分析表，要求计算出改写后文法各非终极符的FIRST和FOLLOW集合。（15分）S → S*aA | aA| *aA
A→ +aA | +a六、请构造出文法G[S]识别文法活前缀的有限自动机，请确定是否是SLR（1）第50页共6页文法，如果是，则构造出其LR分析表。（12分）A→aAd |aAb |ε七、为文法S ? ( L ) | aL ? L , S | S写一个属性翻译文法，它输出文法中a的个数。（10分）
八、考虑下面的三地址语句序列，完成下列任务。（1）在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。（2分）（2）画出该代码的控制流图，每个基本块就用（1）的序号表示。（3分）（3）若有循环的话，列出构成每个循环的结点,并指出循环的入口结点。（6分）
答案：5答：改写文法如下：S?*aAS’ | aAS’S’?*AS’ | ?A?+aA’A’?A | ?
6答：拓广文法（
1）S?A （2）A?aAd
（4）A?ε第51页共6页
7解：S’?S
{printf(S.a)}S ? ( L ) {S.a=L.a}S? a
{S.a=1}L ? L , S {L.a=L1.a+S.a}L? S
8解：（1）
L1: e := b
（2）L2: c := 3
b := 4（3）
（5）L4: g := g + 1h := 8（6）L5: h := 9
（7）goto L2
（3）回边3?4，结点5、7、3和4构成一个循环，其中4是入口结点。编译原理R卷1．（20分）写出字母表? = {a, b}上语言L = {w | w中a的个数是偶数}的正规式，并画出接受该语言的最简DFA。2．（15分）考虑下面的表达式文法，它包括数组访问、加和赋值：E ? E[E] | E + E | E = E | (E) | id该文法是二义的。请写一个接受同样语言的LR(1)文法，其优先级从高到低依次是数组访问、加和赋值，并且加运算是左结合，赋值是右结合。3．（10分）下面是产生字母表? = { 0, 1, 2}上数字串的一个文法：S ? D S D | 2D ? 0 | 1写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和从右向左读都一样时，称它为回文数）。第52页共6页
1．语言L的正规式是：
(a b*a | b)* 或 b*(a b*a b*)*
接受该语言的最简DFA是：
3．E ? T = E | T T ? T + F | F F ? F[E] | (E) | id S? ? S
S ? D1 S1 D2 S ? 2
print(S.val)S.val = (D1.val = D2.val) and S1.val
S.val = true
编译原理S卷 1．（15分）(a) 字母表? = { ( , ) }上的语言{ ( ), (( )( )), ((( ))), ( )( )( )( )( )}是不是正规语言？为什么？ (b) 正规式 (0 | 1)* 和( (? | 0) 1* )*是否等价，说明理由。
2．（15分）接受文法
S ? A a | b A c | d c | b d a
A ? d活前缀的DFA见下图。请根据这个DFA来构造该文法的SLR(1)分析表，并说明该文法为什么不是SLR(1)文法。
3．（10分）现有字母表?={ a }，写一个和正规式a*等价的上下文无关文法，要求所写的文法第53页共6页既不是LR文法，也不是二义文法。
4．（20分）
(a) 下面的文法定义语言L = { anbncm | m, n ? 1}。写一个语法制导定义，其语义规则的作用是：对不属于语言L的子集L1= { anbncn | n ? 1}的句子，打印出错信息。
D ? a D b | a b
C ? C c | c
(b) 语句的文法如下：
S ? id := E | if E then S | while E do S | begin S ; S end | break写一个翻译方案，其语义动作的作用是：若发现break不是出现在循环语句中，及时报告错误。答案1． (a) 语言{ ( ), (( ) ( )), ((( ))), ( ) ( ) ( ) ( ) ( )}是正规语言，因为该语言只包括有限个句子，它可以用正规式定义如下：
( ) | (( )( )) | ((( ))) | ( ) ( ) ( ) ( ) ( )(b) 我们分析正规式( (? | 0) 1* )*表示的语言。可以看出正规式(? | 0) 1*描述的语言是集合{?, 1, 11, 111, …, 0, 01, 011, 0111, …-，它含长度为1的两个串0和1。那么，(0 | 1)* 所描述的语言是( (? | 0) 1* )* 所描述的语言的子集，因为(0 | 1)* 表示字母表{0, 1}上所有串的集合，因此( (? | 0) 1* )* 所描述的语言不可能再有更多的句子，因而也是表示字母表{0, 1}上所有串的集合。
2．分析表如下。因为有两处有移进－归约冲突，所以该文法不是SLR(1)文法。 注：
S ? a S a | a | ?4． (a) 语法制导的定义如下：
if D.length ? C.length then print (“error”)
D.length := 1
D ? a D1 b
D.length := D1.length + 1
C.length := 1第54页共6页C ? C1 c
C.length := C1.length + 1(b) 翻译方案如下：S? ? {S.loop := false}SS ? id := ES ? if E then {S1.loop := S.loop}S1S ? while E do {S1.loop := true}S1S ? begin {S1.loop := S.loop}S1 ; {S2.loop := S.loop}S2 endS ? break{if not S.loop then print(“error”) }
编译原理T卷1、（15分）(a) 用正规式表示字母表{a, b}上，a不会相邻的所有串。
b*(abb*)*(a| ?)(b) 画出一个最简的确定有限自动机，它接受所有大于101的二进制整数。2、（10分）构造下面文法的LL(1)分析表。S ? a B S | b A S | ?A ? b A A | aB ? a B B | b3、（10分）下面的文法是二义文法S ? EE ? while E do E | id := E | E + E | id | (E)请你为该语言重写一个规范的LR(1)文法，它为该语言中的各种运算体现通常的优先级和结合规则。不需要证明你的文法是规范LR(1)的。4、（10分）为下面文法写一个语法制导的定义，它完成一个句子的while-do最大嵌套层次的计算并输出这个计算结果。S ? EE ? while E do E | id := E | E + E | id | (E)8、（5分）把下面左边的文件file1.c提交给编译器，编译器没有报告任何错误。而把文件file2.c提交给编译器，错误报告如下：file2.c: 2: error: conflicting types for ‘func’file2.c: 1: error: previous declaration of ‘func’试分析原因。（在这两个文件中，第1行都是函数func的原型，第2行都是函数func的定义，函数体为空。）file1.c
file2.cint func(double);
int func(double);int func(f) {}
int func(float f) {}9、（5分）教材上第342页倒数第7行说“将C++语言中一个类的所有非静态属性构成一个C语言的结构类型，取类的名字作为结构类型的名字”。在这一章都学过后，你认为这句话需要修改吗？答案1、 (a) b*(abb*)*(a| ?)(b) 见下图。若不允许前缀的无效0，则去掉状态0上的0转换。
第55页共6页
2、 开始符号集合和后继
3、S ? EE ? while E do E | A A ? id := A | T T ? T + F | F F ? id | (E)4、 语法制导的定义如下：S ? E
print(S.loop);E ? while E1 do E2
E.loop := max(E1.loop, E2.loop) +1;E ? id := E
E.loop := E1. E ? E1 + E2
E.loop := max(E1.loop, E2.loop); E ? id
E.loop := 0; E ? (E1)
E.loop := E1.8、文件file1.c中，函数func的定义采用传统的方式，形式参数f的类型被提升到double。函数原型中该参数也声明成double类型，两者类型相同，因此没有错误。而在文件file2.c中，函数func的定义采用现在提倡的形式，形式参数的类型就是float，不会提升。它的类型和函数原型中声明的类型不相同，所以编译器会报告错误。 9、需要修改，增加虚方法表指针作为第一个域。编译原理U卷 1．（20分）写出字母表? = {a, b}上语言L = {w | w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。
2．（15分）说明下面的文法不是SLR(1)文法，并重写一个等价的SLR(1)文法。
S ? M a | b M c | d c | b d a
3．（10分）为下面的语言写一个无二义的文法：ML语言中用分号分隔语句的语句块，例如：
( ( s ) ; ( s ) ; s ) ; ( s ) 6．（15分）考虑下面的三地址语句序列：
if w &= x goto L2第56页共6页
7．（5分）如果（1）用编译命令cc test.c会报告有未定义的符号；（2）用编译命令cc test.c Clusr.a会得到可执行程序（Clusr.a表示连接库libusr.a）。 那么，用编译命令cc test.c Clusr.a Clusr.a是否会报告有多重定义的符号？请说明理由。答案1．语言L的正规式是：(a|b)*(aa|bb)接受该语言的最简DFA是：
goto L2 L1: goto L3 L2: c := 3
c := 6 L3: if y &= z goto L4
goto L5 L4: g := g + 1
goto L1 L5: h := 9 （1）在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。 （2）画出该代码的控制流图，每个基本块就用（1）的序号表示。 （3）若有循环的话，列出构成每个循环的结点。
S ? M a | b M c | d c | b d a
因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进?归约冲突。
等价的SLR(1)文法是S ? d a | b d c | d c | b d a
SL ? S | SL ; SS ? s | ( SL )6．（1）
（2）第57页共6页
L1: goto L3
（3）L2: c := 3
b := 4（4）L3: if y &= z goto L4
（6）L4: g := g + 1h := 8
（7）L5: h := 9
（8）（3）结点5、7和3构成一个循环，其中5是入口结点。
7．不会。连接时，第一次遇到库libusr.a便能解决所有的外部引用。这样在第二次遇到库libusr.a时什么东西也不会加入目标程序。
12.试写出VT＝{0，1}上下述集合的正则表达式：*⑴ 所有以1开始和结束的符号串。
1(0|1)1|1 ****⑵ 恰含有3个1的所有符号所组成的集合。
0101010⑶ 集合{01，1}。
01|1*⑷ 所有以111结束的符号串。
(0|1)111*⑴ 试写出非负整数集的正则表达式。
0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9) ⑵ 试写出以非5数字为头的所有非负整数集的正则表达式。*0|(1|2|3|4|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)
设VT＝{a,b}，试构造下述正则表达式的确定性有限状态自动机：*⑴ a(a|b)baa
⑵ (a|b)bbb**
编译原理V卷1. （6分）回答下列问题在存储管理中，为什么在活动记录内为临时变量分配空间？1）在符号表管理中，为什么将变量名保存在符号表中？2.
(8分)试消除下列文法中的左递归。S → SaA|Se|B
A → BbA|B
B → cSd|?
(15分)写出下列文法中各候选式的FIRST集和各非终结符的FOLLOW集,构造该文法的LL（1）分析表，并说明它是否为LL（1）文法。第58页共6页S → aA|BAA→ cB|?B → bB|?
4.（18分）给定文法G[S]S → L + L ｜LL → LB|BB → 0|1
(1) 构造拓广文法，按LR(0)分析的需要画出识别这个拓广文法的所有规范句型活前缀的DFA。(2) 求出这个文法的SLR（1）分析表5.（7分）写出能产生字母表{x,y}上的不含两个相邻的x,且不含两个相邻的ｙ的全体符号串的有限状态自动机。
6.（16分）设文法G[E]:E → RP|P
P → (E)|i
R → RP+| RP* |P+|P* 画出句子i+i*(i+i)的语法分析树，给出其最右推导和最左归约，并指出它的句柄。
7. (10分)下面是关于文法S → xYS|yXS|?X → yXX|xY → xYY|y的一个语法制导定义，S → xYS1 S.nx := Y.nx + S1.nx + 1S.ny := Y.ny + S1.nyS → yXS1
S.nx := X.nx + S1.nxS.ny := X.ny + S1.ny + 1S → ? S.nx := 0S.ny := 0X → yX1 X2
X.nx := X1.nx + X2.nxX.ny := X1.ny + X2.ny + 1X → x
X.nx := 1X.ny := 0Y → xY1 Y2
Y.nx := Y1.nx + Y2.nx + 1Y.ny := Y1.ny + Y2.nyY → y Y.nx := 0Y.ny := 1
(1) 请说明上述语法制导定义的作用是什么。(2) 按照此语法指导定义给出句子xxxyyyxy的语义分析过程或画出带注释的语法分析树．答案：1答：在栈式存储管理方式中，以活动记录的形式为一次过程调用（函数调用）中的局部数据提供存储空间，该活动记录随过程调用被分配，随过程调用的结束而释放；临时变量第59页共6页
通常用于保存表达式计算中的中间结果，在活动记录中为临时变量分配空间，可以保证该空间随过程调用被分配，随活动记录的释放被自动释放。答：符号表中将保存变量名及其各种属性，变量名将用于变量的识别、涉及变变量名与存储空间的绑定、以及类型、作用域、存储地址等各种变量属性的设置、获取等各种维护功能。2解：消除左递归
提取左因子
改写后的文法
S → SaA|Se|B
A → BbA | B
S → BS’→ S（aA | e ）| B
→ B ( bA | ?)
S’ → aA S’ | e S’ | ?
引进非终结符S’
引进非终结符A’
A →B A’S → BS’
A’ → bA | ?S’→（aA | e ）S’ | ?
A’ → bA | ?
B → cSd|?
3解：各候选式的FIRST集
(4分)FIRST（aA）={a}
FIRST（BA）={ b，c，? }
FIRST（cB）={c}FIRST（?）={?}
FIRST（bB）={ b }
FIRST（?）={?}
各非终结符的FOLLOW集
(4分)FOLLOW(S)= {#}
FOLLOW(A)= {#}
FOLLOW(B)= { c，#}
LL（1）分析表
A → ?B → bB
说明它是否为LL（1）文法 (2分)
判断1分，理由1分因为LL（1）分析表无冲突，所以该文法是LL（1）文法。
I2：{（1，1），（2，1），（3，1），（5，0），（6，0）} I3：{（4，1）} I4：{（5，1）} I5：{（6，1）} I6：{（1，2），（3，0），（4，0），（5，0），（6，0）} I7：{（3，2）}
FOLLOW(S)={#}FOLLOW(L)={0,1,+,#}
FOLLOW(B)={0,1,+,#}5解：第61页共6页x
(1)语法分析树：E
(PE)+iP+iPRi
（2）最右推导：E? RP ? R(E) ? R(RP) ? R(Ri) ? R(P+i) ? R(i+i) ? RP*(i+i) ? Ri*(i+i)
? P+i*(i+i) ? i+i*(i+i)最左归约：i+i*(i+i) ? P + i*(i+i)P+i*(i+i) ? Ri*(i+i)Ri*(i+i) ? RP*(i+i)RP*(i+i) ? R(i+i)R(i+i) ? R(P+i)R(P+i) ? R(Ri)R(Ri) ? R(RP)R(RP) ? R(E)R(E) ? RPRP ? E句子i+i*(i+i)的句柄为：i；
编译原理W卷例1
求表达式文法的语法符号的 FIRST 集和FOLLOW 集表达式文法:E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id第62页共6页
例2消除下述文法的左递归。S→Ac|c
例3已知文法Ｇ：S →
)（1）构造文法 Ｇ 的预测分析表。（2）若输入串为“（ａ，）”，请给出语法分析过程。例4给定文法Ｇ＝（｛ ｉ，ｄ，'('，')'｝，｛Ｅ，Ａ｝，Ｅ，Ｐ）其中
( Ｅ )(1)消除左递归；(2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集；(3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?。例5 if语句的原始文法S→ if E then S |if E then S else S |other存在左因子 if E then S,改写此文法消除左因子。.例6 构造简单算术表达式的分析器附加题
将左线性文法G=(VN,VT,P,S)转换成等价的有限状态自动机M=(Q,VT, δ,q0,F)的一种等价变换中认为“对产生式A→Ba∈P则M中用移动A∈δ(B，a)与之对应”，请问这种对应使用的是自顶向下的分析思想还是自底向上的分析思想？为什么？（本题第一问最高奖励3分，第二问最高奖励7分）答案
1解：FIRST(F)={(,id}FIRST(T)=FIRST(F)={(,id}FIRST(E)=FIRST(T)={(,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+}, FIRST(*)={*}FIRST( ( )={(}FIRST( ) )={)}FIRST(id)={id}FOLLOW(E) =
{ #, ) }FOLLOW(E')= FOLLOW( E ) = { #, ) }FOLLOW(T) = FIRST(E’)∪FOLLOW(E)∪FOLLOW(E’) = ,+,),#-FOLLOW(T')= FOLLOW(T)= {+,},#}FOLLOW(F) = FIRST(T’)∪FOLLOW(T)∪FOLLOW(T’) =,*,+,-,#-
2【解】先将间接左递归,变成直接左递归将B的定义代入A产生式得：A→Sab|ab|b，将A的定义代入S产生式得: S→Sabc|abc|bc|c采用引进新的非终结符的方法消除直接左递归：S→abcS’|bcS’|cS’S’→abcS’|ε第63页共6页删除“多余的”产生式：A→Sab|ab|b和B→Sa|a得到文法G[S]： S→abcS’|bcS’|cS’
S’→abcS’|ε
3【解】（１）1）求各非终结符的 FISRT 集和 FOLLOW 集：FIRST(S) = { (, a )FIRST(L) = { a }? FIRST(S) = { (, ), a }FOLLOW(S) = , ’,’, # -FOLLOW(L) =
FOLLOW(S) =, ’,’, # -2
4【解】(1)消除左递归后的文法为:E → iAＥ＇Ｅ＇→ ? | AＥ＇A → iA →ｄA → ( E )(2)各非终结符的 FISRT集和FOLLOW集FIRST( E ) =｛ｉ｝FIRST(Ｅ＇) = ｛ｉ, ｄ, (, ?)FIRST( A ) =｛ｉ, ｄ, ()FOLLOW( E ) =｛?, # ｝FOLLOW(Ｅ＇) =｛ ｝, # ｝FOLLOW( A ) =｛ｉ, ｄ, (, ), # ｝(3)改写后文法的预测分析表：
5【解】引进非终结符S’ S'→ε|else S第64页共6页提取左因子：S→ if E then SS’|other改写后的文法:S→ if E then SS’|otherS'→ε|else S
6【解】E的子程序(E→T(+T)*)procedure E;beginT;
Ｔ的过程调用
while lookhead='+' dobegin
当前符号等于＋时
match(‘+’);
处理终结符＋
Ｔ的过程调用
lookhead：当前符号T的子程序(T→F(*F)*)procedure T;beginF;
F的过程调用
while lookhead='*' thenbegin
当前符号等于＊时
match('*');
处理终结符＊
F的递归调用
F的子程序(F→(E)|id)procedure F;beginif lookhead='(' thenbegin
当前符号等于（
match('(');
处理终结符（
E的递归调用match(')');
处理终结符）
endelse if lookhead=id thenmatch(id)
处理终结符id
else error
主程序beginlookhead:= 调词法分析程序
E的过程调用 end服务子程序procedure match(t:token);beginif lookhead=t
thenlookhead:=nexttoken第65页共6页else error
出错处理程序7解：（1）该语法制导定义的作用是统计句子中的x和y的个数；（4分）（2）按照该语法制导定义对句子xxxyyyxy进行语义分析的结果为：
S.nx = 4；S.ny = 4；（6分）第66页共6页附加题解：使用的是自底向上的分析方法――归约。A∈δ(B，a)表示在状态B遇到输入a时，到达状态A，将状态看成是目前已经分析出来的中间结果，这样就相当于目前的分析已经得到了前缀B，加上a后相当于获得前缀A，也就是相当于B和紧接着的a可以归约成A，这与产生式A→Ba所表示出来的意义是相同的，所以产生式A→Ba∈P则M中用移动A∈δ(B，a)与之对应。（答到这里可以得4分）要得满分7分，必须根据上述思路给出“对于任意的左线性文法G，存在FA M与之等价：L(M)=L(G)”即：先构造与给定文法G=(VN,VT,P,S)等价的FA M，然后证明所构造的FA与所给的文法G等价。
编译原理X卷四、简述题(每题4分，共24分)1、考虑下面程序Var a：integer；Procedure S(X)；Var X：integer；Begina：＝a＋1；X：＝a＋XEnd；Begina：＝5；S(a)；Print(a)End．试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？2、画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。3、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。4、已知文法G(S)S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。5、何谓优化？按所涉及的程序范围可分为哪几级优化？6、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？五、计算题(共41分)1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。(5分)2、设文法G(S)：S→(L)|a S|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。3、While a＞0 ∨b＜0 doBeginX：＝X＋1；if a＞0 then a：＝a－1else b：＝b＋1End；翻译成四元式序列。(7分)4、已知文法G(E)E→T|E＋TT→F|T *FF→(E)|i(1)给出句型(T *F＋i)的最右推导及画出语法树；(2)给出句型(T *F＋i)的短语、素短语。(7分)第67页共6页5、设布尔表达式的文法为E →E(1)∨E(2)E →E(1)∧E(2)E →i假定它们将用于条件控制语句中，请(1)改写文法，使之适合进行语法制导翻译和实现回填；(2)写出改写后的短个产生式的语义动作。(6分)6、设有基本块T1：＝2T2：＝10/TT3：＝S－RT4：＝S＋RA：＝T2 *T4B：AT5：＝S＋RT6：＝T3 *T5B：＝T6(1)画出DAG图；(2)假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。(6分)
答案：四、简述题1、答：传名：a＝12
(2分)传值：a＝6
(2分)3、答：逆波兰表示：abc*＋ab＋/d－
(2分)三元式序列：① (*，b，c)② (＋，a，①)③ (＋，a，b)④ (/，②，③)⑤ (－，④，d)
(2分)4、答： 句型
句柄((a，a)，a)
a((S，a)，a)
S((T，a)，a)
a((T，S)，a)
T，S((S)，a)
5、 答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。
(2分)三种级别：局部优化、循环优化、全局优化。
(2分)6、 答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。(2分)应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指仅系统的的特点。
(2分)五、计算题1、解：文法G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8第68页共6页C→0|D
(5分)2、解:(1)S→(L)|aS'S'→S|εL→SL'L'→SL'|ε评分细则：消除左递归2分，提公共因子2分。(2)FIRST)S)＝{(，a}
FOLLOW(S)＝{#，，，)}
FIRST(S')＝{，a,ε-
FOLLOW(S')＝{#，，，)}FIRST(L)＝{(，a}
FOLLOW(L)＝{ )}FIRST(L')＝{，，ε-
FOLLOW(L'〕＝{ )}3、解：(1) (j＞，a，0，5)(2) (j，－，－，3)(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)评分细则：控制结构4分，其它3分。4、解：(1) 最右推导：ETF(E)(E＋T)(E＋F)(E＋i)(T＋i)(T*F＋i)(2) 短语：(T*F＋i)，T*F＋i，T*F，i
(2分)素短语：T*F,i
(1分)5、解：(1) E0→E(1)E→E0E(2)EA→E(1)E→EAE(2)E→i
(3分)(2) E→E(1){BACKPATCH(E(1)?FC，NXQ)；E0?TC：＝E(1)?TC}E→E0E(2){E?FC：＝E(2)?FC；E?TC：＝MERG(E0?TC，E(2)?TC)}EA→E(1){BACKPATCH(E(1)?TC，NXQ)；E0?FC：＝E(1)?FC}E→EAE(2){E?TC：＝E(2)?TC；E?FC：＝MERG(EA?FC，E(2)?FC}E→i{E?TC：＝NXQ；E?FC：＝NXQ＋1；GEN(jn2，entry(i)，－0)；GEN(j，－，－，0)
(3分)6、解：(1)DAG：(2) 优化后的四元式T3：＝S－RT4：＝S＋RA：＝5*T4B：＝T3＋T4
(3分)第69页共6页编译原理Y卷二、简答题（每小题 5 分，共 20 分）1 ． LL （ 1 ）分析法对文法有哪些要求？2 ．常见的存储分配策略有几种？它们都适合于什么性质的语言？3 ．常见循环优化都有哪些项目？4 ．什么是活动记录？它主要由哪些内容构成？三、（ 8 分）化简文法 G[S] ：S → ASe | BCaD | aD | ACA → Cb | DBSC → bC | dB → AcD → aD四、（ 12 分） 设 L í {a,b,c}* 是满足下述条件的符号串构成的语言：(1)若出现 a ，则其后至少紧跟两个 c ；(2)若出现 b ，其后至少紧跟一个 c 。试构造识别 L 的最小化的 DFA ，并给出描述 L 的正规表达式。五、（ 12 分） 已给文法 G[S] ： S → SaP | Sf | P P → qbP | q将 G[S] 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。六、（ 12 分） 给定文法 G[S] ： S → Aa|dAb|Bb|dBa A → c B → c构造文法 G[S] 的 LR （ 1 ）分析表。七、（ 8 分） 将下面的条件语句表示成逆波兰式和四元式序列：if a&b then x:=a+b*c else x:=b-a;八、（ 8 分） 给定基本块：A:=3*5B:=E+FC:=A+12D:=E+FA:=D+12C:=C+1E:=E+F假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。
参考答案：二、 1 ．对于 G 中的每个产生式 A →γ 1 | γ 2 | … | γ m ，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即FIRST( γ i ) ∩ FIRST( γ j )= φ（ 1 ≤ i ， j ≤ m ； i ≠ j ）（2）若有γ j ε，则其余候选式γ i 所能推出的符号串不能以 FOLLOW(A) 中的终结符号开始，即有FIRST( γ i ) ∩ FOLLOW(A)= φ（ i ≤ 1,2, … ,m ； i ≠ j ）2 ．有三种分配存储空间的方式：（ 1 ） 静态分配 若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的静态存储管理。 适合 静态管理 的语言应具备条件： 数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。 （ 2） 栈式分配 适用于允许递归调用的程序设计语言 ；（ 3 ） 堆式分配 对于允许程序在运行时为变量 动态申请和释放存储空间 的语言 ， 采用 堆式分配 是最有效的解决方案 。
3 ．不变运算外提；运算强度削弱；消除归纳变量；下标变量地址计算优化。4 ． 一个过程的一次执行所需信息的管理，是通过称为 活动记录 的连续存储块来实现的。活动记录的主要内容有：（ 1） 临时变量域 存放目标程序临时变量的值；（ 2 ）局部数据域 存放过程本次执行时的局部数据、简单变量及数组内情向量等；（ 3 ）机器状态域 保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等；（ 4 ）存取链 为访问其它活动记录中所存放的非局部数据所提供的链地址；（ 5 ）控制链 指向主调过程的活动记录；（ 6 ）实参 存放主调过程为被调用过程所提供的实参信息；（ 6 ）返回值 为主调过程存放被调过程的返回值第70页共6页三、化简后： S → ASe|AC A → Cb C → bC | d四、 DFA 如图所示。相应的正规式为 (c|acc|bc)* 。
五、改造后的文法： S → PS' S' → aPS'| fS' | e P → qP' P' → bP | e
各候选式的 FIRST 集，各非终结符的 FOLLOW 集为产生式
{#}S' → aPS'
{ e }P → qP'
{a,f,#}P' → bP
{a,f,#}→ e
{ e }LL(1) 分析表为
六、分析表如下图所示
七、（ 1 ）逆波兰式：
,其中， BLE 表示汪或等于时的转向指令； * … ] 表示标号。（ 2 ）四元式：(1) ( j&, a, b, (3))(2) ( j, , , (7) )(3) ( *, b, c, T1)(4) ( +, a, T1, T2)(5) ( :=, T2, , x)(6) ( j, , , (9))(7) ( -, b, a, T3)(8) ( :=, T3, , x)(9) ( … … )八、化简后的的四元式序列为A :=D+12E :=E+FC :=28第71页共6页
编译原理Z卷三、（10分）给定文法G=（{S,L}，{a，（，）}，,S→(L)|a L→L,S|S-，S）。给出句型”(S,(a))”的推导和语法树并指出此句型的所有短语、直接短语、句柄和素短语。四、（12分）设语言L是由奇数个a和偶数（可以是0）个b组成的符号串之集。1.构造识别L的DFA；2. 给出定义L的正规文法；五、（10分）将文法G[S]：S→*A A→AS|B+ B→Bi|i 改写为等价的LL(1)文法，并给出相应的LL(1)分析表。七、（8分）某语言算术表达式的文法定义为 E→E+E|i| if B then E else E其中，第三个候选式称为条件算术表达式，B为布尔表达式，then及else后的E均为算术表达式（即简单算术表达式或条件表达式），其语义为，当B为真时，表达式的值取then后的E的值，否则取else的E的值。假定所有表达式是整型的，试将下面关于条件算术表达式的属性翻译文法填写完全：
八、 （8分）给定PASCAL程序语句while a&b do if a&0 then a:=a-1 else a:=a+1;1. 将该语句翻译成逆波兰式；2. 给出编译程序扫描到then处及分号处时所得的四元式序列。九、 (7分)用DAG图对下面的基本块进行优化（假定出基本块后只有A、G、L是活跃的）： A=B*CD=B/CE=2*3F=E+2G=B*CK=E+FG=K*KL=B/C参考答案：三、 解：ST(L) T(L,S) T(L,(L)) T(L,(S)) T(L,(a)) T(S,(a))短语有：“a”,“(a)”,“S”，“S,(a)”，“（S,(a)）”。直接短语有：”S”，“a”句柄：“S”素短语：“a“语法树略。第72页共6页四、解：1。见图：2．S?aA|bB A?aS|bC|e B?bS|aC C?bA|aB五、解：B?iC C ?iC |e A?B+A’ A’ ?ASA’ | e S ? [AFirst(ASA’)=,i-, FOLLOW(A’)=, * +FIRST(iC)={i}, FOLLOW(C) ={ ]}可知文法满足LL(1)文法的条件。分析表：
八、 （8分）给定PASCAL程序语句while a&b do if a&0 then a:=a-1 else a:=a+1;1. 将该语句翻译成逆波兰式；2. 给出编译程序扫描到then处及分号处时所得的四元式序列。第73页共6页九、解：A=B*CG=196L=B/C
编译原理Aa卷一. （10分）改写以下文法，使其满足采用自顶向下分析方法的要求。S ? aXcY| YdX ? XaY| cY ? bYcX| b
二. (15分)考虑文法G[S]：S ? xSNy| NxN ? zN|ε1. 求出该文法的每个非终结符的FOLLOW集；2. 构造该文法的预测分析表。
(20分)符号串xxyyyx是如下文法G[S]的句子，S ? xB | yAA ? xS | yAA | xB ? yS | xBB | y(1)构造该句子的分析树；(2)写出生成该句子的最左推导；(3)写出生成该句子的规范归约过程；指出每步归约中的句柄。四. （20分）考虑简单赋值语句的文法G[S]：S ? id:= EE ? E + EE ? E * EE ? id（1） 试构造识别该文法所有规范句型活前缀的有限自动机。（2） 判断该文法是否为LR(0)文法（必须说明理由）。
五. （15分）考虑以下语法制导定义第74页共6页
（2） 给出处理该句子的结果（Print输出结果）。六（20分）设语言L是“能被5整除的十进制正整数”组成的集合，（1）试写出描述语言L的正规表达式；（2）画出识别语言L的状态转移图。答案：一解:(1)消除 X ? XaY|c 的左递归X ? cX’X’? aYX’| ε(2)提取 Y ? bYcX|b 的左因子Y ? bY’Y’ ? YcX|ε整理后，原文法变为S ? aXcY | YdX ? cX’X’? aYX’|ε
Y ? bZZ ? YcX|ε
二解:1、FIRST(S) = { x, z }FIRST(N) = { z, ε }FOLLOW(S) = { #, y, z }FOLLOW(N) = { x, y }
2、预测分析表
第75页共6页
3解:(1)语法分析树
x Sy y y(2) S?xB?xxBB?xxyB?xxyyS?xxyyyA?xxyyyx
(5分)(3) 规范归约
（9分）xxyyyx ? xxByyx
句柄为 yxxByyx ? xxByyA
句柄为 xxxByyA ? xxByS
句柄为 yAxxByS ? xxBB
句柄为 ySxxBB ? xB
句柄为 xBBxB ? S
句柄为 xB编译原理BB卷四、综合题1. 已知文法 G(E)E →T|E＋TT→F|T *FF →(E)|i(1)给出句型(T *F＋i)的最右推导；(2)给出句型(T *F＋i)的短语、简单短语、句柄、素短语、最左素短语。 解：
(1) 最右推导：E -&T-&F-&(E)-&(E ＋ T)-&(E ＋ F)-&(E ＋ i)-&(T＋i)-&(T*F＋i)(2) 短语：(T*F＋i) ，T*F＋i ，T*F，i简单短语：T*F,i句柄：T*F素短语：T*F,i最左素短语：T*F2. 构造正规式 1(0|1)*101 相应的 DFA 。解：先构造 NFA ：
第76页共6页
重新命名，令 AB 为 B、AC 为 C、ABY 为 D 得：第77页共6页
所以，可得 DFA 为：
3. 文法：S-&MH|aH -&LSo| εK -&dML| εL -&eHfM-&K|bLM判断 G 是否为 LL(1) 文法，如果是，构造 LL(1) 分析表。 解：各符号的 FIRST 集和 FOLLOW集为：
各产生式SELECT集为：
预测分析表
第78页共6页
由于预测分析表中无多重入口，所以可判定文法是 LL(1)的。4. 对下面的文法 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)U{ε}={(,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')UFOLLOW(E)={+,),#};//不包含ε FOLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#}; FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#};//不包含ε FOLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F')UFOLLOW(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]的预测分析表如下：第79页共6页
5.已知文法 G[S] 为：S-&a|^|(T)T-& T,S|S(1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。(2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否未算符优先文法。(3) 给出输入串 (a,a)# 的算符优先分析过程。解：（1）各符号的 FIRSTVT 和 LASTVT：
（2）算符优先关系表：（3）句子(a,a)#分析过程如下：
6.已知文法为：S-&a|^|(T)T-&T,S|S构造它的 LR(0)分析表。解：加入非终结符 S' ，方法的增广文法为：S'-&SS-&aS-&^第80页共6页
S-&(T) T -&T,S T -&S 下面构造它的 LR(0)项目集规范族为：从上表可看出,不存在移进- 归约冲突以及归约归约冲突，该文法是 LR(0)文法。 从而有下面的 LR(0)分析表：
7.已知文法为：A -&aAd|aAb| ε判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。 解：增加一个非终结符 S/后，产生原文法的增广文法有： S'-&A A -&aAd|aAb|ε 下面构造它的 LR(0)项目集规范族为：
第81页共6页
从上表可看出, 状态 I0 和 I2 存在移进- 归约冲突，该文法不是 LR(0)文法。对于 I0 来说有：
FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ ，所以在 I0 状态下面临输入符号为 a 时移进，为 b,d,#时归约，为其他时报错。对于 I2 来说有也有与 I0 完全相同的结论。这就是说，以上的移进 - 归约冲突是可以解决的，因此该文法是 SLR(1)文法。
其 SLR(1)分析表为：
对输入串 ab#给出分析过程为：
第82页共6页
4解:(1)I0: S’ ? .SS ? .id = E
I1: S’ ? S.I2: S ? id. = E
I3: S ? id = .E
E ? .E + E
E ? .E * E
I4: S ? id = E.E ? E. + E
E ? E. * EI5: E ? id.I6: E ? E + .E （2）由于I4、 I8、 I9均有移进―归约冲突，
E ? .E + EE ? .E * E
故该文法不是LR(0)文法。
E ? .idI7: E ? E * EE ? .E + EE ? .E * EE ? .idI8: E ? E + EE ? E.+ EE ? E. * EI9: E ? E * E.E ? E .+ EE ? E .* E
5解：（1）句子11.01的带注释分析树：
第83页共6页print(3+1*2-2)
L.val=2*L.val+B.val=3L.num=L.num +1=2L.val=B.val=1L.num=1 L L B.val=1 L L.val=2*L.val+B.val=1 L.num=L.num +1=2 L.val=B.val=0 L.num=1 L B B.val=1B.val=1 1 B.val=0 B 1 0（2）处理该句子的结果（Print输出结果）为3.256解：（1）语言L的正规表达式为：(1|2|??|9)(0|1|??|9)*(0|5)|5（2）识别语言L的状态转移图为：四、综合题1. 已知文法 G(E)E →T|E＋TT→F|T *FF →(E)|i(1)给出句型(T *F＋i)的最右推导；(2)给出句型(T *F＋i)的短语、简单短语、句柄、素短语、最左素短语。 2.
构造正规式 1(0|1)*101 相应的 DFA 。所以，可得 DFA 为：
3. 文法：S-&MH|aH -&LSo| εK -&dML| εL -&eHfM-&K|bLM判断 G 是否为 LL(1) 文法，如果是，构造 LL(1) 分析表。4. 对下面的文法 G ：E -&TE'E'-&+E| ε
第84页共6页
T -&FT'T' -&T| εF-& PF'F'-& *F'| εP-&(E)|a|b|^(1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (4 分)(2) 证明这个方法是 LL(1) 的。(4 分)(3) 构造它的预测分析表。(2 分)5.已知文法 G[S] 为：S-&a|^|(T)T-& T,S|S(1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。(2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否未算符优先文法。(3) 给出输入串 (a,a)# 的算符优先分析过程。6.已知文法为：S-&a|^|(T)T-&T,S|S构造它的 LR(0)分析表。7.已知文法为：A -&aAd|aAb| ε判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。答案：1解：
(1) 最右推导：E -&T-&F-&(E)-&(E ＋ T)-&(E ＋ F)-&(E ＋ i)-&(T＋i)-&(T*F＋i)(2) 短语：(T*F＋i) ，T*F＋i ，T*F，i简单短语：T*F,i句柄：T*F素短语：T*F,i最左素短语：T*F
2解：先构造 NFA ：
确定化：重新命名，令 AB 为 B、AC 为 C、ABY 为 D 得：第85页共6页
4解：（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)U{ε}={(,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')UFOLLOW(E)={+,),#};//不包含ε FOLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#}; FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#};//不包含ε FOLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F')UFOLLOW(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]的预测分析表如下：
第86页共6页
5解：（1）各符号的 FIRSTVT 和 LASTVT：
（2）算符优先关系表：（3）句子(a,a)#分析过程如下：
6解：加入非终结符 S' ，方法的增广文法为： S'-&SS-&aS-&^S-&(T)T -&T,ST -&S 下面构造它的 LR(0)项目集规范族为：第87页共6页
从上表可看出,不存在移进- 归约冲突以及归约归约冲突，该文法是 LR(0)文法。 从而有下面的 LR(0)分析表：
7解：增加一个非终结符 S/后，产生原文法的增广文法有： S'-&A A -&aAd|aAb|ε 下面构造它的 LR(0)项目集规范族为：
从上表可看出, 状态 I0 和 I2 存在移进- 归约冲突，该文法不是 LR(0)文法。对于 I0 来说有：
FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ ，所以在 I0 状态下面临输入符号为 a 时移进，为 b,d,#时归约，为其他时报错。对于 I2 来说有也有与 I0 完全相同的结论。这就是说，以上的移进 -第88页共6页
归约冲突是可以解决的，因此该文法是 SLR(1)文法。
其 SLR(1)分析表为：
对输入串 ab#给出分析过程为：
编译原理Dd卷7-1
设有如下的三地址码（四元式）序列：read NI:=NJ:=2L1 :
goto L3L2 :
goto L4J:=J+1I:=Ngoto L1L3 :
Print ′YES′haltL4 :
Print ′NO′halt试将它划分为基本块，并作控制流程图。7-2
考虑如下的基本块：D:=B*C第89页共6页
E:=A+BB:= B*CA:=E+D(1) 构造相应的DAG；(2) 对于所得的DAG，重建基本块，以得到更有效的四元式序列。
对于如下的两个基本块：(1)
A:=B*CD:=B/CE:=A+DF:=2*EG:=B*CH:=G*GF:=H*GL:=FM:=L(2)
B:=3D:=A+CE:=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L分别构造相应的DAG，并根据所得的DAG，重建经优化后的四元式序列。在进行优化时，须分别考虑如下两种情况：（）变量G、L、M在基本块出口之后被引用；第90页共6页（）仅变量L在基本块出口之后被引用。7-4
对于题图7-4所示的控制流程图：(1) 分别求出它们各个结点的必经结点集；(2) 分别求出它们的各个回边；(3) 找出各流程图的全部循环。7-5
对于如下的程序：I:=1read J,KL:
A:=K*IB:=J*IC:=A*Bwrite CI:=I+1 第91页共6页
goto Lhalt试对其中的循环进行可能的优化。习题答案
解：划分情况及控制流程如答案图7-1所示：
将四元式序列划分为基本块
解：(1) 相应的DAG如答案图7-2所示。第92页共6页答案图7-2
(2) 优化后的代码为：
解：(1) 相应的DAG如答案图7-3-(1)所示。第93页共6页
若只有G、L、M在出口之后被引用，则优化后的代码为：G:=B*CH:=G*GL:=H*GM:=L若只有L在出口之后被引用，则代码为：G:=B*CH:=G*GL:=H*G
(2) 相应的DAG如答案图7-3-(2)所示。第94页共6页
若只有G、L、M被引用，则代码为：D:=A+C E:=A*C F:=E+D G:=3*F L:=15+F M:=L若只有L被引用，则代码为：D:=A+C E:=A*C F:=E+D L:=+F15
解：(a) 必经结点集：D2={2}第95页共6页
D3 ={2,3}，
D4 ={2,4}D5 ={2,4,5}
D6 ={2,4,6}D7 ={2,4,7}
D8={2,4,7,8}回边及相应的循环：7→4：{4,5,6,7}8→2：{2,3,4,5,6,7,8}(b) 必经结点集：D1 ={1}
D2 ={1,2}D3 ={1,2,3}
D4 ={1,2,3,4}D5 ={1,2,3,5}
D6 ={1,2,3,6}D7 ={1,2,7}
D8 ={1,2,7,8}回边及相应循环：7→2：{2,3,4,5,6,7}(c) 必经结点集：D1 ={1}
D2 ={1,2},D3 ={1,2,3}
D4 ={1,2,4},D5 =1,2,5}
D6 ={1,2,3,6},D7 ={1,2,7}回边及相应循环：5→2：{2，3，4，5}6→6： {6}注意：5→4不是回边。因为4不是5的控制结点。7-5
解：(1) 划分基本块后的流程图如答案图7-5-(1)所示。第96页共6页
(2) 削弱运算强度后的流程图如答案图7-5-(2)所示。
第97页共6页
答案图7-5-(2)
削弱运算强度后的流程图
(3) 消除归纳变量后的流程图如答案图7-5-(3)所示。
答案图7-5-(3)
消除归纳变量后的流程图
编译原理Ee卷综合题：4-4
对于如下的文法G[S]：S→Sb|Ab|bA→Aa|a(1) 构造一个与G等价的LL(1)文法G′[S]；(2) 对于G′[S]，构造相应的LL(1)分析表；(3) 利用LL(1)分析法判断符号串aabb是否是文法G[S]的合法句子。综合题：4-5
设已给文法S→SaB|bB
B→Ac第98页共6页(1) 构造一个与G等价的LL(1)文法G′[S]；(2) 对于G′[S]，构造相应的LL(1)分析表；(3) 利用LL(1)分析法判断符号串bacabc是否是文法G[S]的合法句子。
第4章 习题答案
解：(1) 文法中含有直接左递归的非终结符号S和A，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G′[S]：：S→AbS′|bS′S′→bS′|εA→aA′A′→aA′|ε文法G′[S]的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-4-(1)所示:
答案表4-4-(1)
文法G′[S]的各个FIRST集和FOLLOW集
下面来验证文法G′[S]是否是LL(1)文法。对于文法G′[S]，因为有：对于产生式S→AbS′|bS′，有FIRST(AbS′)∩FIRST(bS′)={a}∩{b}=?； 第99页共6页对于产生式S′→bS′|ε，有FIRST(bS′)∩FOLLOW(S′)={b}∩{#}=?； 对于产生式A′→aA′|ε，有FIRST(aA′)∩FOLLOW(A′)={a}∩{b}=?； 所以文法G′[S]即为所求的与G等价的LL(1)文法。(2) 文法G′[S]的LL(1)分析表如答案表4-4-(2)所示:答案表4-4-(2)
文法G′[S]的LL(1)分析表
(3) 对符号串aabb进行LL(1)分析的过程如答案表4-4-(3)所示。答案表4-4-(3)
对aabb进行LL(1)分析的过程
第100页共6页因为分析成功，所以符号串aabb是文法G[S]的合法句子。
解：(1) 文法中含有直接左递归的非终结符号S，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G′[S]：：S→bBS′S′→aBS′|εA→S|aB→Ac文法G′[S]的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-5-(1)所示:
答案表4-5-(1)
文法G′[S]的各个FIRST集和FOLLOW集
下面来验证文法G′[S]
是否是LL(1)文法。对于文法G′[S]，因为有：对于产生式S′→aBS′|ε，有FIRST(aBS′)∩FOLLOW(S′)={a}∩{#,c}=?； 对于产生式A→S|a，有FIRST(S)∩FIRST(a)={b}∩{a}=?；所以文法G′[S]即为所求的与G等价的LL(1)文法。
(2) 文法G′[S]的LL(1)分析表如答案表4-5-(2)所示:
答案表4-5-(2)
文法G′[S]的LL(1)分析表第101页共6页
(3) 对符号串bacabc进行LL(1)分析的过程如答案表4-5-(3)所示。答案表4-5-(3)
对bacabc进行LL(1)分析的过程
因为LL(1)分析表中B行c列元素为空，即为“出错”，故分析失败，所以符号串bacabc不是文法G[S]的合法句子。编译原理Ff卷 五、计算题： 1.设文法G(S):S→^ | a | (T)
T→T,S | S⑴ 消除左递归；第102页共6页
⑵ 构造相应的FIRST和FOLLOW集合；⑶ 构造预测分析表2.语句 if E then S(1) 改写文法，使之适合语法制导翻译；(2) 写出改写后产生式的语义动作。3.设文法G（S）：S→(T) | aT→T+S | S(1）计算FIRSTVT 和LASTVT；（2）构造优先关系表。4.设某语言的for语句的形式为(1)(2)for i:＝E to E do S其语义解释为(1)i:＝E(2)LIMIT:＝Eagain: if i＜＝LIMIT thenBeginS;i:＝i＋1goto againE（1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。5.把语句while a&10 doif c&0 then a:=a+1else a:=a*3-1;翻译成四元式序列。6.设有基本块D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假设基本块出口时只有M还被引用，请写出优化后的四元序列。7.已知文法G(S)S→a | ^ | (T)T→T,S | S(1) 给出句子(a,(a,a))的最左推导；(2) 给出句型((T,S),a)的短语, 直接短语，句柄。8.对于 C 语言do S while E语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。第103页共6页9.已知文法G(S)
B→d(1)给出句子abbcde的最左推导及画出语法树；
(2)给出句型aAbcde的短语、素短语。
10.设文法G(S):S→(T) | aS | a
T→T,S | S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；
⑶构造预测分析表。 11.把语句if X&0 ∨ Y&0the