How can I fix my grammar I wrote?

Question

I came up with the following grammar that enforces precedence:

A :   L ( '[' A ']' L* )*
L :   M (('+'|'-')M)*
M :   P (('*'|'/')P)*
P :   ID | NUM

where ID can be a letter and num is an integer.

Problem

I can parse the following string:

a[i + 1]

I cannot parse the following string:

a[i] + 1 or a[a[i]*i]

My problem is that A introduces recursion issues. Since I do not want to do backtracking. I have to fix this by rewriting the grammar. I have been looking at this link. However, my attempted fix does not work either. Can someone help?

Attempted Solution:

A : L ( '[' A ']')* | L*`  and let `Z = ( '[' A ']')*

However, I think this changes the definition of my grammar, is still left recursive and doesn't allow me to solve for a[i] + 1 or a[a[i]*i]

Additional Information:

I am actually implementing this in antlr. I tried to use syntatic predicates to fix this, but that didn't help. Perhaps I didn't use them properly?

I am going to continue to crack on this, but the more I think about it the more I get confused. Can someone please help me? This is a conceptual problem I am having I think with how to properly set up grammars that have no backtracking. But I am going to have to do this if I ever want to make my own custom tools properly.

Answer 1

You wouldn't have an issue when you move the index to come after an ID instead of after the L production:

A :   L
L :   M ( ('+'|'-') M )*
M :   P ( ('*'|'/') P )*
P :   ID I | NUM
I :   ( '[' A ']' )*

which would parse all of the 3 input examples you provided:

1. a[i + 1]
2. a[i] + 1
3. a[a[i]*i]