字符集的正規(guī)化指的是讓正則表達式的表達式樹的所有節(jié)點中記錄的字符集合的最小單元都是互不交叉的。舉個例子，[a-g][h-n]沒有交叉，但是[a-g][g-n]就交叉了。所以對[a-g][g-n]做字符集正規(guī)化的結(jié)果就是將表達式修改為([a-f]|g)(g|[h-n])。這樣表達式里面出現(xiàn)的字符集合的最小單元[a-f]、g和[h-n]就沒有交叉了。下面是正規(guī)化的代碼：
正規(guī)化包含兩個步驟，第一步是檢查所有的字符集表達式然后做出一張正規(guī)化列表，譬如從表達式[a-g][g-n]抽取出正規(guī)化列表[a-f]、g和[h-n]。第二步則使用這張列表重寫表達式。[a-g]=[a-f]|g而[h-n]=h|[g-n]，于是便改寫成了([a-f]|g)(g|[h-n])。在這里我們使用
上一篇文章的visitor模式來完成。第一步和第二步的共同點是遍歷所有的節(jié)點，然后獲取所有的CharSetExpression。他們的區(qū)別僅僅在于如何對待CharSetExpression上。所以我們先寫一個算法基類：
1 class CharSetAlgorithm : public RegexExpressionAlgorithm<void, NormalizedCharSet*>
2 {
3 public:
4 void Apply(LoopExpression* expression, NormalizedCharSet* target)
5 {
6 Invoke(expression->expression, target);
7 }
8
9 void Apply(SequenceExpression* expression, NormalizedCharSet* target)
10 {
11 Invoke(expression->left, target);
12 Invoke(expression->right, target);
13 }
14
15 void Apply(AlternateExpression* expression, NormalizedCharSet* target)
16 {
17 Invoke(expression->left, target);
18 Invoke(expression->right, target);
19 }
20
21 void Apply(BeginExpression* expression, NormalizedCharSet* target)
22 {
23 }
24
25 void Apply(EndExpression* expression, NormalizedCharSet* target)
26 {
27 }
28
29 void Apply(CaptureExpression* expression, NormalizedCharSet* target)
30 {
31 Invoke(expression->expression, target);
32 }
33
34 void Apply(MatchExpression* expression, NormalizedCharSet* target)
35 {
36 }
37
38 void Apply(PositiveExpression* expression, NormalizedCharSet* target)
39 {
40 Invoke(expression->expression, target);
41 }
42
43 void Apply(NegativeExpression* expression, NormalizedCharSet* target)
44 {
45 Invoke(expression->expression, target);
46 }
47
48 void Apply(UsingExpression* expression, NormalizedCharSet* target)
49 {
50 }
51 };
足夠細心的話會發(fā)現(xiàn)Apply(CharSetExpression*)沒有了。這是當(dāng)然的，因為下面兩個算法將補全之。首先是提取正規(guī)化列表。方法很簡單，找出每一個字符集，用它來切割正規(guī)化列表就好了。舉個例子，我們處理[a-g][g-h]，首先獲得[a-g]，然后通過跟[g-h]比較知道他們有交集，于是提取交集g，然后切割一下就行了：
1 class BuildNormalizedCharSetAlgorithm : public CharSetAlgorithm
2 {
3 public:
4 void AddRange(NormalizedCharSet* target, CharRange range)
5 {
6 int index=0;
7 while(index<target->ranges.Count())
8 {
9 CharRange current=target->ranges[index];
10 if(current<range || current>range)
11 {
12 index++;
13 }
14 else if(current.begin<range.begin)
15 {
16 // range : [ ?
17 // current : [ ]
18 target->ranges.RemoveAt(index);
19 target->ranges.Add(CharRange(current.begin, range.begin-1));
20 target->ranges.Add(CharRange(range.begin, current.end));
21 index++;
22 }
23 else if(current.begin>range.begin)
24 {
25 // range : [ ]
26 // current : [ ?
27 target->ranges.Add(CharRange(range.begin, current.begin-1));
28 range.begin=current.begin;
29 }
30 else if(current.end<range.end)
31 {
32 // range : [ ]
33 // current : [ ]
34 range.begin=current.end+1;
35 index++;
36 }
37 else if(current.end>range.end)
38 {
39 // range : [ ]
40 // current : [ ]
41 target->ranges.RemoveAt(index);
42 target->ranges.Add(range);
43 target->ranges.Add(CharRange(range.end+1, current.end));
44 return;
45 }
46 else
47 {
48 // range : [ ]
49 // current : [ ]
50 return;
51 }
52 }
53 target->ranges.Add(range);
54 }
于是，我們拿到了這張列表之后，就可以重寫表達式了：
1 class SetNormalizedCharSetAlgorithm : public CharSetAlgorithm
2 {
3 public:
4 void Apply(CharSetExpression* expression, NormalizedCharSet* target)
5 {
6 CharRange::List result;
7 for(int i=0;i<target->ranges.Count();i++)
8 {
9 CharRange targetRange=target->ranges[i];
10 for(int j=0;j<expression->ranges.Count();j++)
11 {
12 CharRange range=expression->ranges[j];
13 if(range.begin<=targetRange.begin && targetRange.end<=range.end)
14 {
15 result.Add(targetRange);
16 }
17 }
18 }
19 expression->ranges.Clear();
20 CopyFrom(expression->ranges.Wrap(), result.Wrap());
21 }
22 };
最后在Expression那里封裝一下就大功告成了：
1 void Expression::NormalizeCharSet()
2 {
3 NormalizedCharSet normalized;
4 BuildNormalizedCharSetAlgorithm().Invoke(this, &normalized);
5 SetNormalizedCharSetAlgorithm().Invoke(this, &normalized);
6 }
至于什么是NormalizedCharSet，這只是一個擁有成員SortedList<CharRange>的類罷了。至此我們還看到了Visitor的另一個優(yōu)點：可以提取算法的公共部分。
posted on 2009-10-17 20:43
陳梓瀚(vczh) 閱讀(1900)
評論(1) 編輯 收藏 引用 所屬分類:
VL++3.0開發(fā)紀(jì)事