最长 token 匹配

注意，下面进入糟糕区域，如果看不懂请查看英文原文!

S05-metasyntax/longest-alternative.t lines 53–460

因为 "longest-token matching" 是一个很长的短语, 我们会经常将这个概念叫做 LTM. 这个基本的概念就是人们在头脑中倾向于怎么去解析文本, 所以计算机应该像人一样尝试做同样的事情. 而使用 LTM 解析文本就是关于计算机怎样决定匹配一组备选分支中的哪一个备选分支的.

在 Perl 6 中, | 代表使用声明性的 longest-token 语义的逻辑备选分支.(你现在能使用 || 来标示旧的暂存的备选分支. 就是, | 和 || 现在在正则语法内的运作方式和在正则语法外的运作方式很像, 在正则语法外部, | 和 || 代表 junctional 和 短路的 OR. 这也包括事实上 | 的优先级比 || 的优先级高.)

在过去, Perl 中正则表达式是通过一个能回溯的 NFA 算法来处理的. 这很强大, 但是很多解析器通过并行地处理 rules , 而不是一个接着一个地处理, 工作起来更高效, 至少达到某种程度. 如果你看一下像 yacc grammar 这样的东西, 你会发现很多 pattern/action 声明, 其中的 patterns 被认为是并行的, 并且最终由 grammar 决定触发哪个 action. 虽然默认的Perl 解析角度是从上至下的(或许使用一个中间层的从下至上角度来处理操作符优先级), 这对用户理解 token 处理进行确定性很有用。所以, 为了 regex 匹配的意图, 我们把 tokens 模式定义为那些不含潜在副作用或自引用的能被匹配的模式。(因为空格在行转换时经常有副作用, 所以通常被这样的模式排除, 给予或采取一点向前查看。) 基本上, Perl 自动地从 grammar 中派生出一个词法分析程序, 而不需要你自己写一个。

为此, Perl 6 中的每个 regex 被要求能把它的纯模式和它的 actions 区分开, 并返回它的初始 token 模式的列表(包含由regex 的纯部分调用的 subrule 的 token 模式, 但是不包含多于一次的 subrule, 因为那可能会引起自引用, 这在传统正则表达式中是不被允许的。) 一个使用|的逻辑备选分支接收两个或多个这种列表并分发给匹配最长 token 前缀的备选分支。出现在第一位的可能是也可能不是那个备选分支。

然而, 如果两个备选分支以同样的长度匹配, 绑定首先由特异性打破。 以最长的固定字符串开头的备选分支胜出; 即一个精确的匹配被看作是比使用字符类更接近. 如果它不起作用, 绑定会由两个方法中的一个破坏. 如果备选分支在不同的 grammars 中, 那么标准的 MRO(方法解析顺序)决定首先尝试哪一个. 如果备选分支在同一个 grammar 文件中, 本文出现的更早的备选分支取得优先权. (如果一个 grammar 的 rules 被定义在不止一个文件中, 那么顺序是未定义的, 则必须使用一个显式的断言用于强制失败, 如果首先尝试错误的那个的话)

这个长的标记前缀大致相当于“令牌”在其他分析系统使用一个词法分析器的概念，但对于Perl这很大程度上是自动从语法定义一个偶然现象。然而，尽管是自动计算的，这一套标记可以由用户修改；各种内构造正则表达式的语法来告诉引擎，这是完成图案的部分开始的副作用，所以将这种构建用户控件被认为是象征性的，什么是不。被视为终止一个令牌声明并启动“行动”部分的结构的结构包括：
这种最长 token 前缀大致相当于在其它解析系统中使用词法解析程序的 "token" 标记, 但对于 Perl 这很大程度上是从 grammar 定义中派生的附带现象。然而，尽管是自动计算的, 这套 tokens 可以由用户修改; regex 中的各种结构声明性的告诉 grammar 引擎, 模式部分结束, 并开始进入副作用, 所以通过插入这样的结构, 用户控制什么是 token, 什么不是。终止 token 声明并开始模式的 "action" 部分的结构包括:

• 任何 :: 或 ::: 回溯控制 (而不是e : 肯定修饰符).
• 任何带有节俭匹配(使用 ?修饰符)量词化的原子。
• 任何 {...} action, 但不是含有闭包的断言。(空的闭包 {} 通常用于显式地终止模式的 pure 部分。) 一般的 **{...} 量词形式的闭包也会终止最长 token, 但是无闭包形式的量词不会。

• 任何诸如 || 或 && 按次序的控制流操作符.
• 作为前一点的结果，因为标准的 grammar 规则使用 || 定义空格, 最长的token 也由那 可能 使用那个规则匹配空格的 regex 或 rule 的任意部分终止, 包括通过 :sigspace隐式匹配的空格。（然而，token 声明明确允许通过在 token 中使用诸如 \h+ 或其它字符类这种低级原语来识别空格）
• Subpatterns（捕获）不终止token模式，但可能需要重新解析 token以找到Subpatterns的位置。同样地，在确定最长token之后断言可能需要被检查。（或者, 如果以任何一种方式模仿了 DFA 语义, 例如, 使用汤普森的NFA，可能可以知道什么时候触发断言而不使用backchecks。）

贪婪量词和字符类不会终止 token 模式。 诸如单词边界的零宽断言也不会。

因为这种断言可以是 token 的一部分, 词法分析程序引擎必须能从这种断言的失败中恢复, 并回溯到下一个最佳 token 候选者, 它可能等长或更短, 但是绝对不会当前候选者更长。

对于含有诸如 <?foo> 或 <?before \s> 这样的正向向前查看的模式, 这种断言会被认为比随后的模式更特殊, 所以向前查看的模式被当作最长 token 的最后一部分; 最长 token 匹配器会足够智能地把额外的 bit 当作是零宽的, 即, 重新匹配任何由向前查看遍历到的文本,当它(如果)继续匹配的时候。(实际上, 如果整个向前查看足够纯粹地参与 LTM, 再匹配可能仅仅优化掉 rematching, 因为向前查看已经在 LTM 引擎中匹配过了)

然而, 对于包含诸如 <!foo> 或 <!before \s> 这种否定向前查看断言的模式, 反面的才是真: 随后的模式被认为比该断言更特殊。所以 LTM 完全忽略了否定向前查看, 并继续从跟在否定向前查看后面的任何东西中查找纯粹模式。你可能会说, 正向向前查看对 LTM 是不透明的, 否地向前查看对 LTM 是透明的。 结论是,如果你想写一个对 LTM 是透明的正向向前查看, 你可以使用两个感叹号的否定: <!!foo> 来标示它。(优化器能自由地移除双否定, 但是不是透明性)。

奇怪的是，这 令牌 关键词具体不确定一个令牌的范围，除了一个令牌模式通常不匹配的空白，而空白是终止令牌的典型方式。
很奇怪, token 关键字不确定 token 的作用域, 除了作为一个 token 模式通常不做很多的空格匹配情况之外, 空格是终止 tokens 的原型方式。

初始token匹配器必须把区分大小写考虑在内（或任何其他规范化原语）并做正确的事, 即使传播到不具有相同的规范化的 rules 时。也就是说，它们必须继续代表较低规则能匹配的一组匹配。

|| 形式有旧的短路语义，而不会试图匹配其右侧, 除非它的左侧耗尽了所有的可能性（包括所有 | 可能性）。regex 中的第一个 || 让它左侧的 token 模式能从外部的最长 token 匹配器中访问, 但从最长 token 匹配隐藏的任何后续的测试。每一个 ||建立了一个新的最长 token匹配器。那就是, 如果你在 || 右侧使用 |，那么右侧为最长 token 处理这子表达式和任何被调用的 subrules建立了一个新的顶级作用域处理这个子表达式和任何所谓的规则。右边的最长 token 自动机是对于左侧的 || 或外部的含有 || 的 regex是不可见的。

大西瓜啊，翻译的狗屎一样，惨不忍睹！