Frist 与 Follow 集合

admin

2020 年 04 月 28 日

256次浏览

暂无评论

1269字数

编译原理

## FIRST

- $FIRST(\alpha)$被定义为可从$\alpha$推导得到的首符号集合，其中$\alpha$是任意的文法符号串。

$$
  FIRST(\alpha)=\{a\mid\alpha\Rightarrow^*a...,a\in V_T\}

&emsp;特别是，$\alpha\Rightarrow^*\epsilon$时，规定$\epsilon\in FIRST(\alpha)$
- 对$A\rightarrow\alpha_i\mid\alpha_j$，希望有

$$
  FIRST(\alpha_i)\cap FIRST(\alpha_j)=\varnothing

&emsp;若$FIRST(\alpha_i)$或$FIRST(\alpha_j)$含$\epsilon$，还需增加条件
- 计算$X$的$FIRST(X)$时，不断运用以下规则，直到没有新的终结符或$\epsilon$可以被加入到$FIRST(X)$

- 如果$X$是终结符，$FIRST(X)=X$
  - 如果$X\rightarrow Y_1Y_2...Y_k$，且$a$在$FIRST(Y_i)$集合中，并且$Y_1\Rightarrow^*\epsilon$，$Y_2\Rightarrow^*\epsilon$,...,$Y_{i-1}\Rightarrow^*\epsilon$，则将$a$插入到$FIRST(X)$中。
  - 如果$X\Rightarrow\epsilon$是一个产生式，则将$\epsilon$插入到$FIRST(X)$中。

## FOLLOW

- $FOLLOW(A)$被定义为可能在某些句型中紧跟在$A$右边的中介符号的集合。

$$
  FOLLOW(A)=\{a\mid S\Rightarrow^*...Aa...,a\in V_T\}

&emsp;如果$A$是某个句型的最右符号,那么**$**属于$FOLLOW(A)$
- 计算非终结符号$A$的$FOLLOW(A)$时，不断运用以下规则，制导没有新的终结符号可以被加入到$FOLLOW(A)$

- 将**$**放到$FOLLOW(S)$中，$S$是开始符号，$\$$是输入右端的结束标记。
  - 如果存在$A\rightarrow\alpha B \beta$，那么$FIRST(\beta)$中所有非$\epsilon$的所有符号都在$FOLLOW(B)$中。
  - 如果存在$\underline{A\rightarrow\alpha B}$或$\underline{A\rightarrow\alpha B\beta\quad\&\quad\epsilon\in FIRST(\beta)}$ ，则$FOLLOW(A)$中所有的符号都在$FOLLOW(B)$中。

最后修改：2021 年 09 月 09 日 01 : 44 PM

如果觉得我的文章对你有用，请随意赞赏