Pest不像我所期望的那样解析递归语法

Question

我使用病虫害机箱在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

PEGs中的选择操作符是有序的，其工作方式如下:给定的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锚定的，所以除了整个输入之外，它永远无法匹配其他任何东西。这意味着递归调用必然会失败。要解决这个问题，您应该将SOI和EOI从exp的定义中删除，而应该有一个与start = {SOI ~ exp ~ EOI}类似的主要规则。

一旦您这样做了，您将得到一个错误，您的exp规则现在是左递归的，pest不支持这个错误。要解决这个问题，您可以使用这样的重复替换左递归(同时替换inner_exp和exp ~ (...) ~ inner_exp选项)，其中operand是一条与infix操作以外的构造匹配的规则：

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

顺便说一句，这也将修复您当前的问题，因为您现在已经没有在infix表达式之前尝试的inner_exp替代方案了。

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

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