编译TopDown╲tBottomUp习题解答.doc

1、已知文法G(S)：SaS|bS|a(1)构造该文法的LR(0)项目集规范族(2)构造识别该文法所产生的活前缀的DFA。(3)构造其SLR分析表，并判断该文法是否是SLR(1)文法。解题思路构造LR(0)项目集规范族，有两种方法：一种是利用有限自动机来构造，另一种是利用函数CLOSURE和GO来构造。本题采取第2种方法，通过计算函数CLOSURE和GO得到文法的LR(0)项目集规范族，而GO函数则把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA。解答(1)将文法G(S)拓广为G(S)：(0)SS(1)SaS(2)SbS(3)Sa构造该文法的LR(0)项目集规范族：I0=CLOSURE(S S)=S S, SaS, SbS, SaI1=GO( I0 , a)=CLOSURE(SaS , Sa)=SaS , Sa , SaS, SbS, Sa I2=GO(I0 , b)=CLOSURE(SbS )= SbS, SaS, SbS, Sa I3=GO(I0 , S)=CLOSURE(S S)= S SGO(I1, a)=CLOSURE(SaS , Sa)=I1GO(I2, b)=CLOSURE(SbS)=I2I4=GO(I1, S)=CLOSURE(SaS)=SaSGO(I2, a)= CLOSURE(SaS , Sa)=I1GO(I2, b)= CLOSURE(SbS)=I2I5=GO(I2, S)=CLOSURE(SbS)= SbS所以，项目集I0，I1，I2，I3，I4和I5构成了该文法的LR(0)项目集规范族。(2)我们用GO函数把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA如图4.1所示。(3)构造其SLR分析表。表4.1 SLR分析表ACTIONGOTO状态ab#S0S1S231S1S2r342S1S253acc4r15r2注意到状态I1存在“移进-归纳”冲突，计算S的FOLLOW集合：FOLLOW(S)=#可以采用SLR冲突消解法，得到表4.1所列的SLR分析表。从分析表可以看出，表中没有冲突项，所以该文法是SLR(1)文法。2、证明AdBd是文法G(S)的活前缀。说明活前缀在LR分析中的作用。给出串dbdb#的LR分析过程。G(S)：(1) SAdB (2)Aa (3) A (4) Bb (5)BBdb (6)B解题思路所谓活前缀是指规范句型的一个前缀，这种前缀不句柄之后的任何符号。根据此定义，直接证明AdBd是文法G(S)的活前缀。解答存在下面的规范推导：可见AdBdb是文法G的规范句型，AdBd是该规范句型的前缀。另外，在该规范句型中Bdb是句柄，前缀是AdBd不含句柄Bdb之后的任何符号，所以AdBd是文法G(S)的活前缀。在LR分析工作过程中的任何时候，栈里的方法符号(自栈底而上)X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型(如果整个输入串确实构成一个句子)。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。构造文法G的LR分析表 4.2所列。表4.2 LR分析表ACTIONGOTOadb#SAB0s3r3121acc2s43r24r6s5r665r4r46s7r17s88r5r5串dbdb#的LR分析过程如下：步骤状态符号输入串00#dbdb#102#Adbdb#2024#Adbdb#30245#Adbdb#40246#AdBdb#502467#AdBdb#6024678#AdBdb#90246#AdB#1001#S# acc3、根据程序设计语言的一般要求，为定义条件语句的二义文法G(S)构造SLR(1)分析表，要求 写出步骤和必要的说明。G(S): SiSeS|iS|a解答将文法G(S)拓广为G(S)：(0) S S(1) SiSeS(2) SiS(3) Sa构造此文法的LR(0)项目集规范族，识别该文法所产生的活前缀的DFA如图4.2所示。注意到状态I4存在“移进归约”冲突，计算FOLLOW集合：FOLLOW（S）e，#当LR分析器处于状态4时，如果下一输入符号是“”，则按SiS归约；如果下一输入符号是“e”，则既可以按SiS归约，也可以执行移入。根据程序设计语言的要求，条件语句的else子句应当和最近的没有else子句的if语句匹配，根据这一要求，我们规定：当LR分析器处于状态4时，如果下一输入符号是“”，则按SiS归约；如果下一输入符号是“e”,则执行移入。构造SLR（1）分析表如表4.3所列。表4.3SLR（1）分析表ACTIONGOTOiea#S0s2s311acc2s2s343r3r34s5r25s2s366r1r14、设下列文法生成变量的类型说明： D id L L , id L | : T T integer | real 构造一个翻译模式，把每个标识符的类型存入符号表。解题思路这是一个对说明语句进行语义分析的题目，不需要产生代码，但要求把每个标识符的类型填入符号表中。解答对D，L，T设置综合属性type。过程addtype(id,type)用来把标识符id及其类型type填入到符号表中。翻译模式如下：D id Laddtype(id.entry,L.type)L ,id L1 addtype(id.entry,L1.type);L.type:=L1.type;L : T L.type:=T.typeT integer T.type:=intergerT real T.type:=real5、文法G的产生式如下： S (L) | a L L , S | S (1)试写出一个语法制导定义，它输出配对括号个数; (2)写一个翻译方案，打印每个a的嵌套深度。如(a),a),打印2,1。解题思路本题包括两部分，第1部分要求写语法制导定义，第2部分要求写翻译方案。语法制导定义（或属性文法）可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。翻译方案（也称翻译模式）给出了使用语义规则进行计算的次序，把某些实现细节表示出来。读者从下面解答中可体会两者的区别。解答（1） 为S、L引入属性h,代表配对括号个数。语法制导定义如下：产生式语义规则S (L)S.h:=L.h+1S aS.h:=0L L1 , SL.h:=L1.h+S.hL SL.h:=S.hSSprint(S.h)(2)为S、L引入d，代表a的嵌套深度。翻译方案如下：SS.d:=0;SS (L.d:=S.d+1; L )S aprint(S.d);L L1.d:=L.d; L1 S.d:=L.d; SL S.d:=L.d S6、下列文法对整型常数和实型常数施用 加法运算符“+”生成表达式;当两个整型数相加时，结果仍为整型数，否则，结果为实型数： E E+T | T T num.num | num (1)试给出确定每个子表达式结果类型的属性文法。 (2)扩充(1)的属性文法，使之把表达式翻译成后缀形式，同时也能确定结果的类型。应该注意使用一元运算符inttoreal把整型数转换成实型数，以便使后缀形如加法运算符的两个操作数具有相同的类型。解题思路确定每个子表达式结果类型的属性文法是比较容易定义的。关键是如何扩充此属性文法，使之把表达式翻译成后缀形式。我们将不在name或num.num向T归约的时候输出该运算对象，而是把运算对象的输出放在T或ET向E归约的时候。这是因为考虑输出类型转换算符inttoreal的动作可能在ET归约的时候进行，如果这时两个运算对象都在前面name或num.num向T归约的时候已输出，需要为第1个运算对象输出类型转换算符时就已经为时太晚。还要注意的是，在ET向E归约时，该加法运算的第1个运算对象已经输出。所以EET的语义规则不需要有输出E运算对象的动作。解答（1）为文法符号E和T配以综合属性type,用来表示它们的类型。类型值分别用int和real来表示。确定每个子表达式结果类型的属性文法如下：产生式语义规则EE1TT.type:=if E1.type=int and T.type=int then int else realETE.type:=T.typeTnum.numT.type:=realTnumT.type:=int(2)下面属性文法将表达式的后缀表示打印输出，其中lexeme属性表示单词的拼写。产生式语义规则EE1Tif E1.type=real and T.type=int then begin E.type:=real; print(T.lexeme); print(inttoreal); endelse if E1.type=int and T.type=real then begin E.type:=real; print(inttoreal); print(T.lexeme); endelse beginE.type:=E1.type;print(T.lexeme);endprint(+);ETE.type:=T.type;print(T.lexeme);Tnum.numT.type:=real;T.lexeme:=num1.lexeme|“.”|num2.lexemeTnumT.type:=int;T.lexeme:=num.lexeme;1: 构造如下给定的文法的预测分析表S ABA Ba B Db | D D d | 解: 因为原文法存在左因子先消除作因子：将A的产生式代入SS BaB|B提取左因子 S BA A aB 引入非终结符号B DB B b | 消除无用的产生式 A Ba | 得到文法：S BAA aB | B DBB b|D d |FIRST(D)=d, FIRST(B)=b, FIRST(B)=b,d , FIRST(A)=a, FIRST(S)=a,b,d, FIRST(BA)= a,b,d, FIRST(aB)=a FIRST(DB)=b,d ,FOLLOW(S)=# FOLLOW(A)=# FOLLOW(B)=a,# FOLLOW(B)=a,# FOLLOW(D)=a,b,# 改写后文法的预测分析表:abd#SS BAS BAS BAS BA AAaBA BB DBB DBB DBB DB BB B bB DD D D dD 因为预测分析表无冲突，所以改写后的文法是LL（1）文法。2：判断下列文法可否改写为LL（1）文法：S A|BA a A |a B bB | b 因为有左因子.所以原文法不是LL（1）文法.改写文法，提取左因子，提取文法：S A|BA a A | A A| B bBB B|求FIRSTT 集和FOLLOW 集FIRST(B)=b FIRST(B)=b, FIRST(B)=b,d , FIRST(A)=a, FIRST(A)=a FIRST(S)= a,b FIRST(aB)=a FIRST(DB)=b,d ,FOLLOW(S)=# FOLLOW(A)=FOLLOW(A)=FOLLOW(B)= FOLLOW(B)=# 因为：FIRST(A) FIRST(B)FIRST(A) FIRST(A) FIRST(A)FIRST(B) FOLLOW(B) FIRST(B)所以 改写后的文法是LL（1）文法。3:S i | (E)E E+S | E-S | S解:因为原文法有左递归和左因子.所以不是LL(1) 文法.先消去E的产生式中的左递归:E SEE +SE|-SE|得到文法:S i | (E)E SEE +SE|-SE|求 FIRST( )集 和FOLLOW( )集FIRST( S)=i,( FIRST(E )= FIRST(SE )= i,(FIRST(E)=+, FOLLOW(S )+,-,),#FOLLOW(E )FOLLOW(E )FIRST(i ) FIRST(E) )=FIRST(+SE ) FIRST(-SE )= FIRST(+SE ) FIRST(-SE )FOLLOW(E ) FIRST(+SE ), FIRST(-SE )所以改写后的文法是LL(1) 文法.4: 求以下文法中各个非终结符号的FIRST( )集 和FOLLOW( )集 A baB|B Abb|a解: FIRST( A)=b, FIRST(B ) =a,bFOLLOW(A ) =b,# FOLLOW(B) = b,#改写文法消除左递归:M MaH |HH b(M) | (M)|b解引入M得到文法:M HMM aHM|H b(M) | (M)|b此文法中不含左递归,但是关于H的产生式中含左因子,提取左因子得到文法:M HMM aHM|H bH| (M)H (M)| 五: 构造如下给定文法的递归子程序:Sa | | (T)T T, S | S解: 引入T,消除左递归得到文法 Sa | | (T)T STT ,ST|FIRST( S)=a, , ( FIRST( T)= FIRST( S)FIRST( T)=,FOLLOW(S ),),#FOLLOW(T )FOLLOW(T )=)因为 FIRST( a ) ,FIRST(),FIRST( (T) 两两相交为FIRST( ,ST) FOLLOW(T )= FIRST( ,ST)所以改写后的文法是LL(1) 文法.语法图:a() T S TST S,T将T代入T 化简得到:, S TS的递归子程序:Procedure S Begin If lookhead=a then match(a); Else if lookhead