编译原理第五章课后题

第五章

1.1考虑下⾯表格结构⽂法G2S->a|^|(T)T->T,S|S

指出(((a,a), ^,(a)),a)的规范规约及每⼀步规约的句柄。根据这个规范规约，给出“移进-规约”的过程，并给出它的语法树⾃下⽽上构造的过程。

答:：规范规约该步规约时的句柄(((a,a), ^,(a)),a) a=> (((S,a), ^,(a)) ,a) S=> (((T,a), ^,(a)) ,a) a=> (((T,S), ^,(a)) ,a) T,S=> (((T), ^,(a)) ,a) （T）=> ((S, ^,(a)) ,a) S=> ((T, ^,(a)) ,a) ^=> ((T, S,(a)) ,a) T, S=> ((T,(a)) ,a) a=> ((T,(S)) ,a) S=> ((T,(T)) ,a) (T)=> ((T,S) ,a) T, S=> ((T) ,a) (T)=> (S,a) S=> (T, a) a=> (T, S) T, S=> (T) (T)=> S

“移进-规约”的过程：符号栈输⼊串动作# (((a,a), ^,(a)),a) # 预备#( ((a,a), ^,(a)),a) # 进#(( (a,a), ^,(a)),a) # 进#((( a,a), ^,(a)),a) # 进#(((a ,a), ^,(a)),a) # 进

#(((S ,a), ^,(a)),a) # 归，⽤S->a#(((T ,a), ^,(a)),a) # 归，⽤T->S

#(((T, a), ^,(a)),a) # 进#(((T,a ), ^,(a)),a) # 进

#(((T,S ), ^,(a)),a) # 归，⽤S->a#(((T ), ^,(a)),a) # 归，T->T,S#(((T) , ^,(a)),a) # 进

#((S , ^,(a)),a) # 归，⽤S->(T)#((T , ^,(a)),a) # 归，⽤T -> S#(( T, ^,(a)),a) # 进#(( T, ^ ,(a)),a) # 进

#(( T, S ,(a)),a) # 归，⽤S->^ #(( T ,(a)),a) # 归，⽤T->T,S #(( T, (a)),a) # 进#(( T, ( a)),a) # 进#(( T, (a )),a) # 进

#(( T, (S )),a) # 归，⽤S->a #(( T, (T )),a) # 归，⽤T -> S #(( T, (T) ),a) # 进#(( T, S ),a) # 归，⽤S->(T) #(( T ),a) # 归，⽤T->T,S #(( T) ,a) # 进#(S ,a) # 归，⽤S->(T) #(T ,a) # 归，⽤T ->S #(T, a) # 进#(T, a ) # 进

#(T, S ) # 归，⽤S->a #(T )# 归，⽤T->T,S #(T) # 进#S # 归，⽤S->(T) 接受。语法树（略）

3 （1）计算练习2的⽂法G2S->a|^|(T)T->T,S|S

的FIRSTVT和LASTVT。

（2）计算G2的优先关系。G2是⼀个算符优先⽂法吗？（3）给出输⼊串(a,(a,a))的算符优先分析过程。答：（1）

因为该⽂法是OP，同时任意两个终结符的优先关系唯⼀，所以该⽂法为OPG。（3）句⼦(a, (a, a))分析过程如下：

4.对下⾯⽂法：S->AS | bA->SA | a

(1) 列出该⽂法所有的LR(0)项⽬。

(2) 构造这个⽂法的LR(0)项⽬集规范族及识别活前缀的DFA答：⽂法拓⼴：S’->SS->AS | bA->SA | aLR（0）项⽬：S’->．S S’->S．

S->．AS S->A．S S->AS．S->．b S-> b．

A->．SA A->S．A A->SA．A->．a A->a．

LR(0)项⽬集规范族及识别活前缀的DFA如下图所⽰：FOLLOW(S)={#,a,b} FOLLOW(A)={a,b}

7.证明⽂法是SLR(1)的但不是LR(0)的：S->AA->Ab|bBaB->aAc|a|aAb

答：(1) 证明不是LR(0):

因为项⽬集规范族的I3 中，有移进和归约的冲突。所以不是LR(0)的

(2)证明是SLR(1)的提⽰：

上图继续画完，找出所有冲突的情况，根据SLR(1)解决办法可以解决，(过程略)所以为SLR(1)的或构造出SLR分析表，⽆多重定义⼊⼝，所以是SLR的．８．证明⽂法：A→BaBb|DbDaB→εD→ε

是LR(1)但不是SLR(1)。

（说明：书中的S为这⾥的A；书中的A为这⾥的B；书中的B为这⾥的D；）答：拓⼴⽂法为G′，增加产⽣式S′→A若产⽣式排序为：0 S'→A1 A →BaBb2 A →DbDa

3 B →ε4 D →ε由产⽣式知：First (S' ) = {a,b}First (A ) = {a,b}First (B ) = {ε}First (D ) = {ε}Follow(S' ) = {#}Follow(A ) = {#}Follow(B ) = {a,b}Follow(D ) = {a,b}

G′的LR(1)项⽬集族及识别活前缀的DFA如下图所⽰：

(修正:上图⾥左上⾓的I1应为:S’->A．，＃图⾥把向前搜索符＃漏掉了，因为是插⼊的图⽚不好修改，这⾥更正⼀下)在I0中：

B →．,a和D →．，b为归约项⽬，但它们的搜索符不同，若当前输⼊符为a时⽤产⽣式B →ε归约，为b时⽤产⽣式D →ε归约，所以该⽂法是LR(1)⽂法。

若不看搜索符，在I0中项⽬B →．和D→．为归约-归约冲突，⽽

Follow(B ) ∩Follow(D ) = {a,b} ∩{a,b}≠，冲突不能⽤Follow集解决，所以该⽂法不是SLR(1)

⽂法。

构造的LR(1)分析表如下：

因为表中不含多重定义⼊⼝，所以该⽂法是LR(1)的.