《编译Bottom-Up习题解答》由会员分享，可在线阅读，更多相关《编译Bottom-Up习题解答（7页珍藏版）》请在金锄头文库上搜索。
1、1、已知文法 G(S)： SaS|bS|aSaS|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
2、SS(1)SaSaS(2)SbSbS(3)Saa构造该文法的 LR(0)项目集规范族：I0=CLOSURE(S S)=S S, SaS, SbS, SaI1=GO( I0 , a)=CLOSURE(SaaS , Saa)=SaaS , Saa , SaS, SbS, Sa I2=GO(I0 , b)=CLOSURE(SbbS )= SbbS, SaS, SbS, Sa I3=GO(I0 , S)=CLOSURE(S S)= S SGO(I1, a)=CLOSURE(SaaS , Saa)=I1GO(I2, b)=CLOSURE(SbbS)=I2I4=GO(I1, S)=CLOSURE(SaS)
3、=SaSGO(I2, a)= CLOSURE(SaaS , Saa)=I1GO(I2, b)= CLOSURE(SbbS)=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 分析表分析表ACTIONGO
4、TO状态状态ab#S0S1S231S1S2r342S1S253acc4r15r2注意到状态注意到状态 I1存在存在“移进移进-归纳归纳”冲突，计算冲突，计算 S 的的 FOLLOW 集合：集合： FOLLOW(S)=# 可以采用可以采用 SLR 冲突消解法，得到表冲突消解法，得到表 4.1 所列的所列的 SLR 分析表。分析表。 从分析表可以看出，表中没有冲突项，所以该文法是从分析表可以看出，表中没有冲突项，所以该文法是 SLR(1)文法。文法。 2、证明、证明 AdBd 是文法是文法 G(S)的活前缀。说明活前缀在的活前缀。说明活前缀在 LR 分析中的作用。给出串分析中的作用。给出串 dbd
5、b#的的 LR 分析过程。分析过程。G(S)：(1) SAdBAdB (2)Aa(2)Aa (3)(3) AA(4)(4) BbBb (5)BBdb(5)BBdb (6)B(6)B 解题思路解题思路 所谓活前缀是指规范句型的一个前缀，这种前缀不句柄之后的任何符号。 根据此定义，直接证明 AdBd 是文法 G(S)的活前缀。 解答解答 存在下面的规范推导：可见 AdBdb 是文法 G 的规范句型，AdBd 是该规范句型的前缀。另外，在该规范句型中 Bdb 是句柄，前缀是 AdBd 不含句柄 Bdb 之后的任何符号，所以 AdBd 是文法 G(S)的活前 缀。 在 LR 分析工作过程中的任何时候，
6、栈里的方法符号(自栈底而上)X1X2Xm应该构成 活前缀，把输入串的剩余部分配上之后即应成为规范句型(如果整个输入串确实构成一个句 子)。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部 分没有错误。 构造文法 G 的 LR 分析表 4.2 所列。 表 4.2 LR 分析表ACTIONGOTOadb#SAB0s3r3121acc2s43r24r6s5r665r4r46s7r17s88r5r5串 dbdb#的 LR 分析过程如下： 步骤状态符号输入串00#dbdb# 102#Adbdb# 2024#Adbdb# 30245#Adbdb# 40246#AdBdb# 502
7、467#AdBdb# 6024678#AdBdb# 90246#AdB# 1001#S# acc 3、根据程序设计语言的一般要求，为定义条件语句的二义文法、根据程序设计语言的一般要求，为定义条件语句的二义文法 G(S)构造构造 SLR(1)分析表，分析表， 要求要求 写出步骤和必要的说明。写出步骤和必要的说明。G(S): SiSeS|iS|aiSeS|iS|a解答 将文法 G(S)拓广为 G(S)：(0) S SS(1) SiSeSiSeS(2) SiSiS(3) Saa构造此文法的 LR(0)项目集规范族，识别该文法所产生的活前缀的 DFA 如图 4.2 所示。注意到状态 I4存在“移进归约
8、”冲突，计算 FOLLOW 集合： FOLLOW（S）e，#当 LR 分析器处于状态 4 时，如果下一输入符号是“” ，则按 SiSiS归约；如果下一 输入符号是“e” ，则既可以按 SiSiS 归约，也可以执行移入。根据程序设计语言的 要求，条件语句的 else 子句应当和最近的没有 else 子句的 if 语句匹配，根据 这一要求，我们规定：当 LR 分析器处于状态 4 时，如果下一输入符号是“” ， 则按SiSiS 归约；如果下一输入符号是“e”,则执行移入。构造 SLR（1）分析 表如表 4.3 所列。 表 4.3 SLR（1）分析表 ACTIONGOTO iea#S 0s2s31 1
9、acc 2s2s34 3r3r3 4s5r2 5s2s366r1r1 4 4、设下列文法生成变量的类型说明：、设下列文法生成变量的类型说明：D D idid L LL L , , idid L L | | : : T TT T integerinteger | | realreal构造一个翻译模式，把每个标识符的类型存入符号表。构造一个翻译模式，把每个标识符的类型存入符号表。 解题思路解题思路 这是一个对说明语句进行语义分析的题目，不需要产生代码，但要求把每 个标识符的类型填入符号表中。 解答解答 对 D，L，T 设置综合属性 type。过程 addtype(id,type)用来把标识符 id
10、 及其类型 type 填入到符号表中。 翻译模式如下： D D idid L L addtype(id.entry,L.type)addtype(id.entry,L.type) L L ,id,id L1L1 addtype(id.entry,L1.type);L.type:=L1.type;addtype(id.entry,L1.type);L.type:=L1.type; L L : : T T L.type:=T.typeL.type:=T.type T T integerinteger T.type:=intergerT.type:=interger T T realreal T.t
11、ype:=realT.type:=real 5 5、文法、文法 G G 的产生式如下：的产生式如下：S S (L)(L) | | a aL L L L , , S S | | S S(1)(1)试写出一个语法制导定义，它输出配对括号个数试写出一个语法制导定义，它输出配对括号个数; ;(2)(2)写一个翻译方案，打印每个写一个翻译方案，打印每个 a a 的嵌套深度。如的嵌套深度。如(a),a),(a),a),打印打印 2,12,1。 解题思路解题思路 本题包括两部分，第 1 部分要求写语法制导定义，第 2 部分要求写翻译方 案。语法制导定义（或属性文法）可以看作是关于语言翻译的高级规范说明， 其
12、中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。翻译方案 （也称翻译模式）给出了使用语义规则进行计算的次序，把某些实现细节表示 出来。读者从下面解答中可体会两者的区别。 解答 （1） 为 S、L 引入属性 h,代表配对括号个数。语法制导定义如下： 产生式语义规则 S S (L)(L)S.h:=L.h+1 S S a aS.h:=0 L L L1L1 , , S SL.h:=L1.h+S.h L L S SL.h:=S.hSSSprint(S.h)(2)为 S、L 引入 d，代表 a 的嵌套深度。翻译方案如下：SS.d:=0;S.d:=0;S SS S (L.d:=S.d+1;(L.d
13、:=S.d+1;L L)S S aprint(S.d);aprint(S.d); L L L1.d:=L.d;L1.d:=L.d;L1L1S.d:=L.d;S.d:=L.d;S S L L S.d:=L.dS.d:=L.dS S 6 6、下列文法对整型常数和实型常数施用、下列文法对整型常数和实型常数施用 加法运算符加法运算符“+”“+”生成表达式生成表达式; ;当两个当两个 整型数相加时，结果仍为整型数，否则，结果为实型数：整型数相加时，结果仍为整型数，否则，结果为实型数：E E E+TE+T | | T T T T num.numnum.num | | numnum(1)(1)试给出确定每个
14、子表达式结果类型的属性文法。试给出确定每个子表达式结果类型的属性文法。(2)(2)扩充扩充(1)(1)的属性文法，使之把表达式翻译成后缀形式，同时也能确定结的属性文法，使之把表达式翻译成后缀形式，同时也能确定结 果的类型。应该注意使用一元运算符果的类型。应该注意使用一元运算符 inttorealinttoreal 把整型数转换成实型数，以便把整型数转换成实型数，以便 使后缀形如加法运算符的两个操作数具有相同的类型。使后缀形如加法运算符的两个操作数具有相同的类型。 解题思路 确定每个子表达式结果类型的属性文法是比较容易定义的。关键是如何扩 充此属性文法，使之把表达式翻译成后缀形式。我们将不在 n
15、ame 或 num.num 向 T 归约的时候输出该运算对象，而是把运算对象的输出放在 T 或 ET 向 E 归 约的时候。这是因为考虑输出类型转换算符 inttoreal 的动作可能在 ET 归约 的时候进行，如果这时两个运算对象都在前面 name 或 num.num 向 T 归约的时候 已输出，需要为第 1 个运算对象输出类型转换算符时就已经为时太晚。 还要注意的是，在 ET 向 E 归约时，该加法运算的第 1 个运算对象已经输 出。所以 EET 的语义规则不需要有输出 E 运算对象的动作。 解答 （1）为文法符号 E 和 T 配以综合属性 type,用来表示它们的类型。类型值分别 用 int 和 real 来表示。确定每个子表达式结果类型的属性文法如下： 产生式语义规则 EE1EE1T
