时间戳

首页 > 解决方案 > Pest 没有像我期望的那样解析递归语法

parsing - Pest 没有像我期望的那样解析递归语法

问题描述

我正在使用害虫箱在 Rust 中实现递归语法：

id = _{ ASCII_ALPHA_LOWER ~ (ASCII_ALPHANUMERIC|"_")* }
integer = _{ (ASCII_NONZERO_DIGIT ~ ASCII_DIGIT*)|"0" }
real = _{ ((integer ~ "." ~ ASCII_DIGIT*) | (integer? ~ "." ~ ASCII_DIGIT+)) ~ (("e"|"E") ~ ("-"|"+")? ~ ASCII_DIGIT+)? }

unaryop = _{ "sin"|"cos"|"tan"|"exp"|"ln"|"sqrt" }

inner_exp = _{ real|integer|"pi"|id }

exp = { SOI ~ ( inner_exp | (exp ~ ( "+"|"-"|"*"|"/"|"^" ) ~ inner_exp) | ("-" ~ exp) | ("(" ~ exp ~ ")") | (unaryop ~ "(" ~ exp ~ ")") ) ~ EOI }

但是，我发现害虫并没有像我预期的那样解析语法。例如，2+3给我一个错误：

 --> 1:2
  |
1 | 2+3
  |  ^---
  |
  = expected EOI

似乎inner_exp正在解析选择，然后，当+遇到符号时，解析器不知道该怎么做。我很确定我编写exp ~ ( "+"|"-"|"*"|"/"|"^" ) ~ inner_exp选项的方式存在问题，但我不确定究竟是什么导致了问题。如果我用该选项替换该选项，exp ~ ( "+"|"-"|"*"|"/"|"^" ) ~ exp则会收到一条错误消息，指出该表达式是左递归的。我该如何修正这个语法？

标签： parsingrustpest

解决方案

PEG 中的选择运算符是有序的，其工作方式如下： 给定e = {alt1 | alt2}：

  • 如果alt1可以成功匹配，alt1则应用并且alt2从不尝试。
  • 否则alt2匹配
  • 如果alt2不能匹配，则匹配e失败

现在e = {e1 ~ e2}工作如下：

  • if e1can be match and e2can be match after it, 都按顺序匹配。
  • 否则e无法匹配。

所以如果你有类似的东西e = {(e1 | e2) ~ e3}，会发生以下情况：

  • 如果e1可以匹配：
    • ife3可以匹配 after e1, 都依次匹配
    • 否则，e匹配失败
  • 如果e1匹配失败，但e2可以匹配：
    • ife3可以匹配 after e2, 都依次匹配
    • 否则，e匹配失败

值得注意的是，如果e1成功和e3失败，它不会返回并尝试匹配e2。因此，如果两者e1和e2都可以产生匹配，但只e2允许e3事后匹配，(e1 | e2) ~ e3则会失败，而(e1 ~ e3) | (e2 ~ e3)会成功。

所以在你的语法中你有(inner_exp | ...) ~ EOI. 现在您的输入inner_exp会产生匹配，因此根据上述规则，其他替代方案从未尝试过，它会尝试匹配EOI下一个。EOI不匹配，所以整个规则都失败了，你会得到你得到的语法错误。

这解释了语法错误，但这不是您的语法存在的唯一问题：

您的exp规则是递归的，但它通过SOIand锚定EOI，因此它永远无法匹配整个输入之外的任何内容。这意味着递归调用必然会失败。要解决此问题，您应该从定义中删除SOIand ，取而代之的是一个主要规则，例如.EOIexpstart = {SOI ~ exp ~ EOI}

完成此操作后，您将收到一个错误，即您的exp规则现在是左递归的，害虫不支持该规则。为了解决这个问题，您可以用这样的重复替换左递归（替换 theinner_exp和exp ~ (...) ~ inner_expAlternatives）其中operand的规则匹配除中缀操作以外的构造：

operand ~ (( "+"|"-"|"*"|"/"|"^") ~ operand)*

顺便说一句，这也将解决您当前的问题，因为您现在不再有inner_exp在替代中缀表达式之前尝试过的替代方法。

您的最后一个问题是您根本没有考虑运算符优先级。inner_exp您可以通过在and之外引入额外的表达式“级别”来解决此问题exp，以便在同一规则中仅定义具有相同优先级的运算符，然后每个规则调用包含下一个更高优先级的规则来解析操作数。看起来像这样：

exp = { summand ~ (("+" | "-") ~ summand)* }
summand = { factor ~ (("*" | "/" | "%") ~ factor)* }
factor = { unary ~ ("^" ~ unary)* }
unary = { "-" ~ unary | unaryop ~ "(" ~ exp ~ ")" | primary }
primary = { "(" ~ exp ~ ")" | real | integer | "pi" | id }

推荐阅读