生成一個解析器程序生成的BNF

Question

我已經看到了兩種方法來解析：

1. 使用解析器生成像happy。這使您可以在BNF中指定您的語言，而不必擔心解析的複雜性。但是，由於它是一個預處理器，所以必須以文本方式編寫整個分析樹。

2. 直接使用解析器megaparsec。通過這種方法，你可以直接訪問你的代碼，這樣你就可以以編程方式生成你的解析器，但是你沒有得到快樂的簡單BNF規範的便利，並帶有優先註釋等。同樣，打印出一個BNF樹用於記錄文檔似乎也不是微不足道的您的解析代碼，除非在構建期間考慮到它。

我希望做的是這樣的：

1. 生成數據結構編程表示BNF。
2. 通過「喜歡」分析器生成器生成分析器。
3. 通過漂亮的打印機生成實際的BNF文檔。

我想這樣做的原因是，我正在處理的語法已經變得相當大，並且有很多重複，因爲它的許多構造與其他構造類似，但略有不同。如果可以通過編程方式生成而不是直接修改快樂的BNF規範，那麼它會改進維護工作，但我寧願不必從頭開發自己的解析器。

這裏有一個好方法的任何想法。如果我能夠生成一個數據結構並將其強制爲happy（因爲它可能會在解析BNF提要後生成它自己的內部結構），但happy似乎沒有庫接口。

我想我可以生成引爆的BNF，並通過餵養到快樂，但它似乎是一個來回轉換混亂的過程。更清潔的方法會更好。也許即使是一個BNF風格的擴展parsec或megaparsec？

Answer 1

最簡單的做法是使某些數據類型表示相關的語法，然後使用一些解析器組合器作爲（運行時）「編譯」步驟將其轉換爲解析器。不幸的是，大多數解析器組合器與解析器生成器相比效率較低和/或靈活性較差（在某些方面），所以這將是一種最低公分母方法。也就是說，grammar-combinators庫可能很有用，雖然它似乎沒有被維護。

有些庫可以在運行時生成解析器。我剛纔發現的一個是Grempa，似乎沒有被維護，但這可能不成問題。另一個選項（由Grempa創建的同一個人維護）是Earley，由於Earley解析器的製作方式，有明確的語法被處理成解析器是有意義的。 Earley解析當然是靈活的，但可能會被壓制（或者不是）。