求算符文法的FIRSTVT集的算法-白红宇

原理

数据结构

1 G = {
   'key':[v1,v2,v3],'key':[v1,v2,v3]};2 VN = [];3 Vt = [];4 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)

输入

1 82 S->#E#3 E->E+T4 E->T5 T->T*F6 T->F7 F->P^F|P8 P->(E)9 P->i

完整算法

1 #!/usr/bin/env python 2 #-*-coding:utf8-*- 3  4 #count = raw_input('Please input P count:'); 5  6 #print "Input all P:\n"; 7 f = open("./2.in", 'r',1); 8 count = int(f.readline()); 9 #G = [];10 G = {};11 VN = [];12 Vt = [];13 FirstVT = {};14 for i in range(0,count):15     #key = raw_input("P key:");16     #value = raw_input("P value:");17     line = f.readline().strip();18     print line;19     arr = line.split("->");20     #P = {'key':key,'value':value};21     #P = {
    22         #'key':arr[0],23         #'value':arr[1]24     #};25     VN.append(arr[0]);26 27     #G.append();28     if arr[0] not in G:29         G[arr[0]] = [];30     G[arr[0]].append(arr[1]);31 #print G;32 33 #for p in G:34     #a  = '';35     #if (p['value'][0] not in VN):36         #a = p['value'][0];37     #elif (len(p['value']) >= 2 ) and ( p['value'][0] in VN):38         #a = p['value'][1];39 40 for k in G:41     vs = G.get(k);42     for v in vs:43         a = '';44         if v[0] not in VN:45             a = v[0];46         elif len(v) >= 2 and v[0] in VN and v[1] not in VN:47             a = v[1];48     49         if k not in FirstVT:50             FirstVT[k] = [];51         52         if a != '':53             #将形如 A->a 的 FirstVT[A] 添加进 a54             FirstVT[k].append(a);55 56 #print FirstVT;57 58 stack = [];59 60 for _k in FirstVT:61     _vs = FirstVT.get(_k);62     for _v in _vs:63         # 将 形如 A->a 的入栈64         stack.append([_k,_v]);65         66 67 #print stack;68 69 while len(stack) > 0:70     ij =  stack.pop();71     B = ij[0];72     a = ij[1];73     for A in G:74         vvs = G.get(A);75         for _vs in vvs:76             # 存在形式如  A->B &&  f[ia,ja]为假77             if _vs[0] == B and A != B and ( a not in FirstVT.get(A) ):78                 FirstVT[A].append(a);79                 stack.append([A,a]);80 81 82 83 #print FirstVT;84 85 print '------------------------------------------------'86 for fk in FirstVT:87     fv = FirstVT.get(fk);88     print 'FIRSTVT(',fk,')={
    ',;89     for item in fv:90         if item != fv[-1] :91             print item,',',;92         else:93             print item,;94     print '}\n',;

原理

数据结构

算法过程

输入

完整算法

运行结果