编译原理期末试题及答案文档格式.docx
- 文档编号:5607426
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:23
- 大小:186.84KB
编译原理期末试题及答案文档格式.docx
《编译原理期末试题及答案文档格式.docx》由会员分享,可在线阅读,更多相关《编译原理期末试题及答案文档格式.docx(23页珍藏版)》请在冰点文库上搜索。
B→d
(1)给出句子abbcde的最左推导及画出语法树;
(2)给出句型aAbcde的短语、素短语。
10.设文法G(S):
S→(T)|aS|a
⑴消除左递归和提公共左因子;
⑵构造相应的FIRST和FOLLOW集合;
⑶构造预测分析表。
12.已知文法G(S)
E→E+T|T
T→T*F|F
F→(E)|i
(1)给出句型(i+i)*i+i的最左推导及画出语法树;
(2)给出句型(E+T)*i+F的短语,素短语和最左素短语。
答案:
(1)消除左递,文法变为G’[S]:
S→^|a|(T)'
T→ST’|S
T’→,ST’|ε
此文法无左公共左因子。
(2)构造相应的FIRST和FOLLOW集合:
FIRST(S)={a,^,(},FOLLOW(S)={#,,,)}
FIRST(T)={a,^,(},FOLLOW(T)={}}
FIRST(T’)={,,ε},FOLLOW(F)={)}
(3)构造预测分析表:
a
^
(
)
#
S
S→a
S→^
S→(T)'
T
T→ST’
T’
T’→ε
T’→,ST’
2.
(1)
C→ifEthen
S→CS
(1)
(2)
C→ifEthen{BACK(E.TC,NXQ);
C.chain:
=E.FC}
S→CS
(1){S.chain:
=MERG(C.Chain,S
(1).Chain)}
4.
(1)F→fori:
=E
(1)toE
(2)do
S→FS
(1)
(2)F→fori:
{GEN(:
=,E
(1).place,_,entry(i));
F.place:
=entry(i);
=Newtemp;
GEN(:
=,E
(2).place,_,LIMIT);
Q:
=NXQ;
F.QUAD:
=q;
GEN(j≤,entry(i),LIMIT,q+2)
F.chain:
GEN(j,_,_,0)}
S→FS
(1)
{BACKPATCH(S
(1).chain,NXQ);
GEN(+,F.place,1,F.place);
GEN(j,_,_,F.QUAD);
S.chain:
=F.chain
}
7.最左推导
S=(T)=>
(T,S)=>
(S,S)=>
(a,S)=>
(a,(T))=>
(a,(T,S))=>
(a,(S,S))=>
(a,(a,S))=>
(a,(a,a))
短语
((T,S),a)
(T,S),a
(T,S)
T,S
a
直接短语
句柄
9.
(1)S=>
aAcBe=>
AAbcBe=>
abbcBe=>
abbcde
(2)短语:
aAbcde,Ab,d
素短语:
Ab,d
10.
(1)S→(L)|aS’
S’→S|ε
L→SL’
L’→,SL’|ε
(2)FIRST(S)={a,(}FIRST(S’)={a,(,ε}
FIRST(L)={a,(}FIRST(L’)={,,ε}
FOLLOW(S)={,,),#}FOLLOW(S’)={,,),#}
FOLLOW(L)={)}FOLLOW(L’)={)}
(3)
(
)
#
S
S→(L)
S→aS’
S’
S’→S
S’→ε
L
L→SL’
L’→,SL’
L’
L’→ε
12.
(1)E=>
E+T=>
T+T=>
T*F+T=>
F*F+T=>
(E)*F+T=>
(E+T)*F+T=>
(T+T)*F+T=>
(F+T)*F+T=>
(i+T)*F+T=>
(i+F)*F+T=>
(i+i)*F+T=>
(i+i)*i+T
=>
(i+i)*i+F=>
(i+i)*i+i
(2)短语i,F,E+T,(E+T),(E+T)*i,(E+T)*i+F
素短语i,E+T
最左素短语E+T
《编译原理》期末试题
(二)
对于函数f2,由于局部变量x的作用域只是函数体的一部分,不会出现上述问题,因而编译器不报错。
6、正规式b*a(bb*a)*b*体现的特点是,每个a的左边都有若干b,除非a是第一个字母。
该正规式定义的语言是:
至少含一个a,但不含子串aa的所有a和b的串集。
最简DFA如下:
start
2
b
1
7、消除左递归后的文法:
B→1B'
B'
→0B'
|1B'
|ε
相应的翻译方案如下:
B→1{B'
.i:
=1}B'
{B.val:
=B'
.val}
→0{B'
1.i:
.i⨯2}B'
1{B'
.val:
1.val}
|1{B'
.i⨯2+1}B'
|ε{B'
.i}
《编译原理》期末试题(三)
2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。
答:
逆波兰式:
abc*bd*+:
=
3、对于文法G(S):
M
1)
2)短语:
Ma),(Ma),b(Ma)b
直接短语:
Ma)句柄:
Ma)
三、设有字母表{a,b}上的正规式R=(ab|a)*。
解:
(1)
(2)将
(1)所得的非确定有限自动机确定化
ε
-0
3
12
+3
-+013
123
+123
13
+13
(3)对
(2)得到的DFA化简,合并状态0和2为状态2:
-+
+
(4)令状态1和2分别对应非终结符B和A
G:
A→aB|a|ε;
B→aB|bA|a|b|ε;
可化简为:
A→aB|ε;
B→aB|bA|ε
四、
设将文法G改写成等价的LL
(1)文法,并构造预测分析表。
G:
S→S*aT|aT|*aT;
T→+aT|+a
解:
消除左递归后的文法G’:
S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT|+a
提取左公因子得文法G’’:
S→aTS’|*aTS’
T→+aT’
T’→T|ε
Select(S→aTS’)={a}
Select(S→*aTS’)={*}
Select(S→aTS’)∩Select(S→*aTS’)=Ф
Select(S’→*aTS’)={*}
Select(S’→ε)=Follow(s’)={#}
Select(S’→*aTS’)∩Select(S’→ε)=Ф
Select(T→+aT’)={+}
Select(T’→T)=First(T)={+}
Select(T’→ε)=Follow(T’)={*,#}
Select(T’→T)∩Select(T’→ε)=Ф
所以该文法是LL
(1)文法。
预测分析表:
*
→*aTS’
→aTS’
→ε
→+aT’
→ε
→T
6设文法G为:
S→A;
A→BA|ε;
B→aB|b
(1)拓广文法G’:
(0)S’→S
(1)S→A
(2)A→BA(3)A→ε(4)B→aB(5)B→b;
FIRST(A)={ε,a,b};
FIRST(B)={a,b}
构造的DFA如下:
项目集规范族看出,不存在冲突动作。
∴该文法是LR
(1)文法。
(2)LR
(1)分析表如下:
(3)输入串abab的分析过程为:
五、对文法G(S):
S→a|^|(T);
T→T,S|S
答:
(1)
>
<
=
(2)是算符优先文法,因为任何两个终结符之间至多只有一种优先关系。
(2分)
(3)给出输入串(a,a)#的算符优先分析过程。
步骤
栈
当前输入字符
剩余输入串
动作
a,a#
#<
(移进
#(
a)#
(<
a移进
#(a
a)#
a>
归约
4
#(N
移进
5
#(N,
)#
<
6
#(N,a
)归约
7
#(N,N
>
8
(=)移进
9
#(N)
)>
#归约
10
#N
接受
五、设有文法G[A]:
A→BCc|gDB
B→bCDE|ε
C→DaB|ca
D→dD|ε
E→gAf|c
(1)计算该文法的每一个非终结符的FIRST集和FOLLOW集;
(2)试判断该文法是否为LL
(1)文法。
(15)
FIRST
FOLLOW
A
B
C
D
E
A,b,c,d,g
A,c,d
C,g
C,d,g
A,b,c,g
是LL
(1)文法。
2.对于文法G[S]:
S→AB,A→Aa|bB,B→a|Sb求句型baSb的全部短语、直接短语和句柄?
句型baSb的语法树如图五
(2)所示。
baSb为句型baSb的相对于S的短语,ba为句型baSb的相对于A的短语,Sb为句型baSb的相对于B的短语,且为直接短语,a为句型baSb的相对于B的短语,且为直接短语和句柄。
3.设有非确定的有自限动机NFAM=({A,B,C},{0,1},δ,{A},{C}),其中:
δ(A,0)={C}δ(A,1)={A,B}δ(B,1)={C}δ(C,1)={C}。
请画出状态转换距阵和状态转换图。
状态转换距阵为:
δ
A,B
∅
状态转换图为
七已知文法G为:
(1)S′→S
(2)S→aAd
(3)S→bAc
(4)S→aec
(5)S→bed
(6)A→e
试构造它的LR
(1)项目集、可归前缀图和LR
(1)分析表。
【】【答案:
】
构造LR
(1)分析表
如下:
二、设∑={0,1}上的正规集S由倒数第二个字符为1的所有字符串组成,请给出该字集对应的正规式,并构造一个识别该正规集的DFA。
(8分)
构造相应的正规式:
(0|1)*1(0|1)(3分)
NFA:
(2分)
11
εεεε1
00
确定化:
(3分)
I
{0,1,2}
{1,2}
{1,2,3}
{1,2,4}
{1,2,3,4}
0
1
0100
01
四、对于文法G(E):
(8分)
E→T|E+T
T→F|T*F
F→(E)|i
1.写出句型(T*F+i)的最右推导并画出语法树。
2.写出上述句型的短语,直接短语、句柄和素短语。
1.(4分)
E⇒T⇒F⇒(E)⇒(E+T)⇒(E+F)
⇒(E+i)⇒(T+i)⇒(T*F+i)
2.(4分)
短语:
(T*F+i),T*F+i,T*F,i
直接短语:
T*F,i
句柄:
T*F
素短语:
九、(9分)设已构造出文法G(S):
(1)S→BB
(2)B→aB
(3)B→b的LR分析表如下
ACTION
GOTO
状态
s3
s4
acc
s6
s7
r3
r1
r2
假定输入串为abab,请给出LR分析过程(即按照步骤给出状态,符号,输入串的变化过程)。
步骤状态符号输入串
00#abab#
103#abab#
2034#abab#
3038#aBab#
402#Bab#
5026#Bab#
60267#Bab#
70269#BaB#
8025#BB#
901#S#acc
1.设有如下文法G(S),试消除其左递归。
G(S):
S—>
Ac|c
A—>
Bb|b
B—>
Sa|a
S→abcS′|bcS′|cS′,S′→abcS′|
2.试构造与下面G(S)等价的无左递归的文法。
Sa|Nb|c
N—>
Sd|Ne|f
S→fN′bS′|cS′,S′→aS′|dN′bS′|
N′→eN′|
3.设有文法G(S):
aBc|bAB
A—>
aAb|b
B—>
b|ε
①求各产生式的FIRST集,FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。
②构造LL
(1)分析表,并分析符号串baabbb是否是。
(1)FIRST(aBc)={a},FIRST(bAB)={b}FIRST(aAb)={a},A→b:
FIRST(A→b)={b},B→b:
FIRST(b)={b},FIRST(ε)={ε}
FOLLOW(A)={b,#},FOOLOW(B)={c,#}
SELECT(S→aBc)={a},SELECT(S→bAB)={b},SELECT(A→aAb)={a},SELECT(A→b)={b},SELECT(B→b)={b},SELECT(B→
)={c,#}
因此,所得的LL
(1)分析表如表A-4所示。
表A-4LL
(1)分析表
输入
VN
输入符号
c
S→aBc
S→bAB
A→aAb
A→b
B→b
B→
(2)分析符号串baabbb成功,baabbb是该文法的句子,如图A-16所示。
图A-16识别串baabbb的过程
4.已知文法G(S):
a|(T)
T—>
T,S|S
①给出句子((a,a),a)的最左推导并画出语法树;
②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。
(1)最左推导:
(T)
(T,S)
(S,S)
(a,S)
(a,(T))
(a,(T,S))
(a,(S,S))
(a,(a,S))
语法树:
如图A-16所示。
图A-16(a,(a,a))的语法树
(2)句型(T,a,(T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树(图A-17)。
a||T,a||(T)||T,a,(T)||(T,a,(T))
a||(T)
最左素短语:
活前缀:
||(||(T||(T,||(T,a
图A-17(T,a,(T))的语法树
项目集族和DFA
1、wab+cde10-/+8+*+
2、abcd-*e/+
3、abc+e*bc+f/+:
4、4231
5、句子b(aa)b的规范归约过程:
符号栈
输入串
b(aa)b#
预备
#b
(aa)b#
移进
#b(
aa)b#
3
#b(a
a)b#
#b(A
a)b#
归约
5
#b(Ma
)b#
#b(Ma)
b#
#b(B
b#
#bA
#bAb
#S
6、消除左递归
S→aFS’|*aFS’
S’→*aFS’|ε
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 期末 试题 答案