编译BottomUp习题解答教学文案.docx
- 文档编号:2058459
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:10
- 大小:65.39KB
编译BottomUp习题解答教学文案.docx
《编译BottomUp习题解答教学文案.docx》由会员分享,可在线阅读,更多相关《编译BottomUp习题解答教学文案.docx(10页珍藏版)》请在冰点文库上搜索。
编译BottomUp习题解答教学文案
编译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→·aS,S→·bS,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.1SLR分析表
ACTION
GOTO
状态
a
b
#
S
0
S1
S2
3
1
S1
S2
r3
4
2
S1
S2
5
3
acc
4
r1
5
r2
注意到状态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…Xm应该构成活前缀,把输入串的剩余部分配上之后即应成为规范句型(如果整个输入串确实构成一个句子)。
因此,只要输入串的已扫描部分保持可归约成一个活前缀,那就意味着所扫描过的部分没有错误。
构造文法G的LR分析表4.2所列。
表4.2LR分析表
ACTION
GOTO
a
d
b
#
S
A
B
0
s3
r3
1
2
1
acc
2
s4
3
r2
4
r6
s5
r6
6
5
r4
r4
6
s7
r1
7
s8
8
r5
r5
串dbdb#的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’):
(1)S’→S
(2)S→iSeS
(3)S→iS
(4)S→a
构造此文法的LR(0)项目集规范族,识别该文法所产生的活前缀的DFA如图4.2所示。
注意到状态I4存在“移进-归约”冲突,计算FOLLOW集合:
FOLLOW(S)={e,#}
当LR分析器处于状态4时,如果下一输入符号是“#”,则按S→iS归约;如果下一输入符号是“e”,则既可以按S→iS归约,也可以执行移入。
根据程序设计语言的要求,条件语句的else子句应当和最近的没有else子句的if语句匹配,根据这一要求,我们规定:
当LR分析器处于状态4时,如果下一输入符号是“#”,则按S→iS归约;如果下一输入符号是“e”,则执行移入。
构造SLR
(1)分析表如表4.3所列。
表4.3 SLR
(1)分析表
ACTION
GOTO
i
e
a
#
S
0
s2
s3
1
1
acc
2
s2
s3
4
3
r3
r3
4
s5
r2
5
s2
s3
6
6
r1
r1
4、设下列文法生成变量的类型说明:
D→idL
L→,idL|:
T
T→integer|real
构造一个翻译模式,把每个标识符的类型存入符号表。
解题思路
这是一个对说明语句进行语义分析的题目,不需要产生代码,但要求把每个标识符的类型填入符号表中。
解答
对D,L,T设置综合属性type。
过程addtype(id,type)用来把标识符id及其类型type填入到符号表中。
翻译模式如下:
D→idL {addtype(id.entry,L.type)}
L→,idL1{addtype(id.entry,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个运算对象输出类型转换算符时就已经为时太晚。
还要注意的是,在E+T向E归约时,该加法运算的第1个运算对象已经输出。
所以E→E+T的语义规则不需要有输出E运算对象的动作。
解答
(1)为文法符号E和T配以综合属性type,用来表示它们的类型。
类型值分别用int和real来表示。
确定每个子表达式结果类型的属性文法如下:
产生式
语义规则
E→E1+T
{T.type:
=ifE1.type=intandT.type=intthenintelsereal
E→T
{E.type:
=T.type}
T→num.num
T.type:
=real
T→num
T.type:
=int
(2)下面属性文法将表达式的后缀表示打印输出,其中lexeme属性表示单词的拼写。
产生式
语义规则
E→E1+T
ifE1.type=realandT.type=intthen
begin
E.type:
=real;
print(T.lexeme);
print(‘inttoreal’);
end
elseifE1.type=intandT.type=realthen
begin
E.type:
=real;
print(‘inttoreal’);
print(T.lexeme);
end
elsebegin
E.type:
=E1.type;
print(T.lexeme);
end
print(‘+’);
E→T
E.type:
=T.type;print(T.lexeme);
T→num.num
T.type:
=real;T.lexeme:
=num1.lexeme||“.”||num2.lexeme
T→num
T.type:
=int;T.lexeme:
=num.lexeme;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 BottomUp 习题 解答 教学 文案