How to deal with nested expressions in grammar kit?

Question

I'm trying to write BNF file for my custom language intellij plugin. I'm getting confused with the rules for nested expressions. My custom language contains both binary operator expressions and array reference expressions. So I wrote the BNF file like this:

{
  extends(".*_expr")=expr
  tokens=[
    id="regexp:[a-zA-Z_][a-zA-Z0-9_]*"
    number="regexp:[0-9]+"
  ]
}

expr ::=  binary_expr| array_ref_expr | const_expr

const_expr ::= number
binary_expr ::= expr '+' expr
array_ref_expr ::= id '[' expr ']'

But when I tried to evaluate expressions like 'a[1+1]' , I got an error:

']' expected, got '+'

Debugging the generated parser code, I found that when analyzing an expression like

a[expr]

, the expression in the brackets must have lower priority than array_ref_expr, thus binary_expr will not be included. If I swapped the priorities of the two expressions, the parser will not analyze expressions like

a[1]+1

. I also tried to make them same priority, or to make one expression right associative, each doesn't work for some specific expressions.

What would I need to do?

Many thanks

Answer 1

Getting rid of the left-recursion in the plus should fix this.

file ::= expr*

expr ::=  plus_expr | expr_
expr_ ::= array_ref_expr | const_expr

plus_expr ::= expr_ '+' expr
const_expr ::= number
array_ref_expr ::= id '[' expr ']'

The expr ::= plus_expr | expr_ could also be expr_ ('+' expr)? but - to me - it makes more sense to use plus_expr so it gets its own node in the Psi tree.