哪种Xpressive方法最能减少堆栈的使用

Question

我在我目前的嵌入式C++项目中广泛地使用了Xpressive。

据我所知，Xpressive是一个很好的堆栈用户。但是，有没有更高效的Xpressive regex方法呢？

例如，匹配表示32位整数的字符串的正则表达式可能需要测试数字6是否小于或等于6。

Xpressive (我知道还有其他正则表达式引擎)支持多种方法，例如：

range('0','6')

或

('0'|'1'|'2'|'3'|'4'|'5'|'6')

或

set['0'|'1'|'2'|'3'|'4'|'5'|'6']

然后正则表达式可以允许3个以下数字，例如：

repeat<3>(_d) >> _b

或

_d >> _d >> _d >> _b

但是，如果可以选择，并且不太关心源代码布局，哪种方法是最优的：

a)堆栈；

b)速度；

c)？

Answer 1

排序和重复会耗尽堆栈，因为它们需要回溯。让我们来看看你的例子。

range('0','6')

这被实现为快速检查字符是否落入字符范围内。它不使用排序或重复，因此不会吞噬堆栈空间。

('0'|'1'|'2'|'3'|'4'|'5'|'6')

一般来说，不要把可以放在集合或范围中的东西放在另一个地方。对于这类事情，他们的效率要高得多。我要注意的是，显然这不是一个有效的xpressive正则表达式。你可以把它写成：

(as_xpr('0')|'1'|'2'|'3'|'4'|'5'|'6')

我相信你知道这一点。我将对此进行类似的编辑：

set[as_xpr('0')|'1'|'2'|'3'|'4'|'5'|'6']

套装速度很快。它们被实现为用于ascii范围的查找表和(对于Unicode)用于256以上字符代码的稀疏矢量。由于某些集合的稀疏性，这种方案可能比简单的范围占用更多的堆空间。但这并不影响匹配时使用的堆栈空间量。我要指出的是，你也可以这样写：

(set= '1','2','3','4','5','6')

现在重复一下：

repeat<3>(_d) >> _b

正如我之前所说的，重复通常是通过递归实现的，以获得正确的回溯。但在这种情况下，xpressive认识到_d只能吃掉一个字符，并且它恰好被重复了3次。所以在这种有限的情况下，它是用一个循环来实现的，以节省堆栈空间。这与下一种情况形成对比：

_d >> _d >> _d >> _b

Xpressive不够聪明，不能像对待repeat<3>(_d)那样对待_d >> _d >> _d。因此，这将为每个_d消耗一个单独的堆栈框架。

简而言之:在可能的情况下，优先使用专门的构造，而不是更通用的等价构造。这为xpressive提供了更多优化的上下文。

此外，了解独立子表达式。如果你能把一些东西放在keep()中，那就去做吧。为什么？keep()匹配子表达式，然后回收该子匹配使用的堆栈空间。这使得通过回溯到该子表达式来尝试不同的事情是不可能的，但有时你不需要这样做。

希望这能有所帮助。