原理
数据结构
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 8 2 S->#E# 3 E->E+T 4 E->T 5 T->T*F 6 T->F 7 F->P^F|P 8 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] 添加进 a 54 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',;
运行结果
