左分解的自动语法转换;和左递归移除

Question

标准方法可用于将不是LL（1）的上下文无关语法转换为等价的语法。有没有可以使这个过程自动化的工具？

在以下示例中，我使用大写字母表示非终端，小写字母表示终端。

下左递归的非终端：

A -> A a | b 

可以转化为右递归形式：

A -> b A' 
A' -> NIL | a A' 

不过，请注意左递归的产生式规则确保表达式联想到左边，和右边的递归制作类似;所以语法修改也会改变表达的关联性。

的另一个问题是间接左递归，如下列：

A -> B a 
B -> A b 

左保也被用来确保只有一个前瞻令牌解析器要求。以下产品必须由两个令牌向前看：

A -> a b | a c 

这也可以重构;到：

A -> a (b | c) 

是否有任何软件工具可以自动执行这些语法转换;并因此产生一个适合LL（1）解析器的等价语法？

Answer 1

Haskell语法组合器库here允许将语法转换为非左递归形式。输入语法必须是解析表达式语法。