Проектирование трансляторов

Блок 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 ДМП-преобразо-

ватель смоделирует в обратном порядке ее правый вывод.


S=a(0)=>a(1)=>...=>a(m)=W


Это правый вывод цепочки W. Каждая правовыводимая цепочка

а(i) распределяется в памяти ДМП так, что ее открытая часть хра-

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

ки. Затем ДМП должен локализовать правый конец основы и сделать

свертку. Число принимаемых ДМП решений - два: решения о переносе

и о свертке (по конкретному правилу).


Грамматика будет LR(K) грамматикой, если для произвольного

правого вывода


S=a(0)=>a(1)=>...=>a(m)=Z


в каждой правовыводимой цепочки а(i), читая ее слева напра-

во, можно выделить основу и определить, каким нетерминалом надо

ее заменить, дойдя при этом не более чем до k-го символа, распо-

ложенного справа от правого конца этой основы.


ОПРЕДЕЛЕНИЕ:

Пусть G=(N,E,P,S) - КС грамматика.

Пополненной грамматикой, полученной из G, будем называть


G'=(N+S',E,P+{S'->S},S').


S' - новый начальный символ, не принадлежащий N.

S' -> S - это нулевое правило грамматики G', добавляемое для

того, чтобы свертку , в которой используется нулевое правило,

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

кается.


ОПРЕДЕЛЕНИЕ: пусть G - КС грамматика, а G' - полученная из

нее пополненная. Будем называть G LR(k) грамматикой для k >= 0,

если из условий:


1) S' -> aAw -> abw;

2) S' -> gBx -> aby;

3) FIRST(k;w) = FIRST(k;y) где k соответствует грамматике.


Из условий следует, что


aAy = gBx (т.е. a=g, A=B, x=y)


Интуитивно это определение говорит о том, что если abw и aby

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

FIRST(w)=FIRST(y), и A->b -последнее правило, использованное в

правом выводе цепочки abw, то правило A->b должно использоваться

также в правом разборе при свертке aby к aAy.

Так как A дает b независимо от w, то LR(k) условие говорит о

том , что в FIRST(w) содержится информация, достаточная для того,

что ab за один шаг выводится из aA. Поэтому никогда не может воз-

никнуть сомнений относительно того, как свернуть очередную право-

выводимую цепочку пополненной грамматики.

Кроме того, работая с LR(k)-грамматикой, мы всегда знаем,

допустить ли данную входную цепочку или продолжать разбор.

Если начальный символ S не встречается в правых частях пра-

вил, то в определении LR(k) грамматики вместо S' можно взять S, а

именно G будет LR-грамматикой, если из трех условий:


1: S=>aAw=>abw;

2: S=>yBx=>aby;

3: FIRST(w)=FIRST(y)


следует, что aAy=yBX.


В данном разделе мы кратко рассмотрим, как для каждой

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

тор, который ведет себя следующим образом.

Прежде всего, этот анализатор строится по пополненной грам-

матике G'. Ведет он себя также, как анализатор типа "пере-

нос-свертка", за исключением того, что после каждого символа

грамматики в магазин будет записываться специальный информацион-

ный символ, называемый LR(k)-таблицей, которые могут определить,

что нужно делать на очередном шаге-свертку или перенос, и в слу-

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


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

│состояния │ действие │ переход │

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

│ │ a b e │ S a b │

│ │ │ │

│ │ │ │

│ T0 │ 2 X 2 │ T1 X X │

│ │ │

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: