language-agnostic - 如何消除以下语法中的左递归？

Question

这是语法，它应该描述一种用逗号作为分隔符的嵌套大括号的语言：

L ::= {L} | L,L |

我希望语法接受和拒绝的字符串的更多示例：

接受：

{,{,,{,}},,{,}}
{{{{}}}}
{,{}}

拒绝：

{}{}
{,{}{}}
{{},{}

Answer 1

手工完成：

L ::= {L }| {大号} ,| ,大号 | ε

或者，我们可以使用更系统的方法并应用 Wikipedia 中的算法来消除立即左递归，而不是仅仅使用它：

L ::= {L }L ₁ | L ₁
L ₁ ::= ε | ,法线₁

Answer 2

首先，该语法不会接受您的第一个示例，因为它要求逗号在右大括号之后和左大括号之前。我建议将其重写为

L::= {L} | ,L

这不会摆脱左递归，但它至少会匹配您可接受的答案。