代币和规则的真正区别是什么？ [英] What's the real difference between a token and a rule?

问题描述

我被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规则更改为regex，这样允许回溯也会使其工作。

问题仍然存在，当token { }(与regex {:ratchet }相同)不匹配时，rule { }(与regex {:ratchet :sigspace }相同)怎么会匹配？

电子邮件地址中没有任何空格，因此无论出于何种目的，它都应该立即失败

推荐答案

此答案解释了问题，提供了简单的解决方案，然后深入探讨。

您的语法问题

首先，您的SO演示了似乎是一个特殊的错误或常见的误解。参见JJ对他提交的跟进问题的答复，和/或我的脚注。^[4]

把错误放在一边，您的语法指示Raku不匹配您的输入：

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

• 剩余输入('com')与剩余原子(<domain> '.' <tld>)不匹配；

• 对token生效的:ratchet表示语法引擎不会回溯到[<subdomain> '.']*原子。

因此，整体匹配失败。

最简单的解决方案

使您的语法有效的最简单的解决方案是将!追加到token中的[<subdomain> '.']*模式。

这将产生以下效果：

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

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

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

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

玩Raku、开发语法和调试

Nil作为已知(或认为)正常工作的语法的响应，您不希望在解析失败的情况下有任何更有用的响应。

对于任何其他方案，都有更好的选择，如my answer to How can error reporting in grammars be improved?中总结的。

特别是，对于玩耍、开发语法或调试语法，到目前为止最好的选择是安装免费逗号并使用其Grammar Live View功能。

修正语法；常规策略

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

• 向前解析，并进行一些回溯。(最简单的解决方案。)

• 向后解析。反写模式，并反转输入和输出。

• 后期分析分析。

向前分析并进行一些回溯

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

---

要打开整个令牌的回溯，只需将声明符切换为regex即可。regex类似于令牌，但特别支持像传统正则表达式那样进行回溯。

另一种选择是坚持使用token，并限制模式中可能回溯的部分。要做到这一点，一种方法是将!附加到原子后，使其回溯，显式覆盖token的整体&棘轮，否则该原子将在该原子成功时启动并匹配移动到下一个原子：

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

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

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

(您也可以使用r作为ratchet的缩写，即:!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> = ...捕获名称为<host>的以下原子。

  (如果原子本身是命名模式，则这通常是多余的，就像本例中一样--<dotted-parts>。但是"；点分部分&是相当通用的；要引用它的第二个匹配(第一个在@之前)，我们需要编写<dotted-parts>[1]。因此，我将其命名为<host>。)

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

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

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

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

---

有时希望在分析过程中进行部分或全部重新分析，以便在完成对.parse的调用时准备好重新分析的结果。

JJ展示了一种编码所谓操作的方法。这涉及：

• 创建包含其名称与语法中的命名规则相对应的方法的"；Actions"；类；

• 通知分析方法使用该操作类；

• 如果规则成功，则调用对应名称的操作方法(同时该规则保留在调用堆栈中)；

• 将与规则对应的Match对象传递给操作方法；

• 操作方法可以执行它喜欢的任何操作，包括重新分析刚刚匹配的内容。

直接内联编写操作更简单，有时甚至更好：

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 $/ }，它输出$/，即代码块出现时的Match对象。)

• 如果像我所做的那样，将代码块放在规则的末尾，它几乎等同于操作方法。

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

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

  (只是将其参数存储在$/的.made属性中，在此上下文中是当前的解析树节点。如果回溯随后丢弃了封闭的解析节点，make存储的结果将被自动丢弃。通常这正是一个人想要的。)

• foo => bar构成Pair。

• postcircumfix [...] operator索引其调用：

  • 在本例中，只有一个前缀.，没有显式的lhs，因此调用是&q；it&q；。它是由given设置的，即(请原谅双关语)$<host><parts>。

• 索引*-n中的*是调用者的长度；因此[ 0 .. *-3 ]是$<host><parts>的最后两个元素。

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

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

---

脚注

¹我真的以为我的前两个选项是可用的两个主要选项。自从我在网上遇到蒂姆·托迪以来，已经有大约30年了。你可能认为我现在已经记住了他的同名格言--有不止一种方法可以做到这一点！

²当心"pathological backtracking"。在生产环境中，如果您对输入或运行程序的系统有适当的控制，您可能不必担心故意或意外的DoS攻击，因为它们要么不会发生，要么会徒劳地关闭在不可用情况下可以重新启动的系统。但如果您做需要担心，即解析运行在需要保护其免受DoS攻击的机器上，则对威胁的评估是谨慎的。(请阅读Details of the Cloudflare outage on July 2, 2019以真正了解可能出错的地方。)如果您在如此苛刻的生产环境中运行Raku解析代码，那么您可能希望通过搜索使用regex、/.../(...是元语法)、:!r(要包括:!ratchet)或*!的模式来开始审核代码。

³.made有一个别名；它是.ast。我认为它代表AS解析T树或A标记的T子集T树，a cs.stackexchange.com question我同意。

⁴对于您的问题，这似乎是错误的：

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

更广泛地说，我认为token和rule之间的唯一区别是后者在each significant space处注入了<.ws>。但这意味着这应该是可行的：

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

但它没有！

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

部分原因是我猜测，自从第一个Raku语法原型通过Pugs获得以来的15年里，我一直找不到任何人报告这一点。这种猜测包括@Larry故意将它们设计成这样工作的可能性，这主要是像我们这样的普通普通人的误解，他们试图根据我们对资源--Roast、原始设计文档、编译器源代码等的分析来解释Raku为什么会这样做。

此外，考虑到目前的行为似乎是理想和直观的(除了与文档相矛盾)，我专注于将我的巨大不适感解释为一种积极的体验--在这段时间长度未知的过渡期内，我不明白为什么它是正确的。我希望其他人也能--或者，更好的，弄清楚到底发生了什么，然后让我们知道！

这篇关于代币和规则的真正区别是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！