编译Bottom-Up习题解答
1、已知⽂法G(S)：
S→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
(1)S→aS
(2)S→bS
比赛获奖感言(3)S→a
构造该⽂法的LR(0)项⽬集规范族：
I0=CLOSURE({S→·S})={S’ →·S, S→·aS, S→·bS, S→·a}
I1=GO( I0, a)=CLOSURE({S→a·S , S→a·})={S→a·S , S→a·, S→·a S, S→·b S, S→·a }
I2=GO(I0 , b)=CLOSURE({S→b·S })={ S→b·S, S→·aS,S→·bS, S→·a } I3=GO(I0 , S)=CLOSURE({S’ →S·})={ S’ →S·}
GO(I1, a)=CLOSURE({S→a·S , S→a·})=I1
现代管理理论GO(I2, b)=CLOSURE({S→b·S})=I2
I4=GO(I1, S)=CLOSURE({S→aS·})={S→aS·}
GO(I2, a)= CLOSURE({S→a·S , S→a·})=I1
GO(I2, b)= CLOSURE({S→b·S})=I2
I5=GO(I2, S)=CLOSURE({S→bS·})={ S→bS·}
南京大屠杀手抄报所以，项⽬集I0，I1，I2，I3，I4和I5构成了该⽂法的LR(0)项⽬集规范族。
(2)我们⽤GO函数把LR(0)项⽬集规范族连成⼀个识别该⽂法所产⽣的活前缀的DFA如图4.1所⽰。
(3)构造其SLR分析表。
表4.1 SLR分析表
注意到状态I1存在“移进-归纳”冲突，计算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→ε
(4) B→b (5)B→Bdb (6)B→ε
思量的近义词所谓活前缀是指规范句型的⼀个前缀，这种前缀不句柄之后的任何符号。根据此定义，直接证明AdBd是⽂法G(S)的活前缀。
解答
存在下⾯的规范推导：
可见AdBdb是⽂法G的规范句型，AdBd是该规范句型的前缀。另外，在该规范句型中Bdb 是句柄，前缀是AdBd不含句柄Bdb 之后的任何符号，所以AdBd是⽂法G(S)的活前缀。
在LR分析⼯作过程中的任何时候，栈⾥的⽅法符号(⾃栈底⽽上)X1X2…X m应该构成活前缀，把输⼊串的剩余部分配上之后即应成为规范句型(如果整个输⼊串确实构成⼀个句⼦)。因此，只要输⼊串的已扫描部分保持可归约成⼀个活前缀，那就意味
着所扫描过的部分没有错误。
构造⽂法G的LR分析表4.2所列。
表4.2 LR分析表
步骤状态符号输⼊串
0 0 # dbdb#籍贯就是户口所在地吗
1 02 #A dbdb#
2 024 #Ad bdb#
3 0245 #Adb db#
4 0246 #AdB db#
5 02467 #AdBd b#
6 024678 #AdBdb #
9 0246 #AdB #
10 01 #S # acc 3、根据程序设计语⾔的⼀般要求，为定义条件语句的⼆义⽂法G(S)构造SLR(1)分析表，要求写出步骤和必要的说明。
G(S): S→iSeS|iS|a
解答
将⽂法G(S)拓⼴为G(S’)：
千里江陵(0)S’→S
(1)S→iSeS
(3)S→a
构造此⽂法的LR(0)项⽬集规范族，识别该⽂法所产⽣的活前缀的DFA如图4.2所⽰。
注意到状态I4存在“移进－归约”冲突，计算FOLLOW集合：
FOLLOW（S）＝｛e，#｝
当LR分析器处于状态4时，如果下⼀输⼊符号是“＃”，则按S→iS归约；如果下⼀输⼊符号是“e”，则既可以按S→iS归约，也可以执⾏移⼊。根据程序设计语⾔的要求，条件语句的el⼦句应当和最近的没有el⼦句的if语句匹配，根据这⼀要求，我们规定：当LR分析器处于状态4时，如果下⼀输⼊符号是“＃”，则按S→iS归约；如果下⼀输⼊符号是“e”，则执⾏移⼊。构造SLR（1）分析表如表4.3所列。
D → id L
L → , id L | : T
T → integer | real
构造⼀个翻译模式，把每个标识符的类型存⼊符号表。
解题思路
这是⼀个对说明语句进⾏语义分析的题⽬，不需要产⽣代码，但要求把每个标识符的类型填⼊符号表中。
解答
对D，L，T设置综合属性type。过程addtype(id,type)⽤来把标识符id及其类型type填⼊到符号表中。
翻译模式如下：
D → id L ｛,L.type)｝
L → ,id L1 {,L1.type);L.type:=L1.type;}
L → : T {L.type:=T.type}
T → integer {T.type:=interger}
T → real {T.type:=real}
5、⽂法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+1
S → a S.h:=0
L → L1 , S L.h:=L1.h+S.h
L → S L.h:=S.h
S’→S print(S.h)
(2)为S、L引⼊d，代表a的嵌套深度。翻译⽅案如下：
S’→｛S.d:=0;｝S
S →‘(’{L.d:=S.d+1;}
L
‘)’
S →a{print(S.d);}
L → {L1.d:=L.d;}
L1
{S.d:=L.d;}
S
L → {S.d:=L.d}
S
6、下列⽂法对整型常数和实型常数施⽤加法运算符“+”⽣成表达式；当两个整型数相加时，结果仍为整型数，否则，结果为实型数：
E → E+T | T
T → num.num | num
(1)试给出确定每个⼦表达式结果类型的属性⽂法。
(2)扩充(1)的属性⽂法，使之把表达式翻译成后缀形式，同时也能确定结果的类型。应该注意使⽤⼀元运算符inttoreal把整型数转换成实型数，以便使后缀形如加法运算符的两个操作数具有相同的类型。
解题思路
确定每个⼦表达式结果类型的属性⽂法是⽐较容易定义的。关键是如何扩充此属性⽂法，使之把表达
式翻译成后缀形式。我们将不在name或num.num向T 归约的时候输出该运算对象，⽽是把运算对象的输出放在T或E＋T向E归约的时候。这是因为考虑输出类型转换算符inttoreal的动作可能在E＋T归约的时候进⾏，如果这时两个运算对象都在前⾯name或num.num向T归约的时候已输出，需要为第1个运算对象输出类型转换算符时就已经为时太晚。
