编译原理(陈火旺第三版)练习答案

Procedure T';

Begin if sym = ‘(‘ or sym = ‘a’ or sym = ‘b’ or sym = ‘ ’ Then begin T;

Else if sym = ‘*’ then error

End

Procedure F; Begin

if sym = ‘(‘ or sym = ‘a’ or sym = ‘b’ or sym = ‘ ’ Then begin P;F' end

Else error End

Procedure F' Begin

If sym = ‘*’

Then begin advance ; F' end End

Procedure P; Begin

If sym = ‘a’ or sym = ‘b’ or sym = ‘ ’

Then advance

Else if sym = ‘(‘ then Begin advance; E ;

If sym = ‘)’ then advance Else error End

Else error end P81-3 解答：（1）该文法不含左递归，计算First集合和Follow集合

Fisrt(S) = {a，b，c} First(A) = {a，ε} First（B）= {b,ε} Follow(S)={#} Follow（A）={b，c} Follow(B) = {c} 满足LL(1)文法的3个条件，所以是LL(1)文法； （2）该文法不含左递归，计算First集合和Follow集合

Fisrt(S) = {a，b} First(A) = {a，b，ε} First（B）= {b,ε} Follow(S)={#} Follow（A）={b} Follow(B) = {b}

考虑A→a|B|ε,Fisrt(A)中含有ε，而Fisrt(A)∩Follow（A）={b}，所以不是LL(1)文法； （3）该文法不含左递归，计算First集合和Follow集合

Fisrt(S) = {a，b，ε} First(A) = {a，ε} First（B）= {b,ε} Follow(S)={#} Follow（A）={a，b，#} Follow(B) = {a，b，#}

考虑A→a|ε,Fisrt(A)中含有ε，而Fisrt(A)∩Follow（A）={a}，所以不是LL(1)文法； (4)是LL（1）文法