-
Notifications
You must be signed in to change notification settings - Fork 7
/
ADVANCES
35 lines (31 loc) · 2.9 KB
/
ADVANCES
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
DON'T KEEP ONE THING NOT DONE IN YOUR MIND.
GrammaUtils
1.我将Grammar拼错成了Gramma,我不打算修正这个错误了
原理说明:
使用相同代码的函数(如果你修改一个,就得修改另一个;最后检查时,必须保证两者内容相同):
LRGramma中的toString系列、getClosure,getNthSymbolAfterDot 和LR1Gramma 相对应的同名方法
如何生成分析表?对于所有的LR系列语法,都是通过遍历每个项集中,检查项集中项的类型,主要看.的位置
可能的优化措施:
在Gramma,LRGramma,LR1Gramma中,大部分使用 ”Util nothing changed“的作为终结条件的算法时,都会涉及对当前正在遍历的结构进行修改;而这种修改大部分情况下都会引起当前迭代器
的失效(实际上,我所做的调试工作大部分都是在修正这些细微的错误);
优化的基本思想是,每次集合改变时,我都知道下一次需要进行修改的元素有哪些;因此我不必重头遍历整个原来的集合
优化措施1: 使用一个集合暂存将要添加的修改,在本次遍历结束后再将它们加入到原集合中;然后设置新的待遍历的集合;重复上述过程 --- 已经更改数个函数,使用了processed和waits结构
在GrammaSymbols中
在void GrammaSymbols::deleteNo(int no)中
erase之后可能需要进行内存释放
在 LRGramma中,
在getAllClosures()中
在求得GOTO集之后,使用了 ‘==’ 判断求得的集合与当前的所有集合进行比较,这一过程是非常低效的; 应当还有其他的判断方法和去重方法。如果等到有一天发现这个方法是瓶颈时,再优化。
在Gramma中
在eliminateDuplication 中
这里应当有一个用于消除集合中重复元素(元素可能是序列)的算法,但是这里为了方便而采用了暴力搜索-移除的方法;本身搜索就是低效的,再者在数组上使用移除操作也是低效的
当然,可能由于这个方法并不是瓶颈,所以优化的价值没有那么高。 而且也存在第二种优化: 对每个序列判断相同时,首先判断长度,然后使用二分搜索来确定是否相等。
在LR1Gramma中
在getAllClosures中
返回了空的项目集,并且这个项目集没有在GOTO中用到,这是错误的。 ====== 这是由于S'->S.产生的,现在已经通过这一检测消除了
可能最好使用move_iterator来插入,这样效率会更高
itemsets.insert(itemsets.end(), tempitmes.begin(),tempitmes.end());
itemsets.insert(itemsets.end(), std::move_iterator<..>(tempitems.begin()),...); ///#include <iterator>
在 void LR1Gramma::getClosure(const ItemType& i,ClosureType& C,const Gramma::SetsType &firstset)中
fsets.erase(fsets.find(gsyms.findEmpty())); //移除empty
erase方法并没有真正的将内存清除;这里可能引起内存泄漏