编译Bottom-Up习题解答

1、1、已知文法G(S)：Sf aS|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)S' -S(i)SfaS(2

2、)S-bS(3)S-a构造该文法的LR(0) 项目集规范族：Io=CLOSURE(S 7 S户S3 S, S aS, S bS,腔 aIi=GO( Io , a尸CLOSURE(S-a S , S-a )=S-a S , S-a -,腔 aS,S bS, S aI2=GO( I。, b尸CLOSURE(S-b S )= S-b S, * aS=r bS, S 7 a a13=GO( I。, S)=CLOSURE( S' S= S' 7 S GO(11, a户CLOSURE(S -aS , Sa )=11GO(12, b)=CLOSURE( S-b S)=I2I4=GO(I i,

3、 S)=CLOSURE( * aS )=SaS GO(12, a)= CLOSURE(S -a S , Sa )=11GO(12, b)= CLOSURE( S-b S)=I2I5=GO(I 2, S)=CLOSURE(S -bS )= S-bS 所以，项目集Io, Il, I2, I3, I4和I5构成了该文法的LR(0)项目集规范族。(2)我们用GO 函数把 LR(0) 项目集规范族连成一个识别该文法所产生的活前缀的DFA 如图4.1 所示。图4识别活前缀的D卜A(3)构造其SLR分析表。表4.1 SLR分析表ACTIONGOTO状态ab#S0S1S231S1S2r342S1S253acc

4、4r15r2注意到状态Ii存在“移进-归纳”冲突，计算 S的FOLLOW 集合：FOLLOW(S)=#可以采用SLR冲突消解法，得到表 4.1所列的SLR分析表。从分析表可以看出，表中没有冲突项，所以该文法是SLR(1)文法。2、证明AdBd是文法G(S)的活前缀。说明活前缀在 LR分析中的作用。给出串 dbdb#的 LR分析过程。G(S)： (1) S-AdB (2)A-a (3) A - e(4) B -b (5)B -Bdb (6)B 一解题思路所谓活前缀是指规范句型的一个前缀，这种前缀不句柄之后的任何符号。根 据此定义，直接证明AdBd是文法G(S)的活前缀。解答存在下面的规范推导：S

5、 > AdB <> AdBdb可见AdBdb是文法G的规范句型，AdBd是该规范句型的前缀。 另外，在该规范句型中 Bdb 是句柄，前缀是 AdBd不含句柄Bdb之后的任何符号，所以 AdBd是文法G(S)的活前缀。在LR分析工作过程中的任何时候， 栈里的方法符号(自栈底而上)XiX2jXm应该构成活 前缀，把输入串的剩余部分配上之后即应成为规范句型(如果整个输入串确实构成一个句子)。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部 分没有错误。构造文法G的LR分析表4.2所列。表4.2 LR分析表ACTIONGOTOadb#SAB0s3r3121a

6、cc2s43r24r6s5r665r4r46s7r17s88r5r5串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)： S - iSeS|iS|a解答将文法G(S)拓广为G(S'):(0) S' -S(1) S-iSeS(2) S- iS(3)S一 a构造此

7、文法的LR(0)项目集规范族，识别该文法所产生的活前缀的DFA如图4.2所示。图4.2识别活前缀的DFA注意到状态I4存在“移进归约”冲突，计算 FOLLOW集合：FOLLOW (S) = e, #当LR分析器处于状态 4时，如果下一输入符号是“ #" ，则按S-iS归约；如果下一 输入符号是“ e”，则既可以按S-iS归约，也可以执行移入。根据程序设计语言的 要求，条件语句的else子句应当和最近的没有else子句的if语句匹配，根据 这一要求，我们规定：当LR分析器处于状态4时，如果下一输入符号是， 则按S-iS归约；如果下一输入符号是“ e”，则执行移入。构造SLR (1)分析

8、 表如表4.3所列。表4.3 SLR (1)分析表ACTIONGOTOiea#S0s2s311acc2s2s343r3r34s5r25s2s366r1r14、设下列文法生成变量的类型说明:D - id LL 一 , id L | : TT 一 integer | real构造一个翻译模式，把每个标识符的类型存入符号表。解题思路这是一个对说明语句进行语义分析的题目，不需要产生代码，但要求把每个 标识符的类型填入符号表中。解答对D, L, T设置综合属性type。过程addtype(id,type) 用来把标识符id及 其类型 type 填入到符号表中。翻译模式如下：D f id L addtyp

9、e(id.entry,L.type) L f ,id L1 addtype(id.entry,L1.type);L.type:=L1.type;L : T L.type:=T.typeT f integer T.type:=intergerT f real T.type:=real5、文法G的产生式如下：S - (L) | aL - L , S | S(1) 试写出一个语法制导定义，它输出配对括号个数;(2) 写一个翻译方案，打印每个a 的嵌套深度。如(a),a), 打印 2,1 。解题思路本题包括两部分，第 1 部分要求写语法制导定义，第 2 部分要求写翻译方案。语法制导定义(或属性文法)可

10、以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。翻译方案 (也称翻译模式) 给出了使用语义规则进行计算的次序，把某些实现细节表示出来。读者从下面解答中可体会两者的区别。解答( 1) 为S、 L 引入属性h, 代表配对括号个数。语法制导定义如下：产生式语义规则5 -(L)S.h:=L.h+16 -aS.h:=0L -L1 , SL.h:=L1.h+S.hL SL.h:=S.hS' -Sprint(S.h)(2)为S、L引入d,代表a的嵌套深度。翻译方案如下：S' - S.d:=0; SS - '(' L.d:=S.d

11、+1; L )S faprint(S.d);L L1.d:=L.d;L1S.d:=L.d; SL S.d:=L.dS6、下列文法对整型常数和实型常数施用加法运算符“+”生成表达式; 当两个整型数相加时，结果仍为整型数，否则，结果为实型数：E - E+T | TT f num.num | num(1) 试给出确定每个子表达式结果类型的属性文法。(2) 扩充 (1) 的属性文法，使之把表达式翻译成后缀形式，同时也能确定结果的类型。应该注意使用一元运算符inttoreal 把整型数转换成实型数，以便使后缀形如加法运算符的两个操作数具有相同的类型。解题思路确定每个子表达式结果类型的属性文法是比较容易定

12、义的。关键是如何扩充此属性文法，使之把表达式翻译成后缀形式。我们将不在name或num.num向T归约的时候输出该运算对象，而是把运算对象的输出放在T 或E T 向 E 归约的时候。这是因为考虑输出类型转换算符inttoreal的动作可能在E+ T归约的时候进行，如果这时两个运算对象都在前面 name或num.num向T归约的时候已输 出，需要为第1 个运算对象输出类型转换算符时就已经为时太晚。还要注意的是，在E T 向 E 归约时，该加法运算的第1 个运算对象已经输出。所以E-E+ T的语义规则不需要有输出E运算对象的动作。解答( 1)为文法符号E 和 T 配以综合属性type, 用来表示它

13、们的类型。类型值分别用 int 和 real 来表示。确定每个子表达式结果类型的属性文法如下：产生式语义规则E- E1 + TT.type:=if E1.type=int and T.type=int then int else realE- TE.type:=T.typeTf num.num T.type:=realTf num T.type:=int(2) 下面属性文法将表达式的后缀表示打印输出，其中 lexeme 属性表示单词的拼 写。产生式语义规则E- E1 + Tif E1.type=real and T.type=int thenbeginE.type:=real;print(T.lexeme);print( inttoreal ); endelse if E1.type=int and T.type=real then beginE.type:=real;print( inttoreal );