求算符文法的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集合中。

原理

数据结构

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的文法的AFIRSTVT集合

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',;

运行结果

 

目录
相关文章
|
算法 C++ 人工智能
消除文法左递归的算法
存储文法的数据结构 1 typedef struct P{ 2 char key; // 产生式左部 3 char * value [16]; // 产生式右部 4 int count; // 几组规则 5 }P...
1201 0
|
算法 Java Go
求LR(0)文法的规范族集和ACTION表、GOTO表的构造算法
原理 数据结构 1 // GO 2 private static Map GO 3 = new HashMap(); 4 5 // 规范族集 C 6 private static Map C 7 ...
1918 0
|
1天前
|
传感器 算法
基于GA遗传算法的多机无源定位系统GDOP优化matlab仿真
本项目基于遗传算法(GA)优化多机无源定位系统的GDOP,使用MATLAB2022A进行仿真。通过遗传算法的选择、交叉和变异操作,迭代优化传感器配置,最小化GDOP值,提高定位精度。仿真输出包括GDOP优化结果、遗传算法收敛曲线及三维空间坐标点分布图。核心程序实现了染色体编码、适应度评估、遗传操作等关键步骤,最终展示优化后的传感器布局及其性能。
|
2天前
|
机器学习/深度学习 算法 安全
基于深度学习的路面裂缝检测算法matlab仿真
本项目基于YOLOv2算法实现高效的路面裂缝检测,使用Matlab 2022a开发。完整程序运行效果无水印,核心代码配有详细中文注释及操作视频。通过深度学习技术,将目标检测转化为回归问题,直接预测裂缝位置和类别,大幅提升检测效率与准确性。适用于实时检测任务,确保道路安全维护。 简介涵盖了算法理论、数据集准备、网络训练及检测过程,采用Darknet-19卷积神经网络结构,结合随机梯度下降算法进行训练。
|
3天前
|
算法 数据可视化 数据安全/隐私保护
一级倒立摆平衡控制系统MATLAB仿真,可显示倒立摆平衡动画,对比极点配置,线性二次型,PID,PI及PD五种算法
本课题基于MATLAB对一级倒立摆控制系统进行升级仿真,增加了PI、PD控制器,并对比了极点配置、线性二次型、PID、PI及PD五种算法的控制效果。通过GUI界面显示倒立摆动画和控制输出曲线,展示了不同控制器在偏转角和小车位移变化上的性能差异。理论部分介绍了倒立摆系统的力学模型,包括小车和杆的动力学方程。核心程序实现了不同控制算法的选择与仿真结果的可视化。
31 15

热门文章

最新文章