First集和Follow集（转）
作者&投稿：和强 （若有异议请与网页底部的电邮联系）
一、First集合
定义：
First集合是对产生式右部的字符串而言的，求取的是非终结符VT（或终结符、空字符、文法符号串）的开始符号集合，集合中包含的是由左部非终结符VT推导得到的终结符VN或空字符ε。以α表示一个文法的字符串，FIRST( α ）表示由α推导出的串的首个终结符或空字符组成的集合。
规则
求文法符号X的FIRST( X ) ，直到没有终结符或空字符可以加入。
① 如果X属于终结符VT，则FIRST(X) = { X } 。
② 如果X属于非终结符VN，且有产生式形如X → a…，则FIRST( X ) = { a }。
③ 如果X属于非终结符VN，且有产生式形如X → ABCdEF…（A、B、C均属于非终结符且包含 ε，d为终结符），需要把d、FIRST( A )、FIRST( B )、FIRST( C )加入到FIRST( X)中。
④ 如果X经过一步或多步推导出空字符ε，将ε加入FIRST( X )。
一组文法符号串
由规则可知单个文法字符的FIRST集，那么一组文法字符串的FIRST集也可以求取了。假设文法符号串S由X1X2X3……Xn组成，则将每个文法符号Xi的FIRST集加入到FIRST( S )中，包括空字符ε。
举例1
设有文法G[A]：
A→BCc | gDB
B→bCDE | ε
C→DaB | ca
D→dD | ε
E→gAf | c
解：
FIRST( A ) = FIRST( BCc ) ∪ FIRST( gDB ）
=FIRST( B )∪FIRST( C )∪{ c }∪{ g }
由规则③规则②可知
FIRST( A ) =FIRST( B )∪FIRST( D )∪{ a }∪{ c }∪{ c }∪{ g }
={ b，ε }∪{ d，ε }∪{ a }∪{ c }∪{ g }
={ a，b，c，d，g ，ε }
FIRST( B ) = { b，ε }
FIRST( C ) = FIRST( D )∪{ a }∪{ c }= { a，c，d，ε }
FIRST( D ) = { d，ε }
FIRST( E ) = { g，c }
对于A来说：有两种选择 BCc 与 gDB，BCc用规则③，gDB用规则②。
对于B来说：有两种选择 bCDE 与 ε，均用规则②。
对于C来说：有两种选择 DaB 与 ca，由于D存在空字符，所以 DaB用规则③，ca用规则②。
对于D来说：有两种选择dD 与 ε ，分别用规则②与规则④。
对于E来说：有两种选择gAf 与 c ，均用规则②。
举例2
设有文法G[S]:
S→aBS | bAS | ε
A→bAA | a
B→aBB | b
解：
FIRST( S ) = FIRST( aBS )∪FIRST( bAS )∪{ ε }={ a，b，ε }
FIRST( A ) = { a，b }
FIRST( B ) = { a，b }
对于S来说：有三种选择 aBS与bAS、ε，分别用②与规则④。
对于A来说：有两种选择bAA与 a，均用规则②。
对于B来说：有两种选择aBB与 b，均用规则②。
二、Follow集合
定义：
Follow集合是对某个非终结符而言的，求取的是非终结符VT的后继符号集合，集合中包含的是由非终结符VT后面紧跟的终结符VN和结束符$，不能出现空字符ε 。以X表示一个非终结符，FOLLOW( X ）表示当X通过规约出现时，接下来的输入可能是哪些终结符。
规则
求非终结符X的FOLLOW( X ) ，直到没有终结符可以加入。
① 如果X是开始符号，则将$加入到FOLLOW(X)中 。
② 如果存在一个产生式S->αXβ，那么将集合FIRST(β)中除ε外的所有元素加入到FOLLOW(X)当中。
③如果存在一个产生式 S->αX , 或者S->αXβ且FIRST(β)中包含ε , 那么将集合FOLLOW(S)中的所有元素加入到集合FOLLOW(X)中。
举例1
设有文法G[A]：
A→BCc | gDB
B→bCDE | ε
C→DaB | ca
D→dD | ε
E→gAf | c
解：
FOLLOW( A ) ={ f ， }∪{ c，d，g， }
FOLLOW( C ) = { c }∪FIRST( D )∪FIRST( E )
={ c }∪{ d }∪{ g，c }
={ c，d，g }
FOLLOW( D ) = FIRST( B )∪FOLLOW(A )∪FIRST( E )∪{ a }
={ b } ∪{ g，c }∪{ f ， }
FOLLOW( E ) = FOLLOW( B )
={ a，c，d，f，g， ；E→gAf，规则②将f加入FOLLOW( A )。
对于B的出现来说：有 A→BCc，规则②将FIRST( C )除ε以外加入进去；有A→gDB，规则③将FOLLOW( A )加入进去；有C→DaB，规则③将FOLLOW( C )加入进去。
对于C的出现来说：有 A→BCc，规则②将c加入进去；有B→bCDE，规则③将FOLLOW( D )加入进去，由于D存在空字符ε，所以需要把FIRST( E )除ε以外也加入进去。
对于D的出现来说：有A→gDB，规则②将FIRST( B )除ε以外加入进去，由于B存在空字符ε，所以规则③将FOLLOW( A )加入进去；有B→bCDE，规则②将FIRST( E )除ε以外加入进去；有C→DaB，规则②将a加入进去。
对于E的出现来说：有B→bCDE，规则③将FOLLOW( B )加入进去。
举例2
设有文法G[S]:
S→aBS | bAS | ε
A→bAA | a
B→aBB | b
解：
FOLLOW( S ) = { }∪{ a，b }
={ a，b， }∪{ a，b }
={ a，b， 加入进去。
对于A的出现来说：有S→bAS，规则②将FIRST( S )除ε以外加入进去,由于S存在空字符ε，规则③将FOLLOW( S )加入进去；有A→bAA，规则②将FIRST( A )除ε以外加入进去。
对于B的出现来说：有S→aBS，规则②将FIRST( S )除ε以外加入进去,由于S存在空字符ε，规则③将FOLLOW( S )加入进去；有B→aBB，规则②将FIRST( B )除ε以外加入进去。
第三部分·如何构造LL(1)分析表
首先画出表格，表格的左列是每一个产生式的左部（不重复），表格的横行是每一个终结符号。
接着逐个考察所有产生式。
抽象算法：
对于G中的每一个产生式， A -> α ,执行以下2步：
1.for ∀ a ∈ FIRST(α)， 将 A -> α 填入 M [A, a ];
//对逐个产生式进行考察，考察产生式的FIRST集合的元素，在找到的元素的对应表格中填写该产生式
//如果发现产生式的FIRST集中包含空符号，就查找该产生式头部的FOLLOW集合中的元素，在元素的对应表格中填写空产生式
原文： https://blog.csdn.net/Cielyic/article/details/82941014
西查通络： First集:是首字母所构成的集合.Follow集:是这个字母后紧接着的字母集合,如果这个字母包含空,则Follow集包含First集的全部.
南川市13821378312： 构造预测分析表中的FIRST和FOLLOW集合到底是怎么构造的,VT和VN到底指的啥,实在是查不清楚 - ？
西查通络： Vt是终结符号集,Vn是非终结符号集 FIRST(a)其实就是可从a推导得出的串的首符号的集合.FOLLOW(a)就是在某些句型中可能紧跟在a右边的终结符号的集合.它们有一个很严谨但是很难懂的创建规则: FIRST集求法 First集合最终是对产生式...
南川市13821378312： 怎么求编译原理中的first集,follow集和selec集 - ？
西查通络： 由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可很直观地得到每个字符串的First集合三,FIRST集求法 First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合
南川市13821378312： 编译原理计算first 集和follow集的简单方法? S - >bBS' S' - >aAS'|ε A - >aB|c B - >dB' B' - >bB'|ε 求计算过程 - ？
西查通络： first : S'=a,ε S=b A=a,c B=d B'=b,ε follow: S'=# S=# A=a B=a B'=a
南川市13821378312： 关于编译原理first follow 和select - ？
西查通络： 首先要明白这三个集的作用和用途,知道了他们是用来做什么的之后,理解起来就简单一些First(A)集的作用是标示在替换非终结符A的时候,替换后的文法的首字母集合,语法分析程序根据这个来判断给定的语言是否是合法的,是符合规则的...
南川市13821378312： 编译原理:FIRST(A) 集合与FOLLOW(A)集合 - ？
西查通络： 1.设计一个演示窗口,包括几本的操作按钮和显示窗口; 2.设计first集合和follow集合生成算法 3.输入文法,按要求显示first集合和follow集合
南川市13821378312： 请问谁能给我讲讲编译器中FIRST和FOLLOW集合的算法要如何实现,有源码就更好了 - ？
西查通络： (1) First集算法模块 先计算所有非终结符的FIRST集合,再求任意串的FIRST集合. 一般形式:对于产生式A->αx...(α为满足α=>*ε的右部最长子串,α可以不存在) 若x=a : a加入到FIRST(A) 若x=B : FIRST(B)加入到FIRST(A) 若x不存在...
南川市13821378312： 一个编译原理的问题 - ？
西查通络： First(α) 是符号串α的开始符号集合.也就是说,用推导的方法对α进行推导,一次次地使用产生式,用产生式右部的符号串替换一个非终结符,所有那些可能出现在第一个符号位置的终结符,就构成了开始符号集.比如,在C语言中,对于符号串...
南川市13821378312： 编译原理计算first 集和follow集的简单方法?S - >bBS' S' - >aAS'|ε A - >aB|c B - >dB' B' - >bB'|ε - ？
西查通络：[答案] first :S'=a,ε S=b A=a,c B=d B'=b,ε follow:S'=# S=# A=a B=a B'=a
南川市13821378312： 编译原理语法分析中,求first,follow集合时,要消除左递归吗 - ？
西查通络： 考虑文法G[S]:S -> xSNy| NxN -> zN|ε1、 求出该文法的每个非终结符的FIRST集和FOLLOW集;2、构造该文法的LL(1)分析表
