GLR解析算法資源

Question

I am writing a GLR parser generator並希望在互聯網和死樹種類（針對那些不熟悉怪胎說話的人的書籍）中關於此算法的資源提供一些建議。

我知道Bison可以生成GLR解析器，並且考慮到它在GPL下，我可以檢查它的代碼，但是如果對算法有完整的描述，那將會很好。

那麼，有沒有人知道我可以利用的任何優質資源？謝謝。

Answer 1

一些好東西我在網上以前也遇到過：

• 了一篇關於Elkhound，另一個開源GLR分析器：斯科特·麥克皮克，喬治C. Necula。 Elkhound: A Fast, Practical GLR Parser Generator。在會議編譯器的構造（CC04）論文集，2004年

四月和用於更詳細地：

• 的UCB/CSSD-2-1214 technical report，它是上述紙的擴展版本;
• 在Bison documentation引用的論文：Elizabeth Scott，Adrian Johnstone和Shamsa Sadaf Hussain。 Tomita-Style Generalised LR Parsers。 TR-00-12，倫敦大學皇家霍洛威學院計算機科學系，2000年12月。

我知道第三個開源的GLR解析器：DParser。

Answer 2

從我所知道的，它的功能與LALR解析器相同 - 除非遇到歧義。

當它，它基本上分爲對應於在該點的可能的選擇分離解析，並在串聯的與他們繼續 - 當解析失敗（由於遇到非法元件），它被簡單地丟棄，因爲它在早些時候的含糊不清之處肯定是錯誤的猜測。

最後，除了一個解析應該已經死了 - 倖存的一個是對這些模糊點的「正確」解析。

Answer 3

我所見過的，有圖片說明的算法的每個步驟的最好的說明，包含在這本書：

http://books.google.ca/books?id=05xA_d5dSwAC&lpg=PA381&dq=generalized%20deterministic%20parsers&pg=PA381#v=onepage&q=generalized%20deterministic%20parsers&f=false

對於僞代碼，去源：廣義LR分析富田，第70頁左右。 Farshi的論文包含一個簡潔的描述。

http://books.google.ca/books?id=PvZiZiVqwHcC&lpg=PP1&dq=generalized%20lr%20parsing&pg=PA70#v=onepage&q=&f=false

這是我嘗試了qb.js技術（qbasic in javascript）之一。

Answer 4

Adrian Johnstone在高級版本的GLR算法上發表了大量的工作。他的publications website可能會是一個有趣的資源。