编译原理考试习题和答案市公开课一等奖百校联赛获奖课件.pptx

程程 序序 设设 计计 语语 言言 Chapter 3.Chapter 3.词法分析词法分析/10/10第1页2CH.3.CH.3.练习题练习题8(P64.)8(P64.)n8.8.给出下面正规表示式。给出下面正规表示式。(1)以以01结尾二进制数串结尾二进制数串;正规式正规式 (0|1)*01(2)能被能被5整除十进制整数整除十进制整数;允许任意允许任意0开头：开头：(0|1|2|3|4|5|6|7|8|9)*(0|5)不允许不允许0开头（开头（0本身除外）：本身除外）：(0|5)|(1|2|3|9)(0|1|2|3|9)*(0|5)/10/10第2页3CH.3.CH.3.练习题练习题7(P64.)7(P64.)n7.7.(1)1(0|1)*101 结构结构DFADFA。解解1:正规式对应正规式对应NFA:XY34511011210 I I0 I1X 1,3,2 1,3,2 3,2 3,4,2 3,2 3,2 3,4,2 3,4,2 3,5,2 3,4,2 3,5,2 3,2 3,Y,4,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 3/10/10第3页 (1)正规式正规式 1(0|1)*101DFA:x3,Y,4,23,4,23,5,211011,3,23,20100101 I I0 I1X 1,3,2 1,3,2 3,2 3,4,2 3,2 3,2 3,4,2 3,4,2 3,5,2 3,4,2 3,5,2 3,2 3,Y,4,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 3/10/10第4页 (1)正规式正规式 1(0|1)*101DFA:I I0 I1X 1,3,2 1,3,2 3,2 3,4,2 3,2 3,2 3,4,2 3,4,2 3,5,2 3,4,2 3,5,2 3,2 3,Y,4,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 305341101120100101/10/10第5页6CH.3.CH.3.练习题练习题7(P64.)7(P64.)n7.7.结构以下正规式对应结构以下正规式对应DFADFA。(1)1(0|1)*101 解解2:正规式对应正规式对应NFA:04123110110 I I0 I10 初初01 11 11 11,2 21,2 21,3 31,2 21,3 31 11,2,4 41,2,4终终4 1,3 31,2 210423110110010DFA:/10/10第6页7n7.7.结构以下正规式对应结构以下正规式对应NFANFA。(P64.)(P64.)(2)1(1010*|1(010)*1)*0XY201131010*1(010)*1XY201136451100*7811(010)*/10/10第7页8n7.7.结构以下正规式对应结构以下正规式对应NFANFA。(P64.)(P64.)(2)1(1010*|1(010)*1)*0XY201136451100*7811(010)*XY2011364511007811910010/10/10第8页XY2011364511007811910010XY201136451100781191001211017.7.(2)1(1010*|1(010)*1)*0NFANFA。/10/10第9页10CH.3.CH.3.练习题练习题14(P64.)14(P64.)n(1)正规式正规式:(10|0)*(2)NFA:确定化确定化:YX1001201001012 I I0 I1X,1,Y 1,Y2 1,Y1,Y2 21,Y I I0 I1初终初终0 1 2 终终 1 1 2 2 1 DFA:/10/10第10页11CH.3.CH.3.练习题练习题14(P64.)14(P64.)n(1)正规式正规式:(10|0)*(2)NFA:YX1001201001012DFA:结构一个结构一个DFA，它接收，它接收 S0,1上全部满足以下条件上全部满足以下条件字符串：每个字符串：每个1都有都有0直接直接跟在右边。跟在右边。10010DFA:(最简最简)/10/10第11页程程 序序 设设 计计 语语 言言 Chapter 2.Chapter 2.高级语言及高级语言及其语法描述其语法描述/10/10第12页13CH.2.CH.2.练习题练习题6(P36.)6(P36.)n6.6.令文法令文法G6G6为为:N D|ND D 0|1|2|3|4|5|6|7|8|9 N D|ND D 0|1|2|3|4|5|6|7|8|9n(1)G6(1)G6语言语言L(G6)L(G6)是什么是什么?n注意注意：集合写法不正确：集合写法不正确n解：解：L(G6)=0,1,2,3,4,5,6,7,8,9L(G6)=0,1,2,3,4,5,6,7,8,9+=0=0 9 9数字组成全部数字串，能够数字组成全部数字串，能够0 0开头开头 n(2)(2)给出句子给出句子01270127、3434和和568568最左和最右推导。最左和最右推导。n注意注意：1)1)步骤，步骤，和和 区分区分；2)2)不能写为不能写为n解：解：01270127最左推导：最左推导：N NNDNDNDDNDDNDDDNDDDDDDDDDDD 0DDD0DDD01DD01DD012D012D01270127 0127 0127最右推导：最右推导：N NNDNDN7N7ND7ND7N27N27ND27ND27 N127N127D127D12701270127+第13页14CH.2.CH.2.练习题练习题8(P36.)8(P36.)n8.8.令文法为令文法为 E T|E+T|E-T E T|E+T|E-T T F|T*F|T/F T F|T*F|T/F F (E)|i F (E)|i (1)给出给出 i+i*i、i*(i+i)最左推导和最左推导和最右推导。最右推导。解解：此处仅以：此处仅以 i*(i+i)为例给出答案为例给出答案最左推导最左推导E E T T T*F T*F F*F F*F i*F i*F i*(E)i*(E)i*(E+T)i*(E+T)i*(T+T)i*(T+T)i*(F+T)i*(F+T)i*(i+T)i*(i+T)i*(i+F i*(i+F)i*(i+i)i*(i+i)最右推导最右推导E E T T T*F T*F T*(E)T*(E)T*(E+T)T*(E+T)T*(E+F)T*(E+F)T*(E+i)T*(E+i)T*(T+i)T*(T+i)T*(F+i)T*(F+i)T*(i+i)T*(i+i)F*(i+i)F*(i+i)i*(i+i)i*(i+i)第14页15CH.2.CH.2.练习题练习题8(P36.)8(P36.)n8.8.令文法为令文法为 E T|E+T|E-T E T|E+T|E-T T F|T*F|T/FT F|T*F|T/F F (E)|i F (E)|iEE -TE -TTF F iF iii-i-i i-i-i 语法树语法树(2)给出给出 i+i+i、i+i*i和和i-i-i语法树。语法树。EE +TE +TTF F iF iii+i+i i+i+i 语法树语法树i+i*i i+i*i 语法树语法树EE +TTTF F iF ii*n注意注意：树枝和符号均不可随意增减！：树枝和符号均不可随意增减！第15页16CH.2.CH.2.练习题练习题9(P36.)9(P36.)n9.9.证实下面文法是二义：证实下面文法是二义：S iSeS|iS|i S iSeS|iS|in证实证实:因为存在句子因为存在句子 iiiei iiiei，它对应两棵不一样语法树，它对应两棵不一样语法树,如右图如右图:所以该文法是二义文法。所以该文法是二义文法。n说明说明：按定义只要能给出一：按定义只要能给出一个反例即可，个反例即可，iiieiiiiei不是唯一不是唯一反例。反例。S i S i S e SiiiSi S e S i Si/10/10第16页程程 序序 设设 计计 语语 言言 Chapter 5.Chapter 5.自下而上自下而上语法分析语法分析/10/10第17页18CH.5.CH.5.练习题练习题1(P133.)1(P133.)n1.1.令文法令文法G1G1为：为：EE+T|T TT*F|F F(E)|i EE+T|T TT*F|F F(E)|i 证证实实E+T*FE+T*F是是它它一一个个句句型型,指指出出这这个个句句型型全全部部短短语语、直接短语和句柄。直接短语和句柄。n证证实实1:存存在在从从开开始始符符号号E出出发发到到E+T*F推导：推导：E E+T E+T*F E+T*F是是G1一个句型。一个句型。短短语语:E+T*F是是句句型型相相对对于于非非终终止止符符E短短语语;T*F是句型相对于非终止符是句型相对于非终止符T短语短语。直直接接短短语语:T*F是是句句型型相相对对于于规规则则TT*F直直接短语接短语句柄句柄:T*FEE +TT *F语法树语法树/10/10第18页19CH.5.CH.5.练习题练习题1(P133.)1(P133.)n1.1.令文法令文法G1G1为：为：EE+T|T TT*F|F F(E)|i EE+T|T TT*F|F F(E)|i 证证实实E+T*FE+T*F是是它它一一个个句句型型,指指出出这这个个句句型型全全部部短短语语、直接短语和句柄。直接短语和句柄。n证证实实2:可可结结构构出出E+T*F语语法法树树，如如右右图图所所表示表示，E+T*F是是G1一个句型。一个句型。n证实证实3:(也可用归约来证实也可用归约来证实)（概概念念熟熟悉悉后后，短短语语、直直接接短短语语和和句句柄柄可可直直接接列列出出而不用说明）而不用说明）短语短语:E+T*F，T*F 直接短语直接短语:T*F 句柄句柄:T*FEE +TT *F语法树语法树/10/10第19页20CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.2.考虑下面表格结构文法考虑下面表格结构文法G2G2：Sa|Sa|(T)TT,S|S|(T)TT,S|S (1)(1)给出给出(a,(a,a)(a,(a,a)最左和最右推导。最左和最右推导。n(1)解解:(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)最右推导：最右推导：S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,(S,a)(T,(a,a)(S,(a,a)(a,(a,a)/10/10第20页21CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2)2.(2)指指出出(a,(a,a)(a,(a,a)规规范范归归约约及及每每一一步步句句柄柄。依依据据这这个个规规范范归归约约，给给出出“移移进进-归归约约”过过程程，并并给给出出它它语语法树自下而上结构过程。法树自下而上结构过程。n(2)解解:(a,(a,a)规范归约及每一步句柄规范归约及每一步句柄:(a,(a,a)(S,(a,a)(T,(a,a)(T,(S,a)(T,(T,a)(T,(T,S)(T,(T)(T,S)(T)S./10/10第21页22CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2).2.(2).给出给出(a,(a,a)“(a,(a,a)“移进移进-归约归约”过程。过程。n(2)解解:(a,(a,a)“移进移进-归约归约”过程过程:步骤步骤 符号栈符号栈 输入串输入串 动作动作 句柄句柄 1#(a,(a,a)#a 2#(a,(a,a)#移进移进(3#(a ,(a,a)#移进移进 a 4#(S ,(a,a)#归约归约 S a S 5#(T ,(a,a)#归约归约 T S a 6#(T,(a,a)#移进移进,7#(T,(a,a)#移进移进(8#(T,(a ,a)#移进移进 a/10/10第22页23CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2).2.(2).给出给出(a,(a,a)“(a,(a,a)“移进移进-归约归约”过程。过程。n(2)解解:(a,(a,a)“移进移进-归约归约”过程过程:步骤步骤 符号栈符号栈 输入串输入串 动作动作 句柄句柄 9#(T,(S ,a)#归约归约 S a S 10#(T,(T ,a)#归约归约 T S a 11#(T,(T,a)#移进移进,12#(T,(T,a )#移进移进 a 13#(T,(T,S )#归约归约 S a T,S 14#(T,(T )#归约归约 T T,S (T)15#(T,(T)#移进移进)16#(T,S )#归约归约 S (T)T,S/10/10第23页24CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2).2.(2).给出给出(a,(a,a)“(a,(a,a)“移进移进-归约归约”过程。过程。n(2)解解:(a,(a,a)“移进移进-归约归约”过程过程:步骤步骤 符号栈符号栈 输入串输入串 动作动作 句柄句柄 17#(T )#归约归约 T T,S (T)18#(T)#移进移进)19#S#归约归约 S (T)20 成功成功,分析结束分析结束,接收输入串接收输入串/10/10第24页25CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2).2.(2).给出给出(a,(a,a)(a,(a,a)语法树自下而上结构过程。语法树自下而上结构过程。n(2)解解:(a,(a,a)语语法法树树自自下下而而上上结结构构过过程程:用序号表示用序号表示S(T )T ,S (T )T ,SSaSaa/10/10第25页26CH.5.CH.5.练习题练习题3(P133.)3(P133.)n3.(1)3.(1)计算练习计算练习2 2文法文法G2FIRSTVTG2FIRSTVT和和LASTVTLASTVT。Sa|Sa|(T)TT,S|S|(T)TT,S|Sn(1)解解:（执行对应算法可求得）（执行对应算法可求得）FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,),/10/10第26页27CH.5.CH.5.练习题练习题3(P133.)3(P133.)n3.(2)3.(2)计计算算文文法法G2G2优优先先关关系系,G2,G2是是一一个个算算符符优优先先文文法法吗吗?Sa|?Sa|(T)TT,S|S|(T)TT,S|Sn(2)解解:FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)n逐逐一一考考查查 S(T)和和 TT,S 两两两两相相邻邻符符号号，得得到到算算符符优优先先关关系系,如如右右图；图；G2是算符优先文法是算符优先文法。a (),#a (=,#=./10/10第27页283.(4)3.(4)给出输入串给出输入串(a,(a,a)(a,(a,a)算算符优先分析过程。符优先分析过程。nSa|Sa|(T)TT,S|S|(T)TT,S|S序号序号符号栈符号栈输入串输入串优先关系优先关系n下下 一一 步步 动动作作0#(a,(a,a)#(移进移进(1#(a,(a,a)#(a移进移进 a2#(a ,(a,a)#(,归约归约 Sa3#(S ,(a,a)#(,移进移进,4#(S,(a,a)#,(移进移进(5#(S,(a,a)#(a移进移进 a6#(S,(a ,a)#(,归约归约 Sa7#(S,(S ,a)#(,移进移进,8#(S,(S,a)#,(=,#=最左素短语最左素短语./10/10第28页29序号序号符号栈符号栈输入串输入串优先关系优先关系n下下 一一 步步 动动作作9#(S,(S,a )#,)归约归约 Sa10#(S,(S,S )#()归约归约 TS,S11#(S,(T )#(=)移进移进)12#(S,(T)#,)归约归约 S(T)13#(S,S )#()归约归约 TS,S14#(T )#(=)移进移进)15#(T)#*#归约归约 S(T)16#S#=#n接收接收17#S#停停.3.(4)3.(4)给出输入串给出输入串(a,(a,a)(a,(a,a)算算符优先分析过程。符优先分析过程。nSa|Sa|(T)TT,S|S|(T)TT,S|S a (),#a (=,#=最左素短语最左素短语./10/10第29页30n5.(1)5.(1)考虑文法考虑文法 SAS|b ASA|a SAS|b ASA|a 列出这个文法全部列出这个文法全部LR(0)LR(0)项目。项目。CH.5.CH.5.练习题练习题5(P134.)5(P134.)n解解(1):(1):拓广文法，加入拓广文法，加入 SSSS 拓广文法拓广文法LR(0)LR(0)项目有项目有:S.S SS.S.S SS.S.AS SA.SS.AS SA.S SAS.S.b Sb.A.SA SAS.S.b Sb.A.SA AS.A ASA.A.a Aa.AS.A ASA.A.a Aa./10/10第30页31n5.(2)5.(2)结构文法结构文法 SAS|b ASA|a SAS|b ASA|a LR(0)LR(0)项目集规范族及识别活前缀项目集规范族及识别活前缀DFADFA。1）拓广文法，加入）拓广文法，加入 SS2）画出）画出 DFA/10/10第31页n5.(2)5.(2)结构文法结构文法 SAS|b ASA|a SAS|b ASA|a LR(0)LR(0)项目集规范族及识别活前缀项目集规范族及识别活前缀DFADFA。0:S.S S.AS S.b A.SA A.a 5:ASA.SA.S S.ASS.b A.SAA.a7:SAS.AS.A A.SAA.a S.ASS.b 1:SS.AS.A A.SA A.a S.AS S.b 3:Sb.4:Aa.2:SA.S S.AS S.b A.SA A.a 6:AS.A A.SA A.a S.AS S.b SbaAASbaASabSabASAbaSabA/10/10第32页33n5.(3)5.(3)文法文法 SAS|b ASA|a SAS|b ASA|a 是是LR(0)LR(0)文法吗？文法吗？0:S.S S.AS S.b A.SA A.a 5:ASA.SA.S S.ASS.b A.SAA.a7:SAS.AS.A A.SAA.a S.ASS.b 1:SS.AS.A A.SA A.a S.AS S.b 3:Sb.4:Aa.2:SA.S S.AS S.b A.SA A.a 6:AS.A A.SA A.a S.AS S.b SbaAASbaASabSabASAbaSabA不是不是LR(0)文法文法！因为存在冲突，比因为存在冲突，比如状态如状态1、状态、状态5/10/10第33页程程 序序 设设 计计 语语 言言 Chapter 4.Chapter 4.自上而下自上而下语法分析语法分析/10/10第34页35CH.4.CH.4.练习题练习题1(P81.)1(P81.)n1.考虑下面文法考虑下面文法G1:Sa|(T)TT，S|Sn(1)消去消去G1左递归。然后对每个非终止符左递归。然后对每个非终止符,写出不写出不带回溯递归子程序。带回溯递归子程序。n解解(1)消左后文法消左后文法G1:Sa|(T)TST T,ST|/10/10第35页36CH.4.CH.4.练习题练习题1(P81.)1(P81.)n解解(1)不带回溯递归子程序不带回溯递归子程序:Sa|(T)Procedure S;Begin if sym=a or sym=then advance else if sym=(then begin advance;T;if sym=)then advance else error end else error End;第36页37CH.4.CH.4.练习题练习题1(P81.)1(P81.)n解解(1)不带回溯递归子不带回溯递归子程序程序:nTST Procedure T;Begin S;T end;n解解(1)不带回溯递归子不带回溯递归子程序程序:nT,ST|procedure T;begin if sym=,then begin advance;S;T end End;第37页38CH.4.CH.4.练习题练习题1(P81.)1(P81.)(2)经改写后文法是否是经改写后文法是否是LL(1)?给出它预测分析表。给出它预测分析表。消左后文法消左后文法G1:Sa|(T)TST T,ST|(2)因为因为G1:文法不含左递归文法不含左递归;对对 Sa|(T)FIRST(a)=a,FIRST()=,FIRST(T)=(,集合互不相交且不含集合互不相交且不含;对对 T,ST|FIRST(,ST)=,FIRST()=,其交集为空。其交集为空。但但FIRST(T)=FIRST(,ST)FIRST()=，,然而，然而，FOLLOW(T)=)FIRST(T)=，,，二者，二者 不不相交。相交。所以，所以，G1是是LL(1)文法。文法。第38页39CH.4.CH.4.练习题练习题1(P81.)1(P81.)(2)结构结构G1预测分析表预测分析表:对对Sa|(T)对对TST FIRST(a)=a FIRST(ST)=a,(FIRST()=对对 T,ST|FIRST(T)=(FIRST(,ST)=,预测分析表预测分析表:FOLLOW(T)=)a (),#SSaSS(T)TTSTTSTTST TTT,ST/10/10第39页40CH4.CH4.1.(3)给出对符号串给出对符号串(a，)分析过程分析过程步骤步骤 符号栈符号栈 输入串输入串 动作动作,所用产生式所用产生式 .0#S (a,)#初始；初始；用用 S,(查表查表 1#)T(a,)#S(T),展开展开S 2#)T a,)#匹配匹配(；用用 T,a 查表查表 3#)TS a,)#TST,展开展开T;用用 S,a 查表查表 4#)Ta a,)#S a,展开展开S 5#)T ,)#匹配匹配a;用用T,查表查表 6#)TS,)#T,ST,展开展开T 7#)TS )#匹配匹配,；用用 S,查表查表 8#)T )#S,展开展开S 9#)T )#匹配匹配；用用 T,)查表查表 10#)#T,展展 开开T 11#匹配匹配)12#分析成功分析成功,结束分析结束分析第40页41CH.4.CH.4.练习题练习题3(P82.)3(P82.)n3.下面文法中下面文法中,哪些是哪些是LL(1),说明理由。说明理由。n(1)SABc A a|B b|。n解，解，因为因为 FOLLOW(S)=#文法不含左递归文法不含左递归;FIRST(S)=a,b,c 对对 Aa|候选式候选式FIRST集合互不相交集合互不相交;FIRST(A)但但,FOLLOW(A)=b,c FIRST(A)=a,二者不相交。二者不相交。Bb|其候选式其候选式FIRST集合互不相交集合互不相交;FIRST(B)但，但，FOLLOW(B)=c FIRST(B)=b,二者也不相交。二者也不相交。所以，文法是所以，文法是LL(1)文法。文法。第41页42CH.4.CH.4.练习题练习题3(P82.)3(P82.)n3.下面文法中下面文法中,哪些是哪些是LL(1),说明理由。说明理由。n(2)SAb A a|B|B b|。n解解(1)因为因为 FOLLOW(S)=#对对 Aa|B|;FIRST(S)=a,b FIRST(B)=b,与与FIRST()=相交相交;所以文法不是所以文法不是LL(1)文法。文法。n解解(2)对对 Aa|因为因为 FIRST(A)=a,b,，FOLLOW(A)=b,FOLLOW和和FIRST二者相交。二者相交。所以文法不是所以文法不是LL(1)文法。文法。第42页43CH.4.CH.4.练习题练习题3(P82.)3(P82.)n3.下面文法中下面文法中,哪些是哪些是LL(1),说明理由。说明理由。n(3)SABBA A a|B b|。n解，解，即使即使 FOLLOW(S)=#文法不含左递归文法不含左递归;FIRST(S)=a,b,对对 Aa|，其候选式，其候选式FIRST集合不相交集合不相交;对对 Bb|，其候选式，其候选式FIRST集合也不相交集合也不相交;但但 对对 Aa|（由 Bb|出发证实也可）FOLLOW(A)=a,b,#,FIRST(A)=a,二者相交。二者相交。所以，文法不是所以，文法不是LL(1)文法。文法。第43页44CH.4.CH.4.练习题练习题3(P82.)3(P82.)n3.下面文法中下面文法中,哪些是哪些是LL(1),说明理由。说明理由。n(4)SaSe|B BbBe|C CcCe|d。n解，解，因为因为 文法不含左递归文法不含左递归;对对 SaSe|B、BbBe|C 和和 CcCe|d 各产生式候选式各产生式候选式FIRST集合均不相交集合均不相交;即即 FIRST(aSe)FIRST(B)=；FIRST(bBe)FIRST(C)=；FIRST(cCe)FIRST(d)=；FIRST(S)=a,b,c,d ，FIRST(B)=b,c,d FIRST(C)=c,d 均不含均不含。所以，文法是所以，文法是LL(1)文法。文法。第44页程程 序序 设设 计计 语语 言言 Chapter 7.Chapter 7.语义分析和中语义分析和中间代码产生间代码产生/10/10第45页46P217-1na*（-b+c）后缀式：后缀式：ab-c+*na+b*（c+d/e）后缀式：后缀式：abcde/+*+n-a+b*（-c+d）后缀式：后缀式：a-bc-d+*+nnot A or not（C or not D）后缀式：后缀式：A not C D not or not orn（A and B）or（not C or D）后缀式：后缀式：A B and C not D or or/10/10第46页47P217-3n-（a+b）*（c+d）-（a+b+c）四元式序列：四元式序列：（1）(+，a，b，T1)（2）(-，T1，-，T2)（3）(+，c，d，T3)（4）(*，T2，T3，T4)（5）(+，a，b，T5)（6）(+，T5，c，T6)（7）(-，T4，T6，T7)/10/10第47页48P218-4n自下而上分析过程中把赋值语句自下而上分析过程中把赋值语句 A:=B*（-C+D）翻翻译译成成三三地地址址码码步骤：步骤：（参看（参看p179语义子程序）语义子程序）/10/10第48页n语法分析语法分析翻译过程：翻译过程：nA:=B*(-C+D)A:=E1*(-C+D)E1.place=k2 A:=E1*(-E2+D)E2.place=k3 A:=E1*(E3+D)A:=E1*(E3+E4)A:=E1*(E5)A:=E1*E6 A:=E7 S.产生一个新中间变量产生一个新中间变量T1E3.place=k5产生代码产生代码 k5:=uminus k3名字名字属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表符号表/10/10第49页50A:=B*(-C+D)三地址码三地址码k5:=uminus k3k6:=k5+k4k7:=k2*k6k1:=k7名字名字属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表符号表（参看（参看p179语义子语义子程序）程序）/10/10第50页51P218-6：用用7.4.2节方法，把节方法，把A or（B and not（C or D）翻译成四元式序列翻译成四元式序列100：（：（jnz，A，-，0）101：（：（j，-，-，102）102：（：（jnz，B，-，104）103：（：（j，-，-，0）104：（：（jnz，C，-，.）105：（：（j，-，-，106）106：（：（jnz，D，-，.）107：（：（j，-，-，.）TCFC/10/10第51页52P218-7100：（：（j，A，C，102）101：（：（j，-，-，115）102：（：（j，B，D，104）103：（：（j，-，-，115）104：（：（j=，A，1，106）105：（：（j，-，-，109）106：（：（+，C，1，T1）107：（：（:=，T1，-，C）108：（：（j，-，-，100）109：（：（j，A，D，111）110：（：（j，-，-，100）111：（：（+，A，2，T2）112：（：（:=，T2，-，A）113：（：（j，-，-，109）114：（：（j，-，-，100）115：用用7.5.1节方法，把下面节方法，把下面语句翻译成四元式序列：语句翻译成四元式序列：while A C and B D do if A=1 then C:=C+1 else while A D do A:=A+2;/10/10第52页程程 序序 设设 计计 语语 言言 Chapter 8.Chapter 11./10/10第53页54CH8.CH8.CH11.CH11.n1.什么是符号表？符号表有哪些主要作用？什么是符号表？符号表有哪些主要作用？n2.符符号号表表表表项项常常包包含含哪哪些些部部分分？各各描描述述什什么么？n3.有有哪哪些些存存放放分分配配策策略略？并并叙叙述述何何时时用用何何种种存放分配策略？存放分配策略？n4.代码优化惯用办法和优化三个层次。代码优化惯用办法和优化三个层次。/10/10第54页程程 序序 设设 计计 语语 言言 补充题补充题/10/10第55页56补充题补充题n1.画画出出编编译译程程序序总总体体逻逻辑辑结结构构图图，简简述述各各部部分主要功效。分主要功效。/10/10第56页57补充题补充题n2.已知文法已知文法GZ:Z0U|1V U1Z|1 V0Z|0n请写出此文法描述只含有个符号全部句子。请写出此文法描述只含有个符号全部句子。nGZ产生语言是什么？产生语言是什么？n该文法在该文法在Chomsky文法分类中属于几型文法？文法分类中属于几型文法？/10/10第57页58【解】【解】n（1）0101，0110，1010，1001n（2）分分析析GZ所所推推导导出出句句子子特特点点：由由Z开开始始推推导导不不外乎图外乎图1所表示四种情形。所表示四种情形。由由Z推推导导出出10或或01后后就就终终止止或或进进入入递递归归，而而Z每每次次递递归归将将推推导导出出相相同同符符号号串串：10或或01。所所以以GZ产产生生语语言言L(GZ)=x|x(10|01)+n(3)该文法属于该文法属于3型文法。型文法。Z0U|1V U1Z|1V0Z|0/10/10第58页59补充题补充题n3.已已知知文文法法和和它它LR分分析析表表以以下下，给给出出串串dbdb#LR分析过程。分析过程。GS：(1)SAdB (2)Aa (3)A (4)Bb (5)BBdb (6)BACTIONACTIONGOTOGOTOa ad db b#S SA AB B0 0s3s3r3r31 12 21 1accacc2 2s4s43 3r2r24 4r6r6s5s5r6r66 65 5r4r4r4r46 6s7s7r1r17 7s8s88 8r5r5r5r5LR分析表分析表/10/10第59页60【解】【解】n串串dbdb#LR分析过程以下：分析过程以下：步步骤骤状状态态符号符号输输入串入串n下一步动作下一步动作0 0 0 0#dbdb#dbdb#r3 归约归约1 10202#A#Adbdb#dbdb#s4 移进移进2 2024024#Ad#Adbdb#bdb#s5 移进移进3 302450245#Adb#Adbdb#db#r4 归约归约4 402460246#AdB#AdBdb#db#s7 移进移进5 50246702467#AdBd#AdBdb#b#s8 移进移进6 6024678024678#AdBdb#AdBdb#r5 归约归约9 902460246#AdB#AdB#r1 归约归约10100101#S#S#acc1111 停停/10/10第60页61补充题补充题n n4.给定文法和语义动作以下：给定文法和语义动作以下：A A aB print“0”aB print“0”A A c print“1”c print“1”B B Ab print“2”Ab print“2”问：按照以上语义子程序，问：按照以上语义子程序，aacbb aacbb 经翻经翻译后输出结果是什么？请给出翻译过程。译后输出结果是什么？请给出翻译过程。第61页62aacbbaacbb翻翻 译译 后后输输出出结结果果是是打打印印出出下下面面字字符符串：串：1bBcAAaBAabA A aB print“0”aB print“0”A A c print“1”c print“1”B B Ab print“2”Ab print“2”第62页63翻译过程和翻译结果翻译过程和翻译结果n语法分析语法分析：naacbbaacbb aaAbb(1)aaAbb(1)aaBb (2)aaBb (2)aAb (3)aAb (3)aB (4)aB (4)A (5)A (5).n翻译过程翻译过程：(1)(1)print“1”(2)(2)print“2”(3)(3)print“0”(4)(4)print“2”(5)(5)print“0”A A A A aB print aB print“0”“0”A A A A c print c print“1”“1”B B Ab print Ab print“2”“2”翻译结果：翻译结果：打印出字符串打印出字符串打印出字符串打印出字符串1 1/10/10第63页64补充题补充题n5.课课堂堂上上讲讲过过以以及及课课件件中中给给出出有有代代表表性例题都要性例题都要亲自动手独力做一遍亲自动手独力做一遍。n6.参参阅阅“编编译译原原理理_(V_jx_Summary_精简精简=完全完全)”/10/10第64页