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'→ε) = {*}∩{+,#,)} =φ