编译原理第七章例题

1．写出下列表达式的三地址形式的中间表示。

（1）5+6 ⨯ (a + b);（2）⌝A∨( B ∧ (C ∨ D));（3）for j:=1 to 10 do a[j + j]:=0;（4）if x > y then x:=10 else x:= x + y;答：⑴100: t1:=a+b101: t2:=6*t1102: t3:=5+t2⑵100: if A goto 102101: goto T102: if B goto 104103: goto F104: if C goto T105: goto 106106: if D goto T107: goto F⑶100: j:=1101: if j>10 goto NEXT102: i:=j+j103: a[i]:=0104: goto 101⑷100: if x>y goto 102101: goto 104102: x:=10103: goto 105104: x:=x+y105:2．将语句if A V B>0 then while C>0 do C:=C+D翻译成四元式。

答：100 (jnz，A，-，104)101 (j，-，-，102)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)1093．试将下述程序段翻译成三地址形式的中间代码表示。

while ( a+b<c OR a=b )while ( a<5 AND b<10 ){ a=a+1;b=b+1;}答：三地址代码如下：100: t:=a+b101: if t<c goto 105102: goto 103103: if a=b goto 105104: goto 112105: if a<5 goto 107106: goto 100107: if b<10 goto 109108: goto 100109: a:=a+1110: b:=b+1111: goto 105112:4．While a＞0 ∨b＜0doBeginX：＝X＋1；if a＞0 then a：＝a－1else b：＝b＋1End；翻译成四元式序列。

7
山东交通学院
《编译原理》
规范推导/规范句型/规范归约
最右推导：在推导的任何一步αβ，其中α和β是句型， 都是对α中的最右非终结符进行替换。 最右推导被称为规范推导。由规范推导所得的句型称为规范 句型 例：G[S]： S→E E→E+T | T T→(E) | i SE T (E) (E+T) (E+i) (T+i) (i+i) 规范归约： 假定α是G的一个句子，称序列αn、αn-1 …、α0是α的一个 规范归约，如果该序列满足： 1、 αn = α 2、 α0为文法的开始符号 3、对任何j，0<j<=n， αj-1是从αj经把句柄替换为相应产生 式的左部而得到的
杨海 yanghai_sdjtu@
23
山东交通学院
《编译原理》
构造识别活前缀的FA(续)
(2) LR(0) 项目集的闭包：即FA中的状态 若当前处于A –> X•YZ刻画的情况，期望移进First(Y) 中的某些符号，假如有产生式Y –> u 。那么Y –> .u， 这个项目也是刻划期望移进First(Y)中的某些符号的 情况。 A –> X•YZ Y –> •u 这两个项目对应移进归约分析的同一个状态，这两个 项目构成一个项目集, 对应每个项目集，分析表将有 一个状态。
4
山东交通学院
《编译原理》
3、规约的一个特殊情况：栈中的全部内容w归约 为开始符号S （即施用 S –> w），且没有余留输 入了，意味着已成功分析了整个输入串。
4、移进归约分析中还会出现一种情况，就是出 错，比如当前的token不能构成一个合法句子的 一部分，例如上面的文法，试分析i+)时就会发生 错误。

第七章习题解答7.1 给定文法：S→(A)A→ABBA→BB→bB→c①构造它的基本LR(0)项目集；②构造它的LR(0)项目集规范族；③构造识别该文法活前缀的DFA；④该文法是SLR文法吗？若是，构造它的SLR分析表。

7.2 给定文法：E→EE+E→EE*E→a①构造它的LR(0)项目集规范族；②它是SLR(1)文法吗？若是，构造它的SLR(1)分析表；③它是LR(1)文法吗？若是，构造它的LR(1)分析表；④它是LALR(1)文法吗？若是，构造它的LALR分析表。

7.3 给出一个非LR(0)文法。

7.4 给出一个SLR(1)文法，但它不是LR(0)文法，构造它的SLR分析表。

7.5 给出一个LR(1)文法，但它不是LALR(1)文法，构造它的规范LR(1)分析表。

7.6 给定二义性文法：① E→E+E② E→E*E③ E→(E)④ E→id用所述的无二义性规则和(或)另加一些无二义性规则，例如，给算符*、+施加某种结合规则。

①构造它的LR(0)项目集规范族及识别活前缀的DFA；②构造它的LR分析表。

习题参考答案7.1 解：文法的基本LR(0)项目集为S→.(A) S→(.A) S→(A.) S→(A).A→.ABB A→A.BB A→AB.B A→ABB.A→.B A→B. B→.b B→b.B→.c B→c.构造该文法的识别活前缀的DFSA如下图所示：I文法的识别活前缀的DFSA该文法的LR(0)项目集规范族={I0，I1，I2，I3，I4，I5，I6，I7，I8}因为在构造出来的识别活前缀的DFA中，每一个状态对应的项目集都不含有移进-归约、归约-归约冲突，所以该文法是LR(0)文法，当然也是SLR文法。

因为 FOLLOW(S)={#}FOLLOW(A)=FIRST{)}∪FIRST(BB)={)，b，c}FOLLOW(B)=FIRST(B)∪FOLLOW(A)={b，c，)}其对应的SLR(1)分析表如下表所示。

第1 题已知文法A→aAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。

答案：文法：A→aAd|aAb|ε拓广文法为G′，增加产生式S′→A若产生式排序为：0 S' →A1 A →aAd2 A →aAb3 A →ε由产生式知：First (S' ) = {ε,a}First (A ) = {ε,a}Follow(S' ) = {#}Follow(A ) = {d,b,#}G′的LR(0)项目集族及识别活前缀的DFA 如下图所示在I0 中：A →.aAd 和A →.aAb 为移进项目，A →.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。

在I0、I2 中：Follow(A) ∩{a}= {d，b，#} ∩{a}=所以在I0、I2 中的移进-归约冲突可以由Follow 集解决，所以G 是SLR(1)文法。

构造的SLR(1)分析表如下：对输入串ab#的分析过程:第2 题若有定义二进制数的文法如下：S→L·L|LL→LB|BB→0|1(1) 试为该文法构造LR 分析表，并说明属哪类LR 分析表。

(2) 给出输入串101.110 的分析过程。

答案：文法：S→L.L|LL→LB|BB→0|1拓广文法为G′，增加产生式S′→S若产生式排序为：0 S' →S1 S →L.L2 S →L3 L →LB4 L →B5 B →06 B →1由产生式知：First (S' ) = {0,1}First (S ) = {0,1}First (L ) = {0,1}First (B ) = {0,1}Follow(S' ) = {#}Follow(S ) = {#}Follow(L ) = {.,0,1,#}Follow(B ) = {.,0,1,#}G′的LR(0)项目集族及识别活前缀的DFA 如下图所示：在I2 中：B →.0 和 B →.1 为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。

N→ Є
D →id: T { enter(top(tblptr), , T.type, top(offset)); top(offset):= top(offset) +T.width } 24
§7.2
说明语句
2.含嵌套说明的翻译模式：
(1)语义规则中的操作: Mktable (previous): 创建一张新符号表,并返回指向新表的一个指针; Enter (table, name, type, offset):
(2)置相对地址为当前offset之值， (3)使offset加上该名字所表示的数据对象的域宽。
20
§7.2 说明语句
3. 相应的翻译模式：
PD { offset:=0 } { enter (, T.type,offset);
DD;D
Did:T
offset:=offset+t.width } Tinteger
(0) (1) (2) (3) (4) (5)
(2) (3) (4)
16
§7.１ 中间语言
4.间接三元式：便于代码优化处理
方法：间接码表+三元式表
按运算的先后顺序列出有关三元式在三元表中的位置 例: 语句X:=(A+B)*C;Y:=D↑(A+B)的间接三元式表示如下所示: 间接代码 三元式表 (1) (2) (3) (1) (4) (5)
30
已归约串
PLACE
输入串
语义动作
# #X # X:= # X:= # X:= # X:= # X:=
X:= -B*(C+D)# X := -B*(C+D)# X_ -B*(C+D)# X__ B*(C+D)# -B X__B *(C+D)# -E X__B *(C+D)# { E.place:=p=<B>} E1 X_T1 *(C+D)# {E1.place:=newtemp=T1; 生成四元式(1) } … … … … # X:=E*(C X_T1__C +D)# # X:=E*(E1 X_T1__C +D)# { E1.place:=p=<C> } … … … …

prev
next 40
LR(0)分析表的构造※
dir
LR(0)分析表相当于识别活前缀的有限自动
机DAF的状态转换矩阵
prev
next 41
LR(0)分析表的构造算法
dir
令包含S’→•S 的项目集Ik的下标k为分析器的初态
LR(0)分析表的ACTION和GOTO表的构造步骤如下:
若项目 A→•a 属于Ik，且转换函数GO(Ik,a)= Ij ，当a为终结符时，则置ACTION[k,a]为Sj 若项目 A→• 属于Ik ，则对a为任何终结符或‘#’， 置ACTION[k,a] = rj ，j为产生式在文法G’中的编 号 若项目 X→•A 属于Ik ，且GO(Ik,A)= Ij ，则置 GOTO[k,A]=j，其中A为非终结符，j为某一状态号 若项目 S’→S• 属于Ik ，则置ACTION[k,#] = acc 其它填上“报错标志”，可用空白表示
Step2 对初态集或其它所构造的项目集应用转
换函数 GO(I，X)= CLOSURE(J)求出新状态 J的项目集
Step3 重复Step2直到不出现新的项目集为止
prev next 36
dir
S’ E A B
E aA | bB cA | d cB | d
c
c a
I4:Ac•A A•cA A•d I2:Ea•A A•cA A•d
prev
next 46
S’E[0] EaA[1]|bB[2] AcA[3]|d[4] BcB[5]|d[6]
dir
对输入串bccd#的分析
符号栈 输入串 bccd# ACTION S3
up
步骤 状态栈 0 1 03 2 035 3 0355 4 5 6 7

1S → a | ∧ | ( T )T → T , S | S解：(1) 增加辅助产生式 S’→＃S＃求 FIRSTVT集FIRSTVT（S’）＝ {#}FIRSTVT（S）＝ {a ∧ ( }FIRSTVT (T) ＝ {,} ∪ FIRSTVT( S ) = { , a ∧ ( }求 LASTVT集LASTVT（S’）＝ { # }LASTVT（S）＝ { a ∧ )}LASTVT (T) ＝ { , a ∧ )}(2)算符优先关系表a ∧( ) , #a ·> ·> ·> ∧·> ·> ·> ( <·<·<·=·<·) ·> ·> ·>, <·<·<··> ·># <·<·<·=·因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法(3)a ∧( ) ,F 1 1 1 11 1g 1 1 1 11 1f 2 2 1 3 2g 2 2 2 1 2f 3 3 1 3 3g 4 4 4 1 2f 3 3 1 3 3g 4 4 4 1 2(4)栈优先关系当前符号剩余输入串移进或规约＃<·( a,a)#移进＃( <· a,a)# 移进# (a ·> , a)# ＃(T <·, a)# ＃(T，<· a )# ＃(T,a ·> ) # ＃(T,T ·> ) # ＃(T =·) # ＃(T) ·> ＃＃T =·＃4.扩展后的文法S’→#S# S→S;G S→G G→G(T)G→H H→a H→(S)T→T+S T→S（1）FIRSTVT(S)={;}∪FIRSTVT(G) = {; , a , ( } FIRSTVT(G)={ ( }∪FIRSTVT(H) = {a , ( } FIRSTCT(H)={a , ( }FIRSTVT(T) = {+} ∪FIRSTVT(S) = {+ , ; , a , ( }LASTVT(S) = {;} ∪LASTVT(G) = { ; , a , )}LASTVT(G) = { )} ∪LASTVT(H) = { a , )}LASTVT(H) = {a, )}LASTVT(T) = {+ } ∪LASTVT(S) = {+ , ; , a , ) }构造算符优先关系表; ( ) a + # ；·> <··> <··> ·> ( <·<·＝·<·<·) ·> ·> ·> ·> ·> a ·> ·> ·> ·> ·> + <·<··> <··># <·<·<·＝·因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法（2）句型a(T+S);H;(S)的短语有：a(T+S);H;(S) a(T+S);H a(T+S) a T+S (S) H直接短语有: a T+S H (S)句柄： a素短语：a T+S (S)最左素短语：a(3)分析a；（a＋a）栈优先关系当前符号剩余输入串移进或规约＃＃a ＃T ＃T；＃T；（<··><·<·<·a；；（a；（a＋a）＃（a＋a）＃（a＋a）＃a＋a）＃＋a）＃移进规约移进移进移进＃T；（T ＃T；（T ＋＃T；（T ＋a＃T；（T ＋T＃T；（T ＃T；（T）＃T；T ＃T <·<··>·>＝··>·>＝·＋a）））＃＃＃a）＃）＃＃＃＃移进移进规约规约移进规约规约接受分析a；（a＋a）栈优先关系当前符号剩余输入串移进或规约＃＃（＃（a ＃（T ＃（T＋<·<··><·<·(a＋＋aa＋a）＃＋a）＃a）＃移进移进规约移进移进＃（T＋T ＃（T＃（T）＃T ·>＝··>＝·））＃＃）＃＃＃＃规约移进规约接受（4）不能用最右推导推导出上面的两个句子。

E:=A+D
G:=A
H:=G*G
F:=H*G
L:=F
M:=L
n6
1
n2/
1
C
n4
41+
n7
1
*
n5
1
D
G
E
(1) G:=B*C H:=G*G L:=G*H M:=L
n1
B
对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料电试力卷保相护互装作置用调与试相技互术通关，1系电过，力管根保线据护敷生高设产中技工资术艺料0不高试仅中卷可资配以料置解试技决卷术吊要是顶求指层，机配对组置电在不气进规设行范备继高进电中行保资空护料载高试与中卷带资问负料题荷试2下卷2，高总而中体且资配可料置保试时障卷，各调需类控要管试在路验最习；大题对限到设度位备内。进来在行确管调保路整机敷使组设其高过在中程正资1常料中工试，况卷要下安加与全强过，看度并22工且22作尽22下可22都能22可地护以缩1关正小于常故管工障路作高高；中中对资资于料料继试试电卷卷保破连护坏接进范管行围口整，处核或理对者高定对中值某资，些料审异试核常卷与高弯校中扁对资度图料固纸试定，卷盒编工位写况置复进.杂行保设自护备动层与处防装理腐置，跨高尤接中其地资要线料避弯试免曲卷错半调误径试高标方中高案资等，料，编试要5写、卷求重电保技要气护术设设装交备备置底4高调、动。中试电作管资高气，线料中课并敷3试资件且、设卷料中拒管技试试调绝路术验卷试动敷中方技作设包案术，技含以来术线及避槽系免、统不管启必架动要等方高多案中项；资方对料式整试，套卷为启突解动然决过停高程机中中。语高因文中此电资，气料电课试力件卷高中电中管气资壁设料薄备试、进卷接行保口调护不试装严工置等作调问并试题且技，进术合行，理过要利关求用运电管行力线高保敷中护设资装技料置术试做。卷到线技准缆术确敷指灵设导活原。。则对对：于于在调差分试动线过保盒程护处中装，高置当中高不资中同料资电试料压卷试回技卷路术调交问试叉题技时，术，作是应为指采调发用试电金人机属员一隔，变板需压进要器行在组隔事在开前发处掌生理握内；图部同纸故一资障线料时槽、，内设需，备要强制进电造行回厂外路家部须出电同具源时高高切中中断资资习料料题试试电卷卷源试切，验除线报从缆告而敷与采设相用完关高毕技中，术资要资料进料试行，卷检并主查且要和了保检解护测现装处场置理设。备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。

while A <= D do A:= A + 2;
7.8 请给出
if A and B and C > D then
if A <B then F:=1
else F:=0
else G:=G+1; 的四元式序列，翻译过程中，采用then 与else 的最近匹配原则。
解：100 ( jnz , A , _ , 102 ) /* A and B and C>D */ 101 ( j , _ , _ , 112 ) 102 ( jnz , B , _ , 104) 103 ( j , _ , _ , 112 ) 104 ( j> , C , D , 106 ) 105 ( j , _ , _ , 112 ) 106 ( j< , A , B , 108 ) /* A < B */ 107 ( j , _ , _ , 110 ) 108 ( := , 1 , _ , F ) /* F:=1 */ 109 ( j , _ , _ ，0) 110 ( := , 0 , _ , F ) /* F:=0 */ 111 ( j , _ , _ , 109) 112 (+ , G , 1 , T1 ) 113 ( := , T1 , _ , G )
TToo EE11.ftarluse
E2.code
TToo EE.truuee To E.false
103 (j,_,_,0) /*为假*/
104 105 106
(jnz,C,_,103) (j,_,_,106) (jnz,D,_,104)
/*为假*/ /*假链链首*/
(1) E→E1 or M E2 { backpatch(E1.falselist,

第七章LR分析法1．已知文法A→aAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。

解：增加一个非终结符S/后，产生原文法的增广文法有：S/→AA→aAd|aAb|ε下面构造它的LR(0)项目集规范族为：02对于I0来说有FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。

对于I2来说有也有与I0完全相同的结论。

这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。

其他SLR(1)分析表为：下面构造它的SLR(1)项目集规范族为：15S→a|^|(T)T→T,S|S(1)构造它的LR(0),LALR(1),LR(1)分析表。

(2)给出对输入符号串(a#和(a,a#的分析过程。

(3)说明(1)中三种分析表发现错误的时刻和输入串的出错位置有何区别。

解：(1)加入非终结符S/，方法的增广文法为：S/→SS→aS→^S→(T)T→T,ST→S下面构造它的LR(0)项目集规范族为：表7.15.1 文法的LR(0)分析表17．若包含条件语句的语句文法可缩写为：S→iSeS|iS|S;S|a其中：i代表if,e代表else,a代表某一语句。

若规定：(1)else与其左边最近的if结合(2);服从左结合试给出文法中i,e,; 的优先关系，然后构造出无二义性的LR分析表，并对输入串iiaea#给出分析过程。

解：加入S/→S产生式构造出增广文法如下：[0] S/→S[1] S→iSeS[2] S→iS[3] S→S;S[4] S→a由习惯可知，定义文法中i,e,;,a4个算符的优先关系为：a>e>i>;。

并且i与;的结合方向均为自左至右。

由上述状态项目集可见：a.状态I1存在移进-归约冲突，由于FOLLOW(S/)∩{;}={#}∩{;}=Φ,所以面临#号时应acc，面临;号时应移进。

第8章 代码生成
8.2.1 假设所有的变量都存放在内存中，为下 面的三地址语句生成代码： 1） x = 1 LD R1 , 1 ST x , R1
3) x = a + 1 LD R1 , a ADD R1 , R1 , 1
8.2.2 假设a和b是元素为4字节值的数组，为下面的三地址语 句序列生成代码。
| 1D1 {D.val 1 2D1.b D1.val; D.b D1.b 1}
| {D.val 0;
D.b 0}
第6章 中间代码生成
6.1.1 为下面的表达式构造DAG ((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))
6.2.1 将算术表达式 a+-(b+c) 翻译成
第7章 运行时环境
7.2.3 图7-9中是递归计算Fiabonacci数列的C语言代码。假设f 的活动记录按顺序包含下列元素：（返回值，参数n，局 部变量s，局部变量t）。通常在活动记录中还会有其他元 素。下面的问题假设初始调用是f(5)。
int f(int n) { int t,s; if (n<2) return 1; s = f(n-1); t = f(n-2); return s+t;
} 图7-9
活动树
5 f(1) 1 f(1)
第
第
个
个
调
调
用
用
即
即
将
将
返
返
回
回
7.2.5 在一个通过引用传递参数的语言中，有 一个函数f(x,y)完成下面的计算： x = x + 1; y = y + 2; return x + y; 如果将a赋值为3，然后调用f(a,a)，那么返回 值是什么？

8
§7.１ 中间语言
例子：如图所示，为a+a*(b-c)+(b-c)*d的DAG
+
+
* a b c
*
d
9
§7.１ 中间语言
2.抽象语法树
例子：(1)a:=b*-c+b*-c的图表示法
assign a * b uminus c b + * uminus c DAG
10
assign
a + * b uminus c
第七章
语义分析和中间代码产生
静态检查器
语法分析器
中间代码产生器
中间代码
优化器 一般情况下，在词法分析程序和语法分析程序对源程序的语法结 构进行分析之后，
要么，由语法分析程序直接调用相应的语义子程序进行语义处理； 要么，首先生成语法树或该结构的某种表示，再进行语义处理。
1
第七章
语义分析和中间代码产生
7.7 类型检查 （略）
4
§7.１ 中间语言
中间语言形式： 后缀式 三地址代码
间接三元式 DAG 抽象语法树
图表示法
三元式 四元式
5
§7.１ 中间语言
一、后缀式—逆波兰式： 规则： (1)E－常量／变量： (2)E－E1 op E2： (3)E－(E1) ： (4)E－op E1： 后缀式为E本身 E1’ E2’ op (E1’) E1’ op
6
§7.１ 中间语言
例子： a*(b+c)— abc+* ab+cd+*
(a+b)*(c+d)—
x+y≤z∨a>0∧(8+z)>3— xy+z≤a0>8z+3>∧∨

…
…
17
2．比例设置语句(SCALE 语句)
比例设置语句是将绘图语句画出的图形进行比例缩放。 它的语法如下：
SCALE IS (横坐标比例因子，纵坐标比例因子) ；
其作用是对绘图语句中的横、纵坐标值按该语句指定的 比例因子缩放。 对于下述的源程序： SCALE IS (100, 100/3)； FOR T FROM 0 TO 2*PI STEP PI/50 DRAW (cos(T)， sin(T))；
3
由于上机时数的限制，我们设计的上机题目仅侧重于前端的
构造技术，包括词法分析、语法分析和语义分析。题目是一 个简单的函数绘图语言的解释器，它接受用户编写的绘图语
句序列(不妨称为源程序)，对语句进行分析和处理，最终将
源程序所规定的图形显示在终端上。
4
希望读者通过上机实习至少达到下述目的：
(1) 会用正规式和产生式设计简单语言的语法； (2) 会用递归下降子程序编写编译器或解释器；
如下：
// This is a comment line 或 -- 此行是注释 两种形式注释的语义是一致的，注释内容均是从注释引 导符(“//”或“--”)开始，直到此行结束。
29
这种形式注释的优点是随着一行的结束注释自动结束，
可以避免因少写注释结束符而使得注释内容无法结束造成程 序错误的问题。它的缺点是当需要书写一大段注释时，每行
11
ROT IS 0.7 ；
ROT IS 1.57 ； 则随后的绘图语句将按1.57而不是0.7弧度旋转。
(3) 无论ORIGIN、ROT和SCALE语句的出现顺序如何，
图形的变换顺序总是：比例变换→旋转变换→平移变换。 (4) 语言对大小写不敏感，例如for、For、FOR等，均被 认为是同一个保留字。 (5) 语句中表达式的值均为双精度类型，旋转角度单位 为弧度且为逆时针旋转，平移单位为点。

编译原理模拟试卷一、选择题（每题1分，共5分）1.在编译过程中，词法分析的主要任务是什么？A.构建语法树B.将源程序分解为单词序列C.语义分析D.代码2.下列哪个不属于编译器的组成部分？A.词法分析器B.语法分析器C.代码器D.数据库管理系统3.在编译器中，中间代码的作用是什么？A.提高编译速度B.方便目标代码C.提高程序的可读性4.下列哪种语言通常被用作编译器的实现语言？A.PythonB.JavaC.C++5.在编译原理中，形式语言的主要作用是什么？A.描述程序设计语言的语法B.描述程序的语义C.描述程序的数据结构D.描述程序的算法二、判断题（每题1分，共5分）1.编译器的主要任务是将源程序转换为目标代码。

（正确/错误）2.语法分析器负责检查源程序中的语法错误。

（正确/错误）3.语义分析是在语法分析之后进行的。

（正确/错误）4.中间代码是一种与机器无关的代码。

（正确/错误）5.代码优化不会影响程序的正确性。

（正确/错误）三、填空题（每题1分，共5分）1.编译器包括____、____、____、____等组成部分。

2.在编译过程中，____负责将源程序分解为单词序列。

3.语法分析器的主要任务是构建____。

4.语义分析器负责检查____。

5.代码器负责____。

四、简答题（每题2分，共10分）1.简述编译器的工作流程。

2.解释什么是词法分析。

3.什么是语法分析？它的主要任务是什么？4.什么是语义分析？它的主要作用是什么？5.简述中间代码的作用。

五、应用题（每题2分，共10分）1.给出一个简单的C语言程序，请描述它通过编译器的过程。

2.什么是编译器的优化？请给出一个例子。

3.解释什么是编译器的错误处理。

4.什么是编译器的调试信息？它的作用是什么？5.请解释编译器的前端和后端。

六、分析题（每题5分，共10分）1.分析并解释编译器中的词法分析、语法分析和语义分析之间的关系。

2.分析并解释编译器中的中间代码和目标代码之间的关系。

第七章语义分析和中间代码产生本章要点1. 中间语言，各种常见中间语言形式；2. 说明语句、赋值语句、布尔表达式、控制语句等的翻译；3. 过程调用的处理；4. 类型检查；本章目标掌握和理解中间语言，各种常见中间语言形式；各种语句到中间语言的翻译；以及类型检查等内容。

本章重点1．中间代码的几种形式，它们之间的相互转换：四元式、三元式、逆波兰表示；3．赋值语句、算术表达式、布尔表达式的翻译及其中间代码格式；4．各种控制流语句的翻译及其中间代码格式；5．过程调用的中间代码格式；6．类型检查；本章难点1. 各种语句的翻译；2. 类型系统和类型检查；作业题一、单项选择题：1. 布尔表达式计算时可以采用某种优化措施，比如A and B用if-then-else可解释为_______。

a. if A then true else B；b. if A then B else false；c. if A then false else true；d. if A then true else false；2. 为了便于优化处理，三地址代码可以表示成________。

a. 三元式b. 四元式c. 后缀式d. 间接三元式3. 使用三元式是为了________：a. 便于代码优化处理b. 避免把临时变量填入符号表c. 节省存储代码的空间d. 提高访问代码的速度4. 表达式-a+b*(-c+d)的逆波兰式是________。

a. ab+-cd+-*；b. a-b+c-d+*；c. a-b+c-d+*；d. a-bc-d+*+；5. 赋值语句x:=-(a+b)/(c-d)-(a+b*c)的逆波兰式表示是_______。

a. xab+cd-/-bc*a+-:=；a. xab+/cd-bc*a+--:=；a. xab+-cd-/abc*+-:=；a. xab+cd-/abc*+--:=；6. 在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以由________来描述。

一、根据形式定义求出活前缀的正规表达式，然 后由此正规表达式构造NFA再确定化为DFA(不 实用，略)
二、求出文法的所有项目，按一定规则构造识别 活前缀的NFA再确定化为DFA(了解)
三、使用闭包函数（CLOSURE）和转向函数 (GOTO(I,X))构造文法G’的LR(0)的项目集规范 族，再由转换函数建立状态之间的连接关系得 到识别活前缀的DFA(掌握)
编译原理 Compilers Principles 第7章9
移进-归约中的问题分析
3） #ab 4） #aA 5） #aAb 6） #aA
bcde# bcde# cde# cde#
归约(A→b) 移进
归约(A→Ab) 移进
分析：已分析过的部分在栈中的前缀不同，而且移 进和归约后栈中的状态会发生变化
S aA cBe
Ab d b
0 S 1*
1 * 句子识别态
2a 3b 4
i
5a 6 A 7 b 8
9 a 10 A 11 c 12 d 13
14 a 15 A 16 c 17 B 18 e 10
构造识别活前缀的有限自动机 例子
句柄识别态
X
0S 2a 5a 9a
14 a
*
1
3b 4 6 A7b 10 A 11 c 15 A 16 c
1） # 2） #a 3） #ab
abbcde# bbcde# bcde#
动作
移进 移进 归约(A→b)
状态栈
0 02 024
ACTION
S2 S4 r2
GOTO
3
对输入串abbcde#的LR分析过程
S
1*
b
4
0 a 2 A 3 b 6

第7章习题7-1 设有如下的三地址码（四元式）序列：read NI:=NJ:=2L1 : if I≤J goto L3L2 : I:=I-Jif I>J goto L2if I=0 goto L4J:=J+1I:=Ngoto L1L3 : Print ′YES′haltL4 : Print ′NO′halt试将它划分为基本块，并作控制流程图。

7-2 考虑如下的基本块：D:=B*CE:=A+BB:= B*CA:=E+D(1) 构造相应的DAG；(2) 对于所得的DAG，重建基本块，以得到更有效的四元式序列。

7-3 对于如下的两个基本块：(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在基本块出口之后被引用；（ⅱ）仅变量L在基本块出口之后被引用。

7-4 对于题图7-4所示的控制流程图：(1) 分别求出它们各个结点的必经结点集；(2) 分别求出它们的各个回边；(3) 找出各流程图的全部循环。

7-5 对于如下的程序：I:=1read J,KL: A:=K*IB:=J*IC:=A*Bwrite CI:=I+1if A<100 goto Lhalt试对其中的循环进行可能的优化。

第8章习题答案7-1 解：划分情况及控制流程如答案图7-1所示：答案图7-1 将四元式序列划分为基本块7-2 解：(1) 相应的DAG如答案图7-2所示。

答案图7-2 DAG(2) 优化后的代码为：D:=B*CE:=A+BB:=DA:=E+D7-3 解：(1) 相应的DAG如答案图7-3-(1)所示。

若只有G、L、M在出口之后被引用，则优化后的代码为：G:=B*CH:=G*GL:=H*GM:=L若只有L在出口之后被引用，则代码为：G:=B*CH:=G*GL:=H*G(2) 相应的DAG如答案图7-3-(2)所示。