编译原理课后答案(第三版 蒋立源 康慕宁编) 下载本文

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