Проверка правильности грамматики LL (2) - PullRequest
Новая
       46

Проверка правильности грамматики LL (2)

4 голосов
/ 19 июня 2011

Проблема 19.5 из Языки и машины Судкампа просит читателя проверить, что грамматика 

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

сильно LL(2). Наборы FIRST и FOLLOW для переменной S вычисляются с использованием алгоритма 19.5.1 (стр. 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). Если наборы предпросмотра длины 2 для правил S не разбивают набор предпросмотра длины 2 для S, то грамматика должна , а не быть сильной LL(2). Но я не могу прийти к выводу, ожидаемому книгой. Что я не понимаю?

1 Ответ

0 голосов
/ 22 июня 2011

Вот решение.Приведенная выше грамматика 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 не может быть повторно определен детерминистскими автоматами, работающими при нажатии, потому что нет способа определить, когда начинать удаление элементов из стека.

...