FIRST 集

• FIRST（X）：可以从符号或符号串X推导出的所有串首终结符构成的集合
• 如果 $X={>}^{\ast }\epsilon$ ，那么 $\epsilon$ 也在 FIRST（X） 中

计算文法符号 $X$ 的 FIRST 集合

对于一个产生式 $X\to Y_1{Y}_2.\dots Y_n$

（1）如果$X$是一个终结符，那么FIRST ( X ) = { X } (X)={X} (X)={X}

（2）如果$X$是一个非终结符，且$X\to Y_1{Y}_2.\dots Y_n$

• 如果 $Y_1$ 是一个终结符，那么FIRST ( X ) = { Y 1 } (X)={Y_1} (X)={Y1​}
• 如果 $Y_1$ 是非终结符，那么
  1. 向 FIRST$(X)$加入 FIRST$(Y_1)$中所有的非 $\epsilon$ 符号
  2. 如果 $\epsilon$ 在 FIRST$(Y_1)$中，再加入FIRST$(Y_2)$中的所有非 $\epsilon$ 符号；如果 $\epsilon$ 在 FIRST$(Y_1)$和 FIRST$(Y_2)$中，再加入 FIRST$(Y_3)$中的所有非 $\epsilon$ 符号，以此类推…
  3. 最后，如果对所有的 $X$， $\epsilon$ 都在FIRST$(X)$中，那么将 $\epsilon$ 加入到 FIRST$(X_1{X}_2.\dots X_n)$中

（3）如果$X\to \epsilon$，那么将 $\epsilon$ 加入FIRST$(X)$中

（4）若存在其它 $X$ 的候选式，则重复应用上述过程

示例：

1. 式子②④⑤的候选式都是以终结符开头（即 $Y_1$是终结符），故他们的FIRST集中分别包含了+、*、(
2. 式子②④的候选式还可以推导出 $\epsilon$ ，故他们的FIRST集中包含了 $\epsilon$
3. 式子③的候选式以非终结符开头（即 $Y_1$是非终结符），故式子③的FIRST集加入了 FIRST$(F)$中所有的非 ε 符号，同理可求式子①的FIRST集
4. 若将 $E\to T{E}^{\prime }$ 改写成 $E\to E^{\prime }T$ （下面简称为式子⑥）
   1. 式子⑥的FIRST集加入了 FIRST$(E^{\prime })$中所有的非 ε 符号
   2. ε 在 FIRST$(E^{\prime })$中，再加入了 FIRST$(T)$中所有的非 ε 符号
   3. FIRST$(T)$中没有 ε ，结束。
   4. 故此时 FIRST ( E ) = { + ， ( ， i d } (E)={+，(，id} (E)={+，(，id}

计算串 $X_1{X}_2.\dots X_n$ 的FIRST集合

（1）向 FIRST$(X_1{X}_2.\dots X_n)$加入 FIRST$(X_1)$中所有的非 $\epsilon$ 符号

（2）如果 $\epsilon$ 在 FIRST$(X_1)$中，再加入FIRST$(X_2)$中的所有非 $\epsilon$ 符号；如果 $\epsilon$ 在 FIRST$(X_1)$和 FIRST$(X_2)$中，再加入 FIRST$(X_3)$中的所有非 $\epsilon$ 符号，以此类推…

（3）最后，如果对所有的 $X$， $\epsilon$ 都在FIRST(X)中，那么将 $\epsilon$ 加入到 FIRST$(X_1{X}_2.\dots X_n)$中

参考地址：

https://www.icourse163.org/learn/HIT-1002123007?tid=1003246005#/learn/announce

最后

以上就是霸气网络为你收集整理的编译原理 —— FIRST集FIRST 集计算文法符号 X X X 的 FIRST 集合计算串 X 1 X 的全部内容，希望文章能够帮你解决编译原理 —— FIRST集FIRST 集计算文法符号 X X X 的 FIRST 集合计算串 X 1 X 所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。