如何在以下语法中消除左递归? [英] How can I eliminate left recursion in the following grammar?

问题描述

这里是语法，应该用逗号作为分隔符来描述嵌套花括号的语言:

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:

接受:

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

拒绝:

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

推荐答案

手工完成:

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

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

或者，我们可以使用一种更系统的方法，而不是仅仅使用它，而是将Wikipedia的算法应用于

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 } L ₁ | L ₁
L ₁ :: =ε | , L L ₁

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

这篇关于如何在以下语法中消除左递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！