精华内容
下载资源
问答
  • 输入任意的上下文无关文法,输出所输入的上下文无关文法一切非终结符的first集合和follow集合 输入任意的上下文无关文法,输出所输入的上下文无关文法一切非终结符的first集合和follow集合
  • 给定文法,构造FIRST集、FOLLOW集的构造的C代码和我个人的实验报告
  • 构造预测分析表 源程序 #include<stdlib.h> #include<stdio.h> #include<string.h> /*/ int count=0; /* 分解的产生式的个数 */ int number; /* 所有终结符和非终结符的总数 */ char start; /* 开始符号 */ char ...
  • FOLLOW集

    千次阅读 2019-10-23 18:12:52
    FOLLOW集 对于一个非中介符号X,FOLLOW(X)表示推导过程中紧跟在X后的非终结符号的集合,举个例子,在推导过程中如果有形如S⇒αXaβ的推导,则非终结符号a∈FOLLOW(X),因为X后面可能会有多个不同的终结符,但是在这...

    FOLLOW集

    对于一个非终结符号X,FOLLOW(X)表示推导过程中紧跟在X后的非终结符号的集合,举个例子,在推导过程中如果有形如S⇒αXaβ的推导,可以得到,非终结符号a∈FOLLOW(X)。因为X后面可能会有多个不同的终结符,但是在这条推导中,我们仅能分析出a∈FOLLOW(X)。

    1.分析

    根据X出现的不同位置,可以分为下面的两种情况

    (1)X是开始符号

    默认开始符号后有一个“界符”——“#或$” ,因此FOLLOW(X)={ # }或{ $ }

    (2)形如S→αXβ

    如果文法中存在上述的产生式,可以看到,使用这条产生式推导,β会跟在X后面,FOLLOW(X)就是X后面跟着得终结符,也就是β可以推导出得非终结符号(除了ε)也就是说,FIRST(β)-{ε}是FOLLOW(X)的子集FOLLOW(X)⊇FIRST(β)-{ε}

    减去{ε}的原因:因为FOLLOW集中跟的是一个终结符号,即使可能存在ε∈FIRST(β),β使用空串产生式进行推导后,X后面仍然会有其他终结符号,而不是ε,这种情况我们在下面讨论,总之,现在先下个结论——FOLLOW集中不会出现ε

    (3)形如S→αX

    如果出现上面的产生式,假设有下面的句型

    …Sw… w为终结符,使用上述产生式进行一步推导...Sw...⇒...αXw,可以看到,在S后面的终结符号出现在了X后面,也就是说FOLLOW(S)是FOLLW(X)的子集FOLLOW(X)⊇FOLLOW(S)

    (4)形如S→αXβ,且ε∈FIRST(β)

    如果,ε∈FIRST(β),则说明β可以推导出空串。如果β使用空串产生式进行推导,那么这样的情况就变成了上面的(3)

    举个例子:

    ...Sw... ⇒ ...αXβw... ⇒ ...αXw...

    可见,如果有形如S→αXβ的产生式,并且ε∈FIRST(β),就变成了情况(3)。同时,ε∈FIRST(β)是情况(2)的特殊情况

    对于情况(4)FOLLOW(X)⊇FIRST(β)-{ε}+FOLLOW(S)

    2.总结

    规则:

    1. 如果S是开始符号,将#或$放入FOLLOW(S)
    2. 如果存在产生式A→αBβ,将FIRST(β)中除了ε的所有元素加入FOLLOW(B)
    3. 如果存在产生式A→αB,或A→αBβ且ε∈FIRST(β),则将FOLLOW(A)加入FOLLOW(B)

    求FOLLOW集:

    假设要求FOLLOW(X),则在文法中找到X在产生式右部的产生式,然后应用上面的三条规则,不断地将子集加入FOLLOW集,知道没有符号可以加入为止。

    举例:

    在这里插入图片描述

    求FOLLOW(E),首先,E是开始符号,将#加入FOLLOW(3);找E出现在右部的产生式,发现只有F→(E) 这里,应用规则2,将FIRST())-{ε}加入FOLLOW(E),也就是将“)”加入FOLLOW(E),没有其他的产生式可以用于分析,所以,FOLLOW(E)的求解完成,综上FOLLOW(E)={#,)}

    求FOLLOW(E’),找出E’在右部的产生式,E→TE'E'→+TE'
    关于产生式E→TE',应用规则3,将FOLLOW(E)加入FOLLOW(E’);
    关于产生式E'→+TE',应用规则3,将FOLLOW(E’)加入FOLLOW(E’)
    综上,FOLLOW(E’)=FOLLOW(E)={#,)}

    求FOLLOW(T),找出T在右部的产生式,E→TE'E'→+TE'
    关于产生式E→TE'既符合规则2,也符合规则3,所以,将FIRST(E’)-{ε}加入FOLLOW(T),将FOLLOW(E)加入FOLLOW(T);
    关于产生式E'→+TE'既符合规则2,也符合规则3,所以,将FIRST(E’)-{ε}加入FOLLOW(T),将FOLLOW(E’)加入FOLLOW(T)。
    FIRST集的求法上一篇博客写过,这里不再赘述,FISRT(E’)={+,ε}
    综上,FOLLOW(T)=FIRST(E’)-{ε}+FOLLOW(E)+FOLLOW(E’)={+,#,)}

    展开全文
  • 编译原理之NULL集、first、follow集C语言实现,实现中句子的转换符号由‘#’代替,数组默认由‘*’作为结束符
  • first集&follow集&select集

    2021-06-08 23:36:44
    first: 一些符号和定义: 文法四元组G=(VT, VN, S, P) VT (vocabulary terminated): 终结符集合 VN(vocabulary not terminated):非终结符集合 S(start):开始符号 P(production):产生式 ε:表示空 #:表示...

    了解递归下降需要一些基础知识,至少了解一些编译原理相关的内容和概念。会计算first集和follow集,select集合,了解LL(1)文法以及消除左递归的知识。
    这里先说明如何求解first集,follow集以及select集

    first集:

    一些符号和定义:
    文法四元组G=(VT, VN, S, P)
    VT (vocabulary terminated): 终结符集合
    VN(vocabulary not terminated):非终结符集合
    S(start):开始符号
    P(production):产生式
    ε:表示空
    #:表示输入结束符,类似EOF
    → ∗ \stackrel{*}{\rightarrow} :表示经过0次至多此推导

    一般大写字母表示非终结符,小写字母表示终结符。
    文法式一套有限的规则,可以创建无限符合此规则的句子。

    first集定义:
    f i r s t ( α ) = { a ∣ α → ∗ a . . . , a ∈ V t } first(\alpha) = \{a|\alpha\stackrel{*}{\rightarrow}a...,a∈V_t\} first(α)={aαa...,aVt}
    注意区分上面的alpha和a,first(α)表示以α开始符号的集合,阿尔法所有可能推导的开头终结符或者式ε.

    例子:

    例子1(后面跟的不是非终结符)

    ...
    A->aB|ε
    A->c
    ...
    First(A)={a,ε,c}
    

    由上,A可以推出非终结符a开头的产生式,或者推出终结符ε,所以first(A)中包含a与ε,此外A可以推导出终结符c,所以First(A)={a,ε,c}。

    例子2.1(后面跟的是非终结符)

    ...
    A->Ba
    B->b
    ...
    First(A)={b}
    

    由上,A得到的产生式中第一个非终结符B可以推导出的终结符为b,所以First(A)={b}

    例子2.2(后面跟的是非终结符)

    ...
    A->Bc
    B->b|ε
    ...
    First(A)={b,c}
    

    接着上面的例子,如果B可以推导出ε,即推出空,那么相当于A可以直接表示为A->c,所以把c也加进来。

    例子2.3(后面跟的是非终结符)

    ...
    A->BC
    B->b|ε
    C->c|ε
    ...
    First(A)={b,c,ε}
    

    上面的例子,A可以推导出如下情况:
    A->b, A->bc, A->c, A->ε
    所以,First(A)={b,c,ε}

    follow集:

    follow集定义:
    f o l l o w ( A ) = { a ∣ S → ∗ . . . A a . . . , a ∈ V t } follow(A) = \{a|S\stackrel{*}{\rightarrow}...Aa...,a∈V_t\} follow(A)={aS...Aa...,aVt}
    其中S表示文法的开始符号,非终结符A后面跟着的终结符或‘#’集合,且式紧挨着A的。

    1. 如果文法的开始符号S,把#加入到follow(S)
    2. 如果A->αBβ是一个产生式,把first(β)\{ε}加入到follow(B)中.(first(β)\{ε}表示把first(β)中去掉ε)
    3. 如果A->αB是一个产生式,或A->αBβ是一个产生式且β->ε,则把follow(A)加入到follow(B)中。

    开始符号S,先将#放入follow集合中;
    注意,A->αBβ,α可以式终结符也可以为非终结符也可以为空,β可以为终结符或者非终结符,但是不能为空且,且B后面要有符号;

    如:

    ...
    A->aBC
    A->aBd
    A->BC
    A->Bd
    A->B // 这是错误的,B后面要有符号
    ...
    First(A)={b,c,ε}
    

    如果,A->αB为一个产生式,或者A->αBβ是一个产生式,且β->ε,则把follow(A)加入到follow(B)中;
    如:

    ----------------------
    // 对于A->αB
    A->B  // α为空
    A->cB // α推出c
    A->CB // α推出非终结符C 
    ----------------------
    // 对于 A->αBβ
    A->dBC // 这是错误的,B后面要有符号
    C->ε // 要求C必须推出ε,即A可以表示为A->dB
    

    以上将follow(A)加入到follow(B)中

    例子1:

    终结符:if, b, ohter, else, then

    G(S): S->I E T S P | O
    I->if
    E->b
    O->other
    L->else
    T->then
    P->LS | ε
    

    由上,非终极符得到的first集如下:

    first(S) = {if, other}
    first(I) = {if}
    first(E) = {b}
    first(O) = {other}
    first(L) = {else}
    first(P) = {else, ε}
    

    对应的follow集合:

    // S是开始符,所以将#加入到集合中. 根据follow集的定义,找到产生式G(S): S->I E T S P | O 中的 S的
    // 所在位置为 G(S): S->I E T S P | O  (这里S就是定义里面的A)
    //                         ^
    // S后面存在P,根据规则2,将first(P)\{ε}加入到follow(B)中
    // 此外,有p->ε,看规则3表述为A->αBβ,且β->ε,要把follow(A)加入到follow(B),但是在
    // 这里变成将follow(S)加入到follow(S)当中,定义中的A和B是两个符号,所以此处不做操作。
    follow(S) = {#, else}
    // I后面是E,把E的first集加入到follow(I)
    follow(I) = {b}
    // E后面是T,将first(T)加入到follow(E)
    follow(E) = {then}
    // O后面没有符号,根据规则3,将follow(S)加入到follow(O)中
    follow(O) = {else, #}
    // L后面是S,将S的first集加入到follow(L)中
    follow(L) = {if, other}
    // 同O,P后面没有符号,将follow(S)加入到follow(P)
    follow(P) = {else, #}
    

    例子2:

    G(E):E->TE'
    E'->+TE' | ε
    T->FT'
    T'->*FT' | ε
    F->(E) | i
    

    对应的first集合:

    first(E) = {i, (}
    first(T) = {i, (}
    first(E') = {+, ε}
    first(T') = {*, ε}
    first(F) = {(, i}
    

    对应的follow 集合:

    follow(E) = {#, )} // E作为开始符,且在F->(E) | i 产生式中,E后存在 ) 符号
    follow(E') = {#, )} // 根据规则 A->αB,则E->TE'follow(E)加入到follow(E')
    follow(T) = {+, #, )} // 有E->TE',根据A->αBβ规则,有α为空,E'->ε,此时将follow(E)加入follow(T),根据E'->+TE' | ε将first(+)\{ε}加入follow(T)
    follow(T') = {+, #, )} // T->FT'follow(T)加入
    follow(F) = {(*,+,#,)} // T->FT',根据A->αBβ,α为空,T'->ε,将follow(T)加入;T'->*FT' | ε,根据A->αBβ,将first(T') / {ε} 加入
    

    first集和follow集的意义:
    为什么要有这两个集合?含义式什么?

    代码的逻辑时自左向右写的,因此需要从左向右处理用户代码逻辑,即语法分析过程要先处理最左部分的源码。
    但是产生式右侧的最左符号可能是终结符,也可能是非终结符,如果是非终结符,可能会出现无限的递归情况,如:
    P->Pa,那么得到Paaaaa…
    上面在推导的过程中会产生死循环,这种递归方式也叫做左递归,所以要消除左递归。
    提取左公因式时,各个候选是有公共前缀,需要将公共前缀消除,所以需要找出候选式所有相同的首字符。

    此外,有些非终结符可以推导为空,那么该非终结符后面的字符就成为了首部,因此需要follow集,其实也就是非终结符后面所有可能出现的终结符或结束符。(可以看看上面几个例子,是不是这样的情况)

    select集

    select集定义:
    select(A->α)表示可以使用产生式A->α得到的起始符号的集合。
    计算规则如下:
    如果 ε ∉ f i r s t ( α ) ε\notin first(α) ε/first(α) 那么 s e l e c t ( A − > α ) = f i r s t ( α ) select(A->α) = first(α) select(A>α)=first(α)
    如果 ε ∈ f i r s t ( α ) ε∈first(α) εfirst(α) 那么 s e l e c t ( A − > α ) = f i r s t ( α ) \ { ε } ∪ f o l l o w ( A ) select(A->α) = first(α)\backslash\{ε\}∪follow(A) select(A>α)=first(α)\{ε}follow(A)

    例子:

    G(E):E->TE'
    E'->+TE' | ε
    T->FT'
    T'->*FT' | ε
    F->(E) | i
    

    上面已经计算过这个例子的first和follow集

    那么每个产生式对应的select集为:

    select(E->TE') = {i, (} // T无法推出ε,所以取first(T)
    select(E'->+TE') = {+} // 直接取first(+)
    select(E'->ε) = {#, )} // 注意候选式要分开计算,因为是ε所以取follow(E')
    select(T) = {(,i} // first(F)
    select(T'->*FT') = {*} // first(*)
    select(T'->ε) = {+, #, )} // follow(T')
    select(F->(E)) = {(} // first(()
    select(F->i) = {i} // first(i)
    

    比较简单

    select集的意义:

    给定输入的表达式字符串需要根据表达式的字符串中的字符用来寻找正确的产生式,即输入的表达式字串中的字符作为key,产生式作为value,那么这个select集就是构造的map

    展开全文
  • 题目:First集和Follow集生成算法模拟 【问题描述】 设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。(算法参见教材) 【基本要求】 动态模拟算法的基本功能是: (1) 输入一个文法G; (2) ...
  • 编译原理用C语言求first集sellect集follow集,最后,判断给出的文法是否是LL(1)文
  • 如何求First集与Follow集(超详细)

    千次阅读 多人点赞 2020-12-23 18:16:37
    如何求First集与Follow集 已知文法如下,求First集与Follow集 G[E]:E→TE′E′→+TE′∣εT→FT′T′→∗FT′∣εF→(E)∣i G[E]: E{\rightarrow} TE' \\ {\quad\quad\quad\quad\quad}E'{\rightarrow}+TE'|\var...

    如何求First集与Follow集

    已知文法如下,求First集与Follow集
    G [ E ] : E → T E ′ E ′ → + T E ′ ∣ ε T → F T ′ T ′ → ∗ F T ′ ∣ ε F → ( E ) ∣ i G[E]: E{\rightarrow} TE' \\ {\quad\quad\quad\quad\quad}E'{\rightarrow}+TE'|\varepsilon \\ {\quad\quad\quad}T{\rightarrow}FT'\\ {\quad\quad\quad\quad\quad}T'{\rightarrow}*FT'|\varepsilon\\ {\quad\quad\quad}F{\rightarrow}(E)|i\\ G[E]:ETEE+TEεTFTTFTεF(E)i

    First集:

    1. 第一次查看所有式子

    2. 首先看第一个式子: E → T E ′ E{\rightarrow} TE' ETE,候选式中未包含终结符,暂时无法得出结果

      当前First集:

      First(E) = { }
      First(E ′ ' ) = { }
      First(T) = { }
      First(T ′ ' ) = { }
      First(F) = { }

    3. 第二个式子: E ′ → + T E ′ ∣ ε E'{\rightarrow}+TE'|\varepsilon E+TEε,可以得到其所有候选式的串首终结符: +、 ε {\varepsilon} ε,将其加入到First(E ′ ' )中

      当前First集:

      First(E) = { }
      First(E ′ ' ) = {+, ε {\varepsilon} ε}
      First(T) = { }
      First(T ′ ' ) = { }
      First(F) = { }

    4. 第三个式子同 1,First集无变化

    5. 第四个式子同 2,将 *、 ε {\varepsilon} ε加入到First(T ′ ' )中

      当前First集:

      First(E) = { }
      First(E ′ ' ) = {+, ε {\varepsilon} ε}
      First(T) = { }
      First(T ′ ' ) = { *, ε {\varepsilon} ε}
      First(F) = { }

    6. 第五个式子: F → ( E ) ∣ i F{\rightarrow}(E)|i F(E)i,将 (、i 加入到First(F)中

      当前First集:

      First(E) = { }
      First(E ′ ' ) = {+, ε {\varepsilon} ε}
      First(T) = { }
      First(T ′ ' ) = { *, ε {\varepsilon} ε}
      First(F) = { (,i}

    7. 第二次查看所有式子

    8. 第一个式子可得,First(T) 是First(E) ,但First(T)是空的,故无变化

      [注:参照书本58页第三行②,若有 X → Y X{\rightarrow}Y XY, Y Y Y是非终结符,就把First(Y)中非 ε {\varepsilon} ε元素加入到First(X)中]

    9. 第二个式子不能得到新的结果,下一步

    10. 第三个式子可得,First(F)是First(T),故将 ( ,i 加入到First(T)
      当前First集:

      First(E) = { }
      First(E ′ ' ) = {+, ε {\varepsilon} ε}
      First(T) = { (,i }
      First(T ′ ' ) = { *, ε {\varepsilon} ε}
      First(F) = { (,i }

    11. 后续式子均不能得到新的结果,下一步

    12. 第三次查看所有式子

    13. 第一个式子得,First(T) 是First(E),故First集产生变化

      当前First集:

      First(E) = {(,i }
      First(E ′ ' ) = {+, ε {\varepsilon} ε}
      First(T) = { (,i }
      First(T ′ ' ) = { *, ε {\varepsilon} ε}
      First(F) = { (,i }

    14. 后续式子均无法得到新的结果,求First集完毕

    15. 注:理论上每次First集产生变化就要重新查看一遍所有式子,这里为了方便进行了简写,实际做题时可以按照变化一次重新求一次

    Follow集:

    求Follow集是在已经求出First集的基础上进行

    1. 将#置入Follow(文法开始符号),即Follow(E)

      当前Follow集:

      Follow(E) = { # }
      Follow(E ′ ' ) = { }
      Follow(T) = { }
      Follow(T ′ ' ) = { }
      Follow(F) = { }

    2. 第一次查看所有式子

    3. E → T E ′ E{\rightarrow} TE' ETE可得

      • Follow(E)可以加入到Follow(E ′ ' ),将 # 置入Follow(E ′ ' )

      • Follow(E)可以加入到Follow(T),将 # 置入Follow(T)

        [注:因为E ′ ' 可能为 ε {\varepsilon} ε],

      • First(E ′ ' )中非 ε {\varepsilon} ε元素可以加入到Follow(T)中,将 + 置入Follow(T)

        当前Follow集:

        Follow(E) = { # }
        Follow(E ′ ' ) = { # }
        Follow(T) = { #,+ }
        Follow(T ′ ' ) = { }
        Follow(F) = { }

    4. E ′ → + T E ′ ∣ ε E'{\rightarrow}+TE'|\varepsilon E+TEε 可得

      • Follow(E ′ ' )可以加入到Follow(T),无变化
    5. T → F T ′ T{\rightarrow}FT' TFT可得

      • Follow(T)可以加入到Follow(T ′ ' ),将 #、+ 置入Follow(T ′ ' )

      • Follow(T)可以加入到Follow(F),将 #、+ 置入Follow(F)

      • First(T ′ ' )中非 ε {\varepsilon} ε元素可以加入到Follow(F)中,将 * 置入Follow(F)

        当前Follow集:

        Follow(E) = { # }
        Follow(E ′ ' ) = { # }
        Follow(T) = { #,+ }
        Follow(T ′ ' ) = { #,+ }
        Follow(F) = {#,+ ,* }

    6. T ′ → ∗ F T ′ ∣ ε T'{\rightarrow}*FT'|\varepsilon TFTε 可得

    • Follow(T ′ ' )可以加入到Follow(F),无变化
    1. F → ( E ) ∣ i F{\rightarrow}(E)|i F(E)i 可得

      • 非终结符E后有一个终结符 ),故将 ) 置入Follow(E)

        当前Follow集:

        Follow(E) = { #,) }
        Follow(E ′ ' ) = { # }
        Follow(T) = { #,+ }
        Follow(T ′ ' ) = { #,+ }
        Follow(F) = {#,+ ,* }

    2. 第二次查看所有式子

    3. E → T E ′ E{\rightarrow} TE' ETE可得

      • Follow(E)可以加入到Follow(E ′ ' ),将 ) 置入Follow(E ′ ' )

      • Follow(E)可以加入到Follow(T),将 ) 置入Follow(T)

      • First(E ′ ' )中非 ε {\varepsilon} ε元素可以加入到Follow(T)中,已有+,Follow(T)无变化

        当前Follow集:

        Follow(E) = { #,) }
        Follow(E ′ ' ) = { # ,) }
        Follow(T) = { #,+ ,) }
        Follow(T ′ ' ) = { #,+ }
        Follow(F) = {#,+ ,* }

    4. E ′ → + T E ′ ∣ ε E'{\rightarrow}+TE'|\varepsilon E+TEε 可得

    • Follow(E ′ ' )可以加入到Follow(T),无变化
    1. T → F T ′ T{\rightarrow}FT' TFT可以得到
    • Follow(T)可以加入到Follow(T ′ ' ),将 ) 置入Follow(T ′ ' )

    • Follow(T)可以加入到Follow(F),将 )置入Follow(F)

    • First(T ′ ' )中非 ε {\varepsilon} ε元素可以加入到Follow(F)中,已有*,Follow(F)无变化

      当前Follow集:

      Follow(E) = { #,) }
      Follow(E ′ ' ) = { # ,) }
      Follow(T) = { #,+ ,) }
      Follow(T ′ ' ) = { #,+,) }
      Follow(F) = {#,+ ,*,) }

    1. T ′ → ∗ F T ′ ∣ ε T'{\rightarrow}*FT'|\varepsilon TFTε 可得
    • Follow(T ′ ' )可以加入到Follow(F),无变化
    1. F → ( E ) ∣ i F{\rightarrow}(E)|i F(E)i 并不能得到新的结果
    2. 再次查看所有式子,均不能产生新的变化,求Follow集完毕
    3. 注:理论上每次Follow集产生变化就要重新查看一遍所有式子,这里为了方便进行了简写,实际做题时可以按照变化一次重新求一次

    那么在已知First集和Follow集的情况下如何构造LL1分析表呢

    First集与Follow集:

    First(E) = {(,i }
    First(E ′ ' ) = {+, ε {\varepsilon} ε}
    First(T) = { (,i }
    First(T ′ ' ) = { *, ε {\varepsilon} ε}
    First(F) = { (,i }

    Follow(E) = { #,) }
    Follow(E ′ ' ) = { # ,) }
    Follow(T) = { #,+ ,) }
    Follow(T ′ ' ) = { #,+,) }
    Follow(F) = {#,+ ,*,) }

    LL1分析表:

    第一列为非终结符,第一行为终结符

    i+*(#
    EE遇到 i,i ϵ { \epsilon} ϵ First(E),且E只有一个候选式,填入 E → T E ′ E{\rightarrow} TE' ETEE遇到(,( ϵ { \epsilon} ϵ First(E),且E只有一个候选式,填入 E → T E ′ E{\rightarrow} TE' ETE
    E’+ ϵ { \epsilon} ϵ First(E ′ ' ),在E’的候选式中选择+开头的, 填入 E ′ → + T E ′ E'{\rightarrow}+TE' E+TEFirst(E ′ ' )中含有 ε {\varepsilon} ε,故E’遇到Follow(E ′ ' )中的终结符时均填入 E ′ → ε E'{\rightarrow} {\varepsilon} Eε E ′ → ε E'{\rightarrow} {\varepsilon} Eε
    T T → F T ′ T{\rightarrow}FT' TFT T → F T ′ T{\rightarrow}FT' TFT
    T’ T ′ → ε T'{\rightarrow} {\varepsilon} Tε T ′ → ∗ F T ′ T'{\rightarrow}*FT' TFT T ′ → ε T'{\rightarrow} {\varepsilon} Tε T ′ → ε T'{\rightarrow} {\varepsilon} Tε
    F F → i F{\rightarrow}i Fi F → ( E ) F{\rightarrow}(E) F(E)

    注:大写字母表示非终结符,小写字母与符号表示终结符

    总结:

    1. 当非终结符遇到其First集中的终结符时填入相应候选式
    2. 当非终结符的First集中含有 ε {\varepsilon} ε 元素时,遇到其Follow集中的终结符时填入 非终结符 → ε {\rightarrow} {\varepsilon} ε

    如有错误欢迎指正

    展开全文
  • ( 编译原理JAVA求First集Follow集
  • 博文链接:https://zpchen.iteye.com/blog/208947
  • 简单的FIRST集FOLLOW集求解的程序。。。。压缩文档中ffs.cpp为源程序。。。。使用了bool。。。。所以做了cpp。。。。Production文本是供程序使用的产生式。。。。其余的是过程文件。。。。可以忽略。。。。
  • . . . . .下载可编辑. 构造预测分析表 源程序 #include<stdlib.h> #include<stdio.h> #include<string.h> /*/ int count=0; /*分解的产生式的个数*/ int number; /*所有终结符和非终结符的总数*/ char start;...
  • /L(1)文法(源代码) ilud sh inlude stib #dein aRuleNum 8 #fine VNu defne MaxVNum 5 eine aStackepth 20 #efi xLn 20 defie MaxSLngt struct Node 产生式右部结构*/ nt rCro;... ; struc pNe { int lCurs;...
  • 接下来求follow集 从开始符号S开始推倒,开始符号的follow里面一定要有#, 所以开始符号的S的follow集要有#, follow是找->后面的,比如找S的follow,就要看谁的->后面有S,D->aS里面有S,然后在看D->aS的S后面有...

    所有大写字母代表非终结符,小写字母代表终结符,省略号代表未知数目(可能为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)文法

     


     

    原文地址:

    https://blog.csdn.net/u014374031/article/details/50239667

    https://blog.csdn.net/luobida222/article/details/73542851

    展开全文
  • 编译原理之first集,follow集,select集解析

    万次阅读 多人点赞 2018-04-30 19:30:32
    为了方便自顶向下语法分析,需要求文法对应的first集,follow集,以及select集。本文主要分为两部分,一个是求法解析,还有一个例子详解:第一部分是求法解析将对first集,follow集,select集分为三种讲解方法①定义...
  • PAGE / NUMPAGES 构造预测分析表 源程序 #include<stdlib.h> #include<stdio.h> #include<string.h> /*/ int count=0; /*分解的产生式的个数*/ int number; /*所有终结符和非终结符的总数*/ char start;...
  • 编译原理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集~~有兴趣的可以看一下,有漏了一个条件,不过注明出来了~~
  • 编译原理之first集 & follow集 & select集 详解

    千次阅读 多人点赞 2020-04-12 01:37:38
    编译原理之first集 & follow集 & select集 详解 一、first集,follow集,以及select集求法解析 二、例子详解 1、关于first集: 2、关于follow集: 3、关于select集: 叮嘟!这里是小啊呜的学习课程资料整理。好记性...
  • 编译原理:求First集和Follow集

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

    千次阅读 多人点赞 2019-12-06 20:39:54
    First算法描述 1.若X->a…,则将终结符a放入First(X)中 2.若X->ε,则将ε放入First(X)中 3.若有X->Y1Y2Y3…Yk,则 (1)把First(Y1)去掉 ε后加入First(X) (2)如果First(Y1)包含ε,则...
  • FIRST 的定义 简单的说 FIRST 就是一个文法符号串的开始符号集合 设 G=(VT,VN,S,P)是上下文无关文法, FIRST(α)={a|α=>aβ,a∈VT,α,β∈v*} 若 α=> ε(经过0或多步推导可以推出为空串),则...
  • 对文法中的非终结符,求first集和follow集
  • 计算first集和follow集

    2012-06-04 19:53:51
    编译实验中求一文法的first集和follow集
  • C++实现first集follow集

    千次阅读 2019-11-10 18:54:38
    //follow集 //将文件中的文法转换成产生式 void fun1(string str){ exp e; e.ter = str[0]; int i = 3; for(int k = i;k ();k++){ if(str[k] == '|'){ e.nonter.push_back(str.substr(i,k-i)); i = ...
  • 一、FIRST FIRST(A)为A的开始符或者首符号。 1、定义: 设G=(VT,VN,S,P)是上下文无关文法 ,FIRST(α)={a|α能推导出aβ,a∈VT,α,β∈V*} 特别的,若α能推导出ε,则规定ε∈FIRST(α). 2、根据定义求解...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,202
精华内容 11,280
关键字:

follow集