模拟题Word格式.docx
《模拟题Word格式.docx》由会员分享，可在线阅读，更多相关《模拟题Word格式.docx（18页珍藏版）》请在冰点文库上搜索。
六、应用题（共20分）
设有文法G[S]：
S→（L）∣aS∣a L→L,S∣S
（1）将其改写为LL
（1）文法（10分）
（2）构造改写后文法的LL
（1）分析表（10分）
七、应用题（共10分）
设有文法G′[E]：
F→E1 E1→E1+T1|T1 T1→T T→T*F|F
→（E）|i
其相应的简单优先矩阵如图所示，试给出对符号串i*i+i进行简单优先分析的过程。
八、简答题（共10分）
将下列语句翻译成四元式序列
IF a<
b∨c<
0 THEN BEGIN b:
=b+2；
c:
=c-1 END
ELSE WHILE a<
=d DO BEGIN a:
=a-2；
d:
=d+1 END
九、应用题（共10分）
对于如下的程序，试对其中的循环进行优化：
I:
=5
readJ,K
L:
A:
=J*K
B:
=J*I
WriteB
=I+1
if I<
30 goto L
halt
模拟试题1答案
1.A 2.B 3.D 4.A 5.D
解：
对应的文法为：
S→aSa∣bSb∣cSc∣ε
对于G，我们可得到W={A,B}，于是得到消除ε-产生式后的文法为：
S→AbB∣a∣bB∣Ab∣b A→AB∣caB∣B∣ca B→Aa∣b∣a
与正规式相应的NFA如图所示：
（1）相应的状态转换图如图所示：
（2）相应的3型文法为：
S→aA∣bB A→aC∣bB∣a B→aA∣bD∣b
C→aC∣bD∣a∣b D→aC∣bD∣a∣b
（1）提取S-产生式中的公因子a和消除L-产生式中的直接递归性后，我们便得到了与原文法等价的文法G′[S]：
：
S→（L）∣aS′
S′→S∣ε
L→SL′
L′→,SL′|ε
文法G′[S]的各候选式的FIRST集和各非终结符号的FOLLOW集如表6-
（1）所示:
表6-
（1） 文法G′[S]的各个FIRST集和FOLLOW集
产生式
FIRST
FOLLOW
S→（L）
S→aS′
{（}
{a}
{,,）,#}
S′→S
S′→ε
{a,（}
{ε}
L→SL′
{）}
L′→,SL′
L′→ε
{,}
下面来验证文法G′[S]是否是LL
（1）文法。
对于文法G′[S]，因为有：
对于产生式S→（L）∣aS′，有FIRST（（L））∩FIRST（aS′）={（}∩{a}=∅；
对于产生式S′→S∣ε，有FIRST（S）∩FOLLOW（S′）={a,（}∩{,,）,#}=∅；
对于产生式L′→,SL′|ε，有FIRST（,SL′）∩FOLLOW（L′）={,}∩{）}=∅；
所以文法G′[S]即为所求的与G等价的LL
（1）文法。
（2）文法G′[S]的LL
（1）分析表如表6-
（2）所示:
表6-
（2） 文法G′[S]的LL
（1）分析表
a
（
）
#
S
S′
L
L′
对符号串i*i+i进行简单优先分析的过程如表7所示。
因为分析成功，所以符号串i*i+i是文法G′[E]的合法句子。
表7 符号串i*i+i的语法分析过程
步骤
分析栈
关系
当前符号
余留输入串
句柄
所用产生式
低于
i
*i+i#
1
#i
优于
*
i+i#
F→i
2
#F
F
T→F
3
#T
等于
4
#T*
+i#
5
#T*i
+
i#
6
#T*F
T*F
T→T*F
7
T
T1→T
8
#T1
T1
E1→T1
9
#E1
10
#E1+
11
#E1+i
12
#E1+F
13
#E1+T
14
#E1+T1
E1+T1
E1→E1+T1
15
E1
E→E1
16
#E
分析成功
相应的四元式序列为：
（1） （j<
a,b,5）
（2） （j,0,0,3）
（3） （j<
c,0,5）
（4） （j,0,0,10）
（5） （+,b,2,T1
（6） （=,T1
0,b）
（7） （-,c,1,T2
（8） （=,T2
0,c）
（9） （j,0,0,17）
（10）（j≤,a,d,12）
（11）（j,0,0,17）
（12）（-,a,2,T3
（13）（=,T3
0,a）
（14）（+,d,1,T4
（15）（=,T4
0,d）
（16）（j,0,0,10）
（17）
划分基本块后的流程图如图（a）所示，外提不变运算后的流程图如图（b）所示。
削弱运算强度后的流程图如图（c）所示，消除归纳变量后的流程图如图（d）所示。
模拟试题2
一、填空题（每空1分，共10分）
1．设G[S]是一文法，我们把G产生的
（1）所组成的集合称为G产生的语言，且记为L（G）。
2.一个句型的最左直接短语（即规范分析中，最先被归约的子串）称之为此句型的
（2）。
3．一个状态转换图是由一组矢线连接的有限个结点所组成的（3）。
每一结点均代表在识别或分析过程中扫描器所处的状态。
其中含有一个（4）和若干个终态，分别指示分析的开始和结束。
4.所谓自顶向下的语法分析，就是对已给的输入符号串w，试图（5）地为它构造一棵语法树。
或者说，从文法的开始符号出发，为w构造一个（6）。
5.为了对含有下标变量的赋值语句产生中间代码，需要定义如下两种形式的四元式：
其一是所谓（7）四元式（=[]，T1[T]，0，X）；
另一种是（8）四元式（[]=，X，0，T1[T]）。
6.设d是结点n的（9），若在流程图中，存在着从结点n到d的有向边，则称此有向边n→d为流程图中的一条（10）。
试描述由下列文法所产生的语言：
S→aABb A→Aab∣ε B→aA∣a
三、证明题（共10分）
试证明文法:
Z→aZbZ∣aZ∣a
为二义性文法。
四、应用题（共20分）
（1）将如图所示的NFA确定化（10分）
（2）将所得DFA最小化（10分）
五、简答题（共10分）
消除下列文法的左递归性:
Z→Ac∣Ba A→Zb∣a B→Zd∣c
S→aAc A→b∣bB B→e∣dB
（1）构造此文法的LR（0）项目集及状态转换图；
（10分）
（2）构造SLR
（1）分析表。
七、简答题（共10分）
设有三维PASCAL数组A[1·
·
10,1·
20,1·
30]，将下列语句翻译成四元式序列：
X:
=A[2*I,J+1,I]+Y/Z
八、应用题（共10分）
对于如下的基本块，若变量G，L，M在基本块出口之后被引用：
A:
=B*C
D:
=B/C
E:
=6
F:
=2*E
G:
H:
=A+D
L:
=H*F
M:
=L
（1）构造相应的DAG；
（2）重建经优化后的四元式序列。
模拟试题2答案
（1）全部句子
（2）句柄 （3）有向图 （4）初始状态 （5）自上而下
（6）最左推导 （7）变址取数 （8）变址存数 （9）必经结点 （10）回边
L[G]={a（ab）na（ab）mb∣n,m≥0}
证明：
因为文法G[Z]的一个句子aaabaaba对应如下的两个最左推导序列：
Z⇒aZbZ⇒aaZbZbZ⇒aaabZbZ⇒aaabaZbZ⇒aaabaabZ⇒aaabaaba
Z⇒aZbZ⇒aaZbZ⇒aaabZ⇒aaabaZbZ⇒aaabaabZ⇒aaabaaba
所以文法G[Z]为二义性文法。
（1）将具有ε动作的NFAM确定化后得DFAM′，其状态转换矩阵如图（a）所示，给各状态重新命名，即令：
[S,A]=1, [A,C]=2, [B,A,C]=3, [B,A]=4
且由于2和3的组成中均含有M的终态C，故2和3组成了DFAM′的终态集Z′。
于是，所构造之DFAM′的状态转换矩阵和状态转换图如图（b）及（c）所示。
（d）最小化后的DFAM〞的状态转换图
（2）现将DFAM′最小化：
（ⅰ）初始分划由两个子集组成，即
π0:
{1,4},{2,3}
（ⅱ）为得到下一分划，考察子集{1,4}。
因为
{1}a
={4}a
={2}
{1}b
={4}b
={3}
故1和4不可区分，于是便得到下一分划
π1:
{1,4},{2,3}
（ⅲ）再考虑{2,3}，因为
{2}b={4}ì
{1,4}
而 {3}b={3}ì
{2,3}
故2和3可区分，从而又得到
π2:
{1,4},{2},{3}
此时子集已全部分裂，故最小化的过程宣告结束。
（ⅳ）现选择状态1作为{1,4}的代表，将状态4从状态转换图中删去，并将原来引至4的矢线都引至1，这样，我们就得到了最小化后的DFAM〞如图（d）所示。
文法G[Z]中的Z,A,B都是间接左递归的非终结符号。
将A-产生式和B-产生式的右部代入产生式
Z→Ac∣Ba
中，并消除无用符号A,B后得到与原文法等价的文法G′[Z]：
Z→Zbc∣ac∣Zda∣ca
文法G′[Z]中的Z是直接左递归的非终结符号，则消除Z-产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G"
[Z]：
Z→acZ′∣caZ′
Z′→bcZ′∣daZ′∣ε
（1）在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 3.A→bB
1.S→aAc 4.B→e
2.A→b 5.B→dB
识别文法G[S]全部可归前缀的DFA如图所示。
（2）由图可知，在项目集I4中存在“移进-归约”冲突。
在项目集I4中,由于FOLLOW（A）={c}，FOLLOW（A）∩{e,d}=∅，所以其项目集的“移进-归约”冲突能通过SLR
（1）规则得到解决，所以文法G[S]是SLR
（1）文法。
因为FOLLOW（S）={#}，FOLLOW（A）={c}，FOLLOW（B）={c}，所以文法G[S]的SLR
（1）分析表如下表所示。
状态
ACTION
GOTO
b
c
d
e
A
B
s2
acc
s4
s5
r2
s8
s7
r1
r3
r4
r5
（1） （*,2,I,T1
（2） （+,J,1,T2
（3） （*,T1
20,T3
（4） （+,T2
T3
（5） （*,T3
30,T4
（6） （+,I,T4
T4
（7） （-,a,C,T5
（8） （=[],T5[T4],0,T6）
（9） （/,Y,Z,T7）
（10）（+,T6
T7
T8
（11） （=,T8
0,X）
（1）相应的DAG如图所示。
（2）优化后的代码为：
D:
G:
H:
=G+D
L:
=H*12
M:
升级会员 