LL（1）不能含糊

Question

如何證明LL（1）語法不能模糊？

我知道什麼是模糊語法，但不能證明上述定理/引理。

Answer 1

我認爲這幾乎是LL（1）定義的直接結果。通過矛盾嘗試證明;假設你有一個不明確的LL（1）語法，並尋找可以證明是真實的而不是真實的東西。作爲一個起點「你在處理輸入時總是知道什麼？」

由於這看起來像是一個家庭作業問題，而且實際上我還沒有完成上述問題，所以我會在上面簡單介紹一下。

Answer 2

證明沒有模棱兩可的語法可以是LL（1）語法。有關提示，請參閱http://www.cse.ohio-state.edu/~rountev/756/pdf/SyntaxAnalysis.pdf，幻燈片18-20。另見http://seclab.cs.sunysb.edu/sekar/cse304/Parse.pdf，頁碼。 11和之前。

Answer 3

這是我的初稿。它可能需要一些微調，但我認爲它涵蓋了所有的情況。我認爲許多解決方案是可能的。這是直接的證據。

（附註：很可惜SO不支持數學，例如在膠乳。）

證明

令T和N是末端和非末端符號的集。

讓下面保持

MaybeEmpty(s) = true <=> s ->* empty 
First(s) = X containing all x for which there exists Y such that s ->* xY 
Follow(A) = X containing all x for which there exists Y,Z such that S ->* YAxZ 

注意，一個語法是LL（1）如果下式成立每對製作A的 - > B和A - > C：

1. (not MaybeEmpty(B)) or (not MaybeEmpty(C)) 
2. (First(B) intersect First(C)) = empty 
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty 

考慮使用LL（1）的語言，其中A -> B和A -> C。 也就是說有一些終端TZ的字符串允許不同的分析樹進行多重派生。

假設左派生達到S ->* TAY ->* TZ。下一步可能是TAY -> TBY或TAY -> TCY。 因此，如果語言BY ->* Z和CY ->* Z都是不明確的。 （注意，由於A是任意的非終端中，如果沒有這樣的情況存在，語言非模糊。）

情況1：Z =空

通過LL的規則1（1）的語法，B和C中至多有一個可以得出空的（非模糊的情況）。

情況2位：Z是非空的，並且既不B或c中衍生出空

通過LL的規則2（1）的語法，以B和C的至多一個可以允許進一步的推導，因爲Z的引出端子不能同時在First(B)和First(C)（非含糊的情況）。

案例3位：Z是非空的，並且或者MaybeEmpty(B)或MaybeEmpty(C)

注意由LL的規則1（1）的語法，B和C不能同時獲得空。因此假設MaybeEmpty(C)爲真。

這給出了兩個子情況。

例3a：CY -> Y;和案例3b：CY ->* DY，其中D不爲空。

在3a中我們必須選擇BY ->* Z和CY -> Y ->* Z，但請注意，First(Y) subset-of Follow(A)。由於Follow(A)不與First(B)相交，因此只能進行一個派生（非歧義）。

在3b中我們必須選擇BY ->* Z和CY ->* DY ->* Z，但請注意First(D) subset-of First(C)。由於First(C)不與First(B)相交，因此只能進行一個派生（非模糊）。

因此，在任何情況下，派生只能通過可用產品之一進行擴展。因此，語法並不含糊。