Scala的解析器組合，二義性文法與剖析林

Question

我試圖讓解析器通過評估它們對用戶上下文/歷史和知識，從一個模糊的語法返回所有可能的分析結果（剖析林），然後從剖析林基礎。出於性能原因，這可能應該使用packrat解析器和搜索限制/上限參數來限制應用生產規則中遞歸調用的次數以避免無限循環。

作爲新Scala和它的解析器組合，我無法弄清楚如何做到這一點，或者是否可以在全部完成。有人可以幫忙嗎？非常感激。

最好的問候， 托馬斯·胡安

Answer 1

你不能做到這一點Scala的內置解析器組合。 Packrat組合器僅限於無歧義的語法。如果嘗試解決模糊問題，即使對於明確的路徑，您也會失去記憶功能並且分析複雜度變爲O（k^n）。所以，不要這樣做。

你想要的是一個正確處理歧義的解析器組合框架。據我所知，唯一的Scala框架是我的GLL combinators。語法幾乎是相同的Scala的解析器組合（其主要區別在於較高的arity功能工作正確），但輸出的是Stream[A]，其中A是的結果類型。因此，你會得到一個解析森林。請注意，結果實際上不是SPPF（共享打包解析林），所以如果您生成指數數量的結果，則該流將具有成比例的大小。這樣做是爲了保持結果類型的最大靈活性。

GLL組合子在最差的情況下爲O（n^3），即使對於病態歧義語法也是如此。在平均情況下，在解析軌跡明確的情況下，GLL組合器是O（n）。恆定的時間開銷目前有點過分，但優化是一個正在進行的項目。我們在生產中使用GLL組合器，編號爲Precog，所以您可以預期圖書館將繼續保持良好狀態。