4

Sudkamp のLanguages and Machinesの問題 19.5では、文法が

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

強いLL(2)です。変数のFIRSTおよびFOLLOWセットは、Sアルゴリズム 19.5.1 (p. 583、第 3 版) を使用して計算されます。

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

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

Sルールの長さ 2 の先読みセットが、 の長さ 2 の先読みセットを分割しないことは明らかです。これは、 で構成される長さ 2 の先読みセットを生成Sするルールによります。S -> λ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、文法はstrongであってはなりませんLL(2)。しかし、本が期待する結論に達することはできません。私は何を理解していませんか？

4

1 に答える 1

0

これが解決策です。上記の文法Gは強力ではありませんLL(2)。これを確認するには、強力なLL(k)文法の定義を思い出してください。左端に 2 つの派生がある場合は常に、文法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-21T21:39:59.933 に答える