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

UptoLike

ВУЗ: 

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

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

Рубрика: 

231
Аналогично из 2
’) следует, что [B → β
1
.β
2
, v]∈ ,
FIRST ( ).
G
k
vy∈
При
этом
22
222
FIRST ( ) FIRST ( ) FIRST ( ) FIRST ( )
FIRST ( ) FIRST ( ) FIRST ( ) EFF ( ).
GG G G
k
kkkk
GGGG
k
kkkk
ux y y
vvv
∈=β=β⊕ =
=β⊕ =β=β
Последнее равенство имеет место, так как β
2
∈ V
T
*
. Существование этих
двух LR(k)-ситуаций, допустимых для одного и того же активного префикса
αβ, означает нарушение необходимого и достаточного LR(k)-условия, что
противо-речит исходному предположению о том, что G — LR(k)-грамматика.
Следовательно теорема доказана.
Теорема 3.7. Пусть G = (V
N
, V
T
, P, S) — LR(k)-грамматика. Канонический
LR(k)-анализатор, построенный по G, выполняя разбор цепочки x∈ L(G), совер-
шает O(n) движений, где n = | x |.
Доказательство. Разбирая цепочку x∈ L(G), LR(k)-анализатор выполняет
чередующиеся движения типа сдвиг (shift) и свертка (reduce). Любое из этих
движений на вершине магазина устанавливает некоторую LR(k)-таблицу.
Очевидно, что число сдвигов в точности равно n. Каждому сдвигу может
предшествовать не более #T
сверток, где T — каноническое множество LR(k)-
таблиц (состояний)
анализатора. В противном случае какая-то из LR(k)-таблиц
появилась бы повторно. При неизменной непросмотренной части входной
цепочки это означало бы зацикливание анализатора. Тогда вследствие теоремы
3.5 существовало бы как угодно много правосторонних
выводов сколь угодно
большой длины одной и той же цепочки w, что означало бы неоднозначность
грамматики G. На основании теоремы 3.6 грамматика G не являлась бы LR(k)-
грамматикой,
что противоречило бы первоначальному предположению.
Итак,
общее число движений канонического LR(k)-анализатора N ≤ n + c × n =
= n × (c + 1) = O(n), где c ≤ #T;
c — константа, зависящая от грамматики.
Что и требовалось доказать.
Замечание 3.6. LR(k)-анализатор на ошибочных цепочках “зациклиться” не
может. Цепочка — ошибочная, если для некоторого её префикса не существует
продолжения, дающего цепочку из
L(G). Действительно, если бы анализатор
зациклился, прочитав только часть входной цепочки, то, как мы только что выяснили,
это означало бы, что грамматика
G не есть LR(k)-грамматика.
§ 3.8. Простые постфиксные
синтаксически управляемые LR-трансляции
Мы знаем, что простые семантически однозначные схемы синтаксически
управляемых трансляций с входными LL(k)-грамматиками определяют тран-
сляции, реализуемые детерминированными магазинными преобразователями.
Аналогичную
ситуацию интересно рассмотреть в отношении схем с LR(k)-грам-
матиками в качестве входных. К сожалению, существуют такие простые семан-
тически однозначные схемы на базе LR(k)-грамматик, которые задают трансля-
ции, не реализуемые детерминированными магазинными преобразователями.
()
G
k
V
α
β

Страницы