Удаление косвенной левой рекурсии (не понимаю формальных символов)

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

Это часть моей грамматики в Antlr:

expression
    : literal
    | unaryExpression
    | binaryExpression
    | priorityExpression
    | invocation
    ;

binaryExpression: expression binaryOperator expression;

binaryOperator
    : ADD
    | SUBTRACT
    | DIVIDE
    | CONCAT
    | EQUALS
    | NOT_EQUALS
    | LESS_THAN
    | GREATER_THAN
    | MULTIPLY
    ;

Как мне удалить рекурсию в binaryExpression?


antlr4 left-recursion context-free-grammar
person markonius    schedule 17.06.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Просто удалив binaryExpression и используя expression binaryOperator expression непосредственно в expression:

expression
    : literal
    | unaryExpression
    | expression binaryOperator expression
    | priorityExpression
    | invocation
    ;

binaryOperator
    : ADD
    | SUBTRACT
    | DIVIDE
    | CONCAT
    | EQUALS
    | NOT_EQUALS
    | LESS_THAN
    | GREATER_THAN
    | MULTIPLY
    ;

РЕДАКТИРОВАТЬ

но теперь я теряю узел двоичного выражения в AST, и мне приходится обнаруживать его позже в коде.

Затем используйте метки:

expression
    : literal                              #literalExpr
    | unaryExpression                      #unaryExpr
    | expression binaryOperator expression #binaryExpr
    | priorityExpression                   #priorityExpr
    | invocation                           #invocationExpr
    ;

binaryOperator
    : ADD
    | SUBTRACT
    | DIVIDE
    | CONCAT
    | EQUALS
    | NOT_EQUALS
    | LESS_THAN
    | GREATER_THAN
    | MULTIPLY
    ;

Кроме того, я хотел бы лучше понять, как удалить эту рекурсию, а не выгружать ее в Antlr.

Вы не можете. ANTLR просто не допускает таких непрямых леворекурсивных правил. Только прямая левая рекурсия.

person Bart Kiers    schedule 17.06.2018
comment
да, но теперь я теряю узел двоичного выражения в AST, и мне приходится обнаруживать его позже в коде, эффективно задерживая эту часть синтаксического анализа. Кроме того, я хотел бы лучше понять, как удалить эту рекурсию, а не выгружать ее в Antlr. - person markonius; 17.06.2018
comment
@MackThax проверьте мой EDIT - person Bart Kiers; 18.06.2018
comment
В дополнение к решению Барта, вот ответ от меня, где я описываю алгоритм для удалить прямую левую рекурсию. - person Mike Lischke; 18.06.2018