#编译原理答案第五章.docx
- 文档编号:11093883
- 上传时间:2023-05-29
- 格式:DOCX
- 页数:22
- 大小:88.56KB
#编译原理答案第五章.docx
《#编译原理答案第五章.docx》由会员分享,可在线阅读,更多相关《#编译原理答案第五章.docx(22页珍藏版)》请在冰点文库上搜索。
#编译原理答案第五章
练习5.1
解答:
输入(4*7+1>*2n,带注释的分析树如下:
练习5.2
解答:
(1>根据表5.3中的语法制导定义建立表达式((a>+(b>>的分析树和语法树
(2>根据图5.17的翻译模式构造((a>+(b>>的分析树和语法树
练习5.3
解答:
设置下面的函数和属性:
expr1||expr2:
把表达式expr2拼写在表达式expr1后面。
deletep(expr>:
去掉表达式expr左端的‘<’和右端的‘>’。
E.expr,T.expr,F.expr:
属性变量,分别表示E,T,F的表达式。
E.add,T.add,F.add,属性变量,若为true,则表示其表达式中外层有‘+’号,否则无‘+’号。
E.pmark,T.pmark,F.pmark,属性变量,若为true,表示E,T,F的表达式中左端为‘<’,右端是‘)’。
语法制导定义如下:
产生式
语义规则
E->E1+T
if(T.pmark==true>
THENE.expr=E1.expr||'+'||deletep(T.expr>
ELSEE.expr:
=E1.expr||'+'||T.expr。
E.add:
=true。
E.pmark:
=false。
E->T
if(T.pmark==true>
THENE.expr:
=deletep(T.expr>
ELSEE.expr:
=T.expr。
E.add:
=T.add。
E.pmark:
=false。
T->T1*F
T.expr:
=T1.expr||'*'||F.expr。
T.add:
=false。
T.pmark:
=false。
T->F
T.expr:
=F.expr。
T.add:
=F.add。
T.pmark:
=F.pmark。
F->(E>
if(E.add==false>
THENBEGIN
F.expr:
=E.expr。
F.add:
=false。
F.pmark:
=false。
END
ELSEBEGIN
F.expr:
='('||E.expr||'>'。
F.add:
=true。
F.pmark:
=true。
END。
F->id
F.expr:
=id.lexval。
F.add:
=false。
F.pmark:
=false。
练习5.4
解答:
(1>语法制导定义如下:
产生式
语义规则
E->E1+T
if(E1.type==int>AND(T.type==int>
THENE.type:
=int
ELSEE.type:
=real。
E->T
E.type:
=T.type。
T->num
T.type:
=int。
T->num.num
T.type:
=real。
(2>设E.pf和T.pf分别是E和T的前缀形式,||是两个字符串的连接,语法制导定义如下:
产生式
语义规则
E->E1+T
if(E1.type==int>AND(T.type==int>
THENE.type:
=int
ELSEBEGIN
E.type:
=real。
if(E1.type==int>AND(T.type==real>
THENE1.pf:
='inttoreal'||E1.pf
ELSEif(E1.type==real>AND(T.type==int>
THENT.pf:
='inttoreal'||T.pf
END。
E.pf:
='+'||E1.pf||T.pf。
E->T
E.type:
=T.type。
E.pf:
=T.pf。
T->num
T.type:
=int。
T.pf:
=int.lexval。
T->num.num
T.type:
=real。
T.pf:
=real.lexval。
练习5.5
解答:
(1>用综合属性决定s.val的语法制导定义:
产生式
语义规则
S->L
S.val:
=L.val。
S->L1.L2
S.val:
=L1.val+L2.val*L2.p。
L->B
L.val:
=B.val。
L.p:
=2-1。
L->L1B
L.val:
=L1.val*2+B.val。
L.p:
=L.p*2-1。
B->0
B.val:
=0。
B->1
B.val:
=1。
注:
L.p表示恢复L.val的因子。
(2>分析:
设B.c是B的综合属性,是B产生的位对最终值的贡献。
要求出B.c,必须求出B产生位的
权,设B.i。
B.i的求法请参看下面的图示:
另外,设L.fi为继承因子,L.fs为综合因子,语法制导定义如下:
产生式
语义规则
S->L
L.i:
=1。
L.fi:
=2。
L.fs:
=1。
S.val:
=L.val。
S->L1.L2
L1.i=1。
L1.fi=2。
L1.fs:
=1。
L2.i=2-1。
L2.fi=1。
L2.fs:
=2-1。
S.val:
=L1.val+L2.val。
L->B
L.s:
=L.i。
B.i:
=L.s。
L.val:
=B.c。
L->L1B
L1.i:
=L.i*L1.fi。
L.s:
=L1.s*L1.fs。
B.i:
=L.s。
L.val:
=L1.val+B.c。
B->0
B.c:
=0。
B->1
B.c:
=B.i。
若把文法改写成如下形式,则语法制导定义会更清楚:
S->L.R|L
L->LB|B
R->RB|B
B->0|1
产生式
语义规则
S->L
L.i:
=1。
S.val:
=L.val。
S->L.R
L.i=1。
R.i=2-1。
S.val:
=L.val+R.val。
L->L1B
B.i:
=L.i。
L1.i:
=L.i*2。
L.val:
=L1.val+B.c。
L->B
B.i:
=L.i。
L.val:
=B.c。
R->R1B
R1.i:
=R.i。
R.s:
=R1.s*2-1。
B.i:
=R.s。
R->B
R.s:
=R.i。
B.i:
=R.s。
R.val:
=B.c。
B->0
B.c:
=0。
B->1
B.c:
=B.i。
练习5.6
解答:
产生式
语义规则
D->D1,id
D.type:
=D1.type。
addtype(id.entry,D1.type>。
D->Tid
D.type:
=T.type。
addtype(id.entry,T.type>。
T->int
T.type:
=int。
T->real
T.type:
=real。
练习5.7
解答:
(1>
产生式
语义规则
E->TR
R.i:
=T.type。
E.type:
=R.s。
R->+TR1
if(R.i==int>AND(T.type==int>
THENR1.i:
=int
ELSER1.i:
=real。
R.s:
=R1.s。
R->ε
R.s:
=R.i。
T->num.num
T.type:
=real。
T->num
T.type:
=int。
(2>
产生式
语义规则
E->TR
R.itype:
=T.type。
R.ipf:
=T.pf。
E.pf:
=R.spf。
E.type:
=R.stype。
R->+TR1
if(R.itype==int>AND(T.type==int>
THENR1.itype:
=int
ELSEBEGIN
R1.itype:
=real。
if(R.itype==real>AND(T.type==int>
THENT.pf:
='inttoreal'||T.pf
ELSEif(R.itype==int>AND(T.type==real>
THENR.ipf:
='inttoreal'||R.ipf
END。
R1.ipf:
='+'||R.ipf||T.pf。
R.stype:
=R1.stype。
R.spf:
=R1.spf。
R->ε
R.stype:
=R.itype。
R.spf:
=R.ipf。
T->num
T.type:
=int。
T.pf:
=int.lexval。
T->num.num
T.type:
=real。
T.pf:
=real.lexval。
注:
R.ipf是R的继承属性,是它的前缀表示。
R.spf是R的综合属性,是它的前缀表示。
练习5.8
解答:
设计两个函数lookup(name>和enter(name,type>,lookup(name>查找符号表,若查到,则返回name在符号表中的地址;否则返回NULL。
enter(name,type>在符号表中建立name的符号表项,并填写上name的类型type。
翻译模式如下:
D->T{L.in:
=T.type}L
L->{L1.in:
=L.in}
L1,id{if(lookup(id.name>>
thenerror
elseenter(id.name,L.in>}
L->id{if(lookup(id.name>>
thenerror
elseenter(id.name,L.in>}
T->int{T.type:
=int}
T->real{T.type:
=real}
练习5.9
解答:
(1>翻译模式如下:
D->idL{addtype(id.entry,L.type>}
L->,idL1{L.type:
=L1.type。
addtype(id.entry,L.type>}
L->:
T{L.type:
=T.type}
T->integer{T.type:
=integer}
T->real{T.type:
=real}
(2>预测翻译程序由如下过程组成:
PROCEDURED。
VARL.type:
(integer,real>。
id.entry:
^id-entry。
BEGIN
id.entry:
=id.lexval。
match(id>。
L.type:
=L。
addtype(id.entry,L.type>
END。
FUNCTIONL:
(integer,real>。
VARL.type,L1.type:
(integer,real>。
id.entry:
^id-entry。
BEGIN
if(lookahead==','>
THENBEGIN
match(','>。
match(id>。
id.entry:
=id.lexval。
L1.type:
=L。
L.type:
=L1.type。
addtype(id.entry,L.type>。
END
ELSEBEGIN
match(':
'>。
L.type:
=T。
END。
return(L.type>。
END。
FUNCTIONT:
(integer,real>。
VART.type:
(integer,real>。
BEGIN
if(lookahead=='integer'>
THENBEGIN
match(integer>。
T.type:
=id.lexval
END
ELSE
if(lookahead=='real'>
THENBEGIN
match(real>。
T.type:
=id.lexval。
END
ELSEERROR。
return(T.type>。
END。
练习5.10
解答:
(1>对于F1subF2subF3,其最左推导和分析树如下:
S=>L
=>B
=>BsubF3
=>BsubF2subF3
=>F1subF2SubF3
显然,F3.ps:
=shrink(F2.ps>。
F2.ps:
=shrink(F1.ps>。
为此,为B设一个综合属性B.pt,其值等于其下标F的继承属性F.ps。
语法制导定义如下:
产生式
语义规则
S->L
L.ps:
=10。
S.ht:
=L.ht。
L->B
B.ps:
=L.ps。
L.ht:
=B.ht。
L->L1B
L1.ps:
=L.ps。
B.ps:
=L.ps。
L.ht:
=max(L1.ht,B.ht>。
B->B1subF
B1.ps:
=B.ps。
F.ps:
=shrink(B1.pt>。
B.ht:
=disp(B1.ht,F.ht>。
B.pt:
=F.ps。
B->F
F.ps:
=B.ps。
B.ht:
=F.ht。
B.pt:
=B.ps。
F->{L}
L.ps:
=F.ps。
F.ht:
=L.ht。
F->text
F.ht:
=text.h*F.ps
(2>翻译模式如下:
S->{L.ps:
=10}
L{S.ht:
=L.ht}
L->{B.ps:
=L.ps}
B{L.ht:
=B.ht}
L->{L1.ps:
=L.ps}
L1{B.ps:
=L.ps}
B{L.ht:
=max(L1.ht,B.ht>}
B->{B1.ps:
=B.ps}
B1
sub{F.ps:
=shrink(B1.pt>}
F{B.ht:
=disp(B1.ht,F.ht>。
B.pt:
=F.ps}
B->{F.ps:
=B.ps}
F{B.ht:
=F.ht。
B.pt:
=B.ps}
F->{L.ps:
=F.ps}
{L}{F.ht:
=L.ht}
F->text{F.ht:
=text.h*F.ps}
练习5.11
解答:
(1>假设基础文法含左递归的翻译模式如下:
A->{A1.i:
=A.i}
A1{Y.i:
=A.i}
Y{A.a:
=g(A1.a,Y.y>}
A->{X.i:
=A.i}
X{A.a:
=f(X.x>}
消除基础文法左递归后的翻译模式如下:
A->{X.i:
=A.i}
X{R.i:
=f(X.x>。
R.yi:
=A.i}
R{A.a:
=R.s}
R->{Y.i:
=R.yi}
Y{R1.i:
=g(R.i,Y.y>。
R1.yi:
=R.yi}
R1{R.s:
=R1.s}
R->ε{R.s:
=R.i}
属性R.yi用于传递A.i给Y。
(2>设基础文法含左递归的翻译模式如下:
A->{A1.i:
=h1(A.i>}
A1{y.i:
=h2(A.i>}
Y{A.a:
=g(A1.a,Y.y>}
A->{X.i:
=h3(A.i>}
X{A.a:
=f(X.x>}
考虑XY1Y2Y3,其继承属性的计算如下:
消除基础文法中的左递归后,基础文法为:
A->XR
R->YR|ε
继承属性的计算如下图所示:
当识别出X后,并不能计算出X的继承属性,因而,也就无法计算有关X的其他属性。
只好把X的源表示或中间表示作为继承传给R,继续沿R传下去,然后再作为综合属性传回来。
直到能计算出X.i,再对X的成分进行翻译。
Y1,Y2,Y3的翻译思想和X类似,具体的翻译模式省略。
练习5.12
解答:
S->{L.ps:
=10。
L.iht:
=0}
L{S.ht:
=L.ht}
L->{B.ps:
=L.ps}
B{L.ht:
=max(L.iht,B.ht>}
L->{B.ps:
=L.ps}
B{L1.iht:
=max(L.iht,B.ht>。
L1.ps:
=L.ps}
L1{L.ht:
=L1.ht}
B->{F.ps:
=B.ps}
F
sub{B1.ps:
=shrink(B.ps>}
B1{B.ht:
=disp(F.ht,B1.ht>}
B->{F.ps:
=B.ps}
F{B.ht:
=F.ht}
F->{L.ps:
=F.ps}
{L}{F.ht:
=L.ht}
F->text{F.ht:
=text.h*F.ps}
练习5.13
解答:
(1>
栈
输入
动作
$
abbb$
初始
$M
abbb$
规约M->ε
$MM
abbb$
规约M->ε
$MMM
abbb$
规约M->ε
$MMMa
bbb$
移进
$MMML
bbb$
规约L->a
$MMMLb
bb$
移进
$MML
bb$
规约L->MLb
$MMLb
b$
移进
$ML
b$
规约L->MLb
$MLb
$
移进
$L
$
规约L->MLb
接受
(2>构造文法的LR(1>项目的识别文法活前缀的DFA:
在项目集I0,I2,I2中,存在移进-规约冲突,因此,它不是LR(1>的。
练习5.14
解答:
(1>把表5.10的语法制导定义改写成下面的翻译模式:
S->L{B.ps:
=L.s}
B{S.ht:
=B.ht}
L->ε{L.s:
=10}
B->{B1.ps:
=B.ps}
B1{M.i:
=B.ps}
M{B2.ps:
=M.s}
B2{B.ht:
=max(B1.ht,B2.ht>}
M->ε{M.s:
=M.i}
B->{B1.ps:
=B.ps}
B1
sub{N.i:
=B.ps}
N{B2.ps:
=N.s}
B2{B.ht:
=disp(B1.ht,B2.ht>}
B->text{B.ht:
=text.h*B.ps}
N->ε{N.s:
=shrink(N.i>}
(b>设一个栈ps,管理继承属性B.ps的值。
栈的三个操作为
push(ps,值>,pop(ps>,top(ps>.
翻译模式如下:
S->L{B.ps:
=top(ps>}
B{S.ht:
=B.ht}
L->ε{push(ps,10>}
B->{B1.ps:
=top(ps>}
B1{B2.ps:
=top(ps>}
B2{B.ht:
=max(B1.ht,B2.ht>}
B->{B1.ps:
=top(ps>}
B1
sub
N(B2.ps:
=top(ps>}
B2{B.ht:
=disp(B1.ht,B2.ht>。
pop(ps>}
B->text{B.ht:
=text.h*B.ps}
N->ε{push(ps,shrink(top(ps>>>}
练习5.15
解答:
A③B④C②D⑤
练习5.16
解答:
(1>FALSE(2>TRUE(3>TRUE(4>FALSE(5>TRUE(6>FALSE
练习5.17
解答:
atype:
ARRAY(0..9,ARRAY(-10..10,integer>>。
cell:
RECORD((a×integer>×(b×integer>>。
pcell:
POINTER(cell>。
或:
POINTER(RECORD((a×integer>×(b×integer>>>。
foo:
ARRAY(1..100,cell>。
或:
ARRAY(1..100,RECORD((a×integer>×(b×integer>>>。
bar:
integer×cell→pcell。
或:
integer×cell→POINTER(RECORD((a×integer>×(b×integer>>>。
练习5.18
解答:
D->id:
T{addtype(id.entry,T.type>>}
T->char{T.type:
=char}
T->integer{T.type:
=integer}
T->listofT1{T.type:
=list(T1.type>}
E->num{E.type:
=integer}
E->id{E.type:
=lookup(id.entry>}
E->Literal{E.type:
=char}
E->(L>{E.type:
=list(L.type>}
L->E,L1{L.type:
=IF(E.type=L1.type>
THENE.type
ELSEtype_error}
L->E{L.type:
=E.type}
练习5.19
解答:
(1>
S->id:
=E{S.type:
=IFid.type=E.type
THENE.type
ELSEtype_error。
S.val:
=IFid.type=E.type
THENE.val
ELSEval_error}
S->IFETHENS1{S.type:
=IFE.type=boolean
THENS1.type
ELSEtype_error。
S.val:
=IFE.type=boolean
THENS1.val
ELSEval_error}
S->WHILEEDOS1{S.type:
=IFE.type=boolean
THENS1.type
ELSEtype_error。
S.val:
=IFE.type=boolean
THENS1.val
ELSEval_error}
S->S1。
S2{S.type:
=S2.type。
S.val:
=S2.val}
(2>
E->E1ANDE2{E.type:
=IF(E1.type=boolean>AND(E2.type=boolean>
THENboolean
ELSEtype_error}
E->E1ORE2{E.type:
=IF(E1.type=boolean>AND(E2.type=boolean>
THENboolean
ELSEtype_error}
E->NOTE1{E.type:
=IF(E1.type=boolean>
THENboolean
ELSEtype_error}
E->E1opE2{E.type:
=IF(E1.type=E2.type>
TH
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 答案 第五