كيف يمكنني القضاء على العودية الأيسر في القواعد التالية؟

Question

إليك القواعد النحوية، والتي من المفترض أن تصف لغة من الأقواس المتداخلة مع فواصل كمحددين:

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

بعض الأمثلة الأخرى من الأوتار كنت أتوقع أن يقبل القواعد ورفضه:

قبول:

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

يرفض:

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

Answer 1

القيام به باليد:

L :: = { ل } | { ل } , | , ل |. ε.

أو بدلا من الجناح فقط يمكننا استخدام نهج أكثر منهجية وتطبيق الخوارزمية من ويكيبيديا إزالة العودية اليسار الفورية:

L :: = { ل } ل₁ | ل₁
ل₁ ::= ε | , ليرة لبنانية₁

Answer 2

بادئ ذي بدء، لن يقبل هذا النحو مثالك الأول، لأنه يتطلب أن تكون الفواصل بعد هدفين وثيق وقبل هدفين مفتوحين. أود أن أقترح إعادة كتابة ذلك

L::= {L} | ,L

هذا لن يتخلص من العودية اليسرى، لكنه سوف يطابق إجاباتك المقبولة على الأقل.