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可以匹配的话：
  • 如果e3之后可以匹配e1，则两者依次匹配
  • 否则e匹配失败
• 如果e1无法匹配，但e2可以匹配：
  • 如果e3之后可以匹配e2，则两者依次匹配
  • 否则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，因此它永远无法匹配除整个输入之外的任何内容。这意味着递归调用必然总是失败。要解决这个问题，您应该从 and 的定义中删除SOI和，取而代之的是像 这样的主要规则。EOIexpstart = {SOI ~ exp ~ EOI}

完成此操作后，您将收到一条错误消息，指出您的exp规则现在是左递归的，而 pest 不支持该规则。要解决这个问题，您可以用重复替换左递归，如下所示（同时替换 theinner_exp和exp ~ (...) ~ inner_exp替代项），其中operand是与中缀操作以外的结构匹配的规则：

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

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

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

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