LL（*）與PEG解析器：有什麼區別？

Question

我想知道ANTLR v3是否將其內部解析算法顯示爲「LL（*）」，它完全代表了PEG（解析表達式語法）解析器。

有區別嗎？

Answer 1

ANTLR article對於PEG是錯誤的。 LL（*）是DCFG（確定性上下文無關語法）的一個子集，它是CFG（上下文無關語法）的一個子集。

PEG可以表達上下文敏感的語法像A{n}B{n}C{n}，其中A和B和C都發生n倍。這裏的定義：

s := &(x C) A+ y/ε 
x := A x B/A B 
y := B y C/B C 

但是沒有辦法在CFG中定義這樣的語法（證明涉及泵引理）。所以PEG不是CFG的子集。 PEG是否是CFG的超集？我不知道。 LL（*）和PEG之間

兩個主要區別：

1. LL（*）只能先行一個DFA圖案，而PEG可先行一個遞歸模式。例如，在PEG中，您可以查找嵌套的parens，而LL（*）不能。

2. 在PEG的選擇操作/是優先選擇（或「佔有慾」），這意味着如果你有規則A/AB，它永遠不會到達右側AB。在規則A | AB的LL（*）中，可以匹配AB。

如果您的PEG語法沒有預見性，或者您的預覽模式可以縮減爲DFA，則可以將其轉換爲LL（*）。否則，這是不可能的。

Answer 2

根據該工具上市here ANTLR是一個充滿代表性的PEG解析器：

ANTLR，由特倫斯·帕爾一套行之有效的解析器生成器，支持廣泛的PEG特點，並結合packrat與LL解析技術解析。

Answer 3

在ANTLR中，您可以對語法中的所有生產規則啓用全局回溯，因此對於k >= 1，您可以解析與PEG的幾乎相同的結果。當然，由於所有潛在的回溯，解析器的運行時間會降低。以（某些）內存爲代價，您還可以啓用記憶，使其表現得像一個Packrat解析器，能夠以線性時間解析輸入。

所以不，沒有太大的區別w.r.t ANTLR和PEG/Packrat（啓用正確的選項！）。

Answer 4

ANTLR和PEG不一樣。這是一個相當理論化的問題，我認爲這將是最適合你參考Terrence Parr寫的this論文，他在這裏準確地指出了ANTLR和PEG之間的差異以及ANTLR LL（*）解析策略的一些優點。我不想讓自由來解釋他在那裏寫的東西，但是最好是閱讀整篇論文。