Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[28]

1.S - aSb

2.S - ab

ELRM(G) имеет команды:

1)(Zo, ±, Z0) - (vo, Л, Zovo), vo = {01Л};

2)(vo, a, vo) - (v2, Л, voV2), V2 = {11--, 21-};

3)(v2,b, v2) - (v5, Л, v2v5), v5 = {22-};

4)(v2,a, v2) - (v4, Л, V2V4), v4 = {11b, 21b};

5)(v5, ±,vov2v5) - 2,vovi), vi = {02Л};

6)(v4, b, v4) - (vs, Л, v4vs), vs = {22b};

7)(v4,a, v4) - (v4, Л,V4V4);

8)(vs,b, v2v4vs) - (b, 2,v2vs), vs = {12-};

9)(vs, b, v4v4vs) - (b, 2, v4V7), vz = {12b};

10)(b, Л, vs) - (v6, Л, vsv6), v6 = {13-};

11)(v6, -, vov2v3v6) - (-, 1, vovi);

12)(b, Л,V7) - (vg, Л,V7V9), v9 = {13b};

13)(Vg, b, V2V4V7V9) - (b, 1, V2V3);

14)(vg, b, v4v4v7vg) - (b, 1, v4v7);

15)(-, Л,ZoVoVl) - (f, 0,Zo).

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

Будем называть эквивалентными преобразователи, которые допускают одинаковые множества входных цепочек, одинаково преобразуя каждую входную цепочку.

С помощью формул (10)-(12) нетрудно доказать индукцией по длине маршрута, что M(G) определяет маршрут T с начальной вершиной (Zo, Zo) и конечной вершиной (q, Z) тогда и только тогда, когда ELRM(G) определяет маршрут T" с теми же длиной, начальной вершиной, пометкой и выходом и конечной вершиной (v, Z), где либо v = q G £U{±}, либо v - прогноз, содержащий q. Следовательно, M(G) и ELRM(G) эквивалентны.

2.2.3. Построение по ELRM(G) недетерминированного слеванаправо анализатора. Как и M(G), ELRM(G) генерирует каждый разбор входной цепочки. Таким образом, ELRM(G) является недетерминированным анализатором. Придадим ему более обычную в теории синтаксического анализа форму таблиц, управ ляющих работой алгоритма анализа. Определим две таблицы анализа слева направо без возвратов и с заглядыванием вперед на один входной символ, близкие по организации к введенным в классической работе [Knuth 65]. Одну назовем таблицей действий и обозначим через AT(G), другую назовем таблицей переобозначений и обозначим через RT(G). Их строчки имеют соответственно вид (прогноз, входной символ, действие) и (прогноз, символ из V - {-L}, прогноз). Действие есть сдвиг или свертка, задаваемая номером правила, которое необ ходимо применить. Будем считать, что сдвиг маркера конца входной цепочки вызывает останов анализатора.

Название таблицы переобозначений связано с тем, что каждый прогноз ана -лизатора можно интерпретировать как новое обозначение некоторого символа грамматики Augm(G). Возможность такой интерпретации прогнозов позволяет хранить в магазине анализатора одни прогнозы, но мы, следуя сложившейся тра диции, будем считать, что в магазине хранятся пары вида (символ, прогноз).


Правила построения таблиц по преобразователю ELRM(G) таковы. Команда вида (10) определяет строчки

(v, a, v) G RT(G) и (v, a,) G AT(G).

Команда вида (11) определяет строчки

(v(0),Ap,v) G RT(G) и (v(np),a,p) G AT(G).

Команда вида (12) определяет строчки

(v(1),S,v(2)) G RT(G) и (v(2), ±, сдвиг) G AT(G).

Работу самого анализатора (назовем его ELR(1)анализатором, подразумевая обобщение LR(1)техники, и обозначим через A(G)) можно описать следующим образом.

Алгоритм 4. Один из вариантов обработки входной цепочки, которые имеет право выбрать недетерминированный ELR(1)анализатор A(G).

Вход. AT(G); RT(G); цепочка x, подлежащая анализу.

Выход. Последовательность П, представляющая правый вывод цепочки x в грамматике G, или сигнал неудачи.

Вспомогательные обозначения: input - очередной входной символ, next - символ, подлежащий засылке в магазин, top - верхний в магазине прогноз.

Метод. Пока не сдвигался маркер конца входной цепочки, выполнять: если 3 действие: (top,input, действие) G AT(G), то

если действие=сдвиг,

то (next := input, продвинуться на одну позицию во входной цепочке); если действие,

то (next := Ap; удалить из магазина np элементов, добавить в последовательность П номер p);

если 3п : (top, next,п) G RT(G),

то заслать в магазин пару (next,n),

иначе сигнализировать неудачу иначе сигнализировать неудачу.

Из конструкции данного алгоритма и его таблиц следует корректность A(G) в том смысле, что он заканчивает удачно для цепочек из

±L(G)± = L(Augm(G))

и только для них, формируя при этом разбор цепочки. Буква E в термине "ELR(1)-анализатор"указывает на обобщение техники LR(1) анализа на случай любой при веденной бесконтекстной грамматики.

Как видно, алгоритм A(G) совпадает с LR(1) алгоритмом, если пара (top, input) однозначно определяет действие, а (top, next) однозначно определяет прогноз. Другими словами, если преобразователь ELRM(G) является детерминирован -ным, то A(G) осуществляет LR(1)анализ. Нетрудно указать и переход от таблиц LR(1)анализа к магазинному преобразователю, совпадающему с ELRM(G). Та -ким образом, получаем следующее важное утверждение.


Теорема 7. Грамматика G является ЬРу(1)грамматикой тогда и только тогда, когда ELRM(G) - детерминированный преобразователь □

2.3. Некоторые приемы уменьшения анализаторов

2.3.1. Уменьшение анализатора, имеющего форму преобразователя.

ELRM(G) использует магазин явно чрезмерно, "пропуская"через него обозначение каждого прочитанного символа и каждого символа, полученного сверткой. В то же время в командах этого преобразователя состояния частично или полностью выражают информацию, черпаемую из магазина. Попытаемся модифицировать ELRM(G) так, чтобы магазин не использовался в тех случаях, когда достаточно состояний.

Ясно, что магазин необходим при наличии в грамматике самовставляющихся символов. Но иногда он нужен и в случае грамматики без самовставлений, чтобы правильно сформировать выход.

Далее M обозначает преобразователь ELRM(G) или результат некоторого его преобразования.

Пусть длины маршрутов T и T" равны. Пусть эти маршруты прочитывают оди -наковые входные цепочки и пишут одинаковые выходные. Пусть для любых T и T, i = 1, 2, 3, таких, что маршруты с одним номером имеют одну длину и верны равенства T = TiT2T3 и T = T[T2T33, T и Т/ прочитывают одинаковые входные цепочки и формируют одинаковые выходные. Тогда будем говорить, что T проеци -руется на T и при этом T22 является проекцией маршрута T2, а вершина beg(T22) является проекцией вершины beg(T2).

Пусть автомат M получен из автомата MM некоторым преобразованием. Пусть существует такая биекция

ф : Core(M) - Core(M),

что T Е Core(M) проецируется на ), причем родословные маршрутов T и ф) с элементарными предками имеют одинаковые длины и Tj проецируется на Tj, 1 < j < 5, для тех элементов (Ti,T2,T3,T4,T5) и (T[,T2,ЦT,Ц) этих родо -словных, которые имеют в них один и тот же порядковый номер. Тогда назовем преобразование автомата M в MM сохраняющим родословные. Из теоремы 1.4 (о развитии) следует

Лемма 17. Пусть преобразование M в M! сохраняет родословные. Тогда M и MM эквивалентны □

Заметим, что для сохраняемости родословных достаточно, чтобы проекции раз -личных вершин были различны, проекции цикла и нецикла были соответственно циклом и нециклом, проекции парных циклов также были парными циклами. Однако, эти условия не необходимы, как можно убедиться на примере магазинного автомата, определяемого командами

(po, a, Zo) - (pi, Zoa),

(pi,a, a) - (pi,aa),

(pi,b,a) - (p2, л;ь

(p2,b,a) - (ps, л;ь

(p3,b,Z0) - (f,Zo).



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]