3

我正在为类似于 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);

它会抛出ParseException类似ScriptParser.ParseExpression("1 is null")or的代码ScriptParser.ParseExpression("1 in (1, 2, 3)"): "Parsing failure: Left recursion in the grammar."。

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

4

1 回答 1

7

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

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

就您而言，我希望您需要执行以下操作：

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

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

它使构建您从解析器返回的任何对象更加痛苦，但是在选择语句而不是执行“选择新表达式（arg1，arg2）”中，我将其更改为函数调用，并且函数决定返回的特定对象取决于参数是什么。

于 2013-11-24T22:10:30.083 回答