精华内容
下载资源
问答
  • 编译原理FIRST和FOLLOW求解,让你一学就会!
  • 编译原理FIRST集和FOLLOW集的求法

    千次阅读 多人点赞 2019-06-18 17:16:41
    编译原理FIRST集和FOLLOW集的求法 由于最近要期末考试了,所以要从头到尾复习(预习)一遍了。陈意云老师写的课本比较抽象,看不太懂,最后又找了中科大的编译原理课,可能听的时候太困了没有集中精力,又跑去看了...

    编译原理FIRST集和FOLLOW集的求法

    由于最近要期末考试了,所以要从头到尾复习(预习)一遍了。陈意云老师写的课本比较抽象,看不太懂,最后又找了中科大的编译原理课,可能听的时候太困了没有集中精力,又跑去看了以前曾经看过的哈工大的公开课,应该是看懂了,所以就厚颜无耻的来捋一捋,欢迎交流,批评指正。

    废话不多说,直接看怎么计算的吧。
    首先看FIRST集,文字描述如下:

    1.FIRST(X):可以从X推导出的所有串首终结符构成的集合
    如果X=>*ε,那么ε∈FIRST(X)

    举个栗子

    表达式FIRST集FOLLOW集
    E -> TE’{}{}
    E’-> +TE’|ε{}{}
    T-> FT’{}{}
    T’->*FT’|ε{}{}
    F-> (E)|id{}{}

    我是这样做的,首先看有终结符的表达式F-> (E)|id可以得到FIRST(F)={(, id};
    再看有终结符的表达式T’->FT’|ε,得到FIRST(T’)={*, ε}
    再看E’-> +TE’|ε,得到FIRST(E’)={+ , ε},所得得到以下结果:

    表达式FIRST集FOLLOW集
    E -> TE’{}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}{}
    T-> FT’{}{}
    T’->*FT’|εFIRST(T’)={*, ε}{}
    F-> (E)|idFIRST(F)={(, id}{}

    然后再从头看每个表达式可以得到FIRST(E)=FIRST(T),所以去求FIRST(T);
    所以来看表达式T-> FT’,得到FIRST(T)=FIRST(F),又因为F无法推导出ε,所以FIRST(T)=FIRST(F);
    同理可得FIRST(E)=FIRST(T)=FIRST(F)
    所以表就更新为以下结果:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}{}
    T-> FT’FIRST(T)={(, id}{}
    T’->*FT’|εFIRST(T’)={*, ε}{}
    F-> (E)|idFIRST(F)={(, id}{}

    这时候,我们FIRST集就已经求完了,接下来看FOLLOW集:
    同样先来文字描述:

    FOLLOW(A):可能在某个句型中紧跟在A后边的终结符a的集合
    FOLLOW(A)={a| S=>*αAaβ, a∈VT, α,β∈(VT∪VN)*
    如果A是某个句型的最右符号,则将结束符“$”添加到FOLLOW(A)中。

    还是上面的栗子:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}{}
    T-> FT’FIRST(T)={(, id}{}
    T’->*FT’|εFIRST(T’)={*, ε}{}
    F-> (E)|idFIRST(F)={(, id}{}

    我是首先找处在句子最右边的非终结符有哪些,由上面的表达式可以看出,分别有E’、T’所以首先把"$"填进去:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$}
    T-> FT’FIRST(T)={(, id}{}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$}
    F-> (E)|idFIRST(F)={(, id}{}

    然后从头开始看,首先看E,先直观的看E后面跟有哪些终结符;很容易可以看到有“)”;
    又因为E为开始符号,所以FOLLOW(E)中有“$”符
    再看T,T后面跟的是E’,所以FOLLW(T)要包含FIRST(E’);又由于E’可以推导出空串,所以T也可以是最右符号;
    再看T’,T’首先是最右符号,所以FOLLOW(T)包含结束符;
    最后看F,F后面跟的是T’,所以FOLLOW(F)包含FIRST(T’),又由于T’可以推导出空串,所以F也可以是最右符号
    所以得到以下列表:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}FOLLOW(E)={), $}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$}
    T-> FT’FIRST(T)={(, id}FOLLOW(T)={+, $}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$}
    F-> (E)|idFIRST(F)={(, id}FOLLOW(F)={*, $}

    接下来再看有表达式推导得到的FOLLOW集是否发生改变:
    又由于E->TE’,所以FOLLOW(E)=FOLLOW(E’);
    又因为T->FT’,所以FOLLOW(T)=FOLLOW(T’)
    所以有些FOLLOW集需要更新如下所示:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}FOLLOW(E)={), $}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$, )}
    T-> FT’FIRST(T)={(, id}FOLLOW(T)={+, $}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$, +}
    F-> (E)|idFIRST(F)={(, id}FOLLOW(F)={*, $}

    再看有些表达式能够推出空串,所以右边非终结符的FOLLW集合需包含左边非终结符的FOLLW集合,如E -> TE’,由于E’能够推导出空串,所以FOLLW(T)要包含FOLLW(E),根据这条规则,对FOLLW集做以下更新:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}FOLLOW(E)={), $}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$, )}
    T-> FT’FIRST(T)={(, id}FOLLOW(T)={+, $, )}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$, +, )}
    F-> (E)|idFIRST(F)={(, id}FOLLOW(F)={*, $, +,)}

    总结

    FIRST集没什么问题,很好求,但是FOLLOW集合想对就比较麻烦,需要考虑的地方比较多,在做题目的时候千万不要遗漏!
    欢迎批评指正,交流。

    展开全文
  • 编译原理课程设计。。。。简单的FIRST集FOLLOW集求解的程序。。。。压缩文档中ffs.cpp为源程序。。。。使用了bool。。。。所以做了cpp。。。。Production文本是供程序使用的产生式。。。。其余的是过程文件。。。。...
  • 写了两天的代码才写出来的,本来想多要点分的,想到我去找习题答案的时候花了很大功夫,就算了,跟大家共享,一定给我顶上啊~~~~~ 有陈火旺版的编译原理习题答案和我自己用类C写的编译原理FIRST集求解的源代码,里面...
  • First集Follow集通俗易懂的讲解加实例First ... 以非终结符开头,先把C的First放到A的First里再看如果C的First中有空(∈)的话就把D的First放到A的First里(因为如果C的First为空,那么D的First就有可能紧挨

    #First集Follow集通俗易懂的讲解加实例

    ##First

    如A->aB | CD

    这里面包含了组成First(A)的两种情况:
    以终结符开头,当然要把这个终结符(a)放到A的First里
    以非终结符开头,先把C的First放到A的First里

    再看如果C的First中有空(∈)的话就把D的First放到A的First里(因为如果C的First为空,那么D的First就有可能紧挨着A,所以就要添进A的Fisrt),如果D也有空的话往后依次类推
    

    小结:
    1、对于终结符而言,FIRST集中的元素只有它本身
    2、对于非终结符而言,如果开始符是终结符或者空符号串ε,则加入其FIRST集中;若开始符是非终结符,则要加入它的不含ε的FIRST集,并考虑其为ε时的情况。

    技巧:First一般从下往上找。
    如果要找A的First,我们要找A的定义式,即A在左边的式子,看着他的右边来找。

    ##Follow

    如S->(L) | aL | LC

    找Follow的三种情况:
    先在候选式(右边)中找到该非终结符,如L(注意例中只有一个定义,但找Follow要看到所有右边出现该非终结符的)

    如果L的右边是终结符,    那么这个终结符加入L的Follow
    
    如果L的右边是非终结符, 那么把这个非终结符的First除去空加到L的Follow中
    
    如果L处在末尾,那么,'->'左边符号的Follow成为L的Follow
    
    另外要注意的是:
    	开始符号的Follow中要加上‘#’        
    

    小结:
    1、FOLLOW集对于非终结符而言,是非终结符的全部后跟符号的集合,如果后跟终结符则加入,如果后跟非终结符,则加入该非终结符的不含空符号串的FIRST集,特别地,文法的识别符的FOLLOW集需要额外的加入‘#’。

    技巧:Follow一般从上往下找。
    如果要找L的Follow,要从式子的右边找到L,然后来找L的Follow,这与First是不同的。

    ##举个栗子:

    文法:
    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的Follow集 产生式:S→ABc A→a|ε ,但只有S→ABc 有用。跟随在A后年的终结符号是FIRST(B)={b,ε},当FIRST(B)的元素为ε时,跟随在A后的符号就是c,所以 Follow(A)={b,c} 同理Follow(B)={c}

    ##SELECT集
    ###1、定义:
    给定上下文无关文法的产生式A→α, A∈VN,α∈V*, 若α不能推导出ε,则SELECT(A→α)=FIRST(α)   
    如果α能推导出ε则:SELECT(A→α)=(FIRST(α) –{ε})∪FOLLOW(A)
    需要注意的是,SELECT集是针对产生式而言的。

    ###2、LL(1)文法:
    ① 一个上下文无关文法是LL(1)文法的充分必要条件是:对每个非终结符A的两个不同产生式,A→α, A→β,满足SELECT(A→α)∩SELECT(A→β)=空集 其中α,β不同时能推导出ε。
    ② LL(1)文法的含义:
    第一个L 从左到右扫描输入串
    第二个L 生成的是最左推导
    1 向右看一个输入符号便可决定选择哪个产生式。
    ③LL(1)文法的判别:当我们需选用自顶向下分析技术时,首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合,进而判别文法是否为LL(1)文法。

    ###3.求解示例:
    1、文法G [S]为:
      S→AB
      S→bC
      A→ε
      A→b
      B→ε
    B→aD
    C→AD
    C→b
    D→aS
    D→c
    求每个产生式的SELECT集,并判断文法G是否为LL(1)文法?
    解:SELECT(S→AB)=(FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}   
    SELECT(S→bC)=FIRST(bC)={b}   
    SELECT(A→ε)=(FIRST(ε) -{ε})∪FOLLOW(A)={a,c,#}   
    SELECT(A→b)=FIRST(b)={b}   
    SELECT(B→ε)=(FIRST(ε) -{ε})∪FOLLOW(B)={#}   
    SELECT(B→aD)=FIRST(aD)={a}   
    SELECT(C→AD)=FIRST(AD)={a,b,c}   
    SELECT(C→b)=FIRST(b)={b}   
    SELECT(D→aS)=FIRST(aS)={a}   
    SELECT(D→c)=FIRST©={c}

    由以上计算结果可得相同左部产生式的SELECT交集为:   
    

    SELECT(S→AB)∩SELECT(S→bC)={b,a,#}∩{b}={b}≠ф   
    SELECT(A→ε)∩SELECT(A→b)={a,c,#}∩{b}=ф   
    SELECT(B→ε)∩SELECT(B→aD)={#}∩{a}=ф   
    SELECT(C→AD)∩SELECT(C→b)={b,a,c}∩{b}={b}≠ф   
    SELECT(D→aS)∩SELECT(D→c)={a}∩{c}=ф   
    由LL(1)文法定义知该文法不是LL(1)文法,因为具有相同左部其产生式的SELECT集的交集不为空。

    小结:
    1、Select集的作用是将first集和follow集进行合并,如果两个文法的左端都是A,若他们的select集交集为空,表明他们是两个无关的,不会产生不确定性的文法,反之,则表明文法不是LL(1)文法。

    末尾彩蛋

    加入知识星球,有什么相关问题,有更多大佬及时解答
    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 利用vs中的c语言完成编译原理的follow集合first集的算法实现
  • 编译原理 first集 follow集 实例 解析

    千次阅读 2018-05-01 18:11:14
    编译原理只看书的话还是很难学,上课听老师讲的蛮好,可忘得也很快,再复习看书的时候已然忘记老师当时是怎么讲的了QAQ...现在只能在网上找教程自学一下喽:先看看为什么要有first集和follow集: 这个很简单了,x是...

    编译原理只看书的话还是很难学,上课听老师讲的蛮好,可忘得也很快,再复习看书的时候已然忘记老师当时是怎么讲的了QAQ...

    现在只能在网上找教程自学一下喽委屈:先看看为什么要有first集和follow集:


           

           这个很简单了,x是终结符,那它的FIRST集肯定也是x了。

     

            举个栗子::Y->b|ε,那么First (Y)={b, ε}(b是终结符)

            举个栗子:Y->b|ε,那么First (Y)={b, ε}(b是终结符),X->Yabcd|ε,则FIRST(X) = (First(Y)--{ε})∪ {ε}(这

            里的{ε}是由法则2  推导出来 )

       

             举个栗子:

    1、文法G [S]为:

    SAB                                  First(S) =(First(A)-{ε})∪(First (B)-{ε}) ∪{ε}∪{b} 

    SbC                                   因为A的first有ε,B的first有ε,S->AB,所以是First(A)-{ε})∪(First (B)-{ε}) ∪{ε}
    A→ε         然后S->bC由法则2得,所以再加一个b就是First(A)-{ε})∪(First(B)-{ε})∪{ε}
    Ab                                    ∪{b}

    B→ε          由之前的法则:First (A)={b, ε}First (B)={a, ε}所以First(S) ={a,b,ε}

    BaD

    CAD

    Cb

    DaS

    Dc


        

        FOLLOW集就是找后面有没有能处理这个终结符的非终结符,如果有就继续,没有则报错!所以此处我们的视角和求解first集的视角有所不同,此时我们应该向后看,找后面的。


            这个不用多说,初始规定就是这样。


            举个栗子:文法G [E]为:    

                       E   →  TE'          因为E是文法的识别符所以把#加入FOLLOW(E),又由规则F  →  (E) | i 得E

                       E'  →  +TE' | ε    的后跟符号  )(  first(')') = {)}  ) ,所以,FOLLOW(E)={ #,) };

                       T   →  FT'

                       T'  →  *FT' | ε

                       F  →  (E) | i

              举个栗子:文法G [E]为:    

                       E   →  TE'          先给出它们的FIRST集:(求解方法见上面FIRST集的求解)

                       E'  →  +TE' | ε            FIRST(F)={ (,i }

                       T   →  FT'                    FIRST(T’)={ *,ε }

                       T'  →  *FT' | ε             FIRST(T) ={ (,i }

                       F  →  (E) | i                 FIRST(E’)={ +,ε }

                                                       FIRST(E)={ (,i }

    FOLLOW集的求解:因为E是文法的识别符所以把#加入FOLLOW(E),又由规则F  →  (E) | i 得E的后跟符号),所以,FOLLOW(E)={ #,) };

    FOLLOW(E’)={ #,) }    ∵E → TE’   follow集的目的是为了在E'无法处理当前终结符的时候,判断E'之后有没有能处理该终结符的非终结符,    ∴FOLLOW(E)加入 FOLLOW(E')

    FOLLOW(T)={+,),#}      ∵E'→ +TE’  ∴FIRST(E’)-{ε}加入FOLLOW(T); 又E’→ε,     ∴ FOLLOW(E’)加入FOLLOW(T)此处如果把E'->+TE'看为A->aBb,b=>ε的话,则Follow(E')加入Follow(E')中,这样没有任何意义。

    FOLLOW(T’)= FOLLOW(T)= {+,),#}      ∵T → FT’   ∴ FOLLOW(T)加入FOLLOW(T’)
    FOLLOW(F)={*,+,),#}    ∵T → FT’   ∴ FOLLOW(F)=FIRST(T’)-{ε} ; 又T’→ε ∴ FOLLOW(T)加入FOLLOW(F)

            

    展开全文
  • 编译原理实验 first、follow、select集合的求解,经测试正确,c语言编写
  • java语言实现编译原理,文法G的first集和follow集求解
  • 是完整的程序,没有错误,能够求所有的ll文法的first,follow
  • 编译原理 First集和Follow集的求法

    千次阅读 2018-11-19 13:17:56
    转载地址 ... 自上而下分析: ...First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可很直...

    转载地址

    https://blog.csdn.net/Alexander_Frank/article/details/51280798

    自上而下分析:

    FIRST集求法

        First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可很直观地得到每个字符串的First集合。

    1. 直接收取:对形如U->a…的产生式(其中a是终结符),把a收入到First(U)中

    2. 反复传送:对形入U->P…的产生式(其中P是非终结符),应把First(P)中的全部内容传送到First(U)中【意思就是只需要把第一个非终结符的First集传过去~这个地方是要注意的地方,也是难点】。

    FOLLOW集的求法

        Follow集合是针对非终结符而言的,Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合,特别地,“#”是识别符号的后随符。注意Follow集合是从开始符号S开始推导。

    1. 直接收取:注意产生式右部的每一个形如“…Ua…”的组合,把a直接收入到Follow(U)中。因a是紧跟在U后的终结符。

    2.直接收取:对形如“…UP…”(P是非终结符)的组合,把First(P)直接收入到Follow(U)中【在这里,如果First(P)中有空字符,那么就要把左部(假设是S)的Follow(S)送入到Follow(U)中。还有就是Follow集中是没有空字符的】。

    3. 直接收取:若S->…U,即以U结尾,则#∈Follow(U)

    4.*反复传送:对形如U->…P的产生式(其中P是非终结符),应把Follow(U)中的全部内容传送到Follow(P)中。


    当构造完这两个集合,则开始构造文法分析表

    对每一个产生式A->XXX,执行

    (1)对First(A)中的每一个终结符a,把A->XXX加入M[A,a]中。

    (2)若‘空’在First(A)中,把Follow(A)的每一个终结符b(包括$),把A->XXX加入M[A,b]中。剩下为错误条目,空白处理。



    展开全文
  • 编译原理first集合和follow集合

    千次阅读 2013-04-15 11:59:10
    编译原理:求First集与Follow集的方法 2011.06.4 1 Comment 最近马上要步入考试周了,编译原理的这个Follow集一直令我头大啊,今天百度了下下,找到一篇文章,看了以后我瞬间就明白了如何求解...
  • 编译原理FIRST集和FOLLOW集的求法以及构建LL(1)分析表

    万次阅读 多人点赞 2019-07-01 10:57:57
    文章目录FIRST集的求法FOLLOW集的计算生成预期分析表算法例题 FIRST集的求法 FIRST集是一个文法符号串所可能推导出的符号串的第一个终结符的集合 对于文法G的任一符号串α\alphaα = x1x2…xnx_{1}x_{2} \ldots x_{n...
  • 本资源用C#开发,集成了first集和follow集 正规式到NFA转换 等
  •  First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可很直观地得到每个字符串的First集合。 1. 直接收取:对...
  • 对文法拆分 并求First集和Follow集和预测分析表
  • 编译原理 FIRST集和FOLLOW集的求法

    千次阅读 2014-12-27 09:16:47
    前几日纠结于编译原理First 和 Follow集合的求法,然后发现了一片不错的博文,记于此。 原文地址: http://blog.sina.com.cn/s/blog_a1132bf901011ylj.html First集合的求法:   First集合最终是对产生式...
  • 已知文法 G(E)  E →T|E+T T→F|T *F F →(E)|id 求所有非终结符的first集合和follow集合
  • 1.为什么要引入FIRST集的概念? 因为有公共左因子的问题,公共左公因子是指在文法的产生式集合中,某个非终结符的多个候选式具有相同的前缀。 一般来说,公共左公因子的产生式为 A→αβ1│αβ2 A→\alpha\beta_1...
  • 用java实现的,实现了整个方法只要改变G(E).txt中内容就可以分析不同的语法了。
  • 最近在学编译原理,老师教学很严,所以自己得把每个知识点学懂。  first集的求法比较简单  1. 对形如U->a„的产生式(其中a是终结符),把a收入到First(U)中.  2. 对形入U->P„的产生式(其中P是非...
  • DEV C++ 项目实现 不会建项目的看这个——>如何创建项目 ...提取码:b1qz 使用教程 解压后打开文件夹,直接用Dev c++运行LL1,如图: 即可实现。...一分钱都不要啊, 比那些要C币的都好,点个赞呗亲们!...
  • 编译原理FIRST集FOLLOW集

    万次阅读 多人点赞 2017-12-01 17:22:29
    编译原理 FIRST,FOLLOW集的求法
  • 编译原理first集合

    2013-07-23 08:59:24
    里面是编译原理课上所讲的求first的集合的源代码,使用C++编写的
  • first编译原理 c++版本first编译原理 c++版本
  • 编译原理JAVA求First集Follow集

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,574
精华内容 22,629
关键字:

编译原理first