Chomsky層次結構和LL（*）解析器

Question

我想解析一種編程語言。我閱讀了很多關於正式語言和喬姆斯基層次結構和ANTLR的內容。但是，我無法找到有關如何將ANTLR v3作爲LL（*）遞歸下降解析器接受到的語言與層次結構關聯的信息。

Chomsky類型如何與LL（*）混合？任何信息（在線，書籍，論文）非常感謝。

編輯：ANTLR的句法/語義謂詞和回溯如何映射到這裏？

Answer 1

的喬姆斯基層次基本上是：

1. 正規語言
2. 上下文無關文法
3. 上下文相關文法
4. 遞歸可枚舉（圖靈完成）文法

LL語法（和解析器）是上下文無關語法的一個子集。使用它們是因爲常規語言對於編程而言太弱，並且因爲一般的上下文無關語法分析器是O（n^3），這對解析程序來說太慢。 事實上，用助手函數來擴充解析器確實使它更強大。 The Wikipedia entry on LL parsers解釋了這一些。 The Dragon Book被認爲是編譯器的主要教科書，並且可以進一步解釋。

Answer 2

LL（*）是上下文無關語言的子集。然而，另一個問題是antlr可以解析，給出謂語和回溯，這擴大了它的能力。

注意，如果我們談LL（*），這意味着ANTLR v3的，而不是2