奥鹏作业答案-谋学网

 找回密码
 会员注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

VIP会员,3年作业免费下 !奥鹏作业,奥鹏毕业论文检测新手作业下载教程,充值问题没有找到答案,请在此处留言!
2020年07月最新全国统考资料投诉建议,加盟合作!点击这里给我发消息 点击这里给我发消息
奥鹏课程积分软件(ver:3.1)
查看: 993|回复: 0

东师《编译原理》练习题辅导资料

[复制链接]
发表于 2015-3-16 15:32:24 | 显示全部楼层 |阅读模式
谋学网
编译原理练习题一
一、选择题

1. 下列文法中,           不是产生语言 {abna∣n≥1} 的文法。
A.A→aBa        B→b∣bB        B.A→aB          B→ba∣bB      
C.A→aB         B→ba∣bBa      D.A→aB          B→bC         C→bC∣a
2. 设有文法G[S]:S→aAB       A→bAc∣ε       B→bB∣Ae∣ε
则经消去ε-产生式后与G等价的文法G1[S]为             。
A.S→aA∣aB∣aAB∣a       A→bc∣bAc        B→bB∣Ae∣b∣e
B.S→aAB       A→bAc      B→bB∣Ae        
C.S→aA∣aB      A→bc     B→b∣e
D.S→aA∣aB∣a       A→bc∣bAc      B→bB∣Ae∣b∣e
3. 下列文法中,           是LL(1)文法。      
A.S→bBS′a     S′→aBS′∣ε   A→S∣a    B→Ac
B.S→bS∣bA∣b     A→aA∣a            
C.E→E+T∣T    T→T*F∣F     F→(E)∣i
D.S→bBS′      S′→aBS′∣ε   A→S∣a    B→Ac
4. 下列文法中,           是简单优先文法。      
A.E→E+T∣T    T→T*F∣F      F→(E)∣i            
B.S→A/        A→aA∣AS∣/
C.E→E+E∣E*E∣(E)∣i      
D.E→E1   E1→E1+T1∣T1     T1→T   T→T*F∣F   F→(E)∣i
5. 当扫视到数组说明进行语义处理时,必须把一个数组的如维数、各维的上、下界等记录下来。为了便于引用,通常是把上述内容存放于数组相应的            之中。
A.信息向量        B.内情向量       C.地址向量       D.指针向
6. 设有文法G[S]:   S→aS∣W∣U       U→a           V→bV∣ac      W→aW
则经化简后与G等价的文法G1[S]为           。
A.S→aS∣W          V→bV∣ac      W→aW         
B.S→aS∣U          U→a      
C.S→aS∣W∣U       U→a           W→aW         
D.S→aS             V→bV∣ac
7. 下列文法中,          是LL(1)文法。   
A.S→aS∣aA         A→bA∣ac              
B.S→AS∣b          A→SA∣a
C.E→E+E∣E*E∣(E)∣i                     
D.S→aS∣bA         A→bA∣ac
8. 所谓相容,是指在一个项目集中,不出现这样的情况,            和归约项目并存,或多个归约项目并存。   
A.移进项目        B.基本项目      C.待约项目        D.后继项目
9. 下列表示中,            不是目前经常使用的中间语言的形式。  
A.逆波兰式        B.四元式       C.五元式       D.树形表示
10. 如果从流程图的首结点到流程图中某一结点n的所有通路都要经过结点d,我们就说结点d控制了结点n,或者把d称为n的必经结点,记作            。  
A.d DFA n        B.d DOM n       C.d DAG n       D.d DAM n

二、证明题
1、试证明文法    S→aB∣bA     A→aS∣bAA∣a     B→aBB∣bS∣b    为二义性文法。

三、简答题
对于如下文法,求各候选式的FIRST集和各非终结符号的FOLLOW集。
S→ACAB|bA|ε        A→aAd|e        B→bB|c    C→cC|
四、应用题   
1、对于如下的状态转换矩阵

分别画出相应的状态转换图;(10分)       (2) 写出相应的3型文法。
2、将如图所示的DFA最小化。

五、应用题
1、设有文法G[E]:    E→E+T|T        T→T*F|F       F→(E)|i
其相应的算符优先矩阵如下图所示,试给出对符号串i*i+i进行算符优先分析的过程。
        (        i        *        +        )        #
(        ○<
○<
○<
○<
○=

i                        ○>
○>
○>
○>

*        ○<
○<
○>
○>
○>
○>

+        ○<
○<
○<
○>
○>
○>

)                        ○>
○>
○>
○>

#        ○<
○<
○<
○<
       

2、
试描述由文法:S→aAd      A→aAd∣bBc      B→bBc∣e      所产生的语言。

六、应用题
1、设有文法G[S]: S→aABb      A→Acd∣d     B→Bce∣e
(1) 将其改写为LL(1)文法;
(2) 构造改写后文法的LL(1)分析表。
2、已知文法G[S]:S→aAB     A→bA∣a    B→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 :   if  I≤J  goto L3
          X:=I*A
L2 :   I:=I-J
if  I>J  goto L2
J:=J+1
I:=N
goto L1
   L3:    X:=J*A
试将它划分为基本块,并作控制流程图。

2、设有如下的三地址码(四元式)序列:
   I:=1
read  L,M
L1 :   if  I>10 goto L2
A:=L*M
B:=L*I     
C:=M*A
D:=M+B
I:=I+1
goto L1
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∣A      A→AB∣caB∣B      B→Aa∣b   中的单产生式。
2、消除文法:    S→ABb∣a      A→aB∣caB∣ε      B→aA∣b∣ε     中的ε-产生式。
3、试构造一文法,使其描述语言:  L(G)={ anbmcmdn∣m,n≥1 }

三、应用题
1、设有文法G[S]: S→aBc∣bAB       A→aAb∣b     B→b∣ε
(1) 构造该文法的LL(1)分析表;  (2) 分析符号串baabbb是否为该文法的句子。
2、将如图所示的具有ε动作的NFA确定化:

3、将如图所示的NFA确定化:

四、简答题(
1、对正规式((a∣b) *∣ab*)b ,构造与其相应的状态转换图。
2、设有文法G[Z]: Z→ZAc∣Ba     A→Ab∣a       B→Bd∣c    ,将其改写为LL(1)文法。
3、消除文法:     S→aAc      A→Bb∣a       B→Ad∣c      的左递归性。

五、应用题
1、设有文法G′[E]:  E→E1     E1→E1+T1|T1     T1→T     T→T*F|F     F→(E)|i
其相应的简单优先矩阵如下图所示,试给出对符号串i+i进行简单优先分析的过程。

2、设有文法G[S]: S→ABAC      A→aD       B→b      C→d      D→c
(1)构造此文法的LR(0)项目集及状态转换图;)  (2)构造SLR(1)分析表。
3、设有文法G[S]: S→aAB     A→bA∣a       B→cB∣b
(1)构造此文法的LR(0)项目集及状态转换图;   (2)构造LR(0)分析表。

六、简答题
1、将语句:  IF  a<b ∨ c<0    THEN   b:=b+2      ELSE   a:=a-2       翻译成四元式序列。
2、将语句:   while  A<C∧B>0  do   C:=C+B*D翻译成四元式序列。
3、将中缀式   A+B*(C-D)/(E+F)   改写为逆波兰式。
七、应用题
1、对于如右所示的基本块,若变量G,M                        A:=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) 求出各个回边,并找出流程图的全部循环。


奥鹏作业答案,奥鹏在线作业答案
您需要登录后才可以回帖 登录 | 会员注册

本版积分规则

投诉建议
 
 
客服一
客服二
客服三
客服四
点这里给我发消息
点这里给我发消息
谋学网奥鹏同学群2
微信客服扫一扫
快速回复 返回顶部 返回列表