编译原理教程课后习题答案——第三章(3)

句柄(即最左直接短语)：S 可以通过分析图3-8的语法树来求素短语和最左素短语，即找出语法树中的所有相邻终结符(中间可有一个非终结符)之间的优先关系。确定优先关系的原则是： ① 同层的优先关系为； ② 不同层时，层次离树根远者优先级高，层次离树根近者优先级低(恰好验证了优先关系表的构造算法)； ③ 在句型ω两侧加上语句括号“#”，即#ω#，则有#?ω和ω?#，由此我们得到句型(SdSdS)的优先关系如图3-9所示。

因此，由图3-9得到SdS为句型(SdSdS)的素短语，它同时也是该句型的最左素短语。 (3) 输入串(adb)#的分析过程见表3-7。 表3-7 输入串(adb)#的分析过程 符号栈 输入串 说 明 # (adb)# 移进 #( adb)# 移进 #(a db)# 用S→a归约 #(S db)# 移进 #(Sd b)# 移进 #(Sdb )# 用S→b归约 #(SdS )# 用A→S归约 #(SdA )# 用A→SdA归约 #(A )# 移进 #(A) # 用S→(A)归约 #S # 分析成功 为便于分析，同时给出了(adb)#的语法树，如图3-10所示。

S

(A) SdA

aS

b图3-10 (adb)的语法树

3.14 在算符优先分析法中，为什么要在找到最左素短语的尾时才返回来确定其对应的头，能否按扫描顺序先找到头后再找到对应的尾，为什么？ 【解答】 设句型的一般形式为N1a1N2a2…NnanNn+1。其中，每个ai都是终结符，而Ni则是可有可无的非终结符。对上述句型可以找出该句型中的所有素短语，每个素短语都具有如下形式：

…aj-1?ajaj+1…ai?ai+1… 如果某句型得到的优先关系如下： …?…?……?…? 则当从左至右扫描到第一个“?”时，再由此从右至左扫描到第一个“?”时，它们之间(当然不包含第一个“?”前一个终结符和第二个“?”后一个终结符)即为最左素短语。

如果由左至右扫描到第一个“?”，可以看出这并不一定是最左素短语的开头，因为由它开始

并不一定是素短语(在其内部还可能包含其他更小的素短语)，所以，在算符优先分析算法中，只有先找到最左素短语的尾(即“?”)，才返回来确定与其对应的头(即“?”)；而不能按扫描顺序先找到头然后再找到对应的尾。 3.15 试证明在算符文法中，任何句型都不包含两个相邻的非终结符。 【解答】 设文法G=(VT,VN,S, ξ)，其中VT是终结符集；VN是非终结符集；ξ为产生式集合；S是开始符号。 对句型的推导长度n作如下归纳： (1) 当n=1时，S?α，则存在一条产生式S→α属于ε，其中a∈(VT∪VN) *。由于文法是算符文法，所以α中没有两个相邻非终结符，故归纳初始成立。 (2) 设n=k时结论成立，则对任何k+1步推导所产生的句型必为 Sα∪β?α∨β 其中，α、β∈(VT∪VN) *，U∈VN，而U→V是一条产生式。

由归纳假设，U是非终结符，设α=α1α2…αn，β=β1β2…βm，其中αi、βj ∈(VT∪VN) (1≤i≤n-1,2≤j≤m) ；但αn和βm必为位于U两侧的终结符。 设V=V1V2…Vr，由于它是算符文法的一个产生式右部候选式，因此V1V2…Vr中不会有相邻的非终结符出现。又因为αnV1和Vrβ1中的αn、β1为终结符，也即在推导长度为k+1时所产生的句型

α1α2…αnV1V2…Vrβ1β2…βm 不会出现相邻的非终结符，故n=k+1时结论成立。显然，在α或β为空时结论也成立。

3.16 给出文法G[S]: S→aSb∣P P→bPc∣bQc

Q→Qa∣a (1) 它是Chomsky哪一型文法？ (2) 它生成的语言是什么？ (3) 它是不是算符优先文法？请构造算符优先关系表证实之； (4) 文法G[S]消除左递归、提取公共左因子后是不是LL(1)文法？请证实。

【解答】 (1) 根据Chomsky的定义，对任何形如A→β的产生式，有A∈VN，β∈(VT∪VN)*时为2型文法。而文法G[S]恰好满足这一要求，故为Chomsky 2型文法。 (2) 由文法G[S]可以看出：S推出串的形式是ai P bi(i≥0)，P推出串的形式是bjQcj(j≥1)，Q推出串的形式是ak(k≥1)。因此，文法G[S]生成的语言是L={aibjakcjbi|i≥0, j≥1, k≥1}。

(3) 求出文法G[S]的FIRSTVT集和LASTVT集： FIRSTVT(S)={a,b} FIRSTVT(P)={b} FIRSTVT(Q)={a}

LASTVT(S)={b,c} LASTVT(P)={c} LASTVT(Q)={a} 构造优先关系表如表3-8所示。 由于在优先关系中同时出现了a?a和a?a以及b?b和b?b，故文法G[S]不是算符优先文法。

表3-8 优先关系表 a b c a ? ? ? ? b ? ? c ? ?

(4) 消除文法G[S]的左递归： S→aSb | P P→bPc | bQc Q→aQ′

Q′→aQ′| ε 提取公共左因子后得到文法G′[S]: S→aSb | P P→bP′ P′→Pc | Qc Q→aQ′

Q′→aQ′| ε

求每个非终结符的FIRST集和FOLLOW集如下： FIRST(S)={a,b} FIRST(P)={b} FIRST(P′)={a,b} FIRST(Q)={a} FIRST(Q′)={a, ε}

FOLLOW(S)={b,#} FOLLOW(P)={b,c,#} FOLLOW(P′)={b,c,#} FOLLOW(Q)={c} FOLLOW(Q′)={c}

通过检查G′[S]可以得到： ① 每一个非终结符的所有候选式首符集两两不相交； ② 存在形如A→ε的产生式Q′→aQ′| ε，但有

FIRST(aQ′)∩FOLLOW(Q′)={a}∩{c}=Φ 所以文法G′[S]是LL(1)文法。

**3.17 LR分析器与优先关系分析器在识别句柄时的主要异同是什么？

【解答】 如果S?aAδ且有A?β，则称β是句型αβδ相对于非终结符A的短语。特别的，如果有A?β，则称β是句型αβδ相对于规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。规范归约是关于α的一个最右推导的逆过程，因此，规范归约也称最左归约。请注意句柄的“最左”特征。

LR分析器用规范归约的方法寻找句柄，其基本思想是：在规范归约的过程中，一方面记住已经归约的字符串，即记住“历史”；另一方面根据所用的产生式推测未来可能碰到的输入字符串，即对未来进行“展望”。当一串貌似句柄的符号串呈现于栈顶时，则可根据历史、展望以及现实的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。事实上，规范归约的中心问题恰恰是如何寻找或确定一个句型的句柄。给出了寻找句柄的不同算法也就给出了不同的规范归约方法，如LR(0)、SLR(1)、LR(1)以及LALR就是在归约方法上进行区别的。 算符优先分析不是规范归约，因为它只考虑了终结符之间的优先关系，而没有考虑非终结符之间的优先关系。此外，算符优先分析比规范归约要快得多，因为算符优先分析跳过了所有单非产生式所对应的归约步骤。这既是算符优先分析的优点，同时也是它的缺点，因为忽略非终结符在归约过程中的作用存在某种危险性，可能导致把本来不成句子的输入串误认为是句子，但这种缺陷容易从技术上加以弥补。为了区别于规范归约，算符优先分析中的“句柄”被称为最左素短语。

3.18 什么是规范句型的活前缀？引进它的意义何在？ 【解答】 在讨论LR分析器时，需要定义一个重要概念，这就是文法的规范句型

的“活前缀”。 字的前缀是指该字的任意首部，例如，字abc的前缀有ε、a、ab或abc。所谓活前缀，是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。之所以称为活前缀，是因为在其右边增添一些终结符号后，就可以使它成为一个规范句型。 引入活前缀的意义在于它是构造LR(0)项目集规范族时必须用到的一个重要概念。 对于一个文法G，首先要构造一个NFA，它能识别G的所有活前缀，这个NFA的每个状态即为一个“项目”。文法G每一个产生式的右部添加一个圆点称为G的一个LR(0)项目(简称项目)，可以使用这些项目状态构造一个NFA。我们能够把识别活前缀的NFA确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。构成识别一个文法活前缀的DFA项目集(状态)的全体称为这个文法的LR(0)项目集归范族。 3.19 试构造下述文法的SLR(1)分析表。 G[S]: S→bASB | bA A→dSa | e B→cAa | c 【解答】 首先将文法G[S]拓广为G[S′]: G[S′]： (0) S′→S (1) S→bASB (2) S→bA (3) A→dSa (4) A→e (5) B→cAa (6) B→c 构造文法G[S′]的LR(0)项目集规范族如下： I0: S′→·S I5: A→e· S→·bASB I6: S→bAS·B S→·bA B→·cAa I1: S′→S· B→·c I2: S→b·ASB I7: A→dS·a S→b·A I8: S→bASB· A→·dSa I9: B→c·Aa A→·e B→c· I3: S→bA·SB A→·dSa S→bA· A→·e S→·bASB I10: A→dSa· S→·bA I11: B→cA·a I4: A→d·Sa I12: B→cAa· S→·bASB S→·bA 文法G[S′]的DFA如图3-11所示。

I0： S′→·S S→·bASB S→·bA S S′→S· I1： I：S→bA·SBSb I：S→b·ASBA3 S→bA·2 S→b·A S→·bASBb A→·dSa S→·bA A→·eee I5：A→e·dbS I7：A→dS·a I4：A→d·Sa S→·bASBa S→·bA I10：A→dSa· I6：S→bAS·BB I：S→bASB·8 B→·cAa B→·cc I9：B→c·Aa B→c· A→·dSa A→·edA I11：B→cA·aa I12：B→cAa· 图3-11 文法G[S′]的DFA

注意，在比较熟练的情况下，也可以不构造LR(0)项目集规范族而直接画出文法G[S′]的DFA。 由于I3和I9既含有移进项目又含有归约项目，故文法G[S]不是LR(0)文法。我们构造文法G[S′]的FOLLOW集如下： (1) FOLLOW(S′)={#}； (2) 由S→…AS…得FIRST(S)\\{ ε}FOLLOW(A)；即FOLLOW(A)={b}； 由S→…SB得FIRST(B)\\{ ε}FOLLOW(S)；即FOLLOW(S)={c}； 由A→…Sa得FIRST(′a′)\\{ ε}FOLLOW(S)；即FOLLOW(S)={a,c}； (3) 由S′→S得FOLLOW(S′)FOLLOW(S)，即FOLLOW(S)={a,c,#}； 由S→…B得FOLLOW(S)FOLLOW(B)，即FOLLOW(B)={a,c,#}；

由S→…A得FOLLOW(S)FOLLOW(A)，即FOLLOW(A)={a,b,c,#}； 对I3有：{b}∩FOLLOW(S)={b}∩{a,c,#}=Φ 对I9有：{d,e}∩FOLLOW(B)={d,e}∩{a,c,#}= Φ 故文法G[S]是SLR(1)文法。最后得到SLR(1)分析表见表3-9。 表3-9 SLR(1)分析表

ACTION GOTO 状态 a b c d e # S A B 0 s2 1 1 acc 2 s4 s5 3

3 r2 s2 r2 r2 6

4 s2 7

5 r4 r4 r4 r4

6 s9 8 7 s10 8 r1 r1 r1 9 r6 r6 s4 s5 r6 11

10 r3 r3 r3 r3

11 s12

12 r5 r5 r5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理教程课后习题答案——第三章(3)在线全文阅读。