46023 (Проектирование трансляторов), страница 5

│ │ +5 4+ │

│ │ │ │ │

│ │ +B D+ │

│ │ │ │ │

+А` +А` └──+──┘ │

│ │ ┌──/│\──┐ │

│ │ │ │ │ │

+1 +1 │ +B` │ │

│ │ │ │ │ │

│ │ │ +5 │ │

│ │ │ │ │ │

А А B В А А

Ф : BA ─> BDA B. .A

\./

./│\.

B D A

ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ПОРОЖДАЮЩИХ ГРАММАТИК

В ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ

Грамматики называются эквивалентными, если порождающие их

языки совпадают.

Теорема 1. Пусть в порожденной грамматике имеется одно или

несколько вхождений строки y в правые части порождающих правил.

Преобразование грамматики путем введения нового нетерминала Ф,

нового правила вывода Ф::=y и замена всех или части вхождений

строк y на вхождения нового символа порождает новую грамматику,

эквивалентную исходной.

G - грамматика.

Строка АВ, которая входит хотя бы в одну часть грамматичес-

кого правила, называется парой. Если А С R(А), В С L(В), то пара

рекурсивно-неоднозначна.

Грамматика, не содержащая рекурсивно-неоднозначных пар сим-

волов, называется рекурсивно-приведенной. Любая приведенная грам-

матика - рекурсивно-приведенная.

АЛГОРИТМ ПРЕОБРАЗОВАНИЯ РЕКУРСИВНО-НЕОДНОЗНАЧНОЙ ГРАММАТИКИ

В ГРАММАТИКУ ПРЕДШЕСТВОВАНИЯ

1. Находим множество правых символов. Выбираем все рекурсив-

ные символы грамматики (А R(А)). Грамматические правила имеют

вид: Ф::=(psi). Выделяем все вхождения этих символов в строки

psi, при условии, что они являются левыми частями пар. Для каждо-

го выбранного символа, имеющего такое вхождение, введем новый не-

терминальный символ А, новое правило вывода и заменим все выде-

ленные вхождения А на вхождения А`.

2. Для каждого нового правила А`::= А ищем другое правило

вида Ф ::= А, и если R(А) не содержит последнего символа строки,

то заменяем правило Ф ::= А на Ф ::= А`.

3. Находим множество левых символов. Выбираем все леворекур-

сивные символы В L(B), при условии, что В - правый член некото-

рой пары. Выделим все вхождения этих символов в строку (psi), при

условии, что эти вхождения являются правыми членами пар. Для каж-

дого В, имеющего такое вхождение, вводим В`, В`::= В и заменим

все вхождения В на вхождения В`.

4. Для каждого нового правила В` ::= В ищем в G другие пра-

вила вида Ф ::= В, при условии, что правые части этих правил сов-

падают. Если L(B) не содержит первого символа строки Ф, то заме-

няем правило Ф ::= В на Ф ::= В`.

5. Находим множество левых и правых символов для полученной

грамматики, находим матрицу отношений предшествования, если мат-

рица однозначна выход.

6. Перебирая все вхождения пар во всех строках (psi), отли-

чаем вхождения таких пар АiDi, где неоднозначность типа >=

имеется либо между Аi и В L(Di). Для каждого отличного вхождения

пары АiDi в строку (psi)m выделяем подстроку хАi, для нее вводим

нетерминал Nj и новое грамматическое правило вида Nj ::= xАi. В

правых строках грамматических правил выделенные вхождения цепоч-

ки xАi заменяем новым символом Nj. Если в одной строке в правой

части выделено несколько вхождений таких цепочек, то надо после-

довательно заменять сначала более длинные, а потом короткие. Если

в правых частях грамматического правила выделено несколько строк,

то замена выполняется сначала для самых длинных строк, потом для

самых коротких.

7. Потом повторяется п. 5.

8. Перебирая все вхождения пар в правых частях грамматичес-

ких правил, выбираем (отмечаем) пары АiDi, где имеется неодноз-

начность. Для каждого отмеченного вхождения вычисляем строку Di y.

Для каждой выделенной подстроки, отличной от других, вводит-

ся новый нетерминал вида Nj ::= Di y. Для всех выделенных под-

строк грамматика будет однозначной.

Грамматики предшествования.

L(U)={S/Эz(U=>Sz)}

R(U)={S/Эz(U=>zS)}

Si = Sj ::= Э F (F: U::=xSiSjy)

Si < Sj ::= Э F ((F: U::=xSiUly) & Si{-L(Ul))

Si > Sj ::= Э F ((F: U::=xUkSjy) & Si{-R(Uk)) v

Э F ((F: U::=xUkUly) & Si{-R(Uk) & Sj {- L(Ul))

Алгоритм.

Обозначения:

L - строка анализируемого текста;

L(k) - к-й символ L;

S - стек реализации процесса свертывания;

S(i) - i-й элемент стека S

u(l),w(l),fi(l),psi(l) - соответственно цепочки u,w,fi,psi

правила P(l);

│u(l)│,│w(l)│,│fi(l)│,│psi(l)│ - длины цепочек u,w,fi,psi;

n - индекс самого нижнего символа S(n), такого что

S(n).x.S(n+1);

m - указатель существования в S пропущенной основы;

│p│ - число правил в грамматике.

Блок 1. Инициирует работу алгоритма.

i=k=1; n=max; m=0; Si=1;

Блок 2. Обработка ошибок.

Блоки 3,4. Нахождение правой границы основы свертывания.

3: S(i) ? L(k) =,>< - 6

4: j=i=i+1;

S(i)=L(k);

k=k+1;

Блоки 5,6. Запоминают n.

5: n=i;

6: S(i).>i да - 5, нет - 8.

Блоки 8,9. Нахождение левой границы основы свертывания.

8: S(j-1) >< S(j), < - 7, = - 9

9: j=j-1;

Блок 7. Начальное значение номеру грамматического правила Р

l=0

Блок 10. Анализ завершения просмотра всех правил.

l=│p│ да - 12, нет - 11.

Блок 11. Переход на просмотр следующего правила.

l=l+1;

Блок 12 проверяет возможность анализа при отсутствии правил

вида (u fi, u psi) для свертывания выделенной основы.

m=0;

Блок 14 проверяет возможность запоминания выделенной основы

в S.

n=i;

Блок 16 - возврат на первую из пропущенных основ.

L(k-n+j)...L(k+1)=S(n)...S(i)

i=j=n;

m=0;

k=k-n+1;

Блоки 13,15,17 проверяют соответствие строк u(l), w(l), fi

(l) выделенной основе и контекстным строкам, ее окружающим.

ЛЕКЦИЯ 6

LR(k)-ГРАММАТИКИ И СООТВЕТСТВУЮЩИЙ АНАЛИЗАТОР

Анализ для LR(k) - грамматики называется методом Кнута.

LR(k)-анализатор - устройство из неограниченных вправо вход-

ной ленты, верхнего и нижнего магазинов.

На входной ленте помещается еще не обработанная правая под-

цепочка анализируемой цепочки. К анализируемой цепочке справа

приписано k маркеров.

В верхнем магазине - цепочки-символы состояний анализатора.

Состояния подбираются так, чтобы они соответствовали возможным

вариантам дерева вывода на различных тактах анализа.

В нижнем магазине - частично свернутые левые подцепочки

входной цепочки (обработанные анализатором).

На каждом такте работы анализатора может выполняться одно из

действий: сдвиг или свертка. После выполнения определенного коли-

чества тактов анализатор допускает или отвергает анализируемую

цепочку.

Выполнение каждого такта можно разбить на 2 этапа. На 1 -

преобразование информации нижнего (и, возможно, верхнего) магази-

нов. Информация для выполнения 1 этапа - правое состояние цепоч-

ки состояний (верхний магазин) и к левых символов не обработан-

ной части входной цепочки. Если действие - сдвиг, в нижний мага-

зин записывается терминал из левого символа входной цепочки. Вер-

хний магазин остается без изменений. Если действие - свертка, то

из нижнего и верхнего магазинов исключается по одинаковому числу

символов, в нижний магазин записывается нетерминал (правая часть

гр.правила). Входная цепочка - без изменений. Информация для

свертки - правые состояние и символ из верхнего и нижнего магази-

нов соответственно (после выполнения 1 этапа). Запись в верхний

магазин "переходного состояния".

Свертка соответствует случаю использования некоторого прави-

ла вывода порождающей грамматики. Символы, исключаемые из нижне-

го магазина, соответствуют правой, а символ, записываемый в мага-

зин - левой части грамматического правила.

ОПРЕДЕЛЕНИЕ: LR(k)-анализатор, соответствующий G=(Vt,Vn,P,S)

- LR(k)=(U,X,H,T,b1,b2,S0,Z0,Sr), где:

U - конечное множество состояний анализатора;

X - конечное множество входных символов, Х=Vt U # -маркер;

H - конечное множество H=(Vt U Vn U Z0),

Х=Vt U # - маркер;

T - {Q U (p,A)}, A C Vn,

p - положительное целое,

Q - сдвиг,

пара (p,A) - cвертка, с исключением p символов из

магазинов и записью в нижний магазин

символа А

k k

b1 - (UxX ) -> T, X - цепочки длины k над алфавитом X;

b1 - частично определенная функция, задающая первые этапы

тактов анализа b2 - (UxH) -> U;

b2 - частично определенная функция, задающая вторые этапы

тактов анализа;

S0 - S0 C U - начальное состояние;

Z0 - граничный маркер;

Sr - Sr C U, заключительное состояние.

Для любой LR(k) - грамматики можно построить LR(1) - грамма-

тику, допускающую тот же язык.

ОПРЕДЕЛЕНИЕ: Автомат с магазинной памятью (сокращенно МП-ав-

томат) - это семерка

P = (Q, X, Г, b, q0, Z0, F),

где:

Q - конечное множество символов состояний, представляющих

всевозможные состояния управляющего устройства;

Х - конечный входной алфавит;

Г - конечный алфавит магазинных символов;

b - отображение множества Q * (X U {e}) * Г в множество ко-

нечных модмножеств множества Q * Г";

q0 C Q - начальное состояние управляющего устройства;

Z0 С Г - символ, находящийся в магазине в начальный момент

(начальный символ);

F C Q - множество заключительных состояний.

ОПРЕДЕЛЕНИЕ: МП-автомат P=(Q,X,Г,b,q0,Z0,F) называется де-

терминированным (сокращенно ДМП-автоматом), если для каждых q C Q

и Z C Г либо

1) b (q,a,Z) содержит не более одного элемента для каждого

а С Х и b (q,e,Z) = 0, либо

2) b (q,a,Z) = 0 для всех а С Х и b (q,e,Z) cодержит не бо-

лее одного элемента.

Утверждение. Любой LR(k) - анализатор может быть преобразо-

ван в детерминированный МП-автомат.

При доказательстве этого утверждения используют свойство

анализатора записывать по одному символу в верхний и нижний мага-

зины. Исключаться из магазина эти символы могут только одновре-

менно и только на этапе свертки, следовательно верхний магазин

может быть исключен, если каждый символ нижнего магазина снаб-

дить индексом. Индекс соответствует тому состоянию, которое запи-

сывается в нижний магазин. Каждый символ нижнего магазина должен

иметь N модификаций, где N - число состояний анализатора, соот-

ветствующих этому символу.

Для любого языка, распознаваемого LR(k)-анализатором, сущес-

твует распознающий этот язык LR(1)-анализатор (класс языков,

распознаваемых LR(k)-анализатором, совпадает с классом языков

LR(1)-анализатора. Входит в класс несущественно неоднозначных

УКС-языков.

Функции b1 и b2 обычно задаются в виде общей таблицы, сос-

тоящей из конечного числа "рядов". Каждый ряд соответствуют неко-

торому состоянию и имеет следующую структуру:

- состояние;

- наблюдаемая цепочка;

- функция действия (b1);

- символ нижнего м-на;

- функция b2 (переходное состояние). Для заключительного

состояния Sr имеется сл. строка:

- состояние Sr;

- наблюдаемая цепочка - ##### - k раз - маркеры Z0;

- функция действия (b1) - допуск;

- символ нижнего м-на;

- функция b2 (переходное состояние). Таблица наз. анализи-

рующей таблицей LR(k)-анализатора.

┌──────────┬───────────────────┬─────┬───────────────┬──────┐

│ │ k │ │ │ │

│ U │ X │ b1 │ H │ b2 │

│ Состояние│ Наблюдаемая строка│ │ Символ нижнего│ │

│ │ │ │ магазина │ │

├──────────┼───────────────────┼─────┼───────────────┼──────┤

│ │ Xi1 │(p,A)│ Zi1 │ Si1 │

│ ├───────────────────┼─────┼───────────────┼──────┤

│ │ Xi2 │ Q │ Zi2 │ Si2 │

│ ├───────────────────┼─────┼───────────────┼──────┤

│ │ ... │(p,B)│ ... │ ... │

│ ├───────────────────┼─────┼───────────────┼──────┤

│ │ Xij │ Q │ Zij │ Sij │

│ ├───────────────────┼─────┼───────────────┼──────┤

│ │ ... │ ... │ ... │ ... │

└──────────┴───────────────────┴─────┴───────────────┴──────┘

LR(k)-грамматики образут широкий класс грамматик, анализи-

руемых естественным образом снизу вверх с помощью ДМП-автомата.

Пусть ах - правовыводимая цепочка какой-то грамматики при-

чем а - либо пустая цепочка либо оканчивается нетерминалом. Тог-

да а называется открытой частью цепочки ах , х - замкнутой. Гра-

ницу между а и х назовем рубежом.

Алгоритм разбора типа "перенос-свертка" можно рассматривать

как программу расширенного ДМП-преобразователя который проводит

разбор "снизу-вверх". Для данной входной цепочки W ДМП-преобразо-