【编译原理】典型题型：判断一个文法是否为LL(1)文法并构造预测分析表（First集和Follow集的求解方法&LL(1)文法的判断条件&预测分析表的构造&消除左递归的方法）

判断一个文法是否为LL(1)文法并构造预测分析表（First集和Follow集的求解方法&LL(1)文法的判断条件&预测分析表的构造）

LL(1)文法的判断条件

1 文法不含左递归 2 对于每个非终结符A的各个候选式的终结首符号集两两不相交 即A→α1|α2|…|αn 则First(αi)∩First(αj)=Ø(1≤i,j≤n且i≠j) 3 对于文法中每个非终结符A 若它的某个候选式的终结首符号集包含ε 则First(αi)∩Follow(A)=Ø(1≤i≤n)

用白话来讲 文法不含左递归就是形如A->Aa|c B->Bb|c这种产生式右部第一个字符是产生式左部的情况 处理方法就引申到 消除左递归的方法 -改写左递归为右递归 即A->Aa|a改写为 A->cA’ A‘->aA’|ε

B->cB’ B‘->aB’|ε 大家应该很容易能从中找到规律 改写时将包含左递归的部分：对A->Aa|c来说 Aa先放一边 然后将c提前 后面补上A’ 然后写A’时 将Aa后面的a提前 并把A改写为A‘ 即A’->aA 不要忘记这里补上ε 每一个都是这样哦

预测分析表的构造方法

行写终结符 列写非终结符 然后将找到对应的first集 将产生式填入对应非终结符&终结符的交叉位置 若First集中含有ε 则要把该非终结符的Follow集加入到预测分析表中

再说很多也不容易理解 我们看题来说明