1.  计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。

G(M)：

M → TB

T → Ba | e

B → Db | eT | e

D → d | e

 

2 将 G[V] 改造为 LL （ 1 ）文法。

G[V]: V → N|N[E]

E → V|V+E

N → i

 

3. 已知文法 G[A] 为：

A → aAB1|a

B → Bb|d

（ I ）试给出与 G[A] 等价的 LL(1）文法 G‘[A] 。

（ 2) 构造 G ' [A]的预测分析表。

（ 3 ）给出输入串 aadl分析过程。

 

 

4 考虑文法 G(S) ：

S → (T)|a+S|a

T → T,S|S

消除文法的左递归及提取公共左因子，然后，对每个非终结符，写出不带回溯的递归子程序。

 

【解答】

1.解答：

计算文法的FIRST和FOLLOW集合：(4分)

FIRST(M) = { a，b，e，d，e }     FIRST(T) = { a，b，e，d，e }

FIRST(B) = {b，e，d，e }        FIRST(D) = {d，e}

FOLLOW (M) = {#}            FOLLOW (T) = { a，b，e，d，#}

FOLLOW (B) = {a，# }           FOLLOW (D) = { b}

 

检查文法的所有产生式，我们可以得到：

1. 该文法不含左递归，

2. 该文法中每一个非终结符M，T，B，D的各个产生式的候选首符集两两不相交。

3. 该文法的非终结符T、B和D，它们都有e候选式，而且

FIRST(T)∩FOLLOW(T)={ a，b，e，d }≠f

所以该文法不是LL(1)文法。(2分)

 

2. 【解答】

LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而文法G[V]中含有回溯，所以先消除回溯得到文法G’[V]：

G'[V]：V→NV’

V’→ε|[E]

E→VE'

E’→ε|+E

N→i

一个LL(1)文法的充要条件是：对每一个终结符A的任何两个不同产生式A→α|β有下面的条件成立：

（1）FIRST(a)∩FIRST(β）＝φ；

（2）假若β=>ε，则有FIRST（a）∩FOLLOW(A）＝φ。

即求出G’［V］的FIRST集和FOLLOW集如下：

FIRST(N)=FIRST(V)=FIRST(E)={i}；

FIRST(V‘)=｛［，ε｝

FIRST(E’)=｛＋，ε｝；

FOLLOW(V)=｛＃｝；

由V’→ε|[E]得：FOLLOW(E’）＝｛]｝；

由V’→… E]得：FIRST(‘ ]’）c FOLLOW(E)，即FOLLOW(V)=｛]｝；

由V→NV’得：FIRST(V’）＼｛ε｝c FOLLOW(N)，即FOLLOW(N)=｛｝｝；

由E→VE’得：FIRST(E’）＼｛ε｝c FOLLOW(V),且FOLLOW(E)c FOLLOW(V),即FOLLOW(V)=｛＃，＋,]｝；

由V→NV’得：FOLLOW(V) c FOLLOW(V’），即FOLLOW(V’）＝｛＃，＋，]｝；

由V→NV’，且V’→e得：FOLLOW(V) cFOLLOW(N)，即FOLLOW(N)=｛［，＃，＋，]］；

由E→VE’得：FOLLOW(E) c FOLLOW(E’），即FOLLOW(E’）＝｛]｝；

则，对V’→ε|[E]有：FIRST(ε）∩FIRST(‘［’)=φ；

对E’→ε|＋E有：FIRST( ε）∩ FIRST(‘＋’）＝φ；

对V’→ε|[E］有：FIRST(‘［’）∩FOLLOW(V’)=｛［｝∩{＃，＋，]｝＝φ；

对E’→ε|+E有：FIRST(‘＋‘）∩ FOLLOW(E‘）=｛＋｝∩｛］｝＝φ。

故文法G‘[V]为LL(1）文法。

 

3. 【解答】

（1)文法G［A]存在左递归和回溯，故其不是LL(1)文法。要将G[A]改造为LL(1)文法，首先要消除文法的左递归，即将形如P→Pα|β的产生式改造为：

P→βP'

P→αP'|ε

来消除左递归。由此，将产生式B-Bb|d改造为：

B→dB’

B’→bB’|ε

其次，应通过提取公共左因子的方法来消除G[A]中的回溯，即将产生式A→aABl|a改造为：

A→aA’

A’→ABl|ε

最后得到改造后的文法为：

G’[A]：A→aA’

A’→ABl|ε

B→dB’

B‘→bB‘|ε

求得：FIRST(A)={a}；FIRST(A‘)={a, ε｝；

FIRST(B)={d}；FIRST(B‘)=｛b，ε｝；

对文法开始符号A，有FOLLOW(A)=｛＃｝；

由A‘→AB1得：FIRST(B)\｛ε｝c FOLLOW(A)，即FOLLOW(A)={#,d}；

由A‘→Abl得：FIRST(‘1’）c FOLLOW（B），即FOLLOW（B）=｛1｝；

由A→aA’得：FOLLOW(A) c FOLLOW(A'），即FOLLOW(A')=｛#,d｝；’

由B→dB‘得：FOLLOW(B) c FOLLOW(B‘)，即FOLLOW(B‘)＝{1}。

对A’→AB1来说，FIRST(A)∩FOLLOW(A')=(a)∩{#,d}=φ，所以文法G’[A]为所求等价的LL(1)文法。

（2）构造预测分析表的方法如下：

①对文法G’[A]的每个产生式A→α执行(2)、(3）步；

②对每个终结符a∈FIRST(A)，把A→a加入到M[A,a]中，其中α为含有首字符a的候选式或为唯一的候选式；

③若ε∈FIRST(A)，则对任何属于FOLLOW(A)的终结符b，将A→ε加入到M[A,b]中；

把所有无定义的M[A,a]标记上“出错”。

由此得到G’[A]的预测分析表，见表3.10。

（3)输入串auld的分析过程，见表3.11。

4【解答】

消除文法G[S]的左递归：

S→（T）|a+S|a

T→ST’

T‘→，ST‘|ε

提取公共左因子：

S→(T)|aS‘

S’→+S|ε

T→ST‘

T‘→，ST‘|ε

改造后的文法已经是LL(1)文法，不带回溯的递归子程序如下：

 

PROCEDURE S;

BEGIN

IF SYM='（’THEN

BEGIN

ADVANCE;

T;

IF SYM='）' THEN ADVANCE

ELSE ERROR

END

ELSE

IF SYM=‘a‘THEN

BEGIN

ADVANCE；

S'

END

ELSE ERROR

END；

 

PROCEDURE S’：

BEGIN

IF SYM=’＋’THEN

BEGIN

ADVANCE;

S

END

END；

 

PROCEDURE T;

BEGIN

S;T'

END;

 

PROCEDURE T'；

BEGIN

IF SYM=‘，‘THEN

BEGIN

ADVANCE;

S;T'

END

END；