c# - Sprache:语法中的左递归

Question

我正在为一种类似于 SQL 的语言开发解析器，但我在创建一些语言规则时遇到了问题，例如:expression IS NULL 和 expression IN (expression1, expression2, ...) 具有逻辑和数学运算符之间的优先级。

我上传了一个GitHub测试项目https://github.com/anpv/SpracheTest/但是这个变体并不好。
我尝试使用以下规则:

private static readonly Parser<AstNode> InOperator =
    from expr in Parse.Ref(() => Expression)
    from inKeyword in Parse.IgnoreCase("in").Token()
    from values in Parse
        .Ref(() => Expression)
        .DelimitedBy(Comma)
        .Contained(OpenParenthesis, CloseParenthesis)
    select new InOperator(expr, values);

private static readonly Parser<AstNode> IsNullOperator =
    from expr in Parse.Ref(() => Expression)
    from isNullKeyword in Parse
         .IgnoreCase("is")
         .Then(_ => Parse.WhiteSpace.AtLeastOnce())
         .Then(_ => Parse.IgnoreCase("null"))
    select new IsNullOperator(expr);

private static readonly Parser<AstNode> Equality =
    Parse
        .ChainOperator(Eq, IsNullOperator.Or(InOperator).Or(Additive), MakeBinary);

在 ScriptParser.ParseExpression("1 is null") 或 ScriptParser.ParseExpression("1 in (1, 2, 3) 这样的代码中抛出 ParseException )"): "解析失败:语法中的左递归。".

我如何预测 Expression，或者是否存在其他变体来解决这个问题？

Answer 1

不幸的是，答案是 Sprache 无法解析左递归文法。我偶然发现源代码中的评论谈到在研究这个问题时如何删除了对左递归语法的错误支持(这也是我发现你的问题的方式) - 请参阅 source code .

为了处理这个问题，您需要重新组织您的解析方式。例如，如果您正在编写一个简单的表达式解析器，这是您必须处理的一个常见问题。在网上搜索有很多关于如何从语法中删除左递归的讨论，尤其是对于表达式。

在您的情况下，我希望您需要执行以下操作:

term := everything simple in an expression (like "1", "2", "3", etc.)
expression := term [ IN ( expression*) | IS NULL | "+" expression | "-" expression | etc.]

或类似的——基本上——你必须自己展开递归。通过这样做，我能够解决我的表达式问题。我怀疑任何基本的编译器书籍可能都有关于如何“规范化”语法的部分。

它使构建从解析器返回的任何对象变得更加痛苦，但在 select 语句中我没有执行“select new Expression(arg1, arg2)”，而是将其更改为函数调用，并且函数根据参数决定返回的特定对象。