遞歸下降vs.生成的解析器 - 效率

Question

手寫遞歸下降解析器（不可避免地LL（k））與生成的LALR解析器在性能方面的差異如何？我知道LALR解析器能夠處理比LL（k）更多的語法;不過，我打算手工編寫解析器，而遞歸下降似乎是最合適的選擇。是否有可能用手（合理可讀地）寫出任何其他類型的興趣？

N.B.我正在使用函數式語言進行尾部調用優化（F＃），所以[精心設計的]遞歸不會像其他語言那樣嚴重。

Answer 1

我認爲很大程度上取決於您嘗試解析的語言。有時會被忘記的另一部分表現是詞法分析（掃描）部分 - 它對性能有重要意義，因爲它處理的是字符而不是符號。遞歸下降是編寫解析器的第一次迭代，它使得解析語言的邏輯非常自然。我認爲如果解析語言適合（沒有左遞歸），你應該從遞歸下降開始。在這個階段選擇LALR的表現似乎是不成熟的優化。 你可以手寫一個chart parser，但我懷疑這是你的意思。用手寫LALR解析器是可能的，但是很乏味。

Answer 2

決定LALR和LL之間的表現在這一點上的原因聽起來像是一個不成熟的優化。解析時間很少是編譯器的瓶頸。如果我是你，我會根據你是否更自如地定義自下而上或自上而下的語法來選擇。個人而言，我發現LALR語法易於使用，而F＃的fsyacc集成（這是我學習解析的過程）使得將yacc集成到您的項目中非常容易。