东师《编译原理》练习题二
一、选择题
1. 文法 G 产生的D的全体是该文法描述的语言。
A ．句型                B. 终结符集
C. 非终结符集
D. 句子
2. 设M为一DFA，并设s 和t是M的两个不同状态。如果s和t    A  ，则称s 和t等价。
A．不可区分          B．可划分
C．可区分            D．待区分
3. 下列说法中正确的是    B 。
A. 所谓递归下降法，是指只能对具有左递归性的文法进行分析的一种语法分析方法。
B. 如果一个文法具有二义性，则它必然不是LL(1)文法。
C. 对于文法G，当进行自顶向下的语法分析时，不会出现回溯的主要条件是，对于G中
的每个
A∈V N，A产生式的所有不同候选式均能推导出以同一终结符号开始的符号串。
D. 对任意非LL(1)文法而言，通过消除左递归和反复提取左因子，都能将其改造为LL(1)文法。
4. 简单优先分析每次归约的是  C  。
A. 最左直接短语
B.直接短语
C.最左素短语
D.控制结点
5. 下列表示中，A是与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=(V N,V T,P,S)是一文法，我们说文法G中的一个符号X∈V N∪V T是有用的，是指X至少出现在一个句子的推导过程中，否则，就说X是无用的。我们将不含形如A→A的产生式和不含无用符号及无用产生式的文法称为已化简的文法。
7．我们常采用形如 (class, value)的二元式作为一个单词的内部表示。
其中,class是一个整数，用来指示该单词的类别，value则是单
词之值。
8．LL(1)分析表可用一个二维数组表示，它的每一行与文法的一个非
终结符号相关联，而其每一列则与文法的一个终结符号或界符#  相关联。
9．若在一个文法G中，不含有形如U→…AB…的产生式，其中A,B∈V N，则
称G为算符文法。
10．将每一运算符都置于其运算对象之后的表达式称为后缀表示，也称为逆波兰表示。
11．把流程图中具有如下性质的一组结点称为程序中的一个循环：(ⅰ) 在这组结点中，有
惟一的入口结点，使得从循环外到循环内任何结点的
所有通路，都必通过此结点；(ⅱ) 这一组结点是强连通的。
12．设G［S］是一个文法，我们把能由文法的开始符号S推导出来的符号
串α称为G的一个句型。当句型α仅由终结符号组成时 (即α∈V T*)，则将它称为G产生的句子。
13．从某一给定的状态q出发，仅经过若干条标记为ε的矢线所
能达到的状态所组成的集合称为ε-CLOSURE(q)。
14．所谓递归下降法，是指对文法的每一非终结符号，都根据相应产生式各候选式的结构，为其编写一个子程序或函数，用来识别该非终结符号所表示的
语法范畴。
15．在每一LR(0)项目［A→α·β］中放置一个向前搜索符号              a ，使之成为［A→α·β,a］的形式，我们将此种项目称为一个LR(1)项目。
16．所谓语法制导翻译，就是对文法中的每个产生式
都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推正则化其实是破坏最优化
导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相
应的语义动作或调用相应的语义子程序。
二、简答题
1、消除文法:    S→AbB∣A      A→AB∣caB∣B      B→Aa∣b  中的单产生式。
1、解：首先求出如下集合
W(S)={S,A,B}, W(A)={A,B}, W(B)={B}
然后按如下步骤得到产生式集P′：
将P中的所有非单产生式添加到P′中：
S→AbB      A→AB∣caB      B→Aa∣b
因为A,B∈W(S)，故将A,B的所有非单产生式的右部作为S-产生式的右部添加到P′中：S→AB∣caB          S→Aa∣b
因为B∈W(A)，故将B的所有非单产生式的右部作为A-产生式的右部添加到P′中：A→Aa∣b
由此得到消除单产生式后的文法如下：
S→AbB∣AB∣caB∣Aa∣b
A→AB∣caB∣Aa∣b
B→Aa∣b
2、消除文法:    S→ABb∣a      A→aB∣caB∣ε      B→aA∣b∣ε中的ε-产生式。解：对于G，我们可得到W={A,B}，于是得到消除ε-产生式后的文法为：
S→ABb∣a∣Bb∣Ab∣b
A→aB∣caB∣a∣ca
B→aA∣b∣a
3、试构造一文法，使其描述语言：  L(G)={ a n b m c m d n∣m,n≥1 }
解：对应的文法为： S→aAd
A→aAd∣bBc
B→bBc∣ε
三、应用题
1、设有文法G[S]： S→aBc∣bAB      A→aAb∣b    B→b∣ε
(1) 构造该文法的LL(1)分析表；  (2) 分析符号串baabbb是否为该文法的句子。
解： (1) 文法G[S]的LL(1)分析表如表所示:
a    b    c #
S S→aBc S→bAB
A A→aAb A→b
B B→b B→εB→ε
(2) 对符号串baabbb的分析过程如表所示：
步骤分析栈余留输入串所用产生式
1 #S baabbb#  S→bAB
2  #BAb baabbb#
3  #BA aabbb#      A→aAb
4 #bAa aabbb#
5  #bA abbb#      A→aAb
6 #bAbAa abbb#
7 #bAbA bbb#      A→b
8 #bAbb bbb#      S′→bS′
9 #bA b#      A→b
10 #bb b#
11 #b    #  分析失败
因为分析失败，所以符号串baabbb不是该文法的句子。
2、将如图所示的具有ε动作的NFA确定化：
解：(1) 将具有ε动作的NFA M确定化后得DFA M′，其状态转换矩阵如图(a)所示，
给各状态重新命名，即令：
[S,1,4]=1,  [1,2,3,4]=2,  [1,4,Z]=3,  [1,4]=4,  [1,3,4,Z]=5
且由于3和5的组成中均含有M的终态Z，故3和5组成了DFA M′的终态集Z′。于是，所构造之DFA M′的状态转换矩阵和状态转换图如图(b)及(c)所示。
3、将如图所示的NFA确定化：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。