我怎样才能修复我写的语法

Question

我想出了以下强制优先级的语法：

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

其中 ID 可以是字母，num 可以是整数。

问题

我可以解析以下字符串：

a[i + 1]

我无法解析以下字符串：

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

我的问题是 A 引入了递归问题。因为我不想回溯。我必须通过重写语法来解决这个问题。我一直在看这个链接。但是，我尝试的修复也不起作用。有人可以帮忙吗？

尝试的解决方案：

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

但是，我认为这改变了我的语法定义，仍然是递归的，不允许我解决a[i] + 1 or a[a[i]*i]

附加信息：

我实际上正在 antlr 中实现这一点。我试图使用句法谓词来解决这个问题，但这没有帮助。也许我没有正确使用它们？

我将继续破解这个问题，但我越想越困惑。有人可以帮我吗？这是我遇到的一个概念问题，我认为如何正确设置没有回溯的语法。但是，如果我想正确制作自己的自定义工具，我将不得不这样做。

Answer 1

当您将索引移动到ID之后而不是L生产之后时，不会有问题：

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

这将解析您提供的所有 3 个输入示例：

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