解引用指的是對命名表達式的處理。這跟C++的宏差不多，留個名字在那里，然后就擴展它。舉個例子，我們寫一個正則表達式判斷一個字符串是否ip地址。判斷一個字符串是否小于256的數(shù)字還是很麻煩的：\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]。但是如果要判斷是否X.X.X.X就要將這個表達式復(fù)制四次（至少兩次），這會導(dǎo)致正則表達式很長。如何解決呢？
在我這個正則表達式的實現(xiàn)里面你可以使用一個名字去對一個正則表達式命名，然后使用之。既然我們知道在X代表上面的正則表達式的時候，(X.){3}X就是我們想要的結(jié)果，所以我們可以把正則表達式寫成：(<#X>\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])((<&X>).){3}(<&X>)，是不是短很多呢。當(dāng)然這里不止支持一個命名，你可以在前面命名很多個，每一個命名里面可以隨意調(diào)用其他命名的內(nèi)容，當(dāng)然只有一個限制就是這不能造成循環(huán)引用。一循環(huán)起來就不是正則文法（Type 3 grammar）了，這個時候應(yīng)該用combinator而不是regex。下面來看解引用的代碼。
代碼還是很簡單的，只需要對表達式進行遞歸就可以了，每一次進入(<&X>)的時候檢查X是否存在和是否正在被處理，我們就可以知道有沒有循環(huán)引用的情況出現(xiàn)了：
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"\"發(fā)生引用循環(huán)。", 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實現(xiàn)，還有從正則表達式產(chǎn)生epsilon-NFA的過程了。
posted on 2009-10-20 06:36
陳梓瀚(vczh) 閱讀(2053)
評論(2) 編輯 收藏 引用 所屬分類:
VL++3.0開發(fā)紀(jì)事