grammar - 令牌和规则之间的真正区别是什么？

Question

由于它的内置语法，我被 Raku 所吸引，我想我会玩弄它并编写一个简单的电子邮件地址解析器，唯一的问题是：我无法让它工作。

在找到真正有效的东西之前，我尝试了无数次迭代，我很难理解为什么。

它归结为，正在更改token为rule。

这是我的示例代码：

grammar Email {
  token TOP { <name> '@' [<subdomain> '.']* <domain> '.' <tld> }  
  token name { \w+ ['.' \w+]* }
  token domain { \w+ }
  token subdomain { \w+ }
  token tld { \w+ }
}
say Email.parse('[e-mail]');

不起作用，它只是打印Nil，但是

grammar Email {
  rule TOP { <name> '@' [<subdomain> '.']* <domain> '.' <tld> }  
  token name { \w+ ['.' \w+]* }
  token domain { \w+ }
  token subdomain { \w+ }
  token tld { \w+ }
}
say Email.parse('[e-mail]');

确实可以正常打印

｢[e-mail]｣
 name => ｢foo.bar｣
 subdomain => ｢baz｣
 domain => ｢example｣
 tld => ｢com｣

我改变的token TOP只是rule TOP.

根据我从文档中收集到的信息，这两个关键字之间的唯一区别是空格rule在token. 如果这是真的，那么第一个示例应该可以工作，因为我想忽略模式的各个部分之间的空白。

去除碎片之间的空间

rule TOP { <name>'@'[<subdomain>'.']*<domain>'.'<tld> }

将行为恢复为打印Nil。

谁能告诉我这里发生了什么？

编辑：将TOP规则改为 a regex，允许回溯使其也可以工作。

问题仍然存在，为什么rule { }（与 相同regex {:ratchet :sigspace }）匹配时token { }（与 相同regex {:ratchet }）不匹配？

电子邮件地址中没有任何空格，因此出于所有意图和目的，它应该立即失败

标签： grammarraku

Answer 1

这个答案解释了问题，提供了一个简单的解决方案，然后深入。

你的语法问题

首先，您的 SO 证明了似乎是一个非凡的错误或常见的误解。请参阅 JJ 对他提出的跟进问题的回答和/或我的脚注。^[4]

将错误/“错误”放在一边，您的语法会指示 Raku与您的输入不匹配：

• 原子急切地从您的输入中[<subdomain> '.']*消耗字符串；'baz.example.'

• 剩余的输入（'com'）无法匹配剩余的原子（<domain> '.' <tld>）；

• 这:ratchet对tokens 有效意味着语法引擎不会回溯到[<subdomain> '.']*原子中。

因此整体匹配失败。

最简单的解决方案

使您的语法工作的最简单的解决方案是附加!到[<subdomain> '.']*您的token.

这具有以下效果：

• 如果任何剩余部分失败token（在子域原子之后），语法引擎将回溯到子域原子，丢弃其最后一个匹配重复，然后再次尝试前进；

• 如果匹配再次失败，引擎将再次回溯到子域原子，丢弃另一个重复，然后重试；

• 语法引擎将重复上述操作，直到剩下的token匹配项或没有[<subdomain> '.']原子的匹配项可以回溯。

请注意，添加!到子域原子意味着回溯行为仅限于子域原子；如果域原子匹配，但 tld 原子不匹配，则令牌将失败而不是尝试回溯。这是因为tokens 的全部意义在于，默认情况下，它们在成功后不会回溯到更早的原子。

玩 Raku、开发语法和调试

Nil可以作为已知（或认为）可以正常工作的语法的响应，并且在解析失败时您不希望有任何更有用的响应。

对于任何其他情况，有更好的选择，正如我对如何改进语法中的错误报告的回答中所总结的那样？.

特别是，要玩转语法、开发语法或调试语法，目前最好的选择是安装免费的 Comma 并使用其语法实时查看功能。

修正你的语法；一般策略

您的语法建议两个三个选项¹：

• 向前解析一些回溯。（最简单的解决方案。）

• 向后解析。把图案倒过来写，把输入和输出倒过来。

• 后解析解析。

向前解析一些回溯

回溯是解析某些模式的合理方法。但最好将其最小化，以最大限度地提高性能，即使如此，如果写得不小心，仍然会带来 DoS 风险。²

---

要为整个令牌打开回溯，只需将声明器切换为regex。Aregex就像一个令牌，但专门支持像传统正则表达式一样的回溯。

另一种选择是坚持token并限制可能回溯的模式部分。一种方法是!在原子之后附加 a 以使其回溯，显式覆盖token' 的整体“棘轮”，否则当该原子成功并且匹配移动到下一个原子时会启动：

token TOP { <name> '@' [<subdomain> '.']*! <domain> '.' <tld> }
                                         

另一种方法!是插入:!ratchet以关闭规则的一部分的“棘轮”，然后:ratchet再次打开棘轮，例如：

token TOP { <name> '@' :!ratchet [<subdomain> '.']* :ratchet <domain> '.' <tld> }  

（您也可以r用作ratchet, ie:!r和的缩写:r。）

向后解析

适用于某些场景的经典解析技巧是向后解析，以避免回溯。

grammar Email {
  token TOP { <tld> '.' <domain> ['.' <subdomain> ]* '@' <name> }  
  token name { \w+ ['.' \w+]* }
  token domain { \w+ }
  token subdomain { \w+ }
  token tld { \w+ }
}
say Email.parse(flip '[e-mail]').hash>>.flip;
#{domain => example, name => foo.bar, subdomain => [baz], tld => com}

对于大多数人的需求来说可能太复杂了，但我想我会把它包括在我的答案中。

后解析解析

在上面我提出了一个解决方案，它引入了一些回溯，另一个避免了它，但在丑陋、认知负荷等方面付出了巨大的代价（向后解析？！？）。

在 JJ 的回答提醒之前，我忽略了另一种非常重要的技术。¹只需解析解析的结果。

---

这是一种方法。我已经完全重构了语法，部分是为了更了解这种做事方式，部分是为了展示一些 Raku 语法功能：

grammar Email {
  token TOP {
              <dotted-parts(1)> '@'
    $<host> = <dotted-parts(2)>
  }
  token dotted-parts(\min) { <parts> ** {min..*} % '.' }
  token parts { \w+ }
}
say Email.parse('[e-mail]')<host><parts>

显示：

[｢baz｣ ｢buz｣ ｢example｣ ｢com｣]

虽然这个语法与你的匹配相同的字符串，并且像 JJ 的后解析，但它显然是非常不同的：

• 语法减少到三个标记。

• 该TOP令牌对通用令牌进行两次调用dotted-parts，并带有一个指定最小部分数量的参数。

• $<host> = ...捕获 name 下的以下原子<host>。

  （如果原子本身是一个命名模式，这通常是多余的，就像在这种情况下一样 -- <dotted-parts>。但是“dotted-parts”是相当通用的；并且引用它的第二个匹配项（第一个出现在之前@），我们需要写<dotted-parts>[1]。所以我通过命名来整理它<host>。）

• 该dotted-parts模式可能看起来有点挑战性，但实际上非常简单：

  • 它使用量词子句 ( ** {min..max}) 来表示任意数量的部分，只要它至少是最小值。

  • 它使用修饰符子句 ( % <separator>)，表示每个部分之间必须有一个点。

• <host><parts>从解析树中提取与规则中parts第二次使用的标记相关联的捕获数据。这是一个数组：.TOPdotted-parts[｢baz｣ ｢buz｣ ｢example｣ ｢com｣]

---

有时，人们希望在解析期间发生部分或全部重新解析，以便在调用.parse完成时准备好重新解析的结果。

JJ 展示了一种对所谓的动作进行编码的方法。这涉及：

• 创建一个“动作”类，其中包含名称对应于语法中命名规则的方法；

• 告诉 parse 方法使用该动作类；

• 如果规则成功，则调用具有相应名称的操作方法（同时规则保留在调用堆栈上）；

• 将规则对应的匹配对象传递给action方法；

• action 方法可以为所欲为，包括重新解析刚刚匹配的内容。

直接内联编写动作更简单，有时更好：

grammar Email {
  token TOP {
              <dotted-parts(1)> '@'
    $<host> = <dotted-parts(2)>

    # The new bit:
    {
      make (subs => .[ 0 .. *-3 ],
            dom  => .[      *-2 ],
            tld  => .[      *-1 ])

      given $<host><parts>
    }

  }
  token dotted-parts(\min) { <parts> ** {min..*} % '.' }
  token parts { \w+ }
}
.say for Email.parse('[e-mail]') .made;

显示：

subs => (｢baz｣ ｢buz｣)
dom => ｢example｣
tld => ｢com｣

笔记：

• 我已经直接内联了进行重新分析的代码。

  {...}（可以在任何可以插入原子的地方插入任意代码块（ ）。在我们有语法调试器之前的日子里，一个经典的用例是{ say $/ }打印$/匹配对象，因为它是在代码块出现的地方。）

• 如果将代码块放在规则的末尾，就像我所做的那样，它几乎相当于一个动作方法。

  （它将在规则完成时调用，并且$/已经完全填充。在某些情况下，内联匿名操作块是可行的方法。在其他情况下，将其分解为像 JJ 那样的操作类中的命名方法是更好的。）

• make是动作代码的主要用例。

  （make所做的只是将其参数存储在 的.made属性中$/，在这种情况下，该属性是当前的解析树节点。make如果回溯随后丢弃封闭的解析节点，则存储的结果会自动丢弃。通常这正是人们想要的。）

• foo => bar形成一个Pair.

• postcircumfix[...]运算符 索引其调用者：

  • 在这种情况下，只有一个.没有明确 LHS 的前缀，所以调用者是“它”。“它”是由 设置的given，即它是（请原谅双关语）$<host><parts>。

• 索引*中的是调用者的长度；除了 的最后两个元素之外的所有元素也是如此。 *-n[ 0 .. *-3 ]$<host><parts>

• 该.say for ...行以.made³结束，以获取maked 值。

• 'd 值是一个包含三对的make列表$<host><parts>。

---

脚注

¹我真的认为我的前两个选项是可用的两个主要选项。自从我在网上遇到 Tim Toady 已经有 30 年了。你会认为现在我已经记住了他的同名格言——有不止一种方法可以做到！

²当心“病态回溯”。在生产环境中，如果您对输入或程序运行所在的系统有适当的控制，则您可能不必担心故意或意外的 DoS 攻击，因为它们要么不会发生，要么会无用地关闭正在运行的系统在呈现不可用的情况下可重新启动。但是，如果您确实需要担心，即解析是在需要保护免受 DoS 攻击的机器上运行的，那么对威胁的评估是谨慎的。（阅读2019 年 7 月 2 日 Cloudflare 中断的详细信息真正了解可能出现的问题。）如果您在如此苛刻的生产环境中运行 Raku 解析代码，那么您可能希望通过搜索使用的模式来开始审核代码regex，/.../（元...语法），:!r（到包括:!ratchet) 或*!.

³有一个别名.made；它是.ast。我认为它代表A S parse Tree或An annotated Subset Tree并且有一个 cs.stackexchange.com 的问题与我一致。

⁴打高尔夫球，这似乎是错误的：

say 'a' ~~ rule  { .* a } # ｢a｣

更一般地说，我认为tokena和 a之间的唯一区别rule是后者<.ws>在每个重要空间处注入 a 。但这意味着这应该有效：

token TOP { <name> <.ws> '@' <.ws> [<subdomain> <.ws> '.']* <.ws>
            <domain> <.ws> '.' <.ws> <tld> <.ws>
} 

但事实并非如此！

一开始这把我吓坏了。两个月后写下这个脚注，我感觉不那么害怕了。

部分原因是我猜测自从第一个 Raku 语法原型通过 Pugs 可用以来的 15 年里我一直无法找到任何人报告这一点的原因。这种猜测包括@Larry 故意将它们设计为像它们一样工作的可能性，并且它是一个“错误”主要是当前像我们这样的普通人试图解释为什么 Raku 会基于它所做的事情的误解我们分析我们的资源——烤、原始设计文档、编译器源代码等。

此外，鉴于当前的“错误”行为似乎是理想和直观的（除了与文档相矛盾），我专注于解释我的极度不适感——在这个我不理解的未知长度的过渡时期为什么它做对了——作为一种积极的体验。我希望其他人也可以 - 或者，更好的是，弄清楚实际发生了什么并让我们知道！