FIRST和FOLLOW的求解过程

Posted by Csming on 2016-11-22

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)中
    1. 反复传送:对形入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)中
    1. 直接收取:若S->…U,即以U结尾,则#∈Follow(U)
  • 4.反复传送:对形如U->…P的产生式(其中P是非终结符),应把Follow(U)中的全部内容传送到Follow(P)中

参考资料:http://blog.csdn.net/jack_wong2010/article/details/9074951