请教有关follow集

kallytin

以下为一LL文法,

program -> stmt_list $$
stmt_list -> stmt stmt_list
stmt_list -> 空串
stmt -> id := expr
stmt -> read id
stmt -> write expr
expr -> term term_tail
term_tail -> add_op term term_tail
term_tail -> 空串
term -> factor factor_tail
factor_tail -> mult_op factor factor_tail
factor_tail -> 空串
factor -> ( expr )
factor -> id
factor -> number
add_op -> +
add_op -> -
mult_op -> *
mult_op -> /

========
first集
========
program         {id ,read, write, $$}
stmt_list         {id, read, write, 空串}
stmt                {id, read, write}
expr                {(, id, number}
term_tail         { +, - , 空串}
term                {(, id, number}
factor_tail        {*, / , 空串}
factor                {(, id, number}
add_op                {+, -}
mult_op                {*, /}

=========
follow集
=========
id                {+,-,*,/,),:=,id,read,write,$$}
number                {+,-,*,/,),id,read,write,$$}
read                {id}
write                {(,id,number}
(                {(,id,number}
)                {+,-,*,/,),id,read,write,$$}
:=                {(,id,number}
+                {(,id,number}
-                {(,id,number}
*                {(,id,number}
/                {(,id,number}
$$                {空串}
program                {空串}
stmt_list        {$$}
stmt                {id, read, write, $$}
expr                {),id,read,write, $$}
term_tail        {),id,read,write, $$}
term                {+,-,),id,read,write,$$}
factor_tail        {+,-,),id,read,write,$$}
factor                {+,-,*,/,),id,read,write,$$}
add_op                {(,id,number}
mult_op                {(,id,number}

1、对于"first集",我认为如下:

1）如果是非终结符，如stmt，则first(stmt)为其右边产生式的第一个终结符的

集合，即如下：
        first(stmt) = {id,read,write}

2) 如果是终结符，如id，则first(id)为该终结符本身，即first(id) = id

3）如果为空串，则为空串本身，即 first(空串) = 空串

问题：

1）我的理解对吗？

2）对于 first(program)所得的集合中 $$ 是怎么得来的？不明白...



2、对于“follow集”

问题：

1）对于follow集，我是不太明白。请以 follow(id)为例讲解一下，谢谢。

kallytin

回复 1# kallytin


顶一下

idv935

第一次回帖  有点儿激动 ！！
    进入正题： 个人认为对first集和follow集含义的理解应该从如何自顶向下的分析LL（1）文法来考虑。不能单纯的只是看first集和follow集的定义。那样子很难理解为什么会要这样的概念。
一  关于first集合
    1：为什么要引入first集合的概念？     在对LL(1)文法进行自顶向下分析时，面对一个输入符号，该选择哪个产生式？ 看下面的例子。
            约定：大写字母为非终结符，小写字母为终结符 S为开始状态
                   文法:S->aBc           （1）
                           S->dEf           （2）
                           B->G             （3）
                           B->H              （4）
                           B->k               (5)
                           G->i               （6）
                           H->j                (7)
                           E->空串        (
        假定一个输入字符串ai
        当前输入为a，那么应该选择S的那个产生式进行推导呢？很明显是产生式（1）。因为有且仅有产生式（1）的右部分会出现a。注意是产生式（1）的右部分。
        现在的推导为S=>aBc。a得到匹配，下一个输入为i。那么下面要对B进行推导。那么产生式（3）和（4）选择哪一个呢？关键是看那个产生式可能推导出以i开头的字符串。也就是看产生式（3）和产生式（4）那个的右部分能够推导出以i开头的字符串。很明显产生式（3）的右部分为G，G能够推导出i。所以应该选择产生式（3）。得到推导S=>aBc=>aGc。这里大概就可以看清楚为什么要引入first集了。就是在当前输入的条件下，看那个产生式的右部分可能推导出当前输入开头的字符串。由此来决定采用那个产生式来进行推导。也就理清了first集的对象，也就是说谁有first集。应该是产生式的右部分的first集。而产生式的右部分是什么？不是单纯的终结符，也不是单纯的非终结符，而是文法符号串。也就是说是某个文法符号串的first集。这个文法符号串可以是任意的终结符和非终结符的组合（当然也包括空串）。而文法符号串的first集就是从文法符号串可能推出的第一个终结符的集合
      
     现在可以回答你关于first集的理解。
    1）如果是非终结符，如stmt，则first(stmt)为其右边产生式的第一个终结符的集合，即如下：
        first(stmt) = {id,read,write}
        非终结符也是文法符号串的一种，假如现在某个产生式的右部分就是stmt,那么由stmt可以推导出所有可能的第一个终结符是什么呢？在这个例子中当然就是id,read,write。但并不是其右边产生式的第一个终结符的集合。
     观察本例中的文法，非终结符B的fisrt集是什么呢？
     观察产生式（3） B->G ,由于产生式（6）   G->i ，所以从非终结符B可能推导出i.....这样的字符串，所以i应该在first(B)中，也就是说所有G可能推导出的第一个终结符B都可能推导出，这也就是为什么first(G)包含于first(B)。
     观察产生式（4） B->H ， 由于产生式（7） H->j，所以从非终结符B可能推导出j.....这样的字符串，所以j应该在first(B)中，同样的first（H） 包含于first（B）。
     由于产生式     B->k               (5)，所以从非终结符B可能推导出k....这样的字符串，所以k应该在first(B)中。这样fisrt（B）={i,j,k};
       2) 如果是终结符，如id，则first(id)为该终结符本身，即first(id) = id
            是这样的。因为当非终结符出现在产生式右部分的时候，它只可能推导出以它本身开头的字符串。在本例的文法中，观察产生式 G->i   （6） 。i出现在产生式右部分，那么i只能推导出以它本身为开头的字符串。
    3）如果为空串，则为空串本身，即 first(空串) = {空串}
        按照first集的定义（first集的定义中有一个额外的规定），是这样的。至于为什么引入空串的first集和first集中包含空串，要到理解follow的引入时阐述。
    4）对于 first(program)所得的集合中 $$ 是怎么得来的？不明白...
             program -> stmt_list $$
             stmt_list -> 空串
         根据这两条产生式。当从终结符stmt_list 推导出空串时，program推导出$$，所以....
    今天先写到这里  下班了  改天有空再写下面的  其实这个概念的理解好好看看编译原理的书就可以的

idv935

(第一次回帖就被加了十分 小骄傲一下 哈哈)
二 关于follow集
       1 follow集概念的引入
       还是上面的文法。假如现在的输入为df。从开始符号S进行推导。
       第一步应该选择产生式（2）S->dEf     进行推导，因为当前输入为d ，d包含于first(dEf)。S=>dEf 。当前输入d得到匹配。
        现在当前输入为f，待扩展的终结符为E。而文法中关于E的产生式只有E->空串        （8）。很明显f和E的推导不匹配。那么现在是不是就说df不是文法的合法字符串呢？不是，因为如果对E用空串进行扩展之后，E后面如果能够紧跟一个f的话，依然可以进行匹配。这里就要引入follow集的概念了。一个非终结符A的follow集就是所有句型中出现在紧跟A之后的终结符或“#”（这里包含是因为总是用“#”来标识输入字符串的结束，最后用来判断语法分析过程是否结束）。也就是说只有非终结符的follow集才有意义。放在这里，E的follow集也就是所有句型中出现在紧跟E之后的终结符或“#”。如果f在follow（E）中，那么采用     E->空串   进行推导之后，f还是有可能得到匹配的。如果f不在follow（E)中，那么即使采用    E->空串   进行推导，下面f也不可能得到匹配。
         总结一下，follow集引入是因为当前输入不在当前待扩展的非终结符的first集中（本例中f不在first（E)中，first（E）为只有一个元素（即空串）的集合）， 而当前待扩展的非终结符的first集可能推导出空串，这个时候如果当前输入在待扩展的非终结符的follow集中(本例中即f在follow(E)中)，那么依然可以进行扩展，因为下面还是有可能匹配的。
         语言组织和表达能力不好，还请原谅。
         下面回答你关于follow集的问题。
         2、对于“follow集”

问题：

1）对于follow集，我是不太明白。请以 follow(id)为例讲解一下，谢谢。
          很明显，终结符的follow集是没有意义的。这点从follow集的引入原因就可以看出。
          本例中，follow（B）={c},因为所有句型中，紧跟在B之后的只有c。
          本例中的这个文法比较简单，反映不出通用的求非终结符follow集的算法。如果想更具体的了解follow集的求法，找一本编译原理教材好好看看。
         

idv935

新手回帖，有啥不对的地方还请批评指正

kallytin

(第一次回帖就被加了十分 小骄傲一下 哈哈)
二 关于follow集
       1 follow集概念的引入
       还是上 ...
idv935 发表于 2010-10-13 10:00

idv935，谢谢你的回复。

（一）根据你的回复，我也重新再理解了一遍first集和follow集。以下是我对follow（id）的理解：

1、follow(id)

1、对于 stmt -> id := expr
        follow(id)         = { := }


2、对于 stmt -> read id
        follow(id)         = { follow(stmt) }
                        = { first(stmt_list) }
                        = { first(stmt), first(空串) }
                       
1)        因为 stmt -> id := expr， stmt -> read id， stmt -> write expr， 所以
        first(stmt) = { id, read, write }
       
2)        因为是求id的follow集，所以
        first(空串)        = follow(stmt_list)
                        = { $$ }

3)        结合1）和 2），可得
        follow(id)         = { id, read, write ,$$}


3、对于 factor -> id
        follow(id)        = { follow(factor) }
                        = { first(factor_tail) }
                        = { first(mult_op), first(空串) }
                       
1)        first(mult_op)         = { *, / }

2)        first(空串)        = { follow(factor_tail) }
                        = { follow(term) }
                        = { first(term_tail) }  //根据 expr -> term term_tail
                        = { first(add_op), first(空串）}

3)        first(add_op)        = { +, - }

4)        first(空串)        = { follow(term_tail) }
                        = { follow(expr) }        //根据 expr -> term term_tail

5)        follow(expr)= { ), follow(stmt) }        //根据 factor -> ( expr )，stmt -> id := expr， stmt -> write expr

6)        follow(stmt)= { first(stmt_list) }        //根据 stmt_list -> stmt stmt_list
                        = { id, read,write ,$$} //根据 第2点

结合1）～6），可知，
        follow(id)        = { *,/, +, -, ), id, read,write ,$$ }


4、结合 第1点 ～ 第3点，可知
        follow(id)         = { :=, *,/, +, -, ), id, read,write ,$$ }//注，第二点与第三点有重合（{ id, read,write ,$$}）



2、问题
   第1点中对 follow(id) 的推导对吗？





（二）有关first集的疑惑。
       
1、        在求first集时，
1)        first(program)        = { first(stmt_list) }
                                = { first(stmt), first(空串) }
                                = { id, read, write, follow(stmt_list) }
                                = { id, read, write, $$ }

2)        first(stmt_list)        = { first(stmt), first(空串) }         // 这里是单独的求非终结符stmt_list的first集
                                = { id, read, write, 空串 }

2、问题：
1）上面 第1点中 的 1）和2）的推导有问题吗？

2）如果没问题，那对于同样的 first(stmt_list）为何会有2个不同的结果？（即为何 2个first(空串）不一样？）
你曾经提到因为stmt_list推导出空串，所以first(program)的最后结果为{ id, read, write, $$ }。但为何不是{ id, read, write, 空串, $$ }或是什么其他结果呢？我的意思是它的推导过程该是怎样的？怎样才能推导出{ id, read, write, $$ }？而不是用肉眼看到的.....

idv935

回复 6# kallytin 你很认真呀  哈哈  期待和你一起交流进步 ！！！  
一：关于follow集
      1 从follow集的引入来说，只有非终结符的follow集才有意义，非终结符的follow集没有意义。而id在问法分析中一般是作为非终结符的。所以follow(id)在文法分析的过程中没有意义。
      2 如果把id当作非终结符，那么你对follow（id）的求解是正确的。
      3 求解非终结符的follow集容易出错，因为它是不断应用求非终结符的三个规则，直到没有新的非终结符可以被加入到任意follow集中为止。所以一般不宜求解单个非终结符的follow集，要求解就求解整个文法中所有非终结符的follow集。（这里指手工实现）
       看龙书上求解非终结符的一段描述(有些希腊字母打不出来，用小写字母代替了，代表文法符号串)
       “计算所有非终结符A的FOLLOW(A)集合时，不断应用下面的规则，直到再没有新的终结符号可以被加入到任意FOLLOW集合中为止。
        1）将$放到FOLLOW(S)中，其中S是开始符号，而$是输入右端的结束标记。
        2）如果存在一个产生式A->aBc,那么FIRST(c)中除空串之外的所有符号都在FOLLOW(B)中。
        3）如果存在一个产生式A->aB，或者存在产生式A->aBc且FIRST(c)包含空串，那么FOLLOW(A)中的所有符号都在FOLLOW(B)中。”
        这些规则是计算所有非终结符A的FOLLOW(A)集合。因为规则3）的存在,使得一个非终结符的FOLLOW集影响别的非终结符的FOLLOW集。假如现在应用规则的时候FOLLOW(A)中只有一个元素，所以将FOLLOW(A)中元素加入到FOLLOW(B)中时也只加入一个元素。检查了几条文法规则之后，FOLLOW(A)是会变的，而这些变动怎么才能反映到FOLLOW(B)中呢？这就要求“不断应用下面的规则，直到再没有新的终结符号可以被加入到任意FOLLOW集合中为止”。
         从上面的描述可以看出手工求解FOLLOW集非常容易出错，我也没有在算法上实现过如何求解FOLLOW集。不过看过一个类似的算法，也是求解一个集合，而且规则和求解FOLLOW(A)相似，应该是用一个STACK来实现求解FOLLOW集。你感兴趣的话可以继续上网找找看，应该不难的。

idv935

回复 6# kallytin
二 关于first集
       推导中有错误。第一行包含错误。
       下面是first(program)的求解过程。
       1）看产生式program->stmt_list $$。求first(program)需要先求解first(stmt_list)。因为stmt_list是非终结符，有可能推出空串。
       2）看下面两个产生式
       stmt_list -> stmt stmt_list
      stmt_list -> 空串
            求first(stmt_list)需要先求解first(stmt)。理由同上。
       3）看下面三个产生式
       stmt -> id := expr
       stmt -> read id
      stmt -> write expr
              可以得出first(stmt)={id，read，write}；
       4）现在来求first（stmt_list)
            stmt_list -> stmt stmt_list
           stmt_list -> 空串
            由于first(stmt)不包含空串，所以对于stmt_list -> stmt stmt_list可以得到first（stmt_list）包含了first(stmt)中的所有元素。
            由于stmt_list -> 空串，所以first（stmt_list)包含空串。
            所以first（stmt_list)={id，read，write，空串}
       5）现在来求first(program)
            program->stmt_list $$
            i）首先first(stmt_list)中的所有非空串元素都应当包含在first(program)中。
            ii) 由于first(stmt_list)包含空串，所以$$应当也包含在first(program)中。
            所以first(program)={id，read，write，$$}。注意这里不包含空串，因为从program是推导不出空串的。
            可以仔细理解一下first集引入的意义和fisrt集的定义，就能理解好书上写的first集的求解规则了。
            有不正确指出请指出。

kallytin

回复 8# idv935

idv935，

再次谢谢你的回复。但我仍有些疑问，如下：

一、follow集
        我的理解是无论first集还是follow集，都是为了预测“下一个单词”用的。因此，当碰到空串（first(空串））时，就会引入follow集，否则不会使用到follow集。那follow集也是为了能提供“下一个单词”，因此follow集的求解过程会不断转化成first集，以不断获得终结符（单词）为目的。是这样吗？

        另，在你的回复了，提到了“2 如果把id当作非终结符，那么你对follow（id）的求解是正确的。”，是指我对follow(id)的推导过程是正确的，是吗？（我想知道我的推导是否正确，目前先不管id是否是非终结符。我在意的是follow集的推导过程）

二、first集

1、你提到“推导中有错误。第一行包含错误。”，指的是什么？是指 first(program)={first(stmt_list)}应该改为first(program)= first(stmt_list) 吗？

2、我仔细看了你提供的first(program)过程，再对比我之前的推导过程，发现：

1)        first(program)        = { first(stmt_list) }
                                = { first(stmt), first(空串) }
                                = { id, read, write, follow(stmt_list) }
                                = { id, read, write, $$ }

你是否认为上面 first(空串) -> follow(stmt_list) 的这个转换是错的？

注：
我也重新看了first集的有关内容，对于空串是直接当作一个元素写入集合了的（例如：first(stmt_list)={id, read, write, 空串}）。但这里涉及到一个是否需要follow集的转换。我个人认为在求解first集的过程中是不用使用到follow集的（虽然我的推导，上面1）里使用到了follow集，但这是为了推导出$$而使用的。我是不知道如何才能推导出$$，而不是肉眼看出）；但是如果在求follow集（例如：C->AB; B->id; B->空串）follow(A)，即求first(B))的过程中如果遇到first(空串），则会转化成求解其follow集（即在first(B)时，当B为空串时，first(B)转化为follow(B))。

idv935

回复 9# kallytin
一 FOLLOW集
    1） 我的理解是无论first集还是follow集，都是为了预测“下一个单词”用的。因此，当碰到空串（first(空串））时，就会引入follow集，否则不会使用到follow集。那follow集也是为了能提供“下一个单词”，因此follow集的求解过程会不断转化成first集，以不断获得终结符（单词）为目的。是这样吗？
          基本正确。不过对碰到空串的情况，更仔细一点儿的理解是这样的。假如当前输入为a，待扩展的非终结符为B。那么非终结符B的first集有以下几种情况
          i）first(B)包含a，不包含空串。那么当前只能对B进行扩展。
          ii) first(B)不包含a，但是包含空串。那么当前就需要考察follow(B)是否包含a。这就是使用到follow集的情况。
          iii)first(B)包含a，也包含空串。那么当前对B进行扩展就包括两种可能。一种是B的某个产生式推导出了a;另一种情况是B推导出了空串，但是follow(B)包含a。这时候就无法只通过查看一个当前输入确定选用那个产生式了。
    2）对follow(id)的推导是正确的