字符集的正規化指的是讓正則表達式的表達式樹的所有節點中記錄的字符集合的最小單元都是互不交叉的。舉個例子，[a-g][h-n]沒有交叉，但是[a-g][g-n]就交叉了。所以對[a-g][g-n]做字符集正規化的結果就是將表達式修改為([a-f]|g)(g|[h-n])。這樣表達式里面出現的字符集合的最小單元[a-f]、g和[h-n]就沒有交叉了。下面是正規化的代碼：
正規化包含兩個步驟，第一步是檢查所有的字符集表達式然后做出一張正規化列表，譬如從表達式[a-g][g-n]抽取出正規化列表[a-f]、g和[h-n]。第二步則使用這張列表重寫表達式。[a-g]=[a-f]|g而[h-n]=h|[g-n]，于是便改寫成了([a-f]|g)(g|[h-n])。在這里我們使用
上一篇文章的visitor模式來完成。第一步和第二步的共同點是遍歷所有的節點，然后獲取所有的CharSetExpression。他們的區別僅僅在于如何對待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 };
足夠細心的話會發現Apply(CharSetExpression*)沒有了。這是當然的，因為下面兩個算法將補全之。首先是提取正規化列表。方法很簡單，找出每一個字符集，用它來切割正規化列表就好了。舉個例子，我們處理[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的另一個優點：可以提取算法的公共部分。
posted on 2009-10-17 20:43
陳梓瀚(vczh) 閱讀(1885)
評論(1) 編輯 收藏 引用 所屬分類:
VL++3.0開發紀事