First集和Follow集,FirstVt集和LastVt集的计算

灰太狼 2022-06-15 03:26 188阅读 0赞

转载自：http://dongtq2010.blog.163.com/blog/static/1750224812011520113332714/

学编译原理的时候，印象最深的莫过于这四个集合了，而且也十分为之纠结。

首先要知道First和Follow是一对，而Firstvt和Lastvt是一对。  
然后要知道这两对都是干什么的。  
First和Follow是为了画预测分析表的（在LL（1）分析法处）。  
而Firstvt和Lastvt是为了画算符优先关系表的（就是表里面填优先大于小于等于的那个）。  
然后要注意他们可都是终结符的集合。  
  
再就是他们如何构建的问题了  
先说First和Follow  
**First**  
如A->aB | CD  
这里面包含了组成First（A）的两种情况：  
 以终结符开头， 当然要把这个终结符放到A的First里  
 以非终结符开头， 先把C的First放到A的First里  
 再看如果C的First中有空的话就把D的First放到A的First里，如果D也有空的话往后依次类推  
技巧： 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中要加上‘\#’   
技巧： Follow一般从上往下找。  
 如果要找L的Follow，要从式子的右边找到L，然后来找L的Follow，这与First是不同的。  
  
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  
再说下Firstvt和Lastvt  
**Firstvt**  
找Firstvt的三条规则： 如果要找A的Firstvt，A的候选式中出现：  
 A->a.......，即以终结符开头，该终结符入Firstvt  
 A->B.......，即以非终结符开头，该非终结符的Firstvt入A的Firstvt  
 A->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt  
  
**Lastvt**  
找Lastvt的三条规则： 如果要找A的Lastvt，A的候选式中出现：  
 A->.......a，即以终结符结尾，该终结符入Lastvt  
 A->.......B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt  
 A->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Firstvt