左分解的自動語法轉換;和左遞歸移除

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允許將語法轉換爲非左遞歸形式。輸入語法必須是解析表達式語法。