括号的匹配

Sun Aug 2, 2020

brace matching

RFC 145，作者 Eric J. Roode：Perl 正则表达式的括号匹配。

问题和建议 #

RFC 145 呼吁建立一个新的 regex 机制，以协助匹配像括号这样的配对字符，确保它们是平衡的。日常使用中或多或少都有很多“配对字符”。 ()、[]、{}、<>、«»、""、''，根据你的本地情况甚至还有 »«，或者在 Unicode 的花哨世界里还有 ⟦⟧ 以及很多很多。在本文中，我将采用 RFC 的标题，并将它们全部称为“括号”。

例如考虑字符串 ([b - (a + 1)] * 7)。我们可能希望提取所有的子公式。

[b - (a + 1)] * 7,
b - (a + 1),
a + 1

中的内容，并使用全局匹配的方式用一对大括号包围。请读者现在就尝试编写这样的 regex。

RFC 作者 Eric Roode 指出，在2000年的 Perl 中，这还是相当困难的。这个任务分为两部分。

确定一个开头的括号和结尾的括号的对应关系。
追踪嵌套层次和每个层次上的匹配括号。

当开口括号有多个选项时，第一个子任务在 regex 中变得很棘手。第二个子任务很难，有一个更深刻的原因，这个原因叫做 “Dyck语言”。Dyck 语言是所有正确配对的小括号字符串的集合（它们之间的假设内容被抹去）。它是计算机科学意义上的语言的原型例子，它不是有规律的，但仍然是无上下文的，这意味着它以某种方式需要一个堆栈来跟踪嵌套级别。当然，regex 比计算机科学意义上的正则表达式更强大，但这一事实可能仍然证明了为什么这是一件困难的事情。Eric Roode 认识到了这个在解析结构化数据中非常常见的任务应该有多容易，与它之间的差距，于是写了一个 RFC。

他提出了一个 use matchpairs 编译指令来解决子任务 №1，提供一个从开括号到收括号的映射。编译指令在词法作用域中被激活，并影响其中所有的 regex 匹配。对于子任务 №2，我们提出了两个新的 regex 元字符，\m 和 \M 用于匹配和记忆相应的括号。使用这些钩子，嵌套层的业务被卸载到 regex 引擎上。

规范和解决方案 #

RFC 145 被标记为"开发中"，这意味着它在 Perl 6 和现在的 Raku 规范中没有得到充分的解决。（关于模式匹配的启示录5包含了对 RFC 145 的回应）但是有一些相关的改进，我将在这一节中使用这些改进来展示如何在今天的 Raku 中处理一开始提出的问题。

使用编译指令来建立一个有效的括号表，然后使用"括号" regex 元字符的想法并没有实现，但是无论如何都要重新设计 regex 语言，设计者从括号匹配中推断出了一个新的用于嵌套结构的 regex 操作符，即 tilde。这个操作符的使用方法是这样的。

anon regex { '(' ~ ')' <body> }

并且它实现了两点：它将 body 和闭合括号转置，使这两个定界符相互靠近，即使 <body> 很长，它还为没有找到闭合括号时设置了错误报告。

我们可以利用这个新功能稍微改进一下 regex 结构，并免费获得错误报告，但它不会跟踪小括号的嵌套级别，如果开头的小括号有多个选项，它也不会为我们计算收尾括号。

要计算收尾括号，只要有一种方法来捕获开头的括号，并将其传递给一个函数，该函数的返回值被动态地插值到 regex 中就足够了。现在，在 Raku 的 regex 和 grammar 中，这很容易实现。

grammar Formula {
    # Registry of understood braces.
    constant %braces =
        '(' => ')',
        '[' => ']',
        '{' => '}',
    ;

    # A parametric token which matches the closing brace
    # corresponding to its argument.
    token closing ($opening) {
        "%braces{$opening}"
    }

    rule braced {
        $<opening>=@(%braces.keys) ~ <closing($<opening>)>
          [ <expr> {} ]
    }

    rule expr {
        [ <:Letter>+ || <:Number>+ || <braced> ]+ % <[+*/-]>
    }
}

关键的部分是 rule braced。¹ 我们捕获开头的括号，然后稍后从 %braces map² 中的查找中要求其对应的结尾括号。列表的 @(%braces.keys) 插值调用最长标记匹配，所以当存在多个前缀重叠的括号时，它会 DWIM。

注意，<expr> 和 <braced> 规则的相互递归使用保证了括号的正确嵌套，而不需要在 regex 引擎中为此专门设置一个齿轮。这属于 Raku 改进的 regex 结构和重用设施。是时候进行测试了。

grammar Formula { … }
sub braced-subexprs ($expr) { … }

braced-subexprs Q|([b - (a + 1)] * 7)|;

-- ([b - (a + 1)] * 7) ---------------------------------------------------------
Braces: ( * ) ||| Subexpr: a + 1
Braces: [ * ] ||| Subexpr: b - (a + 1)
Braces: ( * ) ||| Subexpr: [b - (a + 1)] * 7

总结 #

总而言之，在解析结构化数据时，括号匹配显然是有用的。Eric Roode 提出在 Perl 6 / Raku 中使之简单化。虽然这个功能没有以建议的形式实现，但任务确实变得更容易完成，代码也更容易阅读，特别是由于新的 regex 语法和 grammar 支持。

这还没完! #

如果你和我一样，对静态括号表稍有困扰，但对启发式方法无所谓，那么 Unicode 联盟可能是一个意想不到的盟友。Unicode Bidi_Mirroring_Glyph 属性给出了关于双向书写的提示，即当涉及多个脚本时，将文本放在屏幕上，其中一些脚本从左到右书写，另一些脚本从右到左书写。Raku 内置了对 Unicode 属性的支持，我们可以用这个属性让 Unicode 联盟为我们挑选收尾括号。

    sub unicode-mirror ($_) {
        join '', .comb.reverse.map: {
            .uniprop('Bidi_Mirroring_Glyph')
                or .self
        }
    }

    token closing ($opening) {
        "{ unicode-mirror($opening) }"
    }

    regex braced {
        :sigspace
        $<opening>=<:Symbol + :Punctuation>+ ~ <closing($<opening>)>
        [ <expr> {} ]
    }

&unicode-mirror 启发式将参数分割成字符，颠倒其顺序，然后选择其镜像字形（如果有定义的话），或者保持字符原样，然后将它们重新组合成一个字符串。例如，这个函数成功地将 <{ 变成 }>。

braced 在两个方面进行了调整：现在它接受任何符号和标点符号序列作为开括号，而且当它在消耗开括号时太过贪婪时，它已经变成了一个完全回溯能力的 regex。

有了这些调整，我们就可以疯狂地让 grammar 进行自由联想，匹配一切 “看起来像括号对” 的东西。

-- ([b - (a + 1)] * 7) ---------------------------------------------------------
Braces: ( * ) ||| Subexpr: a + 1
Braces: [ * ] ||| Subexpr: b - (a + 1)
Braces: ( * ) ||| Subexpr: [b - (a + 1)] * 7

-- (=^123^=) -------------------------------------------------------------------
Braces: (=^ * ^=) ||| Subexpr: 123

-- <<<123>> --------------------------------------------------------------------
FAILED

-- >123< -----------------------------------------------------------------------
Braces: > * < ||| Subexpr: 123

-- >123> -----------------------------------------------------------------------
FAILED

-- <{ (a + <b>) / !c! / e * »~d~« }> -------------------------------------------
Braces: < * > ||| Subexpr: b
Braces: ( * ) ||| Subexpr: a + <b>
Braces: ! * ! ||| Subexpr: c
Braces: »~ * ~« ||| Subexpr: d
Braces: <{ * }> ||| Subexpr: (a + <b>) / !c! / e * »~d~«

脚注 #

用于报告大括号子表达式的函数是这样的:

sub braced-subexprs ($expr) {
    # Get all submatches of the C<braced> subrule.
    class BracedCollector {
        has @.braced-subexprs;

        method braced ($/) {
            push @!braced-subexprs, $/
        }

        method braced-subexprs {
            @!braced-subexprs.unique(as => *.pos)
        }
    }

    say "-- $expr ", '-' x (76 - $expr.chars);

    my BracedCollector $collect .= new;
    say "FAILED" and return
        unless Formula.parse($expr, :rule<expr>, :actions($collect));

    for $collect.braced-subexprs -> $/ {
        say "Braces: $<opening> * $<closing> ||| Subexpr: $<expr>";
    }
}

¹ 如果你对 [<expr> {}] 中使用空块感到疑惑，这是由于 Rakudo 的 regex 引擎中的一个实现细节，它不会使捕获 $<opening> 用于后来的子规则 closing，除非它是被迫的。空块是强制的一种方式；参见 RT#111518 和 DOC#3478。

² 据我所知，在 2000 年左右 (也就是本 RFC 发布的时候) ，Perl 5.6 中加入了一个重要的功能，就是将函数调用闭包 $<op> 的返回值插值回来，而这个返回值可能取决于之前的捕获，在这种情况下，它的拼写是 (??{closing $+{op}})。