编译原理试题及答案(二)ppt课件

编译原理参考答案,程序设计语言,Chapter4.自上而下语法分析,2020/5/24,.,2,CH.4.练习题1(P81.),1.考虑下面文法G1:Sa|(T)TT，S|S(1)消去G1的左递归。然后对每个非终结符,写出不带回溯的递归子程序。,解(1)消左后的文法G1:Sa|(T)TSTT,ST|,.,3,CH.4.练习题1(P81.),解(1)不带回溯的递归子程序:Sa|(T)ProcedureS;Beginifsym=aorsym=thenadvanceelseifsym=(thenbeginadvance;T;ifsym=)thenadvanceelseerrorendelseerrorEnd;,.,4,CH.4.练习题1(P81.),解(1)不带回溯的递归子程序:TSTProcedureT;BeginS;Tend;,解(1)不带回溯的递归子程序:T,ST|procedureT;beginifsym=,thenbeginadvance;S;TendEnd;,.,5,CH.4.练习题1(P81.),(2)经改写后的文法是否是LL(1)的?给出它的预测分析表。消左后的文法G1:Sa|(T)TSTT,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)文法。,2020/5/24,.,6,CH.4.练习题1(P81.),(2)构造G1的预测分析表:对Sa|(T)对TSTFIRST(a)=aFIRST(ST)=a,(FIRST()=对T,ST|FIRST(T)=(FIRST(,ST)=,预测分析表:FOLLOW(T)=),.,7,CH4.1.(3)给出对符号串(a，)的分析过程,步骤符号栈输入串动作,所用产生式.0#S(a,)#初始；用S,(查表1#)T(a,)#S(T),展开S2#)Ta,)#匹配(；用T,a查表3#)TSa,)#TST,展开T;用S,a查表4#)Taa,)#Sa,展开S5#)T,)#匹配a;用T,查表6#)TS,)#T,ST,展开T7#)TS)#匹配,；用S,查表8#)T)#S,展开S9#)T)#匹配；用T,)查表10#)#T,展开T11#匹配)12#分析成功,结束分析,.,8,CH.4.练习题3(P82.),3.下面文法中,哪些是LL(1)的,说明理由。(1)SABcAa|Bb|。,解，因为FOLLOW(S)=#文法不含左递归;FIRST(S)=a,b,c对Aa|候选式的FIRST集合互不相交;FIRST(A)但,FOLLOW(A)=b,cFIRST(A)=a,两者不相交。Bb|其候选式的FIRST集合互不相交;FIRST(B)但，FOLLOW(B)=cFIRST(B)=b,两者也不相交。所以，文法是LL(1)文法。,.,9,CH.4.练习题3(P82.),3.下面文法中,哪些是LL(1)的,说明理由。(2)SAbAa|B|Bb|。,解(1)因为FOLLOW(S)=#对Aa|B|;FIRST(S)=a,bFIRST(B)=b,与FIRST()=相交;所以文法不是LL(1)文法。解(2)对Aa|因为FIRST(A)=a,b,，FOLLOW(A)=b,FOLLOW和FIRST两者相交。所以文法不是LL(1)文法。,.,10,CH.4.练习题3(P82.),3.下面文法中,哪些是LL(1)的,说明理由。(3)SABBAAa|Bb|。,解，虽然FOLLOW(S)=#文法不含左递归;FIRST(S)=a,b,对Aa|，其候选式的FIRST集合不相交;对Bb|，其候选式的FIRST集合也不相交;但对Aa|（由Bb|出发证明也可）FOLLOW(A)=a,b,#,FIRST(A)=a,两者相交。所以，文法不是LL(1)文法。,.,11,CH.4.练习题3(P82.),3.下面文法中,哪些是LL(1)的,说明理由。(4)SaSe|BBbBe|CCcCe|d。,解，因为文法不含左递归;对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,dFIRST(C)=c,d均不含。所以，文法是LL(1)文法。,编译原理参考答案,程序设计语言,Chapter7.语义分析和中间代码产生,2020/5/24,.,13,P217-1,a*（-b+c）后缀式：ab-c+*a+b*（c+d/e）后缀式：abcde/+*+-a+b*（-c+d）后缀式：a-bc-d+*+notAornot（CornotD）后缀式：AnotCDnotornotor（AandB）or（notCorD）后缀式：ABandCnotDoror,2020/5/24,.,14,P217-3,-（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),2020/5/24,.,15,P218-4,自下而上分析过程中把赋值语句A:=B*（-C+D）翻译成三地址码的步骤：（参看p179的语义子程序）,语法分析翻译过程：A:=B*(-C+D)A:=E1*(-C+D)E1.place=k2A:=E1*(-E2+D)E2.place=k3A:=E1*(E3+D)A:=E1*(E3+E4)A:=E1*(E5)A:=E1*E6A:=E7S,产生一个新的中间变量T1E3.place=k5产生代码k5:=uminusk3,k1K2k3k4k5k6k7,符号表,2020/5/24,.,17,A:=B*(-C+D)的三地址码,k5:=uminusk3k6:=k5+k4k7:=k2*k6k1:=k7,k1K2k3k4k5k6k7,符号表,（参看p179的语义子程序）,2020/5/24,.,18,P218-6：用7.4.2节的办法，把Aor（Bandnot（CorD）翻译成四元式序列,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，-，-，.）,2020/5/24,.,19,P218-7,100：（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节的办法，把下面的语句翻译成四元式序列：whileACandBDdoifA=1thenC:=C+1elsewhileADdoA:=A+2;,编译原理参考答案,程序设计语言,Chapter8.Chapter11.,2020/5/24,.,21,CH8.CH11.,1.什么是符号表？符号表有哪些重要作用？2.符号表的表项常包括哪些部分？各描述什么？3.有哪些存储分配策略？并叙述何时用何种存储分配策略？4.代码优化的常用措施和优化的三个层次。,编译原理参考答案,程序设计语言,补充题,2020/5/24,.,23,补充题,1.画出编译程序的总体逻辑结构图，简述各部分的主要功能。,2020/5/24,.,24,补充题,2.已知文法GZ:Z0U|1VU1Z|1V0Z|0请写出此文法描述的只含有个符号的全部句子。GZ产生的语言是什么？该文法在Chomsky文法分类中属于几型文法？,2020/5/24,.,25,【解】,（1）0101，0110，1010，1001（2）分析GZ所推导出的句子的特点：由Z开始的推导不外乎图1所示的四种情形。由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出相同的符号串：10或01。所以GZ产生的语言L(GZ)=x|x(10|01)+(3)该文法属于3型文法。,Z0U|1VU1Z|1V0Z|0,2020/5/24,.,26,补充题,3.已知文法和它的LR分析表如下，给出串dbdb#的LR分析过程。GS：(1)SAdB(2)Aa(3)A(4)Bb(5)BBdb(6)B,LR分析表,2020/5/24,.,27,【解】,串dbdb#的LR分析过程如下：,.,28,补充题,4.给定文法和语义动作如下：AaBprint“0”Acprint“1”BAbprint“2”问：按照以上的语义子程序，aacbb经翻译后的输出结果是什么？请给出翻译过程。,.,29,aacbb翻译后的输出结果是打印出下面的字符串：12020,AaBprint“0”Acprint“1”BAbprint“2”,2020/5/24,.,30,翻译过程和翻译结果,语法分析：aacbbaaAbb(1)aaBb(2)aAb(