一道例题带你理解LL(1)分析法

LL（1）分析法步骤

1. 对文法进行改造
2. 求FIRST集
3. 求FOLLOW集
4. 求SELECT集
5. 分析表分析

（❤️一道完整的例题及其解析与步骤）

🌞🌞🌞FIRST集：

（⭐能听懂版本的官方话）：

1. 对终结符a，有FIRST(a)＝{a}
2. 对非终结符A，FIRST(A)包含所有可以从A推导出的符号串的第一个符号（不包括“空串ε”，除非A能推导出ε）

（🌙人话）：

比如第一句E→ TE’，求FIRST(E)，E → TE’，箭头后面第一个字符是T，那么FIRST(E)=FIRST(T)。由T→FT’，得，箭头后面第一个字符是F，那么FIRST(E)=FIRST(T)＝FIRST(F)。因为①F→(E)，第一个字符是“（”，那么括号就是E→ TE’ 的一个FIRST集里面的元素。②由于F还有一个式子F→i，箭头后面第一个字符是“i”，那么i也是E→ TE’ 的一个FIRST集里面的元素。也就是说FIRST(E)=FIRST(T)＝FIRST(F)＝{（,i}。

🌞🌞🌞FOLLOW集：【注意：FOLLOW集里面没有ε】

（⭐能听懂版本的官方话）：

1. 如果S为识别符号，则把“#”添加进入FOLLOW(S)中。
2. 若A→αBβ (β里面没有ε），那么把FIRST(β）加入到FOLLOW（B)中。
3. 若A→αB或者A→αBβ（β里面有ε），那么把FOLLOW（A)加入FOLLOW(B)中。

（🌙人话）：情况比较多，举3个例子

1. E→TE’，找哪个式子中有“谁→”能退出“E”的，找到了F→（E），那么就取E的右边第一个字符“）”。因为“E”又是开始符，需要再加一个“#”，所以FOLLOW(E)={）,#}。
2. E’→TE，找出 谁推出了“E’”，找到了E→TE’，那么看E’后面是啥，一看没东西，那就FOLLOW(E’)=FOLLOW(E)。
3. T→FT’，找谁推出了T，找到了E’→TE’，看看T的后面是啥，一看是E’,那么我们应该把FIRST(E’)添加到FOLLOW（T）中，但是，咱们可以看到FIRST(E’)里面是有“ε”的，所以我们也应该把FOLLOW(E’)加入FOLLOW(T)中，所以咱可以写成FOLLOW(T)=FOLLOW(E’)+FIRST(E’)。

🌞🌞🌞SELECT集：【注意：SELECT集里面没有ε】

（⭐能听懂版本的官方话）：

看FIRST集，如果没“ε”，那么SELECT=FIRST；如果有“ε”，那么SELECT=FOLLOW

（🌙人话）：

1. 比如E→TE’，其中FIRST(E)={（, i }这里面没有“ε”，那么SELECT(E)=FIRST(E)={（, i }。
2. 比如E’的第二个式子，E’→ε，这个里面是有“ε”的，那么SELECT(E’)=FOLLOW(E’)={）,#}。

（❤️列表格的时候建议：SELECT集和FIRST集一样，如果有两个式子的话，要分开写）

步骤⑤分析表分析:

表格是根据SELECT集画的，如E’→TE’填在了 “E’”行的“＋”列；E’→ε填在了“E’”行“）”列和“#”列。
此时可以画一个分析栈，旁边画一个“余留输入串”（❤️如下图）

此时的栈中元素有“#E”，栈顶元素是E，余留串首位是i，根据预测分析表表格，调用（栈顶元素）“E”行的（余留串首位）“i”列对应的产生式E→TE’，将栈中“E”弹出，将箭头后的“TE’”压入栈中（从右往左进入，“E’”先进，栈顶元素是T），然后再根据栈顶元素与余留输入串的串首，找相应的产生式，当栈顶元素＝余留串首位时，抵消。重复操作直到抵消完。

练习