如何消除以下語法中的左遞歸？

Question

這裏的語法，這是爲了描述嵌套括號的語言用逗號分隔符：

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

一些更多的字符串的例子，我期望語法接受和拒絕：

接受：

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

拒絕：

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

Answer 1

手工完成：

L :: = { L } | { L }, | , L | ＆小量;

或者，而不只是即興發揮我們可以用一個更系統的方法，並應用從維基百科的算法removing immediate left recursion：

大號:: = {大號}大號 | L
L :: =＆lt; | , L L

Answer 2

首先，該語法不會接受您的第一個示例，因爲它要求逗號位於左大括號之後和大括號之前。我建議重寫它爲

L::= {L} | ,L 

這不會擺脫左遞歸，但它至少會匹配您的可接受的答案。