求算符文法的FIRSTVT集的算法

原理

数据结构

 G = {'key':[v1,v2,v3],'key':[v1,v2,v3]};

 VN = [];

 Vt = [];

 FirstVT = {'key':[v1,v2,v3],'key':[v1,v2,v3]};

也就是map里放list，同样将文法压缩，对于产生式相同的发到一个map元素里，追加到map元素对应的list后面

算法过程

1、 先求出直接满足A->a 或 A->Ba的文法的A的FIRSTVT集合

2、 扫描FIRSTVT集，将满足蔓延性公式的终结符加到非终结符的FIRSTVT集合中。蔓延性满足下面的条件

若a属于FIRSTVT(B) 且有产生式A->B..... 则a属于FIRSTVT(A)

输入

 8

 S->#E#

 E->E+T

 E->T

 T->T*F

 T->F

 F->P^F|P

 P->(E)

 P->i

完整算法

 #!/usr/bin/env python

 #-*-coding:utf8-*-

 #count = raw_input('Please input P count:');

 #print "Input all P:\n";

 f = open("./2.in", 'r',1);

 count = int(f.readline());

 #G = [];

 G = {};

 VN = [];

 Vt = [];

 FirstVT = {};

 for i in range(0,count):

     #key = raw_input("P key:");

     #value = raw_input("P value:");

     line = f.readline().strip();

     print line;

     arr = line.split("->");

     #P = {'key':key,'value':value};

     #P = {

         #'key':arr[0],

         #'value':arr[1]

     #};

     VN.append(arr[0]);

     #G.append();

     if arr[0] not in G:

         G[arr[0]] = [];

     G[arr[0]].append(arr[1]);

 #print G;

 #for p in G:

     #a  = '';

     #if (p['value'][0] not in VN):

         #a = p['value'][0];

     #elif (len(p['value']) >= 2 ) and ( p['value'][0] in VN):

         #a = p['value'][1];

 for k in G:

     vs = G.get(k);

     for v in vs:

         a = '';

         if v[0] not in VN:

             a = v[0];

         elif len(v) >= 2 and v[0] in VN and v[1] not in VN:

             a = v[1];

         if k not in FirstVT:

             FirstVT[k] = [];

         if a != '':

             #将形如 A->a 的 FirstVT[A] 添加进 a

             FirstVT[k].append(a);

 #print FirstVT;

 stack = [];

 for _k in FirstVT:

     _vs = FirstVT.get(_k);

     for _v in _vs:

         # 将 形如 A->a 的入栈

         stack.append([_k,_v]);

 #print stack;

 while len(stack) > 0:

     ij =  stack.pop();

     B = ij[0];

     a = ij[1];

     for A in G:

         vvs = G.get(A);

         for _vs in vvs:

             # 存在形式如  A->B &&  f[ia,ja]为假

             if _vs[0] == B and A != B and ( a not in FirstVT.get(A) ):

                 FirstVT[A].append(a);

                 stack.append([A,a]);

 #print FirstVT;

 print '------------------------------------------------'

 for fk in FirstVT:

     fv = FirstVT.get(fk);

     print 'FIRSTVT(',fk,')={',;

     for item in fv:

         if item != fv[-1] :

             print item,',',;

         else:

             print item,;

     print '}\n',;

运行结果