精华内容
下载资源
问答
  • 编译原理FOLLOW集的求法

    千次阅读 2020-05-27 14:26:45
    follow集求法有两种,要么逐步推导,推导出所有式子求follow集合,这种方法简单但是容易遗漏 要么就按照步骤一步一步来求 文字定义:FOLLOW(A)集合是所有紧跟A之后的终结符或#所组成的集合(#是句尾的标志),称...
    follow集求法有两种,要么逐步推导,推导出所有式子求follow集合,这种方法简单但是容易遗漏
    要么就按照步骤一步一步来求
    
    文字定义:FOLLOW(A)集合是所有紧跟A之后的终结符或#所组成的集合(#是句尾的标志),称FOLLOW(A)是A的随符集
    

    下面直接介绍规范的求法(这个文法必须消除左递归和提取公共左因子)

    计算所有非终结符号A的follow(A)集合时,不断应用下面的规则,直到再没有新的终结符号可以被加入到任意的follow集合中为止。
    注意:当A是最右部的时候,将$加入到follow(A)中

    (1)将 $ 放到follow(S)中,其中S是文法的开始符号。

    (2)如果存在一个产生式A→αBβ,那么first(β)中除ε之外的所有符号都在follow(B)中。 【 follow(B)是求跟在B后的终结符或$组成的集合,因此对于跟在B后的β,它的first集合就是follow(B)的子集 】

    (3)如果存在一个产生式A→αB,或存在产生式A→αBβ且first(β)包含ε,那么follow(A)中的所有符号都在follow(B)中。 【 对于A→αBβ,且β多步推导出ε ,那么可以用αB替换A, B后面紧跟的字符就是A后面紧跟的字符】


    下面举个例子来按照这种方法求FOLLOW

    文法如下:

    1. E -> TE’
    2. E’ -> +TE’ | ε
    3. T -> FT’
    4. T’ -> *FT’ | ε
    5. F -> (E) | id

    直接给出First集
    first(E) = first(T) = first(F) = { ( , id }
    first(E’) = {+, ε}
    first(T’) = {*, ε}

    FOLLOW E
    E是文法的开始符号,根据规则 (1) 将$加入到 follow(E), follow(E) = { $ }, 
    再根据规则(2)和产生式 5) 加入, 所以 follow(E) = {$, )}
    

    FOLLOW E’

    根据产生式 1 , E'是结尾符号,所以将$加入follow(E’), 根据规则 (3) 和产生式 1,可知,将
    follow(E) 加入到 follow(E‘)中 ,所以 follow(E') = {$, )}
    

    FOLLOW T

     根据产生式 1 和 规则(2) ,first(E') - {ε}加入到follow(T)中,follow(T) = {+} , 
     再根据产生式 1 和规则(3),follow(E)加入到follow(T)中,所以follow(T) = {+, ), $}
    

    FOLLOW T’

    根据产生式 3 因为T'出现在最右部,所以{$}加入follow(T‘)中,再根据规则(3)和产生式3,
    将follow(T)加入到follow(T’)中,所以follow(T') = {+, ), $}
    

    FOLLOW F

    ① 根据产生式 3 和规则 (2),first(T')-{ε}加入到follow(F)中,follow(F) = {*}
    ② 产生式 3 和 规则 (3) ,将follow(T)加入到follow(F)中,follow(F) = {*,+,),$}
    ③ 再根据产生式 4 和规则(3)follow(T')加入follow(F) follow(F) = {+, ), *, $}
    ④ 根据产生式 4 和规则2first(T')加入到follow(F)中, follow(F) = {+,),*,$}
    
    实际上,我们回顾规则开头,当没有新的终结符加入时,不必对所有的式子都应用
    式子进行计算。
    
    展开全文
  • 编译原理之NULL集、first、follow集C语言实现,实现中句子的转换符号由‘#’代替,数组默认由‘*’作为结束符
  • 编译原理课程设计。。。。简单的FIRST集FOLLOW集求解的程序。。。。压缩文档中ffs.cpp为源程序。。。。使用了bool。。。。所以做了cpp。。。。Production文本是供程序使用的产生式。。。。其余的是过程文件。。。。...
  • follow集 定义 follow(A)是可能在某个句型紧跟在A后面终结符a的集合 如果A是某个句型的最右符号,则将终结符$加入到follow(A)中 不断应用下面的规则,直到再没有新的终结符号可以被加入到任意的follow集合中为止。 ...

    first集 定义

    first(x):可以从x推导出的所有串首终结符构成的集合 若x→ ε ,ε ∈first(x)

    follow集 定义

    follow(A)是可能在某个句型紧跟在A后面终结符a的集合

    如果A是某个句型的最右符号,则将终结符$加入到follow(A)中

    不断应用下面的规则,直到再没有新的终结符号可以被加入到任意的follow集合中为止。

    ①如果S是文法的开始符号,那么把$添加进FOLLOW(S)中。($是输入串的结束符)

    ②如果有一个产生式A→αBβ
    1 ε不属于first(β),则folllow(B)=first(β)
    2 ε属于first(β),则follow(B)=first(β)-{ε}+follow(A)

    ③ 如果有一个产生式 A→αB , follow(B)=follow(A)
    α既可为终结符又可为非终结符。

    first集的计算就比较简单了,(2)、(4)、(5)式子的串首终结符比较容易看出,由first集的定义可知ε也属于(2)、(4)first集。由(1)可知,E的first集取决于T,由(3)可知,T的first集取决于F。故而求得各自的first集。
    follow集计算如求E’的follow集看的是(1)式子,对比上面格式为产生式 A→αB 满足规则③,带入公式求出follow(E’)=follow(E);
    求T的follow集看的是(2)式子,满足产生式A→αBβ 符合规则②,又因为ε属于first(E’),得follow(T)=first(E’)-{ε}+follow(E’) 。下面其他求解类似。

    展开全文
  • 语言为C++,使用了set,map容器,输入格式:S -> Aa | g | e,支持多‘|’ 符号,采用文件输入
  • 想了很久想不通,为什么如果A->B,那么A的follow集一定包含于B的FOLLOW集,这个感觉很多老师和教材是直接这么认为的,但是为什么呢?
  • C语音代码。实现功能:1....2.求每个非终结符FIRST 集FOLLOW集和SELECT集模块。3.预测分析表的构建模块。4.文法的检验及消除左公因子和左递归模块。5.对输入终结符串的判断,是否为LL1文法,并进一步分析。
  • ( 编译原理JAVA求First集Follow集
  • 编译原理之first集,follow集,select集解析

    万次阅读 多人点赞 2018-04-30 19:30:32
    为了方便自顶向下语法分析,需要求文法对应的first集,follow集,以及select集。本文主要分为两部分,一个是求法解析,还有一个例子详解:第一部分是求法解析将对first集,follow集,select集分为三种讲解方法①定义...

    为了方便自顶向下语法分析,需要求文法对应的first集,follow集,以及select集。

    本文主要分为两部分,一个是求法解析,还有一个例子详解:

    第一部分是求法解析

    将对first集,follow集,select集分为三种讲解方法

    ①定义介绍及推导

    ②简单推导演示

    ③规范式推导


    讲解顺序为,先用最简单的推导介绍三种不同的集,然后介绍概念,最后介绍正规的推导方法

    三种方法,不同人喜欢不同的理解方法,大家都可以参考,推导方法越往后,越规范!


    默认规则:

    起始符S,其余大写字母为非终结符;

    小写字母为终结符,#为ε; 

    产生式: A->BC, 其中这个是关于A的产生式,A为左部(左边部分),BC为右部 (右边部分)

    Vt是终结符

    Vn是非终结符



    首先文法G[S]

    S-> AB|bC

    A->#|b

    B->aD|#

    C->AD|b

    D->aS|c


    first集:

    ①简单推导

    first,顾名思义就是该关于该符号的所有产生式右部第一个遇到终结符。


    例如:

    first(S)

    用上面那句话:关于S的产生式有两个:S->AB,S->bC
    
    先看简单的情况:S->bC,明显右部第一个终结符是b,  那关于这个产生式的终结符就是b 了,解决一个!
    
    这个时候first(S)={b}
    
    然后是S->AB,这时右部的第一个是A,非终结符,所以不成立。这时你就要再把A的产生式引进来(因为A有关于他的产生式)。
    
    关于A的产生式为:A->#,A->b,分别代入S->AB的产生式得:S->B(应该是S->#B,但是#可以省略) 和S->bB.
    
    看第二个S->bB ,马上就可以知道遇到的第一个终结符是b,
    
    这个时候first(S)={b}
    然后看第一个S->B,这个时候B不是终结符,所以不成立,这时就要把B的产生式导进来。
    
    变成S->aD ,S->#,
    
    然后上面两个式子,分别第一个终结符为a,和 #
    
    则这个时候first(S)={b, a , #}
    
    
    这里强调一下 。为什么S->AB ,会变成后面的S->B 而S->aD就没有S->D, 因为A的产生式是有一个A->#,就是指向空,这个时候代入S->AB不就等于 S->B了吗。而S-aD。因为已经找到第一个终结符了,所以这个产生式就结束推导了





    ②定义讲解:

    定义:设G=(Vt,Vn,P,S)是上下文无关文法。

    first(A)={a| A=*>ab, a∈Vt,b∈V*}

    若a=*>ε ,则规定ε ∈first(a).成first(a)为a的开始符号集或首符号集


    上面是大白话,下面是系统总结一下:

    first,顾名思义就是该关于该符号的所有产生式右部第一个遇到终结符。

    举例:
    
    一、单个非终结符的first集
    
    (1)求终结符的first集,是他本身
    
    first(a)={a}
    
    (2)X->a....
    
    first(X)= a....,取右部的终结符,则a∈first(x)
    
    (3)X->YZ...
    
    first(X)=YZ...,  当右部第一个符号(Y)是非终结符的时候,你就要把这个符号(Y)的产生式导进来了,然后再判断右边第一个是否是终结符。若Y的产生式存在#,则继续导入Z的产生式寻找右边第一个终结符,重复以上动作。即
    
    first(X)=first(Y),若存在Y->#,则继续first(X)=first(Z),直到非终结符不存在#结束。
    
    
    
    二、多个非终结符
    
    X->M...
    
    Y->N...
    
    first(XY)=M...N...  ,同样找右边第一个是终结符的符号,

    ③正规推导:

    (1)对每一文法X∈V,计算first(X)
    
    (2)
    
    ①X∈Vt,则first(X)={X}
    
    ②X∈Vn(非终结符),且有X->a , 则a∈first(X)
    
    ③X∈Vn(非终结符),且有X-># , 若#∈first(X)
    
    ④若有X,Y1,Y2,Y3...∈Vn,且有产生式X->Y1,Y2,Y3=*>#,则first(Y1)-{#},first(Y2)-{#}...first(Yi)都属于first(X)找中
    重复②-④
    
    ⑤当所有Yi=*>#   则first(X)=first(Y1)-{#}∪first(Y2)-{#}.....∪first(Yi)
    当有X-># ,才能说#∈first(X)


    follow集

    follow,顾名思义,就是该符号后面跟着的第一个终结符

    PS:求follow集,都是从开始符号S开始推导


    ①定义介绍

    设G=(Vt,Vn,P,S)是上下文无关算法,A属于Vn,S是开始符号

    follow(A)={a|S=*>uAb 且a∈Vt,a∈first(b),u∈Vt,b属于V*}

    也可定义为
    
    follow(A)={a | S=*>.....Aa....,a∈Vt}.....(1)
    
    若
    
    S=*>...AB....,则follow(A)=first(B)....(2)
    
    若
    
    S=*>....A   ,因为这个时候A属于S,因此这个时候应该看得是S后面的东西也就是follow(S)∈follow(A)....(3)
    
    
    若
    
    S=*>...AB,这个时候first(B)存在空的情况,而这个时候first的空集不能出现在follow集中,因此还应该看S后面的东西,因此这个等于follow(A)=(first(B)-{#})∪follow(S)....(4)
    

    通过上面(1)(2)(3)(4)不难得出,follow(A)就是从开始符号通过各种产生式推导,直到出现A,然后取A后面的第一个终结符


    ps first产生的空集不能给follow,只有follow产生的才可以给,参考上面的(4)


    ②简单推导:

    (1)终结符的follow没有定义,只有非终结符的follow才有定义
    
    
    
    (2)
    
    假设:
    
    S->xAy
    
    A->aBb
    
    先求上面
    
    follow(A):
    
    因为要找A后面的跟着的第一个终结符,所以应该直接看谁能产生A,得
    
    S->xAy,
    
    此时A后面跟着的终结符是y,因此follow(A)={y} ,解决!
    
    
    
    求FOLLOW(B)
    
    
    
    则先找谁能产生B:
    
    B的产生式:
    
    A->aBb,此时,要把first(b)(因为是B后面遇到第一个终结符,也就是first(b),也就是b的first集合)
    
    
    
    
    
    但是如果这个时候b等于#,那么B的follow集应该取得是b(假设b可能为空的情况)后面的东西,那么问题来了,b后面的东西怎么来呢?
    
    S->xAy,先看下A的产生式,(因为永远是从S出发,因此当产生式出现B的时候一定是这样的流程)
    
    然后代入A的产生
    
    S->xaBby
    
    可以看到出现B的时候是这样的,所以这个时候就应该是把b忽视,直接看y,那么这个时候是不是很熟悉?没错就是跟上面求FOLLOW(A)的一样做法,也就是follow(A)∈follow(B)
    
    这个时候可以总结一个规律
    
    当b为#的时候,follow(B) 就应该看谁产生生它的那个非终结符的follow(),在这里就是因为A->xBy,因此看follow(A)
    
    

    ③正规推导

    计算follow集
    
    ①设S为起始,{#}加入follow(S)
    
    ②要求follow(B),若A->aBb是一个产生式,则把first(B)的非空元素加入follow(B)中
    
    ③若B->#,则把follow(A)加入follow(B)中
    
    解释:因为  若D->xAy,A->aBb, 则 D->xaBby,且b=#,则first(y)或者说是 follow(A),  ∈follow(B)
    
    
    
    就是所求符号的右边如果等于# 则不停找上一级


    前排提示:

    做first集的时候,应该第一个找的是左部跟所求符合相同的产生式,然后再分别找这些产生式中右部第一个终结符,然后他们组成一个集合,就是结果


    做follow集的时候,应该第一个找的是右部存在所求符号的产生式(区别:first找左,follow找右,first找的符号要跟所求符号完全一样,follow只要找左部存在所有符号的即可),然后再找该符号后面跟着的第一个终结符,如果后面没有符号(即为#),则继续follow()这个产生式的左部,直到找到终结符为止。


    做follow集的时候往往要不停往上面找上一级,如果有循环语句的话,不妨顺着从S开始往下找(这样也可以找到所求符号的上级),这样虽然繁杂,但是不会陷入死循环



    select集

    在求出first集和follow集后

    select就方便多了

    例:

    select(X->Y),先求first(Y),如果first(Y)存在#∈first(Y)的情况,则再求follow(X),最后求两者的并集即可即可



    例子:

    默认规则:大写字母为非终结符,小写字母和字符(包括 '^'  '( '   ',' 等三个符号 )都是终结符


    S->a
    
    S->^
    
    S->(T)
    
    T->SN
    
    N->,SN
    
    N->#
    
     
    
     first(S)=first(a)∪first(^)∪first((T)) ={a,^,T}
    
    first(T)=first(S)={a,^,T}
    
    first(N)=first(,SN)∪first(#)={ ‘,’ #}
    
    
    
    只有开始符号才有默认{#} ,其余符号的follow集不能通过first产生#,只能通过 ‘∪follow(S)‘ 产生
    
    follow(S)={#}∪follow(N)={#}
    
    follow(T)=first()) ={  ) }
    
    follow(N)=follow(T)={)}


     

    是否=>#

    First

    Follow

    S

    {a,^,(}

    {#,  ’,’ ,  ) }

    T

    {a,^,(}

    { ) }

    N

    {‘,’ , #}

    { ) }


    Select(S->a) =first(a)= {a}
    
    Select(S->^) =first(^)={^}
    
    Select(S->(T)) =first( (T)  )={ ( }
    
    Select(T->SN) = first(S)={a,^,(}
    
    Select(N->,SN)=first( , ) ={ , }
    
    Select(N->#) =follow(N) = { ) }
    
    select技巧。如select(N->,SN)  即求N->,SN  ,看下图,判断右部 有否必否,有终必否,  如果确定是否的,则只计算first(左部)即可。
    在这里左部(,SN) 其中 ‘,‘ 是终结符,所以直接select(N->,SN)=first(,SN). 你也可以判断说:因为S有下图可知是‘否‘, 因此也是只计算first(,SN)



    展开全文
  • 编译原理follow集

    千次阅读 2018-06-30 11:16:30
    ...Ua...a此时加入follow(u)中,即把要求非终结符后的终结符加入,只看产生式右部,不管左边2、A->...UP...若要求非终结符后紧跟的也是非终结符,则把first(P)加入follow(U)这种情况还有一种特殊状况:A-&...

    查了很多概念,但是都比较乱,总结了一下,大致是3种情况:

    1、A->...Ua...

    a此时加入follow(u)中,即把要求非终结符后的终结符加入,只看产生式右部,不管左边

    2、A->...UP...

    若要求非终结符后紧跟的也是非终结符,则把first(P)加入follow(U)

    这种情况还有一种特殊状况:A->...UP

    后跟的非终结符是最后一个符号,则在把first(p)加入的同时,把follow(A)也加入follow(U)

    3、A->...U

    所求的非终结符事最后一个符号,则把follow(A)加入follow(U)


    展开全文
  • 编译原理follow集

    2019-11-14 21:09:37
    1、A->...Ua... a此时加入follow(U)中,即把要求非终结符后的终结符加入,只看产生式右部,不管左边 ...后跟的非终结符是最后一个符号,则在把first(P)加入的同时,把follow(A)也加入follow...
  • 编译原理之FIRST集FOLLOW集

    万次阅读 多人点赞 2017-12-01 17:22:29
    编译原理 FIRST,FOLLOW集的求法
  • 输入任意的上下文无关文法,输出所输入的上下文无关文法一切非终结符的first集合和follow集合 输入任意的上下文无关文法,输出所输入的上下文无关文法一切非终结符的first集合和follow集合
  • 编译原理 first集 follow集 实例 解析

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

    万次阅读 多人点赞 2018-05-29 11:16:36
    经过前阵子的各种百度以及对课本的反复研究,终于弄明白了follow集的求法,下面记录一下! 首先引用龙书里面的一段较为公式化的follow集求法的话: 计算所有非终结符号A的follow(A)集合时,不断应用下面的规则,...
  • First集Follow集通俗易懂的讲解加实例First 如A->aB | CD 这里面包含了组成First(A)的两种情况: 以终结符开头,当然要把这个终结符(a)放到A的First里 以非终结符开头,先把C的First放到A的First里再看如果...
  • 编译原理——自顶向下分析中FOLLOW集的计算

    千次阅读 多人点赞 2018-05-21 20:54:02
    一、FOLLOW集的定义 对于非终结符号A,FOLLOW(A)被定义为:可能在某些句型中紧跟在A右边的终结符号的集合(为什么说是可能?因为在一些推导出来的文法符号串中,该非终结符号A可能在最右边,比如:A—&...
  • 编译原理FIRST集和FOLLOW集的求法以及构建LL(1)分析表

    万次阅读 多人点赞 2019-07-01 10:57:57
    文章目录FIRST集的求法FOLLOW集的计算生成预期分析表算法例题 FIRST集的求法 FIRST集是一个文法符号串所可能推导出的符号串的第一个终结符的集合 对于文法G的任一符号串α\alphaα = x1x2…xnx_{1}x_{2} \ldots x_{n...
  • 编译原理 First集和Follow集的求法

    千次阅读 2018-11-19 13:17:56
    FIRST求法     First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可...
  • }if(mp.containsKey(nextNode)){//非终结符 if(first.get(nextNode).contains(new Character(‘$‘))){//A->@B&, 而 &->$ if(follow.get(leftNode) == null) findFollow(leftNode);if(follow.get(curNode) == null)...
  • 编译原理 —— FOLLOW集

    千次阅读 2019-02-05 22:08:25
    FOLLOW集 FOLLOW(A):紧跟在非终结符A后边的终结符α的集合 如果A是某个句型的的最右符号,则将结束符 $$$ 添加到 FOLLOW(A)中 计算非终结符A的 FOLLOW集合 (1)将$$$放入 FOLLOW(S)中,其中S是开始...
  • 1.Fisrt集 第一步: 如果右边是以终结符符号开头,就直接加入 2.第二步 将空串加入 ...2.计算follow集 总结: 非终结符打头,非终结符的first集合 空产生式 follow集合 终结符打头,终结符 ...
  • 编译原理--follow集

    2018-03-28 19:33:16
    1、来自百度百科的定义:集合 Follow (A) 的定义如下:(1)若 A 是开始符号,则$就在 Follow (A) 中。(2)若存在产生式B →aAg ,则First (g) - { }在 Follow (A) 中。(3)若存在产生式B →aAg ,且ε在 First (g...
  • 本资源用C#开发,集成了first集和follow集 正规式到NFA转换 等
  • 编译原理:求First集和Follow集

    千次阅读 2018-10-25 22:16:04
    #输入文法求First集和Follow集 #要求大写字母表示非终结符,小写字母表示终结符 #最后一个产生式以$结尾或者输入$表示输入结束 #默认第一个产生式的→左边为起始符号 def inputGrammer(): #接收文法输入的函数 ...
  • 编译原理:FIRST集与FOLLOW集

    千次阅读 2018-12-13 20:06:28
    编译原理:FIRST集与FOLLOW集 一、First集合 定义: First集合是对产生式右部的字符串而言的,求取的是非终结符VT(或终结符、空字符、文法符号串)的开始符号集合,集合中包含的是由左部非终结符VT推导得到的...
  • 博文链接:https://zpchen.iteye.com/blog/208947

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,958
精华内容 1,183
关键字:

编译原理follow集怎么算