在 Rust 中构建 Solidity 解析器，遇到“表达式不能失败”和“递归”错误

Question

我正在用 Rust 构建一个 Solidity 解析器。我正在使用 Pest Parser crate and am setting up my grammar.pest file to be very similar to the Solidity repo's Lexer/Parser.

我遇到了两个错误。第一个是错误提示：

            |
          41 | callArgumentList = {LParen ~ ((expression ~ (Comma ~ expression)*)? | LBrace ~ (namedArgument ~ (Comma ~ namedArgument)*)? ~ RBrace) ~ RParen␊
             |                               ^-----------------------------------^
             |
             = expression cannot fail; following choices cannot be reached

我的 grammar.pest.

中定义的此规则显示此错误

callArgumentList = {LParen ~ ((expression ~ (Comma ~ expression)*)? | LBrace ~ (namedArgument ~ (Comma ~ namedArgument)*)? ~ RBrace) ~ RParen
    }

以上语法试图复制 this rule in the Solidity official parser。

我相信我的语法与 Solidity 存储库的语法相匹配，但我不确定这里发生了什么。

其次，我遇到了递归错误。

        --> 131:6
              |
          131 |     (expression ~ LBrack ~ expression? ~ RBrack)␊
              |      ^--------^
              |
              = rule expression is left-recursive (expression -> expression); pest::prec_climber might be useful in this case

第二个错误是由于表达式的语法造成的，但是它必须是递归的。 Here is the rule from the Solidity Repo.

下面是我的 grammar.pest 实现。

expression = {
    (expression ~ LBrack ~ expression? ~ RBrack)
    | (expression ~ LBrack ~ expression? ~ Colon ~ expression? ~ RBrack)
    | (expression ~ Period ~ (identifier | Address))
    | (expression ~ LBrack ~ (namedArgument ~ (Comma ~ namedArgument)*)? ~ RBrack)
    | (expression ~ callArgumentList)
    | (Payable ~ callArgumentList)
    | (Type ~ LParen ~ typeName ~ RParen)
    | ((Inc | Dec | Not | BitNot | Delete | Sub) ~ expression)
    | (expression ~ (Inc | Dec))
    | (expression ~ Exp ~ expression)
    | (expression ~ (Mul | Div | Mod) ~ expression)
    | (expression ~ (Add | Sub) ~ expression)
    | (expression ~ (Shl | Sar | Shr) ~ expression)
    | (expression ~ BitAnd ~ expression)
    | (expression ~ BitXor ~ expression)
    | (expression ~ BitOr ~ expression)
    | (expression ~ (LessThan | GreaterThan | LessThanOrEqual | GreaterThanOrEqual) ~ expression)
    | (expression ~ (Equal | NotEqual) ~ expression)
    | (expression ~ And ~ expression)
    | (expression ~ Or ~ expression)
    | (expression ~ Conditional ~ expression ~ Colon ~ expression)
    | (expression ~ assignOp ~ expression)
    | (New ~ typeName)
    | (tupleExpression)
    | (inlineArrayExpression)
}

谁能帮我解决这两个错误？

Answer 1

链接的 Solidity 语法适用于 Antlr，而非 Pest，它使用不同的解析方法。所以没有理由期望语法在 Pest 中不加修改地工作。

显然，Antlr 有不同的限制。与 Pest 不同，Antlr 通过将其翻译成语义谓词来允许一些左递归，而 Pest 中似乎不存在该功能。相反，PEST 提供优先级攀升，可用于解析代数表达式中的 left-associative 运算符。该功能似乎没有完整记录，但有一些示例可以用作模型。

我不确定 Antlr 如何处理 callArgumentList 生产，但由于 Antlr 可以回溯，因此有多种可能性。 PEG 语法在成功后不会回溯，并且 ? 和 * 表达式总是成功，因为它们可以成功匹配任何内容。这在害虫书中有解释。所以错误信息是正确的；第二种选择永远不会被使用，因为第一种总是会成功，可能什么都不匹配。意图是整个参数列表都是可选的，因此可选性运算符放错了地方。它应该是（重新格式化以避免水平滚动）

callArgumentList = 
    {
      LParen ~
        (
          expression ~ (Comma ~ expression)*
        | 
          LBrace ~ (namedArgument ~ (Comma ~ namedArgument)*)? ~ RBrace
        )? ~
      RParen
    }

区别很细微——我所做的只是将第一个 ? 上移一个级别。

不过，我不知道这是否真的有效，因为支撑映射可能匹配 expression。在这种情况下，可能需要将备选方案以相反的顺序放置以获得正确的解析。（而且这也不能保证有效。这实际上取决于语法的其余部分。）

Answer 2

直接左递归的最简单修复方法是通过插入规则并根据优先级排序来对运算符优先级进行通常的重构。例如（为了简化而删除了许多替代项）：

expression = { array }
array = { arraycolon ~ ( LBrack ~ expression? ~ RBrack ) * }
arraycolon = { qualified ~ ( LBrack ~ expression? ~ Colon ~ expression? ~ RBrack ) * }
qualified = { arraycomma ~ ( Period ~ identifier ) * }
arraycomma = { multexpr ~ ( LBrack ~ (namedArgument ~ (Comma ~ namedArgument)*)? ~ RBrack ) * }
multexpr = { addexpr ~ ( (Mul | Div | Mod) ~ expression ) * }
addexpr = { andexpr ~ ( (Add | Sub) ~ expression ) * }
andexpr = { orexpr ~ ( And ~ expression ) * }
orexpr = { identifier ~ ( Or ~ expression ) * }
namedArgument = { identifier ~ Colon ~ expression }
LBrack = @{ "[" }
RBrack = @{ "]" }
Colon = @{ ":" }
Period = @{ "." }
Comma = @{ "," }
Mul = @{ "*" }
Div = @{ "/" }
Mod = @{ "%" }
Add = @{ "+" }
Sub = @{ "-" }
And = @{ "&&" }
Or = @{ "||" }
identifier = { (ASCII_ALPHANUMERIC | "_" | "-")+ }
WHITESPACE = _{ " " | "\t" | NEWLINE }
COMMENT    = _{ "#" ~ (!NEWLINE ~ ANY)* }

您也可以使用 Dragon 书中的常用重构来完成。或者，您甚至可以使用本机 Pest 功能来指定运算符优先级。

另一个问题是因为?-运算符在( expression ~ ( Comma expression ) * )?中的错误位置。讨论了类似的问题 here。解决方案是重构以删除 ?-operator，然后在正确的位置重新引入它：

x : l (a? | b) r;
   ==> (eliminate ?-operator, useless parentheses)
x : l ( | a | b) r;
   ==> (add ?-operator)
x : l ( a | b )? r ;

使用这个并重新分组，一个可能的解决方案是：

callArgumentList = { LParen ~ ( ( expression ~ ( Comma ~ expression ) * ) | ( LBrace ~ ( namedArgument ~ ( Comma ~ namedArgument ) * ) ? ~ RBrace ) )? ~ RParen }

在 Rust 中构建 Solidity 解析器，遇到“表达式不能失败”和“递归”错误

Building a Solidity parser in Rust, hitting an `expression can not fail` and `recursion` error

parsing

lexer

rust

solidity

pest