first集follow集select集

了解递归下降需要一些基础知识，至少了解一些编译原理相关的内容和概念。会计算first集和follow集，select集合，了解LL(1)文法以及消除左递归的知识。
这里先说明如何求解first集，follow集以及select集

first集：

一些符号和定义：
文法四元组G=(VT, VN, S, P)
VT （vocabulary terminated): 终结符集合
VN（vocabulary not terminated)：非终结符集合
S（start)：开始符号
P（production)：产生式
ε：表示空
#：表示输入结束符，类似EOF
→ ∗ \stackrel{*}{\rightarrow} →∗：表示经过0次至多此推导

一般大写字母表示非终结符，小写字母表示终结符。
文法式一套有限的规则，可以创建无限符合此规则的句子。

first集定义：
f i r s t ( α ) = { a ∣ α → ∗ a . . . , a ∈ V t } first(\alpha) = \{a|\alpha\stackrel{*}{\rightarrow}a...,a∈V_t\} first(α)={a∣α→∗a...,a∈Vt​}
注意区分上面的alpha和a，first(α)表示以α开始符号的集合，阿尔法所有可能推导的开头终结符或者式ε.

例子：

例子1（后面跟的不是非终结符）

...
A->aB|ε
A->c
...
First(A)={a,ε,c}

由上，A可以推出非终结符a开头的产生式，或者推出终结符ε，所以first(A)中包含a与ε，此外A可以推导出终结符c，所以First(A)={a,ε,c}。

例子2.1（后面跟的是非终结符）

...
A->Ba
B->b
...
First(A)={b}

由上，A得到的产生式中第一个非终结符B可以推导出的终结符为b，所以First(A)={b}

例子2.2（后面跟的是非终结符）

...
A->Bc
B->b|ε
...
First(A)={b,c}

接着上面的例子，如果B可以推导出ε，即推出空，那么相当于A可以直接表示为A->c，所以把c也加进来。

例子2.3（后面跟的是非终结符）

...
A->BC
B->b|ε
C->c|ε
...
First(A)={b,c,ε}

上面的例子，A可以推导出如下情况：
A->b, A->bc, A->c, A->ε
所以，First(A)={b,c,ε}

follow集：

follow集定义：
f o l l o w ( A ) = { a ∣ S → ∗ . . . A a . . . , a ∈ V t } follow(A) = \{a|S\stackrel{*}{\rightarrow}...Aa...,a∈V_t\} follow(A)={a∣S→∗...Aa...,a∈Vt​}
其中S表示文法的开始符号，非终结符A后面跟着的终结符或‘#’集合，且式紧挨着A的。

1. 如果文法的开始符号S，把#加入到follow(S)
2. 如果A->αBβ是一个产生式，把first(β)\{ε}加入到follow(B)中.（first(β)\{ε}表示把first(β)中去掉ε)
3. 如果A->αB是一个产生式，或A->αBβ是一个产生式且β->ε，则把follow(A)加入到follow(B)中。

开始符号S，先将#放入follow集合中;
注意，A->αBβ，α可以式终结符也可以为非终结符也可以为空，β可以为终结符或者非终结符，但是不能为空且，且B后面要有符号;

如：

...
A->aBC
A->aBd
A->BC
A->Bd
A->B // 这是错误的，B后面要有符号
...
First(A)={b,c,ε}

如果，A->αB为一个产生式，或者A->αBβ是一个产生式，且β->ε，则把follow(A)加入到follow(B)中；
如：

----------------------
// 对于A->αB
A->B  // α为空
A->cB // α推出c
A->CB // α推出非终结符C 
----------------------
// 对于 A->αBβ
A->dBC // 这是错误的，B后面要有符号
C->ε // 要求C必须推出ε，即A可以表示为A->dB

以上将follow(A)加入到follow(B)中

例子1：

终结符：if, b, ohter, else, then

G(S): S->I E T S P | O
I->if
E->b
O->other
L->else
T->then
P->LS | ε

由上，非终极符得到的first集如下：

first(S) = {if, other}
first(I) = {if}
first(E) = {b}
first(O) = {other}
first(L) = {else}
first(P) = {else, ε}

对应的follow集合：

// S是开始符，所以将#加入到集合中. 根据follow集的定义，找到产生式G(S): S->I E T S P | O 中的 S的
// 所在位置为 G(S): S->I E T S P | O  （这里S就是定义里面的A)
//                         ^
// S后面存在P，根据规则2，将first(P)\{ε}加入到follow(B)中
// 此外,有p->ε，看规则3表述为A->αBβ，且β->ε，要把follow(A)加入到follow(B)，但是在
// 这里变成将follow(S)加入到follow(S)当中，定义中的A和B是两个符号，所以此处不做操作。
follow(S) = {#, else}
// I后面是E，把E的first集加入到follow(I)
follow(I) = {b}
// E后面是T,将first(T)加入到follow(E)
follow(E) = {then}
// O后面没有符号，根据规则3，将follow(S)加入到follow(O)中
follow(O) = {else, #}
// L后面是S，将S的first集加入到follow(L)中
follow(L) = {if, other}
// 同O，P后面没有符号，将follow(S)加入到follow(P)
follow(P) = {else, #}

例子2：

G(E):E->TE'
E'->+TE' | ε
T->FT'
T'->*FT' | ε
F->(E) | i

对应的first集合：

first(E) = {i, (}
first(T) = {i, (}
first(E') = {+, ε}
first(T') = {*, ε}
first(F) = {(, i}

对应的follow 集合：

follow(E) = {#, )} // E作为开始符，且在F->(E) | i 产生式中，E后存在 ) 符号
follow(E') = {#, )} // 根据规则 A->αB，则E->TE'将follow(E)加入到follow(E')
follow(T) = {+, #, )} // 有E->TE'，根据A->αBβ规则，有α为空，E'->ε，此时将follow(E)加入follow(T)，根据E'->+TE' | ε将first(+)\{ε}加入follow(T)
follow(T') = {+, #, )} // T->FT'将follow(T)加入
follow(F) = {(*,+,#,)} // T->FT'，根据A->αBβ，α为空，T'->ε，将follow(T)加入;T'->*FT' | ε，根据A->αBβ，将first(T') / {ε} 加入

first集和follow集的意义：
为什么要有这两个集合？含义式什么？

代码的逻辑时自左向右写的，因此需要从左向右处理用户代码逻辑，即语法分析过程要先处理最左部分的源码。
但是产生式右侧的最左符号可能是终结符，也可能是非终结符，如果是非终结符，可能会出现无限的递归情况，如：
P->Pa，那么得到Paaaaa…
上面在推导的过程中会产生死循环，这种递归方式也叫做左递归，所以要消除左递归。
提取左公因式时，各个候选是有公共前缀，需要将公共前缀消除，所以需要找出候选式所有相同的首字符。

此外，有些非终结符可以推导为空，那么该非终结符后面的字符就成为了首部，因此需要follow集，其实也就是非终结符后面所有可能出现的终结符或结束符。（可以看看上面几个例子，是不是这样的情况）

select集

select集定义：
select(A->α)表示可以使用产生式A->α得到的起始符号的集合。
计算规则如下：
如果$\epsilon \notin first(\alpha )$ 那么$select(A->\alpha )=first(\alpha )$
如果$\epsilon \in first(\alpha )$ 那么 s e l e c t ( A − > α ) = f i r s t ( α ) \ { ε } ∪ f o l l o w ( A ) select(A->α) = first(α)\backslash\{ε\}∪follow(A) select(A−>α)=first(α)\{ε}∪follow(A)

例子：

G(E):E->TE'
E'->+TE' | ε
T->FT'
T'->*FT' | ε
F->(E) | i

上面已经计算过这个例子的first和follow集

那么每个产生式对应的select集为：

select(E->TE') = {i, (} // T无法推出ε，所以取first(T)
select(E'->+TE') = {+} // 直接取first(+)
select(E'->ε) = {#, )} // 注意候选式要分开计算，因为是ε所以取follow(E')
select(T) = {(,i} // first(F)
select(T'->*FT') = {*} // first(*)
select(T'->ε） = {+, #, )} // follow(T')
select(F->(E)) = {(} // first(()
select(F->i) = {i} // first(i)

比较简单

select集的意义：

给定输入的表达式字符串需要根据表达式的字符串中的字符用来寻找正确的产生式，即输入的表达式字串中的字符作为key，产生式作为value，那么这个select集就是构造的map

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！