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);

который бросает ParseException в коде как ScriptParser.ParseExpression("1 is null") или же ScriptParser.ParseExpression("1 in (1, 2, 3)"): "Parsing failure: Left recursion in the grammar.",

Как мне посмотреть Expression или существуют другие варианты решения этой проблемы?

Answer 1

Ответ, к сожалению, Sprache не может разобрать леворекурсивную грамматику. Я наткнулся на комментарии в исходном коде, рассказывающие о том, как при исследовании этого вопроса была удалена ошибочная поддержка леворекурсивных грамматик (именно так я и нашел ваш вопрос) - см. Исходный код.

Чтобы справиться с этой проблемой, вам нужно реорганизовать способ анализа. Например, если вы пишете простой анализатор выражений, это распространенная проблема, с которой вам приходится иметь дело. При поиске в Интернете много обсуждается, как убрать левую рекурсию из грамматики, в частности, для выражений.

В вашем случае, я ожидаю, что вам нужно сделать что-то вроде:

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)" я изменил его на вызов функции, и функция выбирает конкретный объект возвращается в зависимости от аргументов.