计算机编译原理练习题讲义.docx
《计算机编译原理练习题讲义.docx》由会员分享,可在线阅读,更多相关《计算机编译原理练习题讲义.docx(12页珍藏版)》请在冰点文库上搜索。
计算机编译原理练习题讲义
编译原理练习题一
一、选择题
1.下列文法中,不是产生语言{abna∣n≥1}的文法。
A.A→aBaB→b∣bBB.A→aBB→ba∣bB
C.A→aBB→ba∣bBaD.A→aBB→bCC→bC∣a
2.设有文法G[S]:
S→aABA→bAc∣εB→bB∣Ae∣ε
则经消去ε-产生式后与G等价的文法G1[S]为。
A.S→aA∣aB∣aAB∣aA→bc∣bAcB→bB∣Ae∣b∣e
B.S→aABA→bAcB→bB∣Ae
C.S→aA∣aBA→bcB→b∣e
D.S→aA∣aB∣aA→bc∣bAcB→bB∣Ae∣b∣e
3.下列文法中,是LL
(1)文法。
A.S→bBS′aS′→aBS′∣εA→S∣aB→Ac
B.S→bS∣bA∣bA→aA∣a
C.E→E+T∣TT→T*F∣FF→(E)∣i
D.S→bBS′S′→aBS′∣εA→S∣aB→Ac
4.下列文法中,是简单优先文法。
A.E→E+T∣TT→T*F∣FF→(E)∣i
B.S→A/A→aA∣AS∣/
C.E→E+E∣E*E∣(E)∣i
D.E→E1E1→E1+T1∣T1T1→TT→T*F∣FF→(E)∣i
5.当扫视到数组说明进行语义处理时,必须把一个数组的如维数、各维的上、下界等记录下来。
为了便于引用,通常是把上述内容存放于数组相应的之中。
A.信息向量B.内情向量C.地址向量D.指针向
6.设有文法G[S]:
S→aS∣W∣UU→aV→bV∣acW→aW
则经化简后与G等价的文法G1[S]为。
A.S→aS∣WV→bV∣acW→aW
B.S→aS∣UU→a
C.S→aS∣W∣UU→aW→aW
D.S→aSV→bV∣ac
7.下列文法中,是LL
(1)文法。
A.S→aS∣aAA→bA∣ac
B.S→AS∣bA→SA∣a
C.E→E+E∣E*E∣(E)∣i
D.S→aS∣bAA→bA∣ac
8.所谓相容,是指在一个项目集中,不出现这样的情况,和归约项目并存,或多个归约项目并存。
A.移进项目B.基本项目C.待约项目D.后继项目
9.下列表示中,不是目前经常使用的中间语言的形式。
A.逆波兰式B.四元式C.五元式D.树形表示
10.如果从流程图的首结点到流程图中某一结点n的所有通路都要经过结点d,我们就说结点d控制了结点n,或者把d称为n的必经结点,记作。
A.dDFAnB.dDOMnC.dDAGnD.dDAMn
二、证明题
1、试证明文法S→aB∣bAA→aS∣bAA∣aB→aBB∣bS∣b为二义性文法。
三、简答题
对于如下文法,求各候选式的FIRST集和各非终结符号的FOLLOW集。
S→ACAB|bA|εA→aAd|eB→bB|cC→cC|
四、应用题
1、对于如下的状态转换矩阵
分别画出相应的状态转换图;(10分)
(2)写出相应的3型文法。
2、将如图所示的DFA最小化。
五、应用题
1、设有文法G[E]:
E→E+T|TT→T*F|FF→(E)|i
其相应的算符优先矩阵如下图所示,试给出对符号串i*i+i进行算符优先分析的过程。
(
i
*
+
)
#
(
i
*
+
)
#
2、
试描述由文法:
S→aAdA→aAd∣bBcB→bBc∣e所产生的语言。
六、应用题
1、设有文法G[S]:
S→aABbA→Acd∣dB→Bce∣e
(1)将其改写为LL
(1)文法;
(2)构造改写后文法的LL
(1)分析表。
2、已知文法G[S]:
S→aABA→bA∣aB→cB∣b的LR(0)项目集及状态转换图如下图所示,
(1)构造LR(0)分析表;
(2)给出对输入符号串abacb的LR分析过程。
七、简答题
1、设有二维PASCAL数组A[1··10,1··20],给出赋值语句A[I,J]:
=X+Y*Z的四元式序列。
2、将逆波兰式:
ABCD/-*EF*+改写为中缀式。
八、简答题
1、设有如下的三地址码(四元式)序列:
A:
=5
I:
=1
J:
=2
L1:
ifI≤JgotoL3
X:
=I*A
L2:
I:
=I-J
ifI>JgotoL2
J:
=J+1
I:
=N
gotoL1
L3:
X:
=J*A
试将它划分为基本块,并作控制流程图。
2、设有如下的三地址码(四元式)序列:
I:
=1
readL,M
L1:
ifI>10gotoL2
A:
=L*M
B:
=L*I
C:
=M*A
D:
=M+B
I:
=I+1
gotoL1
L2:
halt
对其中的循环进行循环不变运算外提的优化。
编译原理练习题二
一、选择题
1.文法G产生的的全体是该文法描述的语言。
A.句型B.终结符集
C.非终结符集D.句子
2.设M为一DFA,并设s和t是M的两个不同状态。
如果s和t,则称s和t等价。
A.不可区分B.可划分
C.可区分D.待区分
3.下列说法中正确的是。
A.所谓递归下降法,是指只能对具有左递归性的文法进行分析的一种语法分析方法。
B.如果一个文法具有二义性,则它必然不是LL
(1)文法。
C.对于文法G,当进行自顶向下的语法分析时,不会出现回溯的主要条件是,对于G中的每个
A∈VN,A产生式的所有不同候选式均能推导出以同一终结符号开始的符号串。
D.对任意非LL
(1)文法而言,通过消除左递归和反复提取左因子,都能将其改造为LL
(1)文法。
4.简单优先分析每次归约的是。
A.最左直接短语B.直接短语
C.最左素短语D.控制结点
5.下列表示中,是与f×(e+(a×d+c)/d)相应的逆波兰式。
A.fead×c+d/+×B.f×e+a×d+c/d
C.fad×+c/d+e×D.ad×c+d/e+f×
6.设G=(VN,VT,P,S)是一文法,我们说文法G中的一个符号X∈VN∪VT是有用的,是指X至少出现在的推导过程中,否则,就说X是无用的。
我们将不含形如A→A的产生式和不含无用符号及无用产生式的文法称为。
7.我们常采用形如(class,value)的二元式作为一个单词的。
其中,class是一个整数,用来指示该单词的,value则是单词之值。
8.LL
(1)分析表可用一个表示,它的每一行与文法的一个非终结符号相关联,而其每一列则与文法的一个终结符号或相关联。
9.若在一个文法G中,不含有形如的产生式,其中A,B∈VN,则称G为算符文法。
10.将每一运算符都置于其的表达式称为后缀表示,也称为逆波兰表示。
11.把流程图中具有如下性质的一组结点称为程序中的一个循环:
(ⅰ)在这组结点中,有惟一的,使得从循环外到循环内任何结点的所有通路,都必通过此结点;(ⅱ)这一组结点是。
12.设G[S]是一个文法,我们把能由文法的推导出来的符号串α称为G的一个句型。
当句型α仅由组成时(即α∈VT*),则将它称为G产生的句子。
13.从某一给定的状态q出发,仅经过若干条的矢线所能达到的状态所组成的集合称为ε-CLOSURE(q)。
14.所谓递归下降法,是指对文法的每一非终结符号,都根据相应产生式各候选式的结构,为其编写一个,用来识别该非终结符号所表示的。
15.在每一LR(0)项目[A→α·β]中放置一个a,使之成为[A→α·β,a]的形式,我们将此种项目称为一个。
16.所谓,就是对文法中的都附加一个语义动作或语义子程序,且在语法分析过程中,每当需要使用一个产生式进行推导或归约时,语法分析程序除执行相应的外,还要执行相应的语义动作或调用相应的语义子程序。
二、简答题
1、消除文法:
S→AbB∣AA→AB∣caB∣BB→Aa∣b中的单产生式。
2、消除文法:
S→ABb∣aA→aB∣caB∣εB→aA∣b∣ε中的ε-产生式。
3、试构造一文法,使其描述语言:
L(G)={anbmcmdn∣m,n≥1}
三、应用题
1、设有文法G[S]:
S→aBc∣bABA→aAb∣bB→b∣ε
(1)构造该文法的LL
(1)分析表;
(2)分析符号串baabbb是否为该文法的句子。
2、将如图所示的具有ε动作的NFA确定化:
3、将如图所示的NFA确定化:
四、简答题(
1、对正规式((a∣b)*∣ab*)b,构造与其相应的状态转换图。
2、设有文法G[Z]:
Z→ZAc∣BaA→Ab∣aB→Bd∣c,将其改写为LL
(1)文法。
3、消除文法:
S→aAcA→Bb∣aB→Ad∣c的左递归性。
五、应用题
1、设有文法G′[E]:
E→E1E1→E1+T1|T1T1→TT→T*F|FF→(E)|i
其相应的简单优先矩阵如下图所示,试给出对符号串i+i进行简单优先分析的过程。
2、设有文法G[S]:
S→ABACA→aDB→bC→dD→c
(1)构造此文法的LR(0)项目集及状态转换图;)
(2)构造SLR
(1)分析表。
3、设有文法G[S]:
S→aABA→bA∣aB→cB∣b
(1)构造此文法的LR(0)项目集及状态转换图;
(2)构造LR(0)分析表。
六、简答题
1、将语句:
IFa
=b+2ELSEa:
=a-2翻译成四元式序列。
2、将语句:
whileA0doC:
=C+B*D翻译成四元式序列。
3、将中缀式A+B*(C-D)/(E+F)改写为逆波兰式。
七、应用题
1、对于如右所示的基本块,若变量G,MA:
=B+C
在基本块出口之后被引用,D:
=3
(1)构造相应的DAG;(5分)E:
=6
(2)重建经优化后的四元式序列。
(5分)F:
=D*E
G:
=B+C
H:
=A+D
L:
=H*F
M:
=L
2、对于如下的程序,试对其中的循环进行削弱运算强度的优化。
33、对于如图所示的控制流程图:
(1)求出各个结点的必经结点集;
(2)求出各个回边,并找出流程图的全部循环。