解引用指的是對命名表達式的處理。這跟C++的宏差不多，留個名字在那里，然后就擴展它。舉個例子，我們寫一個正則表達式判斷一個字符串是否ip地址。判斷一個字符串是否小于256的數字還是很麻煩的：\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]。但是如果要判斷是否X.X.X.X就要將這個表達式復制四次（至少兩次），這會導致正則表達式很長。如何解決呢？
在我這個正則表達式的實現里面你可以使用一個名字去對一個正則表達式命名，然后使用之。既然我們知道在X代表上面的正則表達式的時候，(X.){3}X就是我們想要的結果，所以我們可以把正則表達式寫成：(<#X>\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])((<&X>).){3}(<&X>)，是不是短很多呢。當然這里不止支持一個命名，你可以在前面命名很多個，每一個命名里面可以隨意調用其他命名的內容，當然只有一個限制就是這不能造成循環引用。一循環起來就不是正則文法（Type 3 grammar）了，這個時候應該用combinator而不是regex。下面來看解引用的代碼。
代碼還是很簡單的，只需要對表達式進行遞歸就可以了，每一次進入(<&X>)的時候檢查X是否存在和是否正在被處理，我們就可以知道有沒有循環引用的情況出現了：
1 class MergeParameter
2 {
3 public:
4 Expression::Map definitions;
5 RegexExpression* regex;
6 };
7
8 class MergeAlgorithm : public RegexExpressionAlgorithm<Expression::Ref, MergeParameter*>
9 {
10 public:
11 Expression::Ref Apply(CharSetExpression* expression, MergeParameter* target)
12 {
13 Ptr<CharSetExpression> result=new CharSetExpression;
14 CopyFrom(result->ranges.Wrap(), expression->ranges.Wrap());
15 result->reverse=expression->reverse;
16 return result;
17 }
18
19 Expression::Ref Apply(LoopExpression* expression, MergeParameter* target)
20 {
21 Ptr<LoopExpression> result=new LoopExpression;
22 result->max=expression->max;
23 result->min=expression->min;
24 result->expression=Invoke(expression->expression, target);
25 return result;
26 }
27
28 Expression::Ref Apply(SequenceExpression* expression, MergeParameter* target)
29 {
30 Ptr<SequenceExpression> result=new SequenceExpression;
31 result->left=Invoke(expression->left, target);
32 result->right=Invoke(expression->right, target);
33 return result;
34 }
35
36 Expression::Ref Apply(AlternateExpression* expression, MergeParameter* target)
37 {
38 Ptr<AlternateExpression> result=new AlternateExpression;
39 result->left=Invoke(expression->left, target);
40 result->right=Invoke(expression->right, target);
41 return result;
42 }
43
44 Expression::Ref Apply(BeginExpression* expression, MergeParameter* target)
45 {
46 return new BeginExpression;
47 }
48
49 Expression::Ref Apply(EndExpression* expression, MergeParameter* target)
50 {
51 return new EndExpression;
52 }
53
54 Expression::Ref Apply(CaptureExpression* expression, MergeParameter* target)
55 {
56 Ptr<CaptureExpression> result=new CaptureExpression;
57 result->expression=Invoke(expression->expression, target);
58 result->name=expression->name;
59 return result;
60 }
61
62 Expression::Ref Apply(MatchExpression* expression, MergeParameter* target)
63 {
64 Ptr<MatchExpression> result=new MatchExpression;
65 result->name=expression->name;
66 result->index=expression->index;
67 return result;
68 }
69
70 Expression::Ref Apply(PositiveExpression* expression, MergeParameter* target)
71 {
72 Ptr<PositiveExpression> result=new PositiveExpression;
73 result->expression=Invoke(expression->expression, target);
74 return result;
75 }
76
77 Expression::Ref Apply(NegativeExpression* expression, MergeParameter* target)
78 {
79 Ptr<NegativeExpression> result=new NegativeExpression;
80 result->expression=Invoke(expression->expression, target);
81 return result;
82 }
83
84 Expression::Ref Apply(UsingExpression* expression, MergeParameter* target)
85 {
86 if(target->definitions.Keys().Contains(expression->name))
87 {
88 Expression::Ref reference=target->definitions[expression->name];
89 if(reference)
90 {
91 return reference;
92 }
93 else
94 {
95 throw ArgumentException(L"正則表達式語法錯誤：引用表達式\""+expression->name+L"\"發生引用循環。", L"vl::regex_internal::RegexExpression::Merge", L"");
96 }
97 }
98 else if(target->regex->definitions.Keys().Contains(expression->name))
99 {
100 target->definitions.Add(expression->name, 0);
101 Expression::Ref result=Invoke(target->regex->definitions[expression->name], target);
102 target->definitions.Set(expression->name, result);
103 return result;
104 }
105 else
106 {
107 throw ArgumentException(L"正則表達式語法錯誤：找不到引用表達式\""+expression->name+L"\"。", L"vl::regex_internal::RegexExpression::Merge", L"");
108 }
109 }
110 };
最后封裝一下：
1 Expression::Ref RegexExpression::Merge()
2 {
3 MergeParameter merge;
4 merge.regex=this;
5 return MergeAlgorithm().Invoke(expression, &merge);
6 }
今天的工作還是很簡單的。下次開始就可以看如何檢查一個正則表達式能否被純DFA實現，還有從正則表達式產生epsilon-NFA的過程了。
posted on 2009-10-20 06:36
陳梓瀚(vczh) 閱讀(2059)
評論(2) 編輯 收藏 引用 所屬分類:
VL++3.0開發紀事