编译原理计算题.docx
- 文档编号:10669851
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:18
- 大小:47.06KB
编译原理计算题.docx
《编译原理计算题.docx》由会员分享,可在线阅读,更多相关《编译原理计算题.docx(18页珍藏版)》请在冰点文库上搜索。
编译原理计算题
编译原理计算题
窗体顶端
1、写一个文法,使其语言是奇数集,且每个奇数不以0开头。
(5分)
2、设文法G(S):
S→(L)|aS|a
L→L,S|S
(1)消除左递归和回溯;
(2)计算每个非终结符的FIRST和FOLLOW;
(3)构造预测分析表。
3、While a>0∨b<0 do
Begin
X:
=X+1;
ifa>0thena:
=a-1
elseb:
=b+1
End;
翻译成四元式序列。
(7分)
4、已知文法G(E)
E→T|E+T
T→F|T*F
F→(E)|i
(1)给出句型(T*F+i)的最右推导及画出语法树;
(2)给出句型(T*F+i)的短语、素短语。
(7分)
5、设布尔表达式的文法为
E→E
(1)∨E
(2)
E→E
(1)∧E
(2)
E→i
假定它们将用于条件控制语句中,请
(1)改写文法,使之适合进行语法制导翻译和实现回填;
(2)写出改写后的短个产生式的语义动作。
(6分)
6、设有基本块
T1:
=2
T2:
=10/T
T3:
=S-R
T4:
=S+R
A:
=T2*T4
B:
A
T5:
=S+R
T6:
=T3*T5
B:
=T6
(1)画出DAG图;
(2)假设基本块出口时只有A,B还被引用,请写出优化后的四元序列。
(6分)
窗体底端
7、已知文法G(S)
S→a|∧|(T)
T→T,S|S
写出句子((a,a),a)的规范归约过程及每一步的句柄。
8、已知文法G(S):
S→a|(T) T→T,S|S的优先关系表如下:
关系
a
(
)
a
-
-
;
;
(
<
<
=
<
)
-
-
>
>
<
<
>
>
请计算出该优先关系表所对应的优先函数表。
9、写一个文法,使其语言是偶数集,且每个偶数不以0开头。
(5分)
10、已知文法G(S):
S→a|∧|(T)
T→T,S|S
⑴给出句子(a,(a,a))的最左推导并画出语法树;
⑵给出句型((T,S),a)的短语、直接短语、句柄。
(8分)
11、把语句
ifx>0∧y>0thenz:
=x+y
elsebegin
x:
=x+2;
y:
=y+3
END;
翻译成四元式序列。
(6分)
12、设某语言的for语句的形式为
fori:
=E
(1)TOE
(2)doS
其语义解释为
i:
=E
(1);
LIMIT:
=E
(2);
again:
ifi<=LIMITthen
BEGIN
S;
i:
=i+1;
gotoagain
END;
⑴写出适合语法制导翻译的产生式;
⑵写出每个产生式对应的语义动作。
(6分)
13、设文法G(S):
S→S+aF|aF|+aF
F→*aF|*a
⑴消除左递归和回溯;
⑵构造相应的FIRST和FOLLOW集合;
⑶构造预测分析表(10分)
14、对以下基本块
T1:
=2
T2:
=A-B
T3:
=A+B
T4:
=T2*T3
T5:
=3*T1
T6:
=A-B
L:
=A+B
T7:
=T6*L
T8:
=T5*4
M:
=T8+T7
L:
=M
⑴画出DAG图;
⑵假设只有L在基本块出口之后还被引用,请写出优化后的四元式序列。
(6分)
15、(8分)化简文法G[S]:
S→ASe|BCaD|aD|AC
A→Cb|DBS
C→bC|d
B→Ac
D→aD
16、(12分)设Lí{a,b,c}*是满足下述条件的符号串构成的语言:
(1)若出现a,则其后至少紧跟两个c;
(2)若出现b,其后至少紧跟一个c。
试构造识别L的最小化的DFA,并给出描述L的正规表达式。
17、(12分)已给文法G[S]:
S→SaP|Sf|P P→qbP|q
将G[S]改造成LL
(1)文法,并给出LL
(1)分析表。
18、(12分)给定文法G[S]:
S→Aa|dAb|Bb|dBaA→cB→c
构造文法G[S]的LR
(1)分析表。
19、(8分)将下面的条件语句表示成逆波兰式和四元式序列:
ifa>bthenx:
=a+b*celsex:
=b-a;
20、(8分)给定基本块:
A:
=3*5
B:
=E+F
C:
=A+12
D:
=E+F
A:
=D+12
C:
=C+1
E:
=E+F
假定出基本块后,只有A、C、E是活跃的,给出用DAG图完成优化后的代码序列。
1、写一个文法,使其语言是奇数集,且每个奇数不以0开头。
(5分)
解:
文法G(N):
N→AB|B
A→AC|D
B→1|3|5|7|9
D→B|2|4|6|8
C→0|D (5分)
2、设文法G(S):
S→(L)|aS|a
L→L,S|S
(1)消除左递归和回溯;
(2)计算每个非终结符的FIRST和FOLLOW;
(3)构造预测分析表。
解:
(1)
S→(L)|aS'
S'→S|ε
L→SL'
L'→SL'|ε
评分细则:
消除左递归2分,提公共因子2分。
(2)
FIRST)S)={(,a} FOLLOW(S)={#,,,)}
FIRST(S')={,a,ε} FOLLOW(S')={#,,,)}
FIRST(L)={(,a} FOLLOW(L)={)}
FIRST(L')={,,ε} FOLLOW(L'〕={)}
3、While a>0∨b<0 do
Begin
X:
=X+1;
ifa>0thena:
=a-1
elseb:
=b+1
End;
翻译成四元式序列。
(7分)
解:
(1)(j>,a,0,5)
(2)(j,-,-,3)
(3)(j<,b,0,5)
(4)(j,-,-,15)
(5)(+,×,1,T1)
(6)(:
=,T1,-,×)
(7)(j≥,a,0,9)
(8)(j,-,-,12)
(9)(-,a,1,T2)
(10)(:
=,T2,-,a)
(11)(j,-,-,1)
(12)(+,b,1,T3)
(13)(:
=,T3,-,b)
(14)(j,-,-,1)
(15)
评分细则:
控制结构4分,其它3分。
4、已知文法G(E)
E→T|E+T
T→F|T*F
F→(E)|i
(1)给出句型(T*F+i)的最右推导及画出语法树;
(2)给出句型(T*F+i)的短语、素短语。
(7分)
解:
(1)最右推导:
ETF(E)(E+T)(E+F)(E+i)
(T+i)(T*F+i)
(2)短语:
(T*F+i),T*F+i,T*F,i (2分)
素短语:
T*F,i (1分)
5、设布尔表达式的文法为
E→E
(1)∨E
(2)
E→E
(1)∧E
(2)
E→i
假定它们将用于条件控制语句中,请
(1)改写文法,使之适合进行语法制导翻译和实现回填;
(2)写出改写后的短个产生式的语义动作。
(6分)
解:
(1)E0→E
(1)
E→E0E
(2)
EA→E
(1)
E→EAE
(2)
E→i (3分)
(2)E→E
(1)
{BACKPATCH(E
(1)·FC,NXQ);
E0·TC:
=E
(1)·TC}
E→E0E
(2)
{E·FC:
=E
(2)·FC;
E·TC:
=MERG(E0·TC,E
(2)·TC)}
EA→E
(1)
{BACKPATCH(E
(1)·TC,NXQ);
E0·FC:
=E
(1)·FC}
E→EAE
(2)
{E·TC:
=E
(2)·TC;
E·FC:
=MERG(EA·FC,E
(2)·FC}
E→i
{E·TC:
=NXQ;E·FC:
=NXQ+1;
GEN(jn2,entry(i),-0);
GEN(j,-,-,0) (3分)
6、设有基本块
T1:
=2
T2:
=10/T
T3:
=S-R
T4:
=S+R
A:
=T2*T4
B:
A
T5:
=S+R
T6:
=T3*T5
B:
=T6
(1)画出DAG图;
(2)假设基本块出口时只有A,B还被引用,请写出优化后的四元序列。
(6分)
解:
(1)DAG:
(2)优化后的四元式
T3:
=S-R
T4:
=S+R
A:
=5*T4
B:
=T3+T4 (3分)
7、已知文法G(S)
S→a|∧|(T)
T→T,S|S
写出句子((a,a),a)的规范归约过程及每一步的句柄。
句型 归约规则 句柄
((a,a),a) S→a a
((S,a),a) T→S S
((T,a),a) S→a a
((T,S),a) T→T,S T,S
((S),a) T→S S
((T),a) S→S(T) (T)
(S,a) T→S S
(T,a) S→a a
(T,S) T→T,S T,S
(T) S→(T) (T)
S (4分)
8、答:
优先函数表如下(f函数2分,g函数2分)
函数
a
(
)
f
4
2
4
4
g
5
5
2
3
9、写一个文法,使其语言是偶数集,且每个偶数不以0开头。
(5分)
10、已知文法G(S):
S→a|∧|(T)
T→T,S|S
⑴给出句子(a,(a,a))的最左推导并画出语法树;
⑵给出句型((T,S),a)的短语、直接短语、句柄。
(8分)
11、把语句
ifx>0∧y>0thenz:
=x+y
elsebegin
x:
=x+2;
y:
=y+3
END;
翻译成四元式序列。
(6分)
12、设某语言的for语句的形式为
fori:
=E
(1)TOE
(2)doS
其语义解释为
i:
=E
(1);
LIMIT:
=E
(2);
again:
ifi<=LIMITthen
BEGIN
S;
i:
=i+1;
gotoagain
END;
⑴写出适合语法制导翻译的产生式;
⑵写出每个产生式对应的语义动作。
(6分)
13、设文法G(S):
S→S+aF|aF|+aF
F→*aF|*a
⑴消除左递归和回溯;
⑵构造相应的FIRST和FOLLOW集合;
⑶构造预测分析表(10分)
14、对以下基本块
T1:
=2
T2:
=A-B
T3:
=A+B
T4:
=T2*T3
T5:
=3*T1
T6:
=A-B
L:
=A+B
T7:
=T6*L
T8:
=T5*4
M:
=T8+T7
L:
=M
⑴画出DAG图;
⑵假设只有L在基本块出口之后还被引用,请写出优化后的四元式序列。
(6分)
9、答:
文法G(S):
S→AB|B|A0
A→AD|C
B→2|4|6|8
C→1|3|5|7|9|B
D→0|C
10、答:
最左推导:
(2分)
S=>(T)=>(T,S)=>(S,S)
=>(a,S)=>(a,(T))=>(a,(T,S))
=>(a,(S,S))=>(a,(a,S))
=>(a,(a,a))
语法树:
(2分,此处略)
11、答:
⑴(j>,x,0,3)
⑵(j,-,-,8)
⑶(j>,y,0,5)
⑷(j,-,-,8)
⑸(+,x,y,T1)
⑹(:
=,T1,-,Z)
⑺(j,-,-,12)
⑻(+,x,2,T2)
⑼(:
=,t2,-,X)
⑽(+,Y,3,t3)
⑾(:
=,T3,-,y)
⑿
(控制结构3分,其它3分)
12、答:
⑴(2分)
F→fori:
=E
(1)toE
(2)do
S→FS
(1)
⑵(每个语义动作2分)
F→fori:
=E
(1)toE
(2)do
{GEN(:
=,E
(1).place,-,entry(i));
F.place:
=entry(i);
LIMIT:
=Newtemp;
GEN(:
=,E
(2).place,-,LIMIT);
:
=NXQ;
F.QUAD:
=q;
GEN(j≤,entry(i),LIMIT,q+2)
F.chain:
=NXQ;
G)j,-,-,0)}
S→FS
(1)
{BACKPATCH(S
(1).chain,NXQ);
GEN(+,F.place,1,F.place);
GEN(j,-,-,F.QUAD);
S.chain:
=F.chain}
13、答:
⑴(消除左递归2分,提公共左因子2分)
S→aFS'|+aFS'
S'→+aFS'|ε
F→*aF'
F'→F|ε
⑵ (3分)
FIRST(S)={a,+}FOLLOW(S)={#}
FIRST(S')={+,ε}FOLLOW(S')={#}
FIRST(F)={*}FOLLOW(F)={+,#}
FIRST(F')={*,ε)FOLLOW(F')={+,#}
⑶ (3分)
-
a
+
*
#
S
S→aFS'
S→+aFS'
-
-
S'
-
S'→+aFS'
-
S'→ε
F
-
-
F→*aF'
-
F'
-
F'→ε
F'→F
F'→ε
14、答:
⑴DAG(3分,此处略)
⑵四元式序列:
(3分)
T2:
=A-B
T3:
=A+B
T4:
=T2*T3
L:
=T4+24
15、化简后:
S→ASe|ACA→CbC→bC|d
16、DFA如图所示。
相应的正规式为(c|acc|bc)*。
17、改造后的文法:
S→PS'S'→aPS'|fS'|eP→qP'P'→bP|e
各候选式的FIRST集,各非终结符的FOLLOW集为
产生式
FIRST集
FOLLOW集
S→PS'
{q}
{#}
S'→aPS'
→fS'
→e
{a}
{f}
{e}
{#}
P→qP'
{q}
{a,f,#}
P'→bP
→e
{b}
{e}
{a,f,#}
LL
(1)分析表为
18、分析表如下图所示
19、
(1)逆波兰式:
其中,BLE表示小于或等于时的转向指令;[…]表示标号。
(2)四元式:
(1)(j>,a,b,(3))
(2)(j,,,(7))
(3)(*,b,c,T1)
(4)(+,a,T1,T2)
(5)(:
=,T2,,x)
(6)(j,,,(9))
(7)(-,b,a,T3)
(8)(:
=,T3,,x)
(9)(……)
20、化简后的的四元式序列为
A:
=D+12
E:
=E+F
C:
=28
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 算题