编译原理复习题 - 给学生(2014)

.. .. ..

13．文法

S ? A a | b A c | d c | b d a A ? d

构造识别活前缀的DFA。请根据这个DFA来判断该文法是不是SLR(1)文法并说明理由。

S’ ? .S S ? .A a S ? .b A c S ? .d c S ? .b d a A ? .d I0 d S ? d .c A ? d . I4 S A S’ ? S . I1 S ? A .a I2 S ? b .A c S ? b .d a A ? .d I3 S ? d c . I8 a S ? A a . I5 S ? b A .c I6 S ? b d .a A ? d . I7 c S ? b A c . I9 S ? b d a . I10 b A d a c 【解】

Follow(S)={#} Follow(A)={a,c}

I4存在冲突且Follow(A)∩{c}={ c} I7存在冲突且Follow(A)∩{a}={ a} 所以不是SLR(1)文法

14．设有文法G[S]:

S→S*S|S+S|(S)|i

该文法是否为二义文法,并说明理由？

参考材料

.. .. ..

【解】该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图所示。

S S i (1) S S S i + S i S i S * + S i (2) * S i

15.构造下面文法的LL（1）分析表。 G[D]: D ? TL

T ? int | real L ? id R R ? , id R | ?

【解】FIRST(T)={ int real } FOLLOW(T)={ id } FIRST(L)={ id } FOLLOW(L)={ #} FIRST(R)={ , ?} FOLLOW(R)={ #}

FIRST(D)={ int real } FOLLOW(D)={#} 因为FIRST(int)∩FIRST(real)=Φ FIRST(, id R)∩FOLLOW(R)=Φ

所以是LL（1）文法，LL（1）分析表如下：

D T L R

16．给定文法S→aS|bS|a，下面是拓广文法和识别该文法所产生的活前缀的DFA。判断该文法是否是

参考材料

int D ? TL T ? int real D ? TL T ? real id L ? id R , R ? , id R # R ? ? .. .. ..

SLR(1)文法：如果是构造其SLR(1)分析表，如果不是请说明理由。

(1)将文法G(S)拓广为G(S’)：

(0)S’→S (1)S→aS (2)S→bS (3)S→a

(2)识别该文法所产生的活前缀的DFA如图1所示。

图1

【解】注意到状态I1存在“移进-归纳”冲突，计算S的FOLLOW集合： FOLLOW(S)={#} {a}∩{b}∩FOLLOW(R)=Φ

可以采用SLR冲突消解法，得到如下的SLR分析表。

从分析表可以看出，表中没有冲突项，所以该文法是SLR(1)文法。

参考材料

.. .. ..

表1 SLR分析表

状态 0 1 2 3 4 5

17．证明下面文法S→AaAb|BbBa A→ε B→ε，是LL（1）文法，但不是SLR（1）文法。 证明：

（1）first（AaAb）={a} first（BbBb）={b} ，有first（AaAb）∩first（BbBb）=Φ 所以根据LL（1）文法的定义，该文法是LL（1）文法。

（2）为了构造识别活前缀的DFA，初态集包含如下四个项目：S→.AaAb S→.BbBa A→. B→. 但该项目中有两个可归约项目：A→. B→.，产生归约-归约冲突，而follow（A）={a，b}，follow（B）={a，b}，有follow（A）∩follow（B）≠Φ，所以使用向前看一个终结符的方法不能解决此冲突，所以该文法不是SLR（1）文法。 18．已知文法G(S)：

S→S*aP| aP| *aP P→+aP| +a

(1) 将文法G(S)改写为LL(1)文法G’(S)；

参考材料

ACTION a S1 S1 S1 b S2 S2 S2 # r3 acc r1 r2 GOTO S 3 4 5