Языки и трансляции. Мартыненко Б.К. - 226 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

224
Проверка A
4
={[S → Sa.Sb, a | b], [S → .SaSb, a | b], [S → ., a | b]}:
u∈ {a,b}, u∉
1
EFF
G
(Sb{a,b}) =
1
EFF
G
(SaSb{a,b}) = ∅.
Вывод: множество A
4
непротиворечиво.
Проверка A
5
={[S → SaSb., ε|a]} — множество непротиворечиво.
Проверка A
7
={[S → SaSb., a | b]} — множество непротиворечиво.
Заметим, что
1
EFF
G
(Sb) =
1
EFF
G
(SaSb)=∅ потому, что из цепочек,
начинающихся на нетерминал S, выводимы терминальные цепочки только
благодаря ε-правилу, используемому на последнем шаге. Таким образом,
получаемые цепочки не участвуют в образовании
1
EFF
G
.
Поскольку противоречивых множеств не найдено, то рассматриваемая
грамматика —
LR(1)-грамматика.
Теорема 3.4. Алгоритм 3.4 даёт правильный ответ, т.е. является
правильным алгоритмом тестирования
.
Доказательство. Утверждение теоремы является прямым следствием
теоремы 3.1, на которой и основывается алгоритм 3.4.
§ 3.6. Канонические LR(k)-анализаторы
Определение 3.12. Пусть G =(V
N
, V
T
, P, S) — контекстно-свободная грам-
матика и S — каноническое множество
LR(k)-ситуаций для грамматики G.
Для каждого множества A ∈ S определим
LR(k)-таблицу T(A ) = ( f, g), состоя-
щую из пары функций:
f: V
T
* k
→ {shift, reduce i, accept, error},
g: V
N
∪ V
T
→ {T(A ) | A ∈ S } ∪ {error}.
Функция
f определяется следующим образом:
а)
f (u) = shift, если существует [A → β
1
.β
2
, v]∈ A , β
2
≠ ε и u∈
EFF
G
k
(β
2
v);
б)
f (u) = reduce i, [A → β., u]∈ A и A → β есть i-е правило из множества
правил
P, i ≥ 1
8
;
в)
f (u) = accept, если [
S
′
→ S., ε]∈ A и u = ε;
г)
f (u) = error в остальных случаях.
Если
G — LR(k)-грамматика, то никаких неоднозначностей по пунктам а) и
б) не может быть.
Функция
g определяется следующим образом:
g(X) =
( ), ãäå GOTO( , ), åñëè ;
error, åñëè .
TX
′′ ′
=≠∅
′
=∅
AA A A
A
8
Напомним, что под нулевым номером числится правило S’ → S, пополняющее данную
грамматику G.

Страницы