精华内容
下载资源
问答
  • 编译原理之first集 & follow集 & select集 详解

    千次阅读 多人点赞 2020-04-12 01:37:38
    编译原理之first集 & follow集 & select集 详解 一、first集,follow集,以及select集求法解析 二、例子详解 1、关于first集: 2、关于follow集: 3、关于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
    

    1、关于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);
    

    2、关于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开始往下找(这样也可以找到所求符号的上级),这样虽然繁杂,但是不会陷入死循环。

    3、关于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)={}
    

    在这里插入图片描述

    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(左部)即可。
    

    在这里插入图片描述

    Ending!
    更多课程知识学习记录随后再来吧!

    就酱,嘎啦!
    

    在这里插入图片描述

    注:
    1、人生在勤,不索何获。
    2、编译原理之first集,follow集,select集解析文章参见:
    https://blog.csdn.net/hxfghgh/article/details/80150011

    展开全文
  • 编译原理之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)



    展开全文
  • 构造select集 编译原理 C语言版本构造select集 编译原理 C语言版本
  • 编译原理求FIRST集、FOLLOW集和SELECT集

    万次阅读 多人点赞 2019-07-02 15:29:50
    最左推导,只需向右看一个符号就可以决定如何推倒 LL(1)文法满足条件:左部相同的产生式的select集的交集为空,并且产生式的右部不能同时推导出ε,那么这个文法是LL(1)文法,否则不是 上面的文法select(C->AD)和...

    转自:https://liuyanzhao.com/8279.html

    觉得解释比较不错。

    所有大写字母代表非终结符,小写字母代表终结符,省略号代表未知数目(可能为0)的不确定类型的文法符号。

    First集合:

    First集合顾名思义就是求一个文法符号串所可能推导出的符号串的第一个终结符的集合

    First(X)就是求X所有推导出的符号串的第一个符号的集合。

    求First集合可分如下几种情况:

    1、单个符号的First集合:单个终结符的First集合就是它自己。

    2、单个非终结符的First集合:

    A-->a… 产生式右部以终结符开头,根据定义,这种情况下显然可以看出a属于First(A)。

    A-->B… 产生式右部以非终结符开头,根据定义,既然可以把A替换成B……,也可以看出First(B)属于First(A)。这是一个递归的推导。

     

    3、多个符号形成的符号串的First结合:

    符号串ABC…,并且A不能推导出空串ε,显然根据定义First(ABC…)=First(A)

     

    符号串ABC…,并且A可能推导出空串ε,当A不是空串的时候,显然First(A)属于First(ABC…),但当A是空串的时候,ABC…就成了BC…,此时根据B是否能推出空串来决定是否将First(B)加入First (ABC…)。这是一个递归的推导,综上所述,符号串中的第一个不能推出空串的符 号前面所有符号的First集合减去空串ε都属于First(ABC…),第一个不能推出空串的 符号的First集合也属于First(ABC…)。也就是假设A、B都可以推出空串,C不能推 出空串,First(ABC…)=First(A)-ε∪First(B)-ε∪First(C)。

     

    注意:First集合中的符号一定是终结符,终结符也包括空串ε。

    A–>…UP… 要求的Follow集合的非终结符后跟非终结符

     

    Follow集合:

    Follow集合也是顾名思义的,就是文法符号后面可能跟随的终结符的集合(不包括空 串ε)

    Follow(X)就是求X后面可能跟随的符号集合。

    求Follow集合可分如下几种情况:

    终结符的Follow集合没有定义,只有非终结符才会有Follow集合。

     

     

    A–>…Ua… 要求的Follow集合的非终结符后跟终结符

    根据定义,显然a属于Follow(U)。这种情况下,Follow(U)和A没有任何关系,产 生式左边是什么无所谓。

     

    A–>…UP… 要求的Follow集合的非终结符后跟非终结符

    根据定义,显然P的第一个符号属于Follow(U),也就是First(P)属于Follow(U)。

     

    A–>…UP并且ε属于First(P) 要求的Follow集合的非终结符后跟非结尾的终结符, 并且结尾非终结符的First集合包含空串。

    这是上一种情况的一种特例,除了要按上一种情况处理,First(P)属于Follow(U) 以外还要进行分析;因为当P推导为空串时,空串不能出现在Follow集合中,所以U 后面跟随的应该是P后面的东西,可P已经是结束的符号,此时U后面显然就是A后 面跟随的东西了。所以在这种情况下Follow(A)也属于Follow(U)。

     

    A–>…U 要求的Follow集合的非终结符在产生式结尾

    这时候又要递归推导,U是A的结尾,所以U后面跟随的东西也就是A后面跟随的东 西。所以Follow(A)属于Follow(U)。

     

    注意:Follow集合中的符号一定是终结符,并且不能包括空串ε,而且定义开始符号 的Follow集合初始为{#(句子括号)}。

     

    Select集合:

    Select集合就是产生式左部的可能的推导结果的起始符号。

    Select(A–>B)就是求这个产生式中A可能推导出起始符号集合(不包含空串ε)。

    求Select集合可分如下几种情况:

    A–>X (X为任意文法符号串,不限于非终结符或单个符号),并且X不能推导出空串 ε

    根据定义,显然A推出的符号串起始就是X的起始,也就是First(X).

    Select(A–>X)= First(X)

    A–>X (X为任意文法符号串,不限于非终结符或单个符号),并且X能推导出空串ε

    根据定义,显然First(X)属于Select(A–>X),此外,当X推导为空串时,显然A 也推导为空串,那么此时推导出的符号串就会是A后面的符号的推导结果。也就是 Follow(A),所以,此时Follow(A)也属于Select(A–>X)。

    注意:Select集合中不包括空串ε,但有可能会包含#(句子括号)。

     

    举个例子:

    S→AB

    S→bC

    A→ε

    A→b

    B→ε

    B→aD

    C→AD

    C→b

    D→aS

    D→c

    求他的first,follow,select

    先求First集

    • First(S) =(First(A)-{ε})∪(First (B)-{ε}) ∪{ε}∪{b} ={a,b,ε}

    因为A的first有ε,B的first有ε,S->AB,所以是First(A)-{ε})∪(First (B)-{ε}) ∪{ε},然后S->bC,所以再加一个b,就是First(A)-{ε})∪(First (B)-{ε}) ∪{ε}∪{b},

    • First (A)={b, ε}

    没什么好解释的

    • First (B)={a, ε}

    ε不用解释,就是B->ε,所以有他,a就是因为B->aD,第一个非终结符是a所以有a,那要不要加上D的first呢,就是a和c,答案是不用,就只要aD里面的a就可以

    • First (C)={a,b,c}

    C->AD这一句,AD都是非终结符,所以要找A和D的first集,D的是a,c,A的是b,ε,因为不是AD同时都能推出ε所以C的first是A和D的first的并集减去ε,还要加上b,因为有C->b这一句

    • First (D)={a,c}

    D->c不用解释,D->aS这一句,不用加上S的first!!!

     

    First (AB)={a,b,ε}

    First (bB)={b}

    First (ε)={ε}

    First (b)={b}

    First (aD)={a}

    First (AD)={a,b,c}

    First (aS)={a}

    First (c)={c}

    AB同时能够推出ε,所以first(AB)就是A和B的first的并集减去ε再并上ε

    bB的first就是b,不用加上B的first

    ε的就是ε,b就是b,c就是c,只有一个终结符ε没什么好说的

    一个终结符和一个非终结符的,就要那个终结符就可以,不用管后面那个非终结符,

    两个非终结符的要看是不是他们两个同时能推出ε,能就有ε,要是有一个不能推出ε,那first集就没有ε

    AB有ε是因为AB都能推出ε,AD没有是因为A能D不能推出ε

    以上first集就求完了,是不是很简单,我搞了一上午。。。

     

    接下来求follow集

    从开始符号S开始推倒,开始符号的follow里面一定要有#,

    所以开始符号的S的follow集要有#,

    follow是找->后面的,比如找S的follow,就要看谁的->后面有S,D->aS里面有S,然后在看D->aS的S后面有没有别的符号,没有就加上D的follow集,如果有,就加上后面那个字母的first集里面除了ε以外的符号,在看这个字母能不能推出ε,如果能,就再加上->左边的那个字母的follow

    看A的follow,首先找所有->后面有A的,找到了S->AB,C->AD,先看S->AB,A后面有B,所以要加上B的first集里面除了ε的其他符号,再看B能不能在有限的步骤里推出ε,有B->ε这句,所以能,就要再加上->左边的S的follow集,所以目前的A的follow集里面有a,和follow(S),再看C->AD这一句,A后面有D,所以要加上D的first集里面除了ε的其他的,再看B能不能在有限的步骤里推出ε,D不能,所以不用加->左边的C的follow,所以A的follow就是a,follow(S),a,c,但是如果有重复的,就只要一个,所以最终就是a,c,follow(S),这个follow(S)到后面还要算出来的,不能就这样写

    看B的follow,找所有->后面有B的,找到了S->AB,看B后面有字母吗?没有,就加上->左边的S的follow,所以follow(B)=follow(S)

    看C的follow,找所有->后面有C的,找到了S-bC,看C后面有字母吗?没有,就加上->左边的S的follow集,所以follow(C)=follow(S)

    看D的follow,找所有->后面有D的,找到了B->aD。C->AD,这两句D后面都没有字母,所以加上->左边的B和C的follow,所以follow(D)=follow(B)并上follow(C)

    最终要把以上的follow都求出来,看

    follow(S)=#+follow(D),

    follow(D)=follow(B)+follow(C),

    所以follow(S)=#+follow(B)+follow(C),

    follow(B)=follow(S),

    follow(C)=follow(S)

    所以follow(S)=#+follow(S)+follow(S),

    所以follow(S)就是#,

    follow(B),follow(C),follow(D)也都是#,

    所以follow(A)就是ac,#,求完了,以上所有的+代表求并集

     

    再看select怎么求

    对于A->a,

    如果a≠>ε,那么select(A->a)=first(a),

    如果a=*>,那么select(A->a)就是first(a)-ε+follow(A)

    看select(S->AB),AB都能推出ε,所以select(S->AB)=first(AB)-ε+follow(S)所以结果是a,b,#

    看select(S->bC),bC不能推出ε,所以是first(bC),结果是b

    看select(A->ε),A能推出ε所以是first(ε)-ε+follow(A)结果a,c,#

    看select(A->b),这里的A是推出b不是ε所以是first(b),结果是b

    看select(B->ε),B能推出ε,所以是first(ε)-ε+follow(B),结果是#

    看select(B->aD),这里B不能推出ε,所以是first(aD),结果是a

    看select(C->AD),这里D不能推出ε,所以算AD不能推出ε,就是first(AD),结果是a,b,c

    看select(C->b),C推不出看ε,所以是first(b),结果是b

    看select(D->aS),这里不能推出ε,所以是first(aS),结果是a

    看select(D->c),这里D不能推出ε,所以是first(c),结果是c

    LL(1)文法

    是自顶向下分析,从左到右扫描输入串,最左推导,只需向右看一个符号就可以决定如何推倒

    LL(1)文法满足条件:左部相同的产生式的select集的交集为空,并且产生式的右部不能同时推导出ε,那么这个文法是LL(1)文法,否则不是

    上面的文法select(C->AD)和select(C->b)的交集是b不是空,select(S->AB)和select(S->bC)的交集也是b不是空,所以这不是一个LL(1)文法

    展开全文
  • 编译原理之--FIRST集、FOLLOW集 和 SELECT集

    万次阅读 多人点赞 2016-09-27 21:08:30
    FIRST集、FOLLOW集 和 SELECT集 一、FIRST集 FIRST(A)为A的开始符或者首符号集。 1、定义: 设G=(VT,VN,S,P)是上下文无关文法 ,FIRST(α)={a|α能推导出aβ,a∈VT,α,β∈V*} 特别的,若α能...
    FIRST集、FOLLOW集 和 SELECT集

    一、FIRST集

    FIRST(A)为A的开始符或者首符号集。

    1、定义:

    设G=(V T ,V N ,S,P)是上下文无关文法 ,FIRST(α)={a|α能推导出aβ,a∈VT,α,β∈V*}   
    特别的,若α能推导出ε,则规定ε∈FIRST(α).

    2、根据定义求解FIRST集对每一文法符号X计算FIRST(X)):

    ①. XVT,则FIRST(X){X}(简单讲,终结符的FIRST集就是它本身)


    XVN,且有产生式Xa…,aVT, 则 aFIRST(X)X→ε,则ε∈FIRST(X)。 (简单讲,若是非终结符X,能推导出以终结符a开头的串,那么这个终结符a属于FIRSTX),若X能够推导出空符号串ε,那么空符号串ε也属于XFIRST集)

    ③. XY…是一个产生式且VN  则把FIRST(Y)中的所有非空符号串ε元素都加入到FIRST(X)中。(这个可以理解吧)


    ④.XVNY1Y2,…,YiVN,且有产生式XY1 Y2 … Yn;当Y1 Y2 … Yn-1都能推导出ε时,则FIRST(Y1)FIRST(Y2)、…、FIRST(Yn-1)的所有非空元素和FIRST(Yn) 包含在FIRST(X)中。

    : FIRST(X)=(FIRST(Y1){ε)∪(FIRST(Y2){ε)∪…∪(FIRST(Yn-1){ε})∪{FIRST(Yn)}

    ⑤.(4)中所有Y能够推导出ε,(i=1,2,n),则

    FIRST(X)=(FIRST(Y1){ε})∪(FIRST(Y2)- {ε}∪…∪(FIRST(Yn) {ε})∪{ε}

    反复使用上述步直到每个符号的FIRST集合不再增大为止。


    3、求解示例

    1、文法G [S]为:
      SAB
      SbC
      A→ε
      Ab
      B→ε
    BaD
    CAD
    Cb
    DaS
    Dc

    求每个非终结符的First集?

    解:对于非终结符S,S的开始符有终结符b和非终结符A,根据上面定义②把b加入FIRST(S),由上面的定义③FIRST(A)中的所有非空符号串ε元素都加入到FIRST(S)中,而且因为SAB符合上面的定义④和⑤,所以FIRST(S)=(FIRST(A)-{ε})∪(FIRST(B) -{ε})∪{ε}那么先求FIRST(A)和FIRST(B),A的开始符有终结符b和空符号串ε,由定义①和定义②全部加入FIRST(A),也就是FIRST(A)={ε,b},同理,FIRST(B)={a,ε},这样FIRST(S)也就求出来了,FIRST(S)={b,a,ε},其实回过头来看之所以要反复调用定义②~⑤,是因为开始符中A可能为空字符串ε,所以要考虑A后面的情况。

    再求,FIRST(C),由定义①,把b加入FIRST(C),再由定义④,FIRST(C)=(FIRST(A)-{ε} )∪{FIRST(D)},先求FIRST(D),易知,FIRST(D)={a,c},所以FIRST(C)={b,a,c}


    4、小结

    1、对于终结符而言,FIRST集中的元素只有它本身

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



    二、FOLLOW集

            FOLLOW(A)={a|S能推导出μAβ,且a∈VT, a∈FIRST(β),μ∈ V T * ,β∈V + },若S能推导出μAβ,且β能推导出ε, 则#∈FOLLOW(A)。 也可定义为:FOLLOW(A)={a|S能推导出…Aa…,a ∈VT} ,若有S能推导出…A,则规定#∈FOLLOW(A) ,这里我们用‘#’作为输入串的结束符,或称为句子括号, 
        如:   #输入串#。

    FOLLOW(A)为非终结符A的后跟符号集合。

    1、定义:

    设G=(VT,VN,S,P)是上下文无关文法,A∈VN,S是开始符号  

    需要注意的是,FOLLOW(A)集是针对非终结符A的,集合中的元素是终结符,是A的 全部 后跟符号的集合,当A是文法G的开始符(识别符)时,把‘#也加入其中’


    2、根据定义求解FOLLOW集对每一文法符号SVN 计算FOLLOW(S)):

    ①. 设S为文法中开始符号,把{#}加入FOLLOW(S)中(这里“#”  为句子括号)。

    若A→αBβ是一个产生式,则把FIRST(β)的非空元素加入

      FOLLOW(B)中。如果β能够推导出ε则把FOLLOW(A)也加入FOLLOW(B)中。


    ③.反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。


    3、求解示例

    1、文法G [E]为:
    E   →  TE'
    E'  →  +TE' |  ε
    T   →  FT'
    T'  →  *FT' |  ε
    F  →  (E) | i

    求每个非终结符的FOLLOW集?

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

    FIRST(F)={ (,i }

    FIRST(T’)={ *,ε }

    FIRST(T) ={ (,i }

    FIRST(E’)={ +,ε }

    FIRST(E)={ (,i }
    FOLLOW集的求解:因为E是文法的识别符所以把#加入FOLLOW(E),又由规则 F  →  (E) | i 得E的后跟符号),所以,FOLLOW(E)={ #,) };
    FOLLOW(E’)={ #,) }    ∵E → TE’   ∴FOLLOW(E)加入 FOLLOW(E’)
    FOLLOW(T)={+,),#}      ∵E'→ +TE’  ∴FIRST(E’)-{ε}加入FOLLOW(T);  又E’→ε,     ∴ FOLLOW(E’)加入FOLLOW(T)
    FOLLOW(T’)= FOLLOW(T)= {+,),#}       ∵T → FT’   ∴ FOLLOW(T)加入FOLLOW(T’)
    FOLLOW(F)={*,+,),#}     ∵T → FT’   ∴ FOLLOW(F)=FIRST(T’)-{ε} ;  又T’→ε ∴ FOLLOW(T)加入FOLLOW(F)


    4、小结

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



    三、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]为:
      SAB
      SbC
      A→ε
      Ab
      B→ε
    BaD
    CAD
    Cb
    DaS
    Dc

    求每个产生式的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)={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集的交集不为空。


    4、小结

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


    转载自:http://blog.csdn.net/diaorenxiang/article/details/17127287


    展开全文
  • FirstFollow通俗易懂的讲解加实例First 如A->aB | CD 这里面包含了组成First(A)的两种情况: 以终结符开头,当然要把这个终结符(a)放到A的First里 以非终结符开头,先把C的First放到A的First里再看如果...
  • 编译原理 —— SELECT集

    千次阅读 2019-02-26 11:27:31
    SELECT集 产生式 A→αA → αA→α 的可选集是指可以选用该产生式进行推导的输入符号的集合,记为SELECT(A→α)SELECT(A→α)SELECT(A→α) 同一非终结符的各个产生式的可选集互不相交(否则依然无法确定...
  • FIRST集、FOLLOW集 和 SELECT集一、FIRST集FIRST(A)为A的开始符或者首符号集。1、定义:设G=(VT,VN,S,P)是上下文无关文法 ,FIRST(α)={a|α能推导出aβ,a∈VT,α,β∈V*} 特别的,若α能推导出ε,则规定ε∈...
  • 编译原理LL(1)文法的判断(first集、follow集和select集) 1、问 如何通过给定的文法,判断该文法是否是LL(1)文法? 2、答 求出该文法的first集、follow集和select集,通过select集之间的关系进行判断 3、集合 ...
  • FIRST集、FOLLOW集和SELECT集

    千次阅读 2016-05-25 17:20:45
    First集、Follow集和Select集有要求,所以在网上找到了这篇博客,课本上有几个小的知识点补充一下 (1)X->Y1Y2···Yk并且 Y1Y2···Yk都能-> ε,则FIRST(Yk) ∈FIRST(X) (2)如果A->αBβ,则FIRST...
  • java 编译原理 ll1 文法分析 first follow select 的 求解
  • FIRST集、FOLLOW集 和 SELECT集

    万次阅读 多人点赞 2013-12-04 22:29:36
    FIRST集、FOLLOW集 和 SELECT集 一、FIRST集 FIRST(A)为A的开始符或者首符号集。 1、定义: 设G=(VT,VN,S,P)是上下文无关文法 ,FIRST(α)={a|α能推导出aβ,a∈VT,α,β∈V*} 特别的,若α能推导出ε,则规定...
  • 1.为什么要引入FIRST的概念? 因为有公共左因子的问题,公共左公因子是指在文法的产生式集合中,某个非终结符的多个候选式具有相同的前缀。 一般来说,公共左公因子的产生式为 A→αβ1│αβ2 A→\alpha\beta_1...
  • 那么,为了成功构造出预测分析表,我们需要计算出FIRST集、FOLLOW集以及SELECT集;这三个集合的定义这里不再粘贴(书上有十分专(nan)业(dong)的定义),只写一下如何计算以及我的理解(刚刚了解编译原理,如有不对还...
  • 《编译原理》-用例题理解-自顶向下语法分析及 FIRST,FOLLOW,SELECT集,LL(1)文法 本笔记是对教材《编译原理》-张晶老师版 做学习笔记。 最近在学《编译原理》,前三章感觉还可以理解,到了第四章就感觉这难度就...
  • 一、SELECT集的定义 首先,SELECT集是针对产生式而言的。 我们也可有认为SELECT集是FIRST推广到了串上
  • 根据定义,显然First(X)属于Select(A–>X),此外,当X推导为空串时,显然A 也推导为空串,那么此时推导出的符号串就会是A后面的符号的推导结果。也就是 Follow(A),所以,此时Follow(A)也属于Select(A–>X)...
  • :左部相同的产生式的select集的交集为空,并且产生式的右部不能同时推导出ε,那么这个文法是LL(1)文法 ,否则不是 上面的文法 select(C->AD)和 select(C->b)的交集是b不是空, select(S->AB)和 select(S->bC)...
  • 编译原理实验 first、follow、select集合的求解,经测试正确,c语言编写
  • SELECT集合的计算

    千次阅读 2019-09-29 16:34:47
  • 编译原理-求SELECT集合

    万次阅读 2018-05-04 14:55:04
    为什么要求SELECT集合:前面求解的FIRST集合和FOLLOW集合都是为了回溯的问题。求SELECT集合是一个比较简单的操作,主要是为了给后面求预测分析表提供数据 方法 首先,得会求解FIRST集合和FOLLOW集合(可点击...
  • mysql select 结果循环

    千次阅读 2021-01-18 21:31:01
    drop procedure if exists add_test;CREATE PROCEDURE add_test()BEGINDECLARE _Done INT DEFAULT 0;DECLARE _companyId bigint(20);DECLARE _currentName .../* 声明游标 */DECLARE rs CURSOR FOR select id A...
  • mysql当中update select结果

    千次阅读 2013-07-10 16:41:35
    在oracle,及sql server中,我们... update a set a.xx= (select yy from b) where a.id = b.id ;  但是在mysql中,不能直接使用set select的结果,必须使用inner join:  update a inner join (select yy
  • 提问 select userid,username,price,vol from table_a … select userid,...要让这两句形成一个结果。怎么办? 解答 select userid,username,price,vol from table_a … union all select userid,username,...
  • 一、原理部分 根据清华大学出版社出版的《编译原理》一书。原理如下: 1.计算能推出空的非终结符。 2.计算first集合 (1)求出每个非终结符的...书上的select集合只是给了一个例子: 5.判别LL1文法 书上同样给了一个
  • 如题,我有一个select的结果 我现在想用另一个select来查询该结果 比如 select (select * from a) 这种写法可以么?
  • 循环select查询结果

    千次阅读 2017-04-18 17:18:47
    --标记id --每次查询特定列比标记id大的第一条数据, --同时更新标记id,直到查询结果为空 declare @id varchar(50) ... select top 1 @id=id from T_SGZ where id>@id order by id if @@ROWCOUNT=0

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 602,503
精华内容 241,001
关键字:

select集