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

查看:4
本文介绍了代币和规则的真正区别是什么?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我被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('foo.bar@baz.example.com');

不起作用,它只是打印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('foo.bar@baz.example.com');

是否工作并正确打印

「foo.bar@baz.example.com」
 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功能。

修正语法;常规策略

您的语法建议两个三个选项1

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

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

  • 后期分析分析。

向前分析并进行一些回溯

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


要打开整个令牌的回溯,只需将声明符切换为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 'foo.bar@baz.example.com').hash>>.flip;
#{domain => example, name => foo.bar, subdomain => [baz], tld => com}

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

后期分析分析

在上面,我提出了一个引入一些回溯的解决方案,以及另一个避免回溯的解决方案,但在丑陋、认知负荷等方面付出了巨大的代价(向后解析?!?)。

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


这里有一种方法。我已经完全重组了语法,部分是为了更好地理解这种做法,部分是为了展示一些Raku语法特征:

grammar Email {
  token TOP {
              <dotted-parts(1)> '@'
    $<host> = <dotted-parts(2)>
  }
  token dotted-parts(min) { <parts> ** {min..*} % '.' }
  token parts { w+ }
}
say Email.parse('foo.bar@baz.buz.example.com')<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('foo.bar@baz.buz.example.com') .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 ...行以.made3结尾,以获取maked值。

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


脚注

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

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

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

4对于您的问题,这似乎是错误的:

say 'a' ~~ rule  { .* a } # 「a」

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

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

但它没有!

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

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

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

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

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆