☰

了解 l3regex 中的断言匹配

tag-icon • tag-icon l3regex
了解 l3regex 中的断言匹配

这个问题有点具体，超出了该l3regex库的官方界面，但我试图了解该库在这里究竟是如何工作的。

给出以下示例文档：

\documentclass{article}
\usepackage{expl3}

\begin{document}
\ExplSyntaxOn

\cs_set:Npn \prepare_regex:N #1 {
    \cs_set_nopar:Npn \l_tmpa_regex {
        \__regex_branch:n {
            \__regex_assertion:Nn \c_true_bool { \char`\^ \__regex_anchor:N \l__regex_min_pos_int }
            \__regex_class:NnnnN  \c_true_bool {\__regex_item_caseful_equal:n {97}}{1}{-1} #1
            \__regex_assertion:Nn \c_true_bool { X \__regex_break_true:w }
            \__regex_class:NnnnN  \c_true_bool { \use:c{__regex_prop_.:} }{0}{-1} \c_false_bool
            \__regex_assertion:Nn \c_true_bool { \char`\$ \__regex_anchor:N \l__regex_max_pos_int }
        }
    }
}

\cs_set:Npn \test_match:n #1 {
    #1:~
    \regex_extract_once:NnNTF \l_tmpa_regex {#1} \l_tmpa_seq {}{}
    \par
}
\ttfamily

greedy~match: \par
\prepare_regex:N \c_false_bool
\test_match:n { ab }
\test_match:n { aab }
\test_match:n { aaab }
\test_match:n { aaaa }

\medskip
lazy~match: \par
\prepare_regex:N \c_true_bool
\test_match:n { ab }
\test_match:n { aab }
\test_match:n { aaab }
\test_match:n { aaaa }

\ExplSyntaxOff
\end{document}

\prepare_regex:N只是为 分配一个正则表达式，\l_tmpa_regex该正则表达式相当于^a+.*$或的编译形式^a+?.*$，具体取决于传递的参数（贪婪匹配或惰性匹配）。此外，在 部分之前添加了一个始终成功的额外断言.*。为了查看断言在内部执行的顺序，我添加了一些将在匹配发生时输出的字符。输出是

在此处输入图片描述

这里有几件事我不明白：

  • 为什么这三个断言一遍又一遍地匹配，而^我认为断言应该只在匹配过程开始时执行，并且$只在匹配过程结束时执行。也许$应该执行几次来确定匹配的结束，但^绝对不是。
  • X为什么在 s系列的“边界”a跨越到s 时，断言不是在每次匹配时仅执行一次b？如果发生回溯（或任何等效用途），那么这将有某种意义，l3regex但事实并非如此，无论是贪婪版本还是懒惰版本。
  • ^$为什么所有匹配项的末尾都有一个单数？这对我来说完全没有意义，因为正则表达式甚至不允许^后面$没有X断言。
  • 惰性匹配会X为a字符串中的每个附加项添加一个，但奇怪的是，不会为最后一个添加。这是为什么？

幸运的是，l3regex它提供了一些调试输出，让我们可以更仔细地查看发生了什么。如果我们加载expl3并[enable-debug]使用以下代码片段与上面的示例一起使用

\prepare_regex:N \c_false_bool
\int_set:Nn \g__regex_trace_regex_int { 100 }
% Recall this tries to match "^a+.*$" greedily
\test_match:n { ab }
\int_set:Nn \g__regex_trace_regex_int { 0 }

我们得到类似于以下的调试输出（另请注意\typeout添加到正则表达式的 s）：

Trace: entering \__regex_build:N
Trace: regex new state L=0-> R=0-> M=1-> 2
Trace: regex new state L=0-> R=1-> M=2-> 3
Trace: entering \__regex_group_aux:nnnnN
Trace: regex new state L=1-> R=2-> M=3-> 4
Trace: entering \__regex_branch:n
Trace: regex new state L=2-> R=3-> M=4-> 5
Trace: regex new state L=2-> R=4-> M=5-> 6
Trace: regex new state L=4-> R=5-> M=6-> 7
Trace: regex new state L=5-> R=6-> M=7-> 8
Trace: regex new state L=6-> R=7-> M=8-> 9
Trace: regex new state L=7-> R=8-> M=9-> 10
Trace: regex new state L=8-> R=9-> M=10-> 11
Trace: leaving \__regex_branch:n
Trace: regex new state L=2-> R=3-> M=11-> 12
Trace: leaving \__regex_group_aux:nnnnN
Trace: \toks1={\__regex_action_start_wildcard: }
Trace: \toks2={\__regex_action_submatch:n {0<}\__regex_action_free:n {2}}
Trace: \toks3={\__regex_action_submatch:n {0>}\__regex_action_free:n {8}}
Trace: \toks4={\typeout {^}\char `\^\__regex_anchor:N \l__regex_min_pos_int
               \__regex_break_point:TF {\__regex_action_free:n {1}}{}}
Trace: \toks5={\__regex_item_caseful_equal:n {97}
               \__regex_break_point:TF {\__regex_action_cost:n {1}}{}}
Trace: \toks6={\__regex_action_free:n {-1}\__regex_action_free:n {1}}
Trace: \toks7={\typeout {X}X\__regex_break_true:w
               \__regex_break_point:TF {\__regex_action_free:n {1}}{}}
Trace: \toks8={\use:c {__regex_prop_.:}
               \__regex_break_point:TF {\__regex_action_cost:n {0}}{}
               \__regex_action_free:n {1}}
Trace: \toks9={\typeout {$}\char `\$\__regex_anchor:N \l__regex_max_pos_int
               \__regex_break_point:TF {\__regex_action_free:n {1}}{}}
Trace: \toks10={\__regex_action_free:n {-7}}
Trace: \toks11={\__regex_action_success: }

Trace: state 1
Trace: state 2
Trace: state 4
^
Trace: state 5
Trace: state 6
Trace: state 5
Trace: state 7
X
Trace: state 8
Trace: state 9
$                <-- up to this point the output makes perfect sense to me
Trace: state 1
Trace: state 2
Trace: state 4
^
Trace: state 8
Trace: state 9
$
Trace: state 10
Trace: state 3
Trace: state 11

我不明白如何使用这些 和 状态映射来解析开始或输出L。NFAR执行M的轨迹一开始对我来说是有意义的。首先，它运行到状态 6，在那里它（由于贪婪匹配）尝试返回到状态 5 以匹配另一个a，但失败了，因此将我们带到了状态 9，在那里已经到达了字符串的末尾。

现在我不明白了。状态 9 以

\__regex_break_point:TF {\__regex_action_free:n {1}}{}

意思是“如果断言匹配，则进入下一个状态”，即状态 10，然后是状态 3，然后是状态 11，然后停止。但奇怪的是，它会从状态 9 跳回到状态 1，^再次检查断言，跳过a匹配（！），$再次检查，然后才进入最后阶段。

我确信这只是因为我对正则表达式匹配的工作原理缺乏了解。但对我来说，这至少是低效的，如果不是错误的，因为正则表达式被定义为查找贪婪匹配，并且应该能够在一次传递中完成。我仍然对此感到困惑。

相关内容