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

Question

我正在使用 pest crate 在 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 }

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

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

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

Answer 1

PEG 中的选择运算符按如下方式排序和工作：给定 e = {alt1 | alt2}:

如果alt1可以匹配成功，则应用alt1，永远不会尝试alt2。
否则匹配alt2
如果alt2也匹配不上，e匹配不上

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

如果可以匹配到e1，后面也可以匹配到e2，则依次匹配。
否则e匹配失败

因此，如果您有类似 e = {(e1 | e2) ~ e3} 的内容，则会发生以下情况：

如果可以匹配到e1:
- 如果在e1之后可以匹配到e3，则两者依次匹配
- 否则e匹配失败
如果e1匹配不上，但是e2可以匹配：
- 如果在e2之后可以匹配到e3，则两者依次匹配
- 否则e匹配失败

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

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

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

您的 exp 规则是递归的，但它是通过 SOI 和 EOI 锚定的，因此它永远不会匹配整个输入以外的任何内容。这意味着递归调用必然会失败。要解决此问题，您应该从 exp 的定义中删除 SOI 和 EOI 并改用像 start = {SOI ~ exp ~ EOI}.

这样的主要规则

完成此操作后，您会收到一条错误消息，提示您的 exp 规则现在为 left-recursive，该害虫不支持该规则。要解决这个问题，您可以像这样用重复替换左递归（替换 inner_exp 和 exp ~ (...) ~ inner_exp 备选方案），其中 operand 是匹配中缀操作以外的构造的规则：

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

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

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

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

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

Pest doesn't parse a recursive grammar as I would expect

parsing

rust

pest