编译原理 复习资料

2)用定义法或关系图法计算FIRST、FOLLOW集; 3)计算各规则的SELECT集; 4)根据同一个左部的规则其SELECT集是否相交来判断给定文法是否为LL(1)文法。

三、用关系图计算FIRST集

1、终结符a结点用符号本身标记,非终结符A结点用FIRST(A)标记;

2、对A→αXβ且α=*>ε,则从A到X连一条箭弧(注意:A→aB或A→a已包含在其中);

3、凡从FIRST(A)结点出发有路径可达到的所有终结符都为FIRST(A)的成员; 4、再根据A能否推导出ε的情况,若能推导出ε,则将ε加入FIRST(A)。

四、用关系图计算FOLLOW集

1、终结符a和#结点用符号本身标记,非终结符A结点用FIRST(A)或FOLLOW (A)标记;

2、从开始符S的FOLLOW(S)到#号连一条箭弧;

3、对规则 A→αBβX且β=*>ε,则从FOLLOW(B)到FIRST(X)连一条箭弧,当X∈VT时,则与X相连;

4、对A→αBβ且β=*>ε,则从FOLLOW(B)到FOLLOW(A)连一条箭弧; 5、对每一个FIRST(A)结点,若有规则A→αXβ,且α=*>ε,则从FIRST(A)到FIRST(X)连一条箭弧;

6、凡从FOLLOW(A)结点出发有路径可到达的所有终结符或#,都为FOLLOW(A)的成员;

五、例题

例1:判别下列G[S]是否为LL(1)文法,要求用关系图求FIRST集和FOLLOW集。 G[S]:S → AB|bC A →ε|b B →ε|aD C → b|AD D → aS|c 解:(1)画出非终结符推导ε的情况表,如下图1所示:

(2)用关系图计算各非终结符的FIRST集,如下图2、图3所示:

图1 图2

图3

(3)用关系图求出FOLLOW集,如下图4、图5所示:

图4 图5

4)根据前述三张表计算SELECTT集如下:

(5)判别是否为LL(1)文法

由于:SELECT(S →AB)∩SELECT(S → bC)={b}≠φ,SELECT(C → b)∩SELECT(C → AD)={b}≠φ。故 G[S]不是 LL((1)文法。 例2:LL((1)文法例子。

G[E]:E → T E' E'→ + T E'|ε T → F T' T'→ * F T'|ε F → ( E )|i 解:由于SELECT(E'→+TE')={+} SELECT(E'→ε)={#,)}

SELECT(T'→ * F T')={*} SELECT(T'→ε)={+,#,)} SELECT(F →( E )) ={(} SELECT(F →i)={i} SELECT( E'→+TE')∩SELECT (E'→ε) = {+}∩{#,)} =φ

SELECT (T'→ * F T') ∩SELECT (T'→ε) = {*}∩{+,#,)} =φ

>>展开全文<<
12@gma联系客服:779662525#qq.com(#替换为@)