first、follow集合求解（编译原理）

拼搏现实的明天。 2021-09-26 02:28 293阅读 0赞

First集合的求法： 
        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所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。
    1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。 2．直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)除ε直接收入到Follow(U)中。 3．反复传送：对形如P－…U的产生式（其中U是非终结符），应把Follow(P)中的全部内容传送到Follow(U)中。(或 P－…UB且First(B)包含ε，则把First(B)除ε直接收入到Follow(U)中，并把Follow(P)中的全部内容传送到Follow(U)中)

例1：判断该文法是不是LL(1)文法，说明理由 S→ABc A→a|ε B→b|ε？ 
        First集合求法就是：能由非终结符号推出的所有的开头符号或可能的ε，但要求这个开头符号是终结符号。如此题A可以推导出a和ε，所以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｝。

例2：文法如下：
    	E→TE'
    	E'→+TE' | ε 
    	T→FT'
    	T'→*FT' | ε 
    	F→(E) | id
    求出各个非终结符的first和follow集合。
    解：根据求解的算法求得下面的结果：
    first（E)=first(T)=first(F)={(，id}；
    first(E')={+，ε}；
    first(T')={*，ε}；
    follow(E)=follow(E')={)，$}；
    follow(T)=follow(T')={+,)，$}；
    follow(F)={+,*,)，ε}；