基於SPARK的解析器的性能如何？

Question

基於SPARK的解析器比基於PLY的解析器AFAIK更慢。但是速度有多慢？它們適用於工業級編譯器嗎？ 如果您有任何關於SPARK的利弊的話，我會很高興聽到。

Answer 1

這些解析器的速度大多是它們支持的語法的屬性。 SPARK支持Earley語法，PLY支持LALR（1）語法。關於每種語法風格的優缺點都有大量的信息，所以我只是在這裏提供一個快速的概述。

Earley和LALR解析器最大的區別在於它們如何處理語法中的重疊和含糊。

LALR（k）解析是確定性的。它只能處理語法中的重疊，可以在k個令牌的前瞻中解決。好處在於與LALR解析器兼容的語法的最壞情況運行時間爲O（n）。

Earley解析與更常見的GLR解析非常相似。他們可以處理無限的前瞻和歧義，但他們通過在每個重疊點或模糊點處將解析樹分成多個路徑來實現。這可能會導致解析器的工作量大大增加，因此Earley/GLR解析的最壞情況運行時間爲O（n^3）。

你使用哪個取決於你想要做什麼。 LALR解析器對速度來說是完美的，但Earley解析器允許比LALR解析器更靈活的語法。由於語言中含糊不清，C++不能被LALR解析器解析。它需要一個Earley/GLR解析器，並且是您爲什麼想要使用Earley/GLR解析器而不是LALR解析器的一個例子。