Restore;

If next_token=’s’ then

If Y then return;

Restore;

X:=false; End;

Function Y:boolean;

Begin

Save;

Y=true;

If next_token=’;’ then

If next_token=’s’ then

If Y then return;

Restore; End;

(2)消去文法左递归，并记为：

P→begin S endS→A|CA→V:=EC→ if E then S

E→VE’E’ →+VE’|εV→I

Function P:boolean;

Begin

Save;

P:=true;

If next_token=”begin” then

If S then

If next_token=”end” then return;;

Restore;

P:=false; End;

Function A:boolean;

Beign

Save;

A:=true;

If V then

If next_token=”:=”

If E then return;

Restore;

A:=flase; End;

Function S:boolean;

Beign

Save;

S:=true;

If A then return;

Restore;

then If C then return;

Restore;

S:=false; End;

Function C:boolean;

Begin

Save;

C:=true;

If next_token=”if” then

If E then

If next_token=”then” then

If S then return;

Restore;

C:=false; End;

Function E:boolean;

Begin

Save;

E:=true;

If V then

If Ep then return;

Restore;

E:=false; End;

Function Ep:boolean;

Being

Save;

Ep:=true;

If next_token=’+’ then

If V then

If E’ then return;

Return; End;

4.解：

5.证：因为是左递归文法，所以必存在左递归的非终结符A，及形如A→α|β的产生式,且αT* Ad.

则first(Ad) ∩first(β)≠φ,从而

first(α) ∩first(β)≠φ，即文法不满足LL（1）文法条件。得证。

6.证：LL（1）文法的分析句子过程的每一步，永远只有唯一的分析动作可进行。现在，假设LL(1)文法G是二义性文法，则存在句子α，它有两个不同的语法树。即存在着句子α有两个不同的最左推导。从而可知，用LL（1）方法进行句子α的分析过程中的某步中，存在两种不同的产生式替换，且均能正确进行语法分析，即LL（1）分析动作存在不确定性。与LL（1）性质矛盾。所以，G不是LL(1)文法。 7.解：

(1)D产生式两个候选式fD和f的first集交集不为空，所以不是LL(1)的。

(2)此文法具有左递归性，据第5题结论，不是LL(1)的。

8.解：

(1)消除左递归性,得：

S→bZ11|aZ21A→bZ12|aZ22Z11→bZ11|εZ12→bZ12

Z21→bZ11|aZ21Z22→bZ12|aZ22|ε

消除无用产生式得：S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21

此文法已满足LL(1)文法的三个条件，

所以 G’[S]: S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21

(2) G’文法的各非终结符的FIRST 集和FOLLOW集：

产生式 FIRST 集 FOLLOW集

S→bZ11

→aZ21 {b} {a} {#}

Z11→bZ11 →ε {b} {ε} {#}

Z21→bZ11

→aZ21 {b} {a} {#}

LL(1)分析表为： a b