LL (1) проверка грамматики - PullRequest
Новая
       11

LL (1) проверка грамматики

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

Пусть G будет грамматикой такой, что: 

S -> aBa
B -> bB | \epsilon

, где \epsilon представляет пустую строку.

После вычисления FIRST и FOLLOW, есть лиспособ определить, является ли G LL(1) без обращения к таблице анализа?

1 Ответ

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

После вычисления наборов FIRST и FOLLOW для переменных G вы можете вычислить наборы прогнозирования длины 1 LA(1) для переменных и правил G. Тогда G является сильным LL(1), если выполняется следующее условие: 

LA(1)(A -> wi) partition LA(1)(A) for each variable A such that A -> wi is a rule.

Кроме того, вы можете доказать, что G является сильным LL(1) из определения сильной LL(k) грамматики без вычисления наборов FIRST и FOLLOW. Это часто проще и менее утомительно, чем вычисление FIRST и FOLLOW для небольших грамматик, таких как G.

У меня нет под рукой книги, поэтому могут быть ошибки в некоторых из этих определений или вычислений. Но так я бы подошел к проблеме. Вычисление наборов FIRST и FOLLOW дает: 

FIRST(1)(S) = trunc(1)({x : S =>* x AND x IN Σ*})
            = trunc(1)({ab^na : n >= 0})
            = {a}

FIRST(1)(B) = trunc(1)({x : B =>* x AND x IN Σ*})
            = trunc(1)({b^n : n >= 0})
            = {ε,b}

FOLLOW(1)(S) = trunc(1)({x : S =>* uSv AND x IN FIRST(1)(v)})
             = trunc(1)({x : x IN FIRST(1)(ε)})
             = trunc(1)(FIRST(1)(ε))
             = {ε}

FOLLOW(1)(B) = trunc(1)({x : S =>* uBv AND x IN FIRST(1)(v)})
             = trunc(1)({x : x IN FIRST(1)(a)})
             = trunc(1)(FIRST(1)(a))
             = {a}

Вычисление наборов предпросмотра длины 1 для переменных и правил дает: 

LA(1)(S) = trunc(1)(FIRST(1)(S)FOLLOW(1)(S))
         = trunc(1)({a}{ε})
         = trunc(1){a}
         = {a}
LA(1)(B) = trunc(1)(FIRST(1)(B)FOLLOW(1)(B))
         = trunc(1)({ε,b}{a})
         = trunc(1){a,b}
         = {a,b}

LA(1)(S -> aBa) = trunc(1)(FIRST(1)(a)FIRST(1)(B)FIRST(1)(a)FOLLOW(1)(S))
                = trunc(1){a}
                = {a}
LA(1)(B -> bB)  = trunc(1)(FIRST(1)(b)FIRST(1)(B))
                = trunc(1){b} 
                = {b}
LA(1)(B -> ε)   = trunc(1)(FIRST(1)(ε)FOLLOW(1)(b))
                = trunc(1)({ε}{a})
                = {a}

Так как LA(1)(B -> ε) и LA(1)(B -> bB) раздел LA(1)(B) и LA(1)(S -> aBa) тривиально, разделы LA(1)(S), G сильны LL(1).

...