时间戳

首页 > 解决方案 > 解析时不匹配一组模式应该如何工作？

regex - 解析时不匹配一组模式应该如何工作？

问题描述

我正在组合一个解析器生成器/PEG 系统，并且被困在 NOT 的情况下。基本上，你可以有这样的规则：

everything_char_except_x = not x

你可以变得更复杂并说：

everything_except_x_or_y = not(x | y)

那么，x 和 y 本身可以是复杂的规则，而不仅仅是字母 x 或 y。

grammar = 8 everything_except_x_or_y 8
everything_except_x_or_y = not(x | y)
x = a | b | c
a = 1 | 2 | 3
b = 100 | 200 | 300
c = 5000 | 6000
y = x+ 4 x+

有什么复杂的。

问题是，你如何解析这样的语句？您如何跳过所有不匹配的内容？

我知道在 regex-land 中，你有/[xy]+[^xy]+[xy]+/，[^xy]意思是不匹配。我真的不知道这在幕后是如何工作的，但是在我稍微复杂（尽管是人为的）示例中，您想要匹配任何字符，然后是除这些序列之外的任何字符，其中包含 1、2 或 3，或 100 , 200, 300 等。有点难以想象，但鉴于我们不匹配，假设我们有898， where 9is not in xor y。然后在解析的时候，我们看到index:1 == 9，不是x，也不是y，所以解析的时候前移1个字符。

但这似乎很麻烦/很慢，一次移动一个字符。我们不能以某种方式一口气推进许多角色吗？或者在这种情况下我们必须总是一次处理一个字符吗？

抱歉，如果这个问题有点模糊，但我正在尝试实现不匹配，并且不太确定它应该如何工作。

我感到困惑的原因是，您可能会检查b前面的 3 个字符，所以如果我们发现我们没有匹配100，比如说，我们可以不跳过 3 个字符而不是 1 个字符吗？那么这意味着，我们不能跳过最长的匹配吗？似乎这个假设会被打破，但这就是我的意思。

我大声思考...

85007060008， 我们会去：

标签： regexparsing

解决方案

（通常的）PEG!运算符，或者至少是 Bryan Ford 在他的 Packrat Parsing 论文中定义的那个），实际上是一个负前瞻运算符，类似于(?!...)许多正则表达式库中的运算符。类似地，PEG 有一个&算子，它是一个类似于 PCRE(?=...)算子的正向前瞻。我认为这些与您想象的否定运算符不同。

前瞻断言不消耗任何输入。但是，它们是成功还是失败，取决于紧随其后的输入文本是否与提供的模式匹配。像所有 PEG 原语一样，它们在指定的输入点成功或失败，因此可以说成功的前瞻匹配从特定位置开始的空字符串，尽管更容易将其视为匹配位置本身。

题外话：正则表达式负字符类与负前瞻断言

这是与正则表达式字符类完全不同的概念。正则表达式字符类总是尝试匹配单个字符，该字符在成功时被消耗。字符类只是定义了一组可匹配的字符；字符类的[^...]形式改为使用集合的逆。可能的字符数量有限；任何一组字符的逆很容易计算。所以实现不需要魔法。

因此，这两个正则表达式做不同的事情（都不是特别有用；这只是一个简单的例子）：

/[^a]./
/(?!a)./

第一个匹配任何字符，而不是a后跟任何字符。所以它会匹配ba但bb不会匹配ab（第一个字符是a）或b（后面没有另一个字符）。

如果下一个字符不是 ，则第二个首先匹配当前输入点a，然后匹配任何字符（仍在当前输入点）。所以它会匹配b但不会匹配a。

至关重要的是，负前瞻断言子模式可以任意长。负字符类只能匹配单个字符。这使得负前瞻显着更强大（实施起来也更昂贵）。

例如，假设您要匹配以“END”的第一个实例结尾的字符序列。这可以在没有否定前瞻断言的情况下完成，但它非常笨拙：

/[^E]*E+([^EN][^E]*E+)*N([^D][^E]*E+([^EN][^E]*E+)*N)*D/

但是如果你有一个否定的前瞻断言，它会更容易，甚至可能是自然的：

/((?!END).)*END/

如果这看起来很神秘（这是可能的，因为它包含很多标点符号），请阅读(?!END).为“任何字符 ( .)，它不是序列 "END" ( (?!END)) 中的第一个字符。

上面的例子碰巧在每个字符位置检查谓词，但那是因为谓词成功后匹配的模式是.，它匹配（任何）单个字符，并且 { 断言 / 匹配任何字符 } 的序列显式重复。这是一个简单的例子，但更复杂的前瞻使用是可能的（并且很常见）。例如，您可能希望匹配以逗号分隔的简单条目或引用条目的列表，并在以序列开头的条目处终止status。（这种模式可以用来跳过 CSV 中不感兴趣的字段。）可以写成：

/((?!status:)([^"\n]*|("[^"]*")+),)*/

在该示例中，Status:仅在条目的开头检查字符串，因此恰好在内部包含该序列的条目不会导致模式终止。

重返 PEG

解析表达式语法，如Bryan Ford (2004) 所定义，有效地将这个概念推广到任意语法，而不限于逐字符匹配。[确切定义见注 1，实际上来自 Ford 的论文，其中的阐述更清楚一些。] 根据 Ford 的说法，PEG 允许逐个字符匹配的事实很有用，因为它消除了使用两种不同的解析技术，一种用于标记化，另一种用于语法。但是前瞻断言使得匹配一些甚至不是上下文无关的有趣语言变得相对容易。例如，Ford 的论文展示了如何编写 PEG 来匹配，这是非上下文无关语言的常见示例：{anbncn}

L → C END_OF_INPUT
A → a A b / ε
B → b B c / ε
C → (& A !b) a* B

Aa匹配具有和s的等长子序列的序列b，而B对bs 和cs 执行相同的操作。有效地将 a末尾的s 与 a 开头的相同sC重叠。如果后跟 an后跟 a 以外的任何内容，则肯定的超前断言成功。然后用于实际匹配s，并且匹配后面的任何内容，此时已知它以与s 的序列相同长度的s 序列开始。因此，bAbB(& A !b)Aba*aBbaC仅匹配三个子序列具有相同长度的序列，这是上下文无关文法无法做到的。

这是如何实施的？

这就是 Bryan Ford 论文的重点，因此阅读它将是一个好的开始。但基本思想很简单：每次在某个输入点尝试进行部分解析时，结果都会被缓存。如果在同一位置再次尝试相同的解析，则立即返回缓存结果。（这就是福特称之为“packrat 解析”的原因；packrat 从不丢弃任何东西，以防它在某个假设的未来再次有用。）

前瞻解析像任何其他解析一样被缓存，详细信息是在回溯解析器以忽略匹配（如有必要）之前缓存结果。因此，如果相同的模式出现在前瞻目标和匹配结构中，前瞻也会将结果放入缓存中，当解析器返回该输入点时，它将能够直接移动到模式的末尾。

如果我正确地阅读了您的问题，那就是您要问的问题，如果是这样，答案基本上是“是”：不是解析器跳到最长匹配的末尾；而是 它跳到先前计算的匹配的末尾，无论它可能是什么。它可以做到这一点，因为 PEG 模式中的所有选项都是有序的，一旦找到与该选项的匹配项，解析器就不会尝试另一个选项。这与 LR(1) 解析算法完全不同，LR(1) 解析算法并行探索所有替代方案，直到它必须减少生产。或者 GLL/GLR 算法，它们也并行探索所有替代方案，以便它们可以返回所有可能的输入解析的森林（或唯一的解析，如果只有一个，不管它是如何被发现的）。事实上，“

Packrat 策略主要是指每个解析器状态在每个输入位置只输入一次，并且由于解析器状态的数量是有限的，因此整个解析可以在线性时间内完成。为了使其实用，需要进行一些优化，但事实证明，只要稍加努力，您就可以生成一个相当快的解析器。

笔记

  1. 前瞻运算符在福特论文的第 67 页上定义如下：

    • “and-followed-by”匹配器的形式为&r，其中r是一元规则。该匹配器实现了句法谓词：它使规则r在序列中的适当位置被调用，如果成功，则将输入位置备份到调用之前的位置r，就好像r没有消耗任何输入文本一样。如果r失败，则整个序列失败。
    • “not-followed-by”匹配器具有形式!r，其中r是一元规则，并实现句法谓词的否定形式：如果r成功，则整个序列失败；但如果r失败，则匹配器成功而不消耗任何输入文本，并且允许继续解析序列。“句法谓词”（与“语义谓词”相对）的使用是由于 Terrance Parr，可以在他 1994 年的论文《向 LL(k) 中添加语义和句法谓词：pred-LL(k) 》中找到。

推荐阅读