CODEWITHSUNDEEP
antlr4context-free-grammarleft-recursion
markonius
markonius

Reputation: 657

Removal of indirect left recursion (I don't understand formal symbols)

I've tried looking for answers to my solution but I can't seem to wrap my head around the generalized solutions. It doesn't help that I can't figure out which of my elements map to capital letters and which are supposed to be represented by small letters.

This is part of my grammar in Antlr:

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

binaryExpression: expression binaryOperator expression;

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

How would I go about removing the recursion in binaryExpression?

Upvotes: 1

Views: 327

Answers (1)

Bart Kiers
Bart Kiers

Reputation: 170268

By simply removing binaryExpression and using expression binaryOperator expression directly in expression:

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

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

EDIT

but now I lose the binary expression node in the AST and I have to detect it later in code

Then use labels:

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
    ;

Also, I'd like to gain a better understanding of how to remove this recursion instead of offloading it to Antlr

You can't. ANTLR simply doesn't allow such indirect left recursive rules. Only direct left recursion.

Upvotes: 1

Related Questions