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

UptoLike

ВУЗ: 

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

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

Рубрика: 

204
Определение 3.3. Грамматики, в которых существует несколько разных
правил, отличающихся только нетерминалами в левой части, называются
необратимыми.
В примере 3.4 мы имели дело с необратимой грамматикой. Причина, по
которой данная грамматика не LR, в том, что правый контекст основы, каким
бы длинным он ни был, не даёт возможности однозначно определить, в какой
нетерминал следует её сворачивать.
Пример 3.5. Рассмотрим грамматику, иллюстрирующую другую причину,
по которой она не LR(1) невозможность однозначно определить, что
является основой в правовыводимой сентенциальной форме:
1)
S → AB, 2) A → a, 3) B → СD, 4) B → aE, 5) С → ab, 6) D → bb, 7) E → bba.
В этой грамматике рассмотрим два правосторонних вывода:
Здесь
αβ = Aab, w = bb, β = ab, x = ε, y = ba,
bba
′
β
=.
И
хотя оказывается, что x ≠ y, а это является
нарушением условия LR(1) ― (см. лемму 3.1).
§ 3.3. LR(k)-Анализатор
Аналогично тому, как для LL(k)-грамматик адекватным типом анализато-
ров является k-предсказывающий алгоритм анализа, поведение которого
диктуется LL(k)-таблицами, для LR(k)-грамматик адекватным механизмом
анализа является LR(k)-анализатор, управляемый LR(k)-таблицами. Эти LR(k)-
таблицы являются строчками управляющей таблицы LR(k)-анализатора.
LR(k)-Таблица состоит из двух подтаблиц, представляющих следующие
функции:
f : V
T
*
k
→ {shift, reduce i, accept, error},
g : V
N
∪V
T
→ T ∪ {error},
где V
T
— входной алфавит анализатора (терминалы грамматики); V
N
—
нетерминалы грамматики;
T — множество LR(k)-таблиц для G. Оно строится
по пополненной грамматике
G
′
для LR(k)-грамматики G.
Алгоритм 3.1: действия LR(k)-анализатора.
Вход: G = (V
N
, V
T
, P, S) — LR(k)-грамматика; T — множество LR(k)-таблиц
для G; T
0
∈ T — начальная LR(k)-таблица; x∈ V
T
*
— входная цепочка.
Выход: π
R
— правосторонний анализ x.
Метод.
LR(k)-Анализатор реализует классический механизм “сдвиг-свёртка”,
описанный в параграфе §3.1. Его действия будем описывать в терминах кон-
β
α
β
y
rm rm rm rm
2) .S S AB AaE Aabba
′
⇒⇒ ⇒ ⇒
rm rm rm rm rm
1) ,S S AB ACD ACbb Aabbb
′
⇒⇒ ⇒ ⇒ ⇒
w
α
β
() () ,
FIRST FIRST
GG
kk
wyb==
β
’

Страницы