【编译Chap4】求first集、follow集例题

方法求 FIRST 集的规则反复扫描所有产生式以A → X 1 X 2 ⋯ X n A\to X_1X_2\cdots X_nA→X1​X2​⋯Xn​为例依次处理X i X_iXi​i从1 to n把F I R S T ( X i ) − { ε } \mathrm{FIRST}(X_i)-\{\varepsilon\}FIRST(Xi​)−{ε}加入F I R S T ( A ) \mathrm{FIRST}(A)FIRST(A)如果ε ∉ F I R S T ( X i ) \varepsilon\notin \mathrm{FIRST}(X_i)ε∈/FIRST(Xi​)停止处理该产生式如果ε ∈ F I R S T ( X i ) \varepsilon\in\mathrm{FIRST}(X_i)ε∈FIRST(Xi​)继续处理下一个X i 1 X_{i1}Xi1​如果所有X i X_iXi​都能推出ε \varepsilonε则把ε \varepsilonε加入F I R S T ( A ) \mathrm{FIRST}(A)FIRST(A)。求 FOLLOW 集的规则开始符号把$输入结束符放入开始符号的 FOLLOW 集。反复扫描所有产生式以A → α B β A \to \alpha B \betaA→αBβ为例把F I R S T ( β ) − { ε } \mathrm{FIRST}(\beta) - \{\varepsilon\}FIRST(β)−{ε}加入F O L L O W ( B ) \mathrm{FOLLOW}(B)FOLLOW(B)。可空情况如果β \betaβ能推导出ε \varepsilonε即ε ∈ F I R S T ( β ) \varepsilon \in \mathrm{FIRST}(\beta)ε∈FIRST(β)或者B BB在产生式最右边则把F O L L O W ( A ) \mathrm{FOLLOW}(A)FOLLOW(A)加入F O L L O W ( B ) \mathrm{FOLLOW}(B)FOLLOW(B)。Appendix如果有左递归先消除左递归消除直接左递归的方法最简单的情况A → A α ∣ β A \to A\alpha \mid \betaA→Aα∣β改写为A → β A ′ A ′ → α A ′ ∣ ε \begin{aligned} A \to \beta A \\ A \to \alpha A \mid \varepsilon \end{aligned}AA′​→βA′→αA′∣ε​一般形式A → A α 1 ∣ A α 2 ∣ ⋯ ∣ A α m ∣ β 1 ∣ β 2 ∣ ⋯ ∣ β n A \to A\alpha_1 \mid A\alpha_2 \mid \cdots \mid A\alpha_m \mid \beta_1 \mid \beta_2 \mid \cdots \mid \beta_nA→Aα1​∣Aα2​∣⋯∣Aαm​∣β1​∣β2​∣⋯∣βn​改写为A → β 1 A ′ ∣ β 2 A ′ ∣ ⋯ ∣ β n A ′ A ′ → α 1 A ′ ∣ α 2 A ′ ∣ ⋯ ∣ α m A ′ ∣ ε \begin{aligned} A \to \beta_1 A \mid \beta_2 A \mid \cdots \mid \beta_n A \\ A \to \alpha_1 A \mid \alpha_2 A \mid \cdots \mid \alpha_m A \mid \varepsilon \end{aligned}AA′​→β1​A′∣β2​A′∣⋯∣βn​A′→α1​A′∣α2​A′∣⋯∣αm​A′∣ε​AppendixLL1表的构造遍历所有产生式以A → α为例对每个终结符 a ∈ FIRST(α)把 A → α 加至 M[A, a]中其中 α 为含有首字符 a 的候选式或唯一的候选式若ε ∈ FIRST(A)则对任何 b ∈ FOLLOW(A) 把 A → ε 加至 M[A, b]中六道例题第一题答案第二题答案firstAabcdgBbεCacdDdεEcgfollow不要忘记$求first非常容易错知乎有很好的方法论若X-a…则将终结符加入FIRST(X)中;注意非终结符的情况若X-e ,则将终结符e加入FIRST(X)中(e表示空集)若 X-BC…D,则将FirstB所有元素除了空集加入FirstX然后检测FirstB若FirstB中不存在空集, 即e,则停止若存在则向B的后面查看将FirstC中所有元素除了空集加入FirstX然后再检测FirstC中是否有e…直 到最后若D之前的所有非终结符的First集中都含有e,则检测到D时将FirstD也加入FirstX若FirstD中含有e,则将 e加入FirstX。总之看到epsilon要继续往后找直到没有epsilon或能确定X可置空为止。再一个简单例子下面的不能因为A的first集是epsilonS的第一个符号是A所以S的first集中就是epsilon这是不对的first集中有epsilon代表该符号可置空而在下面这个例题中S推不出空。所以此时应该向后找A的后面是aa的first是本身a到这里就可以停止了。第三题first:S: a,b,εAa,bBa,bfollow:第四题2010期末A卷第二题第五题lws 模拟试卷一 第二题第六题ref:https://blog.csdn.net/Baron_wu/article/details/84994254https://blog.csdn.net/RENSRM/article/details/111595754https://zhuanlan.zhihu.com/p/268555826