编译原理经典习题详解

编译原理经典习题详解(1)计算文法G[S]各非终结符的First集和Follow集。(2)判断该文法是否为LL(1)文法。(3)若为LL(1)文法，构造其预测分析表。分析与解答：(1)计算First集和Follow集：First集定义：First(X)是由所有从X推导出的句型的第一个终结符组成的集合，若X能推导出ε，则ε也在First(X)中。Follow集定义：Follow(A)是由所有在句型中紧跟在A之后的终结符组成的集合，若A是句型的最右符号，则#（句子结束符）也在Follow(A)中。首先，我们列出所有非终结符：S,A,B。终结符：a,b。计算First集：*First(S)：S有两个产生式：S→aAb和S→bBA。第一个产生式以终结符a开头，所以a∈First(S)。第二个产生式以终结符b开头，所以b∈First(S)。因此，First(S)={a,b}。*First(A)：A有三个产生式：A→ab,A→a,A→ε。A→ab：以a开头，a∈First(A)。A→a：以a开头，a∈First(A)。A→ε：ε∈First(A)。因此，First(A)={a,ε}。*First(B)：B有两个产生式：B→a,B→ε。B→a：以a开头，a∈First(B)。B→ε：ε∈First(B)。因此，First(B)={a,ε}。计算Follow集：首先，令Follow(S)={#}(因为S是开始符号)。*Follow(A)：寻找所有包含A的产生式右部，并查看A之后的符号。1.S→aAb：A后面是终结符b。所以b∈Follow(A)。2.A→ab：A是产生式左部，看右部末尾，无后续符号，故需将Follow(A)的计算依赖于其左部非终结符的Follow集？不，这里A是产生式左部，对于A的产生式右部的末尾符号b，它会影响使用该A产生式的上下文。但计算Follow(A)本身，是看A在其他产生式中作为右部符号时，其后的符号。3.A→a：同上。4.A→ε：同上。另，A在S→aAb中是作为右部中间符号出现的，其后是b，已考虑。A是否在其他产生式中出现？没有了。所以，Follow(A)={b}。*Follow(B)：寻找所有包含B的产生式右部，并查看B之后的符号。B出现在S→bBA中，B后面是A。所以，First(A)中除ε外的元素都属于Follow(B)。First(A)={a,ε}，所以a∈Follow(B)。由于First(A)包含ε，所以还需要将Follow(S)加入Follow(B)。因为当A推导出ε时，B后面紧跟着的就是S的Follow符号。Follow(S)={#}，所以#∈Follow(B)。因此，Follow(B)={a,#}。*再次检查Follow(A)和Follow(B)是否有遗漏：对于A，是否还有其他产生式？没有。所以Follow(A)={b}正确。对于B，是否还有其他产生式？没有。所以Follow(B)={a,#}正确。总结：*First(S)={a,b}*First(A)={a,ε}*First(B)={a,ε}*Follow(S)={#}*Follow(A)={b}*Follow(B)={a,#}(2)判断该文法是否为LL(1)文法：LL(1)文法的定义：对于文法中的任意两个产生式A→α和A→β（α≠β），必须满足：1.First(α)∩First(β)=∅。2.若β能推导出ε（即ε∈First(β)），则First(α)∩Follow(A)=∅；对称地，若α能推导出ε，则First(β)∩Follow(A)=∅。我们需要对文法中每个非终结符的所有产生式对进行检查。*检查非终结符S：S有两个产生式：S→aAb和S→bBA。First(aAb)={a}，First(bBA)={b}。{a}∩{b}=∅。满足条件1。无需检查条件2（因为两个产生式的右部都不能推导出ε，其First集中不含ε）。*检查非终结符A：A有三个产生式：A→ab,A→a,A→ε。需要两两检查：a)A→ab和A→a：First(ab)={a}，First(a)={a}。{a}∩{a}={a}≠∅。仅此一对产生式就不满足LL(1)文法的条件