编译原理 第六章 习题解答

第六章 习题答案

4．文法G： S?S;G|G

G?G(T)|H H?a|(S) T?T+S|S

（1）该文法是算符文法，且不包含ε产生式。 计算每个非终结符的FIRSTVT集合：

FIRSTVT(S) = FIRSTVT(S)∪{;}∪FIRSTVT(G) FIRSTVT(G) = FIRSTVT(G)∪{(}∪FIRSTVT(H) FIRSTVT(H) = {a, (} FIRSTVT(T) = FIRSTVT(T)∪{+}∪FIRSTVT(S) 计算每个非终结符的LASTVT集合：

LASTVT(S) = {;}∪LASTVT(G) = {;, a, )} LASTVT(G) = {)}∪LASTVT(H) = {a, )} LASTVT(H) = {a, )} = {a, )} LASTVT(T) = {+}∪LASTVT(S) = {+, ;, a, )} ①关系

由#S#可知： ## 由G?G(T)|H可知： () ②关系 S# S; G( T) S) T+ ③

关系 #S ;G (T (S +S LASTVT(S)# → {;, a, )}# LASTVT(S); → {;, a, )}; LASTVT(G)( → {a, )}( LASTVT(T)) → {+, ;, a, )}) LASTVT(S)) → {;, a, )}) LASTVT(T)+ → {+, ;, a, )}+ #;((FISRTVT(S) → #FISRTVT(G) → ;FISRTVT(T) → (FISRTVT(S) → ({;, a, (} {a, (} {+, ;, a, (} {;, a, (} {;, a, (} a ( ) # = {;, a, (} = {a, (} = {a, (} = {+, ;, a, (}

+FISRTVT(S) → +构造算符优先关系表如下： + ; a ( ) # + ; 由该文法的算符优先关系表可知，该文法是算符优先文法。 （2）句型a(T+S);H;(S)的语法树如右图所示：

S短语：a(T+S);H;(S)，a(T+S);H，a(T+S)，

a，T+S ，H，(S) 句柄：a S ; G素短语：a，T+S，(S)

S ; G最左素短语：a

H G ( T )H( S ) HT + S

a（3）

对a;(a+a)进行算符优先分析步骤如下：

步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 步骤 1 2 3 4 5 6 7 8 9 10 符号栈 # #a #N #N; #N; ( #N; (a #N; (N #N; (N+ #N; (N+a #N; (N+N #N; (N #N; (N) #N; N #N 符号栈 # #( #(a #(N #(N+ #(N+a #(N+N #(N #(N) #N 当前符号 a ; ; ( a + + a ) ) ) # # # 当前符号 ( a + + a ) ) ) # # 剩余符号串 ;(a+a)# (a+a)# (a+a)# a+a)# +a)# a)# a)# )# # # # 剩余符号串 a +a)# a)# a)# )# # # # 移进或归约 移进 归约 移进 移进 移进 归约 移进 移进 归约 归约 移进 归约 归约 分析成功 移进或归约 移进 移进 归约 移进 移进 归约 归约 移进 归约 分析成功 对(a+a)进行算符优先分析步骤如下： 采用算符优先分析方法进行分析，可知：a;(a+a)和(a+a)均应为该文法的句子。 （4）

句子a;(a+a)的最右推导为：

S=>S;G=>S;H=> S;(S)=> …（无法推出句子a;(a+a)） 句子(a+a)的最右推导为：

S=>G=>H=> (S)=>…（无法推出句子(a+a)）

由以上推导过程可知：a;(a+a)和(a+a)均不是该文法的句子。

（5）由（3）和（4）可看出，算符优先文法忽略了对单个非终结符的归约过程，不是规范归约，因此无法避免把错误的句子得到正确的归约。

（6）算符优先分析过程不是最右推导的逆过程，而规范归约是最右推导的逆过程。

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