如何消除以下语法中的左递归？
这是语法，它应该描述一种以逗号作为分隔符的嵌套大括号的语言：
L ::= {L} | L,L |
我希望语法接受和拒绝的一些字符串示例：
接受：
{,{,,{,}},,{,}}
{{{{}}}}
{,{}}
拒绝：
{}{}
{,{}{}}
{{},{}
Here's the grammar, which is supposed to describe a language of nested braces with commas as delimiters:
L ::= {L} | L,L |
A few more examples of strings I'd expect the grammar to accept and reject:
Accept:
{,{,,{,}},,{,}}
{{{{}}}}
{,{}}
Reject:
{}{}
{,{}{}}
{{},{}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
手工完成：
L ::=
{L}|{L},| <代码>， L | ε或者，我们可以使用更系统的方法，并应用维基百科上的算法 删除立即左递归:
L ::=
{L}L1 | L1L1 ::= ε |
,L L1Done by hand:
L ::=
{L}|{L},|,L | εOr, instead of just winging it we could use a more systematic approach and apply the algorithm from Wikipedia on removing immediate left recursion:
L ::=
{L}L1 | L1L1 ::= ε |
,L L1首先，该语法不会接受您的第一个示例，因为它要求逗号位于右大括号之后和左大括号之前。 我建议将其重写为
这不会消除左递归，但它至少会匹配您可接受的答案。
First of all, that grammar won't accept your first example, since it requires the commas to be after the close brace and before the open brace. I would suggest to re-write it as
This won't get rid of the left recursion, but it will at least match your acceptable answers.