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

最后得到改造后的文法为 G[A′]：A→aA′ A′→ABl | ε B→dB′

B′→bB′| ε 求得：

FIRST(A)={a} FIRST(A′)={a, ε} FIRST(B)={d} FIRST(B′)={b, ε} 对文法开始符号A，有FOLLOW(A)={#}。 由A′→ABl得FIRST(B)\\{ ε}?FOLLOW(A)，即FOLLOW(A)={#,d}； 由A′→ABl得FIRST(′l′) ?FOLLOW(B)，即FOLLOW(B)={l}； 由A→aA′得FOLLOW(A) ?FOLLOW(A′)，即FOLLOW(A′)={#,d}； 由B→dB′得FOLLOW(B) ?FOLLOW(B′)，即FOLLOW(B′)={l}。 对A′→ABl来说，FIRST(A)∩FOLLOW(A′)={a}∩{#,d}=Φ，所以文法G′[A]为所求等价的LL(1)文法。

(2) 构造预测分析表的方法如下： ① 对文法G[A′]的每个产生式A→α执行②、③步。 ② 对每个终结符a∈FIRST(A)，把A→α加入到M[A,a]中，其中α为含有首字符a的候选式或为唯一的候选式。 ③ 若ε∈FIRST(A)，则对任何属于FOLLOW(A)的终结符b，将A→ε加入到M[A,b]中。把所有无定义的M[A,a]标记上“出错”。 由此得到G[A′]的预测分析表，见表3-1。 表3-1 预测分析表 a b l d # A A→aA′ A′ A′→ABl A′→ε A′→ε B B→dB′ B′ B′→bB′ B′→ε

(3) 输入串aadl的分析过程见表3-2。 表3-2 输入串aadl的分析过程 符号栈 当前输入符号 输入串 说 明 a adl# 弹出栈顶符号A并将A→aA′产生式右部反序压栈 #A a a adl# 匹配，弹出栈顶符号a并读出下一个输入符号a #A′a dl# 弹出栈顶符号A′并将A′→ABl产生式右部反序压栈 #A′ a dl# 弹出栈顶符号A并将A→aA′产生式右部反序压栈 #lBA #lBA′a a dl# 匹配，弹出栈顶符号a并读出下一个输入符号d

#lBA′ d l# 由A′→ε仅弹出栈顶符号A′

#lB d l# 弹出栈顶符号B并将B→dB′产生式右部反序压栈

#lB′d d l# 匹配，弹出栈顶符号d并读出下一个输入符号l

#lB′ l # 由B′→ε仅弹出栈顶符号B′ #l l # 匹配，弹出栈顶符号l并读出下一个输入符号# # # 匹配，分析成功

3.11 将下述文法改造为LL(1)文法： G[V]: V→N | N[E] E→V | V+E N→i 【解答】 LL(1)文法的基本条件是不含左递归和回溯(公共左因子)，而文法G[V]中含有回溯，所以先消除回溯，得到文法G[V′]： G [V′]：V→NV′ V′→ε | [E] E→VE′ E′→ε | +E N→i

一个LL(1)文法的充要条件是：对每一个终结符A的任何两个不同产生式A→α|β有下面的条件成立： (1) FIRST(α)∩FIRST(β)=Φ； (2) 假若βε，则有FIRST(α)∩FOLLOW(A)= Φ。 即求出G[V′]的FIRSTVT和LASTVT集如下： FIRST(N)=FIRST(V)=FIRST(E)={i} FIRST(V′)={[, ε} FIRST(E′)={+, ε} FOLLOW(V)={#}

由V′→…E]得FIRST(′)′) ?FOLLOW(E)，即FOLLOW(E)={ ]}； 由V→NV′得FIRST(V′)\\{ ε} ? FOLLOW(N)，即FOLLOW(N)={ [}； 由E→VE′得FIRST(E′)\\{ ε}?FOLLOW(V)，即FOLLOW(V)={#,+}； 由V→NV′得FOLLOW(V) ?FOLLOW(V′)，即FOLLOW(V′)={#,+}； 由V→NV′，且V′→ε得FOLLOW(V) ?FOLLOW(N)，即FOLLOW(N)={[,#,+]； 由E→VE′得FOLLOW(E) ?FOLLOW(E′)，即FOLLOW(E′)={ ]}； 则，对V′→ε |[E]有：FIRST(ε)∩FIRST(′[′]= Φ； 对E′→ε | +E有：FIRST(ε)∩FIRST(′+′)= Φ；

对V′→ε | [E]有： FIRST(′[′)∩FOLLOW(V′)={[]∩{#,+}=Φ； 对E′→ε | +E有： FIRST(′+′)∩FOLLOW(E′)={+}∩{}}=Φ。 故文法G[V′]为LL(1)文法。 3.12 对文法G[E]: E→E+T|T T→T*P|P P→i (1) 构造该文法的优先关系表(不考虑语句括号#)，并指出此文法是否为算符优先文法； (2) 构造文法G的优先函数。

【解答】 FIRSTVT集构造方法： ① 由P→a…或P→Qa…，则a∈FIRSTVT(P)。 ② 若a∈FIRSTVT(Q)，且P→Q…，则a∈FIRSTVT(P)，也即FIRSTVT(Q)?FIRSTVT(P)。 由①得：由E→E+…得FIRSTVT(E)={+}； 由T→T*…得FIRSTVT(T)={*}；

由P→i得FIRSTVT(P)={i}。 由②得：由T→P得FIRSTVT(P)?FIRSTVT(T)，即FIRSTVT(T)={*，i}； 由E→T得FIRSTVT(T)?FIRSTVT(E)，即FIRSTVT(T)={+，*，i}。 LASTVT集构造方法： ① 由P→…a或P→…aQ, 则a∈LASTVT(P)。 ② 若a∈LASTVT(Q)，且P→…Q，则a∈LASTVT(P)，也即LASTVT(Q)?LASTVT(P)。 由①得：E→…+T，得LASTVT(E)={+}； T→…*P，得LASTVT(T)={*}； P→i，得LASTVT(P)={i}。 由②得：由T→P得LASTVT(P)?LASTVT(T)，即LASTVT(T)={*，i}； 由E→T得LASTVT(T)?LASTVT(E)，即LASTVT(E)={+，*，i}。 优先关系表构造方法： ① 对P→…ab…或P→…aQb…，有ab； ② 对P→…aR…而b∈FIRSTVT(R)，有a?b； ③ 对P→…Rb…而a∈LASTVT(R)，有a?b。 解之无①。 由②得：E→…+T，即+?FIRSTVT(T)，有+?*，+?i； T→…*P，即*?FIRSTVT(P)，有*i。 由③得：E→E+…，即LASTVT(E)?+，有+?+，*?+，i?+； T→T*…，即LASTVT(T)?*，有*?*，i?*。 得到优先关系表见表3-3。 由于该文法的任何产生式的右部都不含两个相继并列的非终结符，故属算符文法，且该文法中的任何终结符对(见优先关系表)至多满足、?和?三种关系之一，因而是算符优先文法。

表3-3 习题3.12的优先关系表 + * i + ? ? ?

* ? ? ?

i ? ?

用关系图构造优先函数的方法是：对所有终结符a用有下脚标的fa、ga为结点名画出全部终结符所对应的结点。若存在优先关系a?b或ab，则画一条从fa到ga的有向弧；若a?b或ab，则画一条从g b到f a的有向弧。最后，对每个结点都赋一个数，此数等于从该结点出发所能到达的结点(包括出发结点)的个数，赋给fa的数作为f(a)，赋给gb的数作为g(b)。用关系图法构造本题的优先函数，如图3-7所示。 得到优先函数见表3-4。

4 2 f 4 f f 表3-4 习题3.12的优先函数表

＋*i

+ * i

f 2 4 4

g 1 3 5

13gg*5gi＋

图3-7 习题3.12关系图构造

该优先函数表经检查与优先关系表没有矛盾，故为所求优先函数。 也可由定义直接构造优先函数，其方法是：对每个终结符a，令f(a)=g(a)=1；如果a?b，而f(a)≤g(b)，则令f(a)=g(b)+1；如果a?b，而f(a)≥g(b)，则令g(b)=f(a)+1；如果ab，而f(a)≠g(b)，则令 min{f(a),g(b)}=max{f(a),g(b)}。重复上述过程，直到每个终结符的函数值不再变化为止。如果有一个函数值大于2n(n为终结符个数)，则不存在优先函数。 优先函数的计算过程如表3-5所示。 表3-5 优先函数的计算过程表

迭代次数 函数 + * i

f 1 1 1 0(初值) g 1 1 1

f 2 3 3 1 g 1 2 4

f 2 3 3 2 g 1 3 4

f 2 4 4

3 g 1 3 5 f 2 4 4 4 g 1 3 5 计算最终收敛，并且计算得出的优先函数与关系图构造得出的优先函数是一样的。 3.13 设有文法G[S]: S→a|b|(A) A→SdA|S (1) 构造算符优先关系表； (2) 给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语； (3) 给出输入串(adb)#的分析过程。

【解答】(1) 先求文法G[S]的FIRSTVT集和LASTVT集： 由S→a|b|(A)得FIRSTVT(S)={a,b,(}； 由A→Sd…得FIRSTVT(A)={d}，又由A→S…得FIRSTVT(S) ?FIRSTVT(A)，即FIRSTVT(A)={d,a,b, ( }； 由S→a|b|(A)得LASTVT(S) ={a,b,)}；

由A→…dA得LASTVT(A)={d}，又由A→S得LASTVT(S) ?LASTVT(A)，即LASTVT(A)={d,a,b,)}。

构造优先关系表方法如下： ① 对P→…ab…或P→…aQb…，有ab； ② 对P→…aR…而b∈FIRSTVT(R)，有a?b； ③ 对P→…Rb…而a∈FIRSTVT(R)，有a?b。 由此得到： ① 由S→(A)得()； ② 由S→(A…得(?FIRSTVT(A)，即(?d,(?a,(?b,(?(； 由A→…dA得d?FIRSTVT(A)，即d?d,d?a,d?b,d? (； ③由S→…A)得LASTVT(A)?)，即d?),a?),b?),)?)； 由A→Sd…得LASTVT(S)?d，即a?d,b?d,)?d； 此外，由#S#得##； 由#?FIRSTVT(S)得 #?a,# ?b, # ? (； 由LASTVT(S)?#得a?#, b?#, )?#。 最后得到算符优先关系表，见表3-6。 表3-6 习题3.13的算符优先关系表

a b ( ) d #

a ? ? ? b ? ? ? ( ? ? ? ? ) ? ? ?

d ? ? ? ? ?

# ? ? ?

由表3-6可以看出，任何两个终结符之间至多只满足、?、?三种优先关系之一，故G[S]为算符优先文法。 (2) 为求出句型(SdSdS)的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图3-8所示。 S S(A)

(A)

SdA SdA

SdASdA

SS图3-8 句型(SdSdS)的语法树 .(＜.d＜.d.#＜＞).＞#由图3-8得到： 短语：S，SdS，SdSdS，(SdSdS) 注意，句型中的素短语具有如下形式： aj-1?ajaj+1…ai?ai+1 而最左素短语就是该句型中所找到的最左边的那个素短语，即最左素短语必须具备三个条件： ① 至少包含一个终结符(是否包含非终结符则按短语的要求确定)； ② 除自身外不得包含其他素短语(最小性)； ③ 在句型中具有最左性。 图3-9 句型(SdSdS)的优先关系 简单短语(即直接短语)：S

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