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

Question

我正在用Rust构建一个Solidity解析器。我正在使用Pest解析箱，并设置我的语法。jquery文件与Solidity repo的Lexer/Parser非常相似。

我碰到两个错误。第一个错误是:

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

这个错误显示在my grammar.pest中定义的规则。

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

上面的语法试图在Solidity官方解析器中复制这个规则。

我相信我的语法可以匹配Solidity repo的语法，但是我不确定这里发生了什么。

第二，我得到一个递归错误。

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

第二个错误是由于表达式的语法，但是它必须是递归的。以下是来自Solidity Repo的规则:

下面是我的语法。害虫的实现。

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

直接左递归最简单的修复方法是通过插入规则并根据优先级排序来对操作符优先级进行通常的重构。例如(为了简化，删除了许多alt):

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 ) * )?中的错误位置引起的。这里讨论了一个类似的问题。解决方案是通过重构删除?-操作符，并在正确的位置重新引入它:

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 }

Answer 2

链接的Solidity语法适用于Antlr，而不是Pest，并且它使用不同的解析方法。因此，没有理由期望该语法在不修改的情况下在Pest中工作。

显然，Antlr有不同的局限性。与Pest不同的是，Antlr通过将左递归转换为语义谓词来允许左递归，而这一特性在Pest中似乎并不存在。相反，PEST提供优先级爬升，可用于解析代数表达式中的左结合运算符。这个特性似乎没有完整的文档记录，但是有一些例子可以作为模型使用。

我不确定Antlr如何处理callArgumentList生产，但由于Antlr可以回溯，有各种可能性。PEG语法在成功后不会回溯，?和*表达式总是成功，因为它们不能成功匹配任何东西。这在佩斯的书里有解释。所以错误信息是正确的;第二种选择永远不会被使用，因为第一个选择总是成功的，可能没有匹配。其目的是使整个参数列表都是可选的，因此可选操作符放错了位置。它应该是(重新格式化以避免水平滚动)

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

差异是微妙的——我所做的只是将第一个?向上移动一级。

我不知道这是否真的有效，因为有可能括号映射可以匹配expression。在这种情况下，可能需要将备选项以相反的顺序排列以获得正确的解析。(这也不能保证有效。这实际上取决于语法的其余部分。