什麼是packrat解析？

Question

我知道並使用bison/yacc。但在解析世界中，圍繞packrat解析有很多嗡嗡聲。

這是什麼？它值得研究嗎？

Answer 1

Pyparsing是一個純Python解析庫，支持packrat解析，所以你可以看到它是如何實現的。 Pyparsing使用記憶技術來保存以前在輸入文本中特定位置的特定語法表達式的解析嘗試。如果語法涉及在該位置重試同一表達式，則會跳過昂貴的解析邏輯，並僅從記憶緩存中返回結果或異常。

這裏有更多關於pyparsing wiki的FAQ page的信息，其中還包括Bryan Ford關於packrat解析的原始論文的鏈接。

Answer 2

Packrat解析是一種提供漸近地更好的性能的方法對於parsing expression grammars（PEG）;專門針對PEGs，linear time解析可以得到保證。

實質上，Packrat解析只是意味着緩存子表達式在測試時是否與字符串中的當前位置匹配 - 這意味着如果當前嘗試將字符串適配到表達式失敗，則嘗試適應其他可能的表達式可以從已經被測試過的字符串中已知的子表達式的合格/不合格中受益。