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集合
- 直接收取:对形如U->a…的产生式(其中a是终结符),把a收入到First(U)中
- 反复传送:对形入U->P…的产生式(其中P是非终结符),应把First(P)中的全部内容传送到First(U)中
FOLLOW集求解
- Follow集合是针对非终结符而言的
- Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合
- Follow集合是从开始符号S开始推导
- 直接收取:注意产生式右部的每一个形如“…Ua…”的组合,把a直接收入到Follow(U)中。因a是紧跟在U后的终结符
- 2.直接收取:对形如“…UP…”(P是非终结符)的组合,把First(P)直接收入到Follow(U)中
- 直接收取:若S->…U,即以U结尾,则#∈Follow(U)
- 4.反复传送:对形如U->…P的产生式(其中P是非终结符),应把Follow(U)中的全部内容传送到Follow(P)中
传送门:http://blog.csdn.net/jack_wong2010/article/details/9074951