编译原理FIRST和FOLLOW集的求解

FIRST

• 能由非终结符号推出的所有的开头符号(终结符)或可能的ε
• 假设有以下文法：

S→ABc
A→a|ε
B→b|ε

• 则：FIRST(A)={a,ε},FIRST(B)={b,ε}
• 由于从S可以推得aBc，bc，c，故FIRST(S）=｛a，b，c｝

FOLLOW

• 紧跟随其后面的终结符号或＃
• 把所有包含你要求的符号的产生式都找出来，再看哪个有用。 Follow（S）=｛＃｝

如求A的，产生式：S→ABc A→a|ε ，但只有S→ABc 有用。跟随在A后年的终结符号是FIRST（B）=｛b，ε｝，当FIRST（B）的元素为ε时，跟随在A后的符号就是c，所以 Follow（A）=｛b，c｝ 同理Follow（B）=｛c｝

补充一些编译方法的知识点(来自Jack_Wong2010)

一.终结符和非终结符

• 终结符就是不能再往后推导的字符
• 非终结符可以继续推导

文法产生语言句子

• 从识别符号（开始符）开始，把当前产生的符号串中的非终结符替换为相应规则右部的符号串，直到全部由终结符组成

FIRST集求解

• 关键是求出非终结符的First集合
• 终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合
• 1. 直接收取：对形如U－>a…的产生式（其中a是终结符），把a收入到First(U)中
• 2. 反复传送：对形入U－>P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中

FOLLOW集求解

• Follow集合是针对非终结符而言的
• Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合
• Follow集合是从开始符号S开始推导
• 1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。因a是紧跟在U后的终结符
• 2．直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)直接收入到Follow(U)中
• 3. 直接收取：若S－>…U，即以U结尾，则#∈Follow(U)
• 4．反复传送：对形如U－>…P的产生式（其中P是非终结符），应把Follow(U)中的全部内容传送到Follow(P)中

传送门:http://blog.csdn.net/jack_wong2010/article/details/9074951