编译原理平时作业答案Word格式.doc
《编译原理平时作业答案Word格式.doc》由会员分享，可在线阅读，更多相关《编译原理平时作业答案Word格式.doc（21页珍藏版）》请在冰点文库上搜索。
（2）正则表达式:
1*01*01*01*
DFA
M=（{0，1}，{q0，q1，q2，q3}，q0，{q3}，δ）
δ（q1，1）=q1
δ（q2，0）=q3
δ（q2，1）=q2
δ（q3，1）=q3
3下面是用正规式表示的变量声明：
（int|float）id（,id）*;
请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。
D®
TL;
T®
int|float
L®
L,id|id
4试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else（悬而未决的-else）文法的二义性：
stmt→ifexprthenstmt
|matched-stmt
matched-stmt→ifexprthenmatched-stmtelsestmt
|other
试说明此文法仍然是二义性的。
考虑句子ifethenifethenotherelseifethenotherelseother它具有如下所示的两种分析树stmtexprtheneifstmtifmatched-stmtexprthenmatched-stmteotherifeslestmtmatched-stmtexprthenmatched-stmteothereslestmtmatched-stmtotherstmtmatched-stmtifexprthenmatched-stmteifeslestmteslestmtmatched-stmtexprthenestmtotherexprthenmatched-stmteotherifmatched-stmtother
则上面给出的if-then-else文法仍是二义性的。
5证明下面文法是SLR
（1）文法，并构造其SLR分析表。
E→E+T|T
T→TF|F
F→F*|a|b
该文法的拓广文法G'
为
（0）E'
→E
（1）E→E+T
（2）E→T
（3）T→TF
（4）T→F
（5）F→F*
（6）F→a
（7）F→b
其LR（0）项目集规范族和goto函数（识别活前缀的DFA）如下:
I0={E'
→·
E,E→·
E+T,E→·
T,T→·
TF,T→·
F,F→·
F*,
F→·
a,F→·
b}
I1={E'
→E·
E→E·
+T}I2={E→T·
T→T·
F*,F→·
b}
I3={T→F·
F→F·
*}I4={F→a·
}I5={F→b·
}
I6={E→E+·
b}I7={T→TF·
*}I8={F→F*·
}
I9={E→E+T·
求FOLLOW集：
FOLLOW（E）={＋,＄}
FOLLOW（T）={＋,＄,a,b}
FOLLOW（F）={＋,＄,a,b,*}
构造的SLR分析表如下：
显然，此分析表无多重定义入口，所以此文法是SLR文法。
6为下面的文法构造LALR
（1）分析表
S→E
E→E+T|T
T→（E）|a
其拓广文法G'
：
（0）S'
→S
（1）S→E
（2）E→E+T
（3）E→T
（4）T→（E）
（5）T→a
构造其LR
（1）项目集规范族和goto函数（识别活前缀的DFA）如下:
I0={[S’→·
S,$],[S→·
E,$],[E→·
E+T,$/+],[E→·
T,$/+],
[T→·
（E）,$/+],[T→·
a,$/+]}
I1={[S’→S·
$]}I2={[S→E·
$],[E→E·
+T,$/+]}I3={[E→T·
$/+]}
I4={[T→（·
E）,$/+],[E→·
E+T,）/+],[E→·
T,）/+],
（E）,）/+],[T→·
a,）/+]}
I5={[T→a·
$/+]}I6={[E→E+·
T,$/+],[T→·
a,$/+]}
I7={[T→（E·
）,$/+],[E→E·
+T,）/+]}I8={[E→T·
）/+]}
I9={[T→（·
E）,）/+},[E→·
T,）/+],[T→·
I10={[T→a·
）/+]}I11={[E→E+T·
$/+]}I12={[T→（E）·
I13={[E→E+·
a,）/+]}I14={[T→（E·
）,）/+],[E→E·
+T,）/+]}
I15={[E→E+T·
）/+]}I16={[T→（E）·
合并同心的LR
（1）项目集，得到LALR的项目集和转移函数如下：
·
$]}I2={[S→E·
+T,$/+]}I3,8={[E→T·
$/+/）]}
I4,9={[T→（·
E）,$/+/）],[E→·
I5,10={[T→a·
$/+/）]}I6,13={[E→E+·
T,$/+/）],[T→·
（E）,$/+/）],[T→·
a,$/+/）]}
I7,14={[T→（E·
）,$/+/）],[E→E·
+T,）/+]}I11,15={[E→E+T·
$/+/）]}
I12,16={[T→（E）·
LALR分析表如下：
7
（1）通过构造识别活前缀的DFA和构造分析表，来证明文法E®
E+id|id是SLR
（1）文法。
先给出接受该文法活前缀的DFA如下：
E¢
®
E
E®
E+id
id
I0
E·
+id
I1
id·
I2
+
E+·
I3
E+id·
I4
再构造SLR分析表如下：
状态
动作
转移
id+$
E
0
s2
1
s3acc
2
r2r2
3
s4
4
r1r1
表中没有多重定义的条目，因此该文法是SLR
（1）的。
（2）下面左右两个文法都和
（1）的文法等价
E®
E+Mid|id E®
ME+id|id
M®
e M®
e
请指出其中有几个文法不是LR
（1）文法，并给出它们不是LR
（1）文法的理由。
只有文法
不是LR
（1）文法。
因为对于句子id+id+…+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。
8 根据自上而下的语法分析方法，构造下面文法的LL
（1）分析表。
D®
TL
T®
int|real
idR
R®
idR|e
先计算FIRST和FOLLOW
FIRST（D）=FIRST（T）={int,real}
FIRST（L）={id}
FIRST（R）={,,ε}
FOLLOW（D）=FOLLOW（L）={$}
FOLLOW（T）={id}
FOLLOW（R）={$}
LL
（1）分析表如下：
int
real
$
D
D->
T
T->
int
real
L
L->
idR
R
R->
idR
ε
9下面的文法产生的表达式是对整型和实型常数应用算符+形成的。
当两个整数相加时，结果仍为整数，否则就是实数。
T→num.num|num
（a）给出一个语法制导定义以确定每个子表达式的类型。
（b）扩充（a）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。
使用一元算符inttoreal把整型值转换成相等的实型值，以使得前缀形式中的+的两个操作对象是同类型的。
（a）:
产生式
语义规则
Eà
E1+T
IF（E1.type=integer）and（T.type=integer）THEN
E.type:
=integer
ELSE
=real
E.type:
=T.type
Tà
num.num
T.type:
num
（b）:
BEGIN
Print（‘+’,E1.val,T.val）
END
ELSEBEGIN
IFE1.type=integerTHEN
Begin
E1.type:
E1.val:
=inttoreal（E1.val）
End
IFT.type:
=integerTHEN
Begin
T.type:
T.val:
=inttoreal（T.val）
END
E.val:
=T.val
T.val:
=num.num.lexval
=num.lexval
10假设说明是由下列文法产生的：
D→idL
L→,idL|:
T
T→integer|real
（a）建立一个翻译模式，把每一个标识符的类型加入到符号表中。
（b）从（a）中的翻译模式构造一个预翻译程序。
（a）：
翻译模式
Dà
L
{D.Type:
=L.Type}
{addtype（id.entry,D.type）}
Là
id
L1
{L.Type:
=L1.Type}
{addtype（id.entry,L.type）}
:
{L.type:
=T.type}
integer
{T.type:
=integer}
=real}
（b）：
ProcedureD;
begin
Iflookahead=idthen
Begin
Match（id）;
D.type=L;
addtype（id.entry,D.type）
end
else
error
end
FunctionL:
DataType;
Iflookahead=’,’then
Match（‘,’）;
Iflookahead=idthen
begin
match（id）;
L.Type=L;
addtype（id.entry,L.type）;
return（L.type）
end
Else
End
Elseiflookahead=’:
’then
Match（‘:
’）;
L.Type=T;
return（L.Type）
end
else
error
End
FunctionT:
Iflookahead=integerthen
Match（integer）;
return（integer）
elseIflookahead=realthen
Match（real）;
return（real）
11 为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。
你可以假定所有的整数都不为零，这样就不用担心零的符号。
E*E|+E|-E|unsigned_integer
E®
E1*E2{ifE1.sign=E2.signthenE.sign:
=POSelseE.sign:
=NEG}
+E1{E.sign:
=E1.sign}
-E1{ifE1.sign=POSthenE.sign:
=NEGelseE.sign:
=POS}
unsigned_integer{E.sign:
12 为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。
例如，输入101.101时，S.val:
=5.625。
（不得修改文法。
）
S®
L.R|L
L®
LB|B
R®
BR|B
B®
0|1
L.R S.val:
=L.val+R.val
S®
L S.val:
=L.val
L1B L.val:
=L1.val´
2+B.val
L®
B L.val:
=B.val
BR1 R.val:
=（R1.val+B.val）/2
R®
B R.val:
=B.val/2
0 B.val:
=0
B®
1 B.val:
=1
13试问下面的程序将有怎样的输出？
分别假定：
（a）传值调用（call-by-value）；
（b）引用调用（call-by-reference）；
（c）复制恢复（copy-restore）；
（d）传名调用（call-by-name）。
programmain（input,output）；
procedurep（x,y,z）；
begin
y：
＝y＋1；
z：
＝z＋x；
end；
a：
＝2；
b：
＝3；
p（a＋b,a,a）；
printa
end.
1）．传地址：
所谓传地址是指把实在参数的地址传递给相应的形式参数。
在过程段中每
个形式参数都有一对应的单元，称为形式单元。
形式单元将用来存放相应的实在参数的地址。
当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可以拿得到的
地方。
当程序控制转入被调用段之后，被调用段首先把实参地址捎进自己相应的形式单元中，
过程体对形式参数的任何引用1或赋值都被处理成对形式单元的间接访问。
当调用段工作完毕返回时，形式单元（它们都是指示器）所指的实在参数单元就持有所指望的值。
2）．传结果：
和“传地址”相似（但不等价）的另一种参数传递力法是所谓“传结果”。
这种方法的实质是，每个形式参数对应有两个申元，第1个单元存放实参的地址，第2个单元
存放实参的值。
在过程体中对形参的任何引用或赋值都看成是对它的第2个单元的直接访
问。
但在过程工作完毕返回前必须把第2个单元的内容行放到第1个单元所指的那个实参单
元之中。
3）．传值：
所谓传值，是一种简单的参数传递方法。
调用段把实在参数的值计算出来并
存放在一个被调用段可以拿得到的地方。
被调用段开始丁作时，首先把这些值抄入形式中元
中，然后就好像使用局部名一样使用这些形式单元。
如果实在参数不为指示器，那末，在被
调用段中无法改变实参的值。
4）．传名：
所谓传名，是一种特殊的形——实参数结合方式。
解释“传名”参数的意义：
过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式
参数都替换成相应的实在参数（文字替换）。
它与采用“传地址”或“传值”的方式所产生的结果均不相同。
（a）2；
（b）8；
（c）7；
（d）9。
14对以下的Pascal程序画出过程c第二次被激活时的运行栈，控制链和访问链。
说明在c中如何访问变量x。
programenv；
procedurea；
varx:
integer；
procedureb；
procedurec；
beginx:
=2；
bend；
{procedurec}
begincend；
{procedureb}
beginbend；
{procedurea}
beginaend.{main}
env
controllink
accesslink
a
x
b
c
b
说明：
c中沿着存取链向前走两步，到过程a的活动记录中就可以访问到变量x。
15下面给出一个C语言程序及其在SPARC/SUN工作站上经某编译器编译后的运行结果。
从运行结果看，函数func中4个局部变量i1,j1,f1,e1的地址间隔和它们类型的大小是一致的，而4个形式参数i,j,f,e的地址间隔和它们的类型的大小不一致，试分析不一致的原因。
注意，输出的数据是八进制的。
func（i,j,f,e）
shorti,j;
floatf,e;
{
shorti1,j1;
floatf1,e1;
printf（"
Addressofi,j,f,e=%o,%o,%o,%o\n"
&
i,&
j,&
f,&
e）;
Addressofi1,j1,f1,e1=%o,%o,%o,%o\n"
i1,&
j1,&
f1,&
e1）;
printf（"
Sizesofshort,int,long,float
升级会员 