找出正则表达式失败的位置

Question

找出正则表达式失败的位置

javascriptregexlexical-analysis

17

我正在尝试使用JavaScript编写一个词法分析器，用于查找简单领域特定语言的标记。我开始采用简单的实现方式，它只是尝试从当前行的位置匹配后续的正则表达式，以查找其是否匹配某些标记格式并接受它。

问题在于，当某些内容不匹配正则表达式时，整个正则表达式都失败了，因此我不知道到底是哪个字符导致它失败。

有没有办法找出导致正则表达式失败的字符串位置？

INB4：我不是在询问如何调试我的正则表达式并验证其正确性。它已经正确，可以匹配正确的字符串并丢弃不正确的字符串。我只想编程方式知道正则表达式停止匹配的确切位置，以查找用户输入中不正确的字符的位置，以及其中有多少个字符是正确的。

是否有一些方法仅使用简单的正则表达式来完成它，而不必继续实现全面的有限状态自动机？

- SasQ

3个回答

4

您可以使用否定字符集 RegExp，

[^xyz]
[^a-c]
A negated or complemented character set. That is, it matches anything that is not enclosed in the brackets. You can specify a range of characters by using a hyphen, but if the hyphen appears as the first or last character enclosed in the square brackets it is taken as a literal hyphen to be included in the character set as a normal character.

String.prototype.match()的index属性

返回的数组有一个额外的输入属性，其中包含被解析的原始字符串。此外，它还具有一个索引属性，表示匹配在字符串中的从零开始的索引。

例如，在字符串aBcD7zYx中，使用RegExp /[^a-zA-z]/匹配数字时记录index

var re = /[^a-zA-Z]/;
var str = "aBcD7zYx";
var i = str.match(re).index;
console.log(i); // 4

- guest271314

1

请注意，String.prototype.search()也可以用来替代.match()。 - guest271314

0

有没有办法找出导致正则表达式失败的字符串位置？

不，没有。正则表达式要么匹配，要么不匹配。没有中间状态。

部分表达式可以匹配，但整个模式不能。因此引擎总是需要评估整个表达式：

以字符串“Hello my World”和模式“/Hello World/”为例。虽然每个单词都可以单独匹配，但整个表达式失败了。你无法确定是“Hello”还是“World”匹配——它们都是独立的。同时它们之间的空格也是可用的。

- dognose

1

当然，我知道正则表达式是如何工作的。但你所说的并不排除我所问的问题。请注意，尽管您的正则表达式无法完全匹配给定的字符串，但仍有某个特定字符使其停止匹配：在测试字符串中，m代替了所需的W。这就是我想知道的：导致正则表达式失败的特定字符的位置。 - SasQ

我会说在这个例子中匹配失败发生在第一个字符（即“H”）处。为什么呢？因为“H”既匹配了原始正则表达式的一部分，也匹配了整个“Hello ”部分。它只在“W”处失败，导致整个正则表达式匹配失败。但我仍然可以确定哪个字符是绊脚石。 - SasQ

@SasQ - 如果你的正则表达式总是这么简单（在这种情况下使用正则表达式没有意义），那么你肯定可以得到你想要的答案...你所要做的就是将输入的前_n_个字符与正则表达式的前_n_个字符进行匹配，直到没有匹配为止...然后_n_就是你的失败点。然而，我同意zx81的看法，一旦你开始使用任何有用或复杂的真正的正则表达式，"失败点"就变得不确定了。 - jahroy

我的正则表达式并不总是像@dognose展示的那样简单（而且这是他的例子，不是我的）。但它们足够“简单”，以至于常规DFA可以告诉哪个字符是绊脚石。从自动机理论中，我们知道每个正则表达式都有一个等效的DFA。因此，如果DFA可以告诉我哪个字符导致它失败，我认为正则表达式引擎也可以做到。但这可能取决于正则表达式引擎的实现方式（实际上这可能会产生很大的差异，就像这篇文章所展示的：http://swtch.com/~rsc/regexp/regexp1.html）。 - SasQ

@SasQ - 我绝不是一个正则表达式专家（说实话，我甚至不得不谷歌DFA），但从zx81的回答中，我了解到正则表达式引擎无法回答您的问题，并且它们的实现是为了速度和效率。为了使它们能够回答您的问题，似乎需要大量修改它们的实现。我怀疑世界上其他开发人员不希望正则表达式引擎变得远不如以前那么高效，只是为了回答您的问题。 - jahroy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- zx81 · Accepted Answer

简短回答

没有所谓的“导致正则表达式失败的字符串位置”。

然而，我将向您展示如何回答相反的问题：

在正则表达式的哪个标记处，引擎无法匹配字符串？

讨论

在我看来，关于“导致正则表达式失败的字符串位置”的问题是颠倒的。当引擎用左手移动字符串，右手移动模式时，一个正则表达式标记可以在一刻钟匹配六个字符，然后因量词和回溯，下一刻只匹配零个字符，或者扩展到匹配十个字符。

在我看来，一个更合适的问题可能是：

在正则表达式的哪个标记处，引擎无法匹配字符串？

例如，考虑正则表达式 ^\w+\d+$ 和字符串 abc132z。

\w+ 实际上可以匹配整个字符串。然而，整个正则表达式失败了。这样说正则表达式在字符串结尾失败有意义吗？我不这么认为。考虑下面的情况。

最初，\w+将匹配 abc132z。然后引擎前进到下一个标记：\d+。此时，引擎在字符串中回溯，逐渐放弃 \w+ 中的 2z（所以现在 \w+ 仅对应于 abc13），允许 \d+ 匹配 2。

在这个阶段，因为剩余了 z，所以 $ 断言失败了。引擎回溯，让 \w+ 放弃 3 字符，然后是 1（所以现在 \w+ 仅对应于 abc），最终允许 \d+ 匹配 132。在每一步中，引擎都会尝试 $ 断言并失败。根据引擎内部情况，可能会发生更多的回溯： \d+ 再次放弃了 2 和 3，然后 \w+ 放弃了 c 和 b。当引擎最终停止时，\w+ 仅匹配最初的 a。你能说这个正则表达式“在3上失败了吗？在b上失败了吗？”

不行。如果你从左到右看正则表达式模式，你可以争辩说它失败了在 $ 上，因为它是我们无法添加到匹配中的第一个标记。请注意，还有其他方法来证明这一点。

接下来，我将给您提供一个截图以便更好理解。但首先，让我们看看我们是否能回答另一个问题。

另一个问题

是否有技术可以回答另一个问题：

在正则表达式的哪个标记处，引擎无法匹
^(?:(?=(\w+)))?(?:(?=(\w+\d+)))?(?:(?=(\w+\d+$)))?.
在PCRE、.NET和Python中，您可以更加简洁地编写如下代码:
^(?=(\w+))?(?=(\w+\d+))?(?=(\w+\d+$))?.
每个前瞻都会逐步地在上一个前瞻的基础上添加一个令牌。因此，我们可以单独测试每个令牌。末尾的点是一种可选的华丽修饰，用于视觉反馈：我们可以在调试器中看到至少匹配了一个字符，但是我们不关心该字符，我们只关心捕获组。
1. 第一组测试`\w+`令牌 2. 第二组似乎测试`\w+\d+`，因此逐步测试`\d+`令牌 3. 第三组似乎测试`\w+\d+$`，因此逐步测试`$`令牌
共有三个捕获组。如果这三个都设置了，则匹配成功。如果只有第三组未设置（例如`abc123a`），则可以说是`$`导致了失败。如果设置了第一组但没有设置第二组（例如`abc`），则可以说是`\d+`导致了失败。
为参考：失败路径内部视图
就其价值而言，这是来自RegexBuddy调试器的失败路径视图。