解引用指的是对命名表达式的处理。这跟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) 阅读(2037)
评论(2) 编辑 收藏 引用 所属分类:
VL++3.0开发纪事