驗證是否一個語法是強LL（2）

問題Sudkamp的語言和機具 19.5要求讀者驗證語法驗證是否一個語法是強LL（2）

G : S' -> S## 
    S -> aSa | bSb | λ

強LL(2)。使用算法19.5.1被計算的FIRST和FOLLOW集可變S（第583，第3版）：

FIRST(2)(S) = {λ,aa,bb,ab,ba} 

FOLLOW(2)(S) = {##,a#,b#,aa,bb,ab,ba}

清楚的是，長度-2先行設置針對S規則將不分區長度-2先行設置S，由於規則S -> λ，這產生了長度爲2前瞻組包括FOLLOW(2)(S)：

LA(2)(S)  = {##,a#,b#,aa,bb,ab,ba} 

LA(2)(S -> aSa) = {a#,aa,ab} 
LA(2)(S -> bSb) = {b#,bb,ba} 
LA(2)(S -> λ) = {##,a#,b#,aa,bb,ab,ba}

現在是可能的，我已經在計算犯了一個錯誤FIRST，FOLLOW或LA(2)組爲G。但是，我相當確信我已經正確執行了算法。特別是，我可以恢復到它們的定義：

FIRST(2)(S) = trunc(2)({x : S =>* x AND x IN Σ*}) 
      = trunc(2)({uu^R : u IN {a,b}^*}) 
      = {λ,aa,bb,ab,ba} 

FOLLOW(2)(S) = trunc(2)({x : S' =>* uSv AND x IN FIRST(2)(v)}) 
      = trunc(2)({x : x IN FIRST(2)({a,b}^*{##})}) 
      = trunc(2)({##,a#,b#,aa,bb,ab,ba}) 
      = {##,a#,b#,aa,bb,ab,ba}

現在的問題是：爲什麼是語法強LL(2)。如果S規則的長度爲2的超前集合沒有將長度爲2的超前集合劃分爲S，那麼文法應該爲而不是爲強LL(2)。但我無法達成書中預期的結論。我不瞭解什麼？

來源

2011-06-18 danportin

我使用[給予我的學生的算法]進行了計算（http://www.suigeneris.org/UCABTI/Analisis%20Sintactico%20Descendente%20Predictivo.html），並且我獲得了相同的結果。查找勘誤表或聯繫作者。 – Apalala

我可能會那樣做。您給學生的算法與Sudkamp的算法類似。我找到了另一組算法，並再次獲得了相同的結果。我會在稍後看看這個定義，看看我能否證明這個語法是否是LL（2）。儘管感謝您的檢查。 – danportin

這是一個解決方案。上面給出的語法G不是很強LL(2)。要想看到這一點，回想一下強大的LL(k)語法的定義。一個語法G是LL(k)一些k > 0如果，每當有兩個最左邊的推導

S =>* u1Av1 => u1xv1 =>* uzw1   S =>* u2Av2 => u2yv2 =>* u2zw2

其中ui,wi IN Σ*爲i IN {1,2}和|z| = k，然後x = y。考慮在上述語法G下面最左邊的推導：

S =>* aaSaa## (u1 = aa, v1 = aa##) S =>* baSab## (u2 = ba, v2 = ab##) 
    =>1 aaaa## (x = λ)     =>1 baaSaab## (y = aSa) 
    =>* aaaA## (z = aa, w1 = aa##)  =>* baaaab## (z = aa, w2 = ab##)

推導滿足強LL(2)語法的定義的條件。但是，λ \= aSa，因此G不是很強LL(2)。

很明顯，我們可以建立很多最左邊的派生圖，證明G不是很強LL(2)。但還有其他幾個原因，G不是很強LL(2)。例如，顯然G不能被確定性下推自動機識別，因爲沒有辦法確定何時開始從堆棧中移除元素。

來源

2011-06-21 21:39:59 danportin

我在辯論是否在答案部分發布該解決方案，或編輯原始帖子。如果有人能提供更好的解決方案，我會接受他們的答案。 – danportin

驗證是否一個語法是強LL（2）

回答

相關問題