Главная Промышленная автоматика.

а а.

Рис. 5.21. Дерево остовного разбора.

типа „перенос-свертка" найти один разбор для каждой входной цепочки. Очень часто для целей трансляции достаточно новой грамматики и соответствующего ей анализатора. В таких ситуациях разбор методом операторного предшествования особенно прост и эффективен.

Определение. Пусть G = (N, 2, Р, 5) -операторная грамматика. Остовной грамматикой для G назовем грамматику -- ({5}, 2, Р, 5), содержащую каждое правило 5--Л.. для которого в Р найдется такое правило Л --К.. .У, что для iim

(1) Х,К,. если

(2) Л;-5, если K,.eN.

Но в Р не должно быть правила 5~>5.

Обращаем внимание читателя па то, что L{G)L (G) и, вообще говоря, L (G) может содержать цепочки, не принадлежащие L(G). Теперь опишем алгоритм типа „перенос - свертка", для грамматик операторного предшествования.

Алгоритм 5.19. Построение анализатора, использующего операторное предшествование.

Вход. Грамматика операторного предшествования G = (N, 2, Р, 5).

Выход. Алгоритм разбора Л = {[, g) типа „перенос-свертка" для грамматики G.

Метод. Пусть р обозначает S или е.

(1) /(ар, Ь) -перенос, если а<Ь или aJLb.

(2) / (ар, Ь) = свертка, если аУ>Ь.

(3) /($5, ©-допуск.

(4) / (а, le) ошибка в остальных случаях.

(5) g(ap6y, w) = i, если

(а) р - это S или е,

(б) а<Ь,

(в) отношение = выполняется между последовательными терминальными символами цепочки у, если они существуют,

(г) S-урЬу-правило с номером i грамматики G.

(6) g{ix, le*) -ошибка в остальных случаях. □

Применение алгоритма 5.19 к грамматике G продемонстрировано на примере 5.46. Для доказательства корректности алгоритма 5.19 нам понадобятся две леммы.

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

Доказательство. Элементарная индукция по длине вывода цепочки а. П

Лемма 5.8. Если а-правовыводимая цепочка операторной грамматики, то символ, расположенный непосредственно слева от основы, не может быть нетерминалом.

Доказательство. Если бы этот символ был нетерминалом, то правовыводимая цепочка, к которой свертывается а, содержала бы два смежных нетерминала. □

Теорема 5.26. Алгоритм A = {f, g), построенный алгоритмом 5.19, правильно выдает остовные разборы всех цепочек языка L {G).

Доказательство. В силу следствия из теоремы 5.25 первое встреченное отношение •> и предыдущее <• правильно выделяют основу. Лемма 5.7 оправдывает условие, что р может быть только 6 или е (а не любой цепочкой из 5*). Лемма 5.8 объясняет, почему в пункте (5) р включается в основу. □

5.4.4. ЯзыкФлойда-Эванса

То, чем мы сейчас займемся, не новый алгоритм разбора, а скорее язык, па котором можно описывать детерминированные (безвозвратные) алгоритмы нисходящего н восходящего анализов. Он называется языком Флойда - Эванса. С помощью этого синтаксического метаязыка было реализовано несколько комни-

Пример 5.46 представляет собой частный случай метода, работающего для многих грамматик, особенно для тех, которые определяют языки, являющиеся множествами арифметических выражений. Этот метод включает построение новой грамматики, получаемой из старой заменой всех нетерминалов одним нетерминалом и устранением цепных правил. Для грамматики операторного предшествования всегда можно с помощью алгоритма



гл. 5. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ

ляторов. Этот язык не совсем правильно называют еще языком продукций или правил, так как операторы языка не связаны с определенными правилами грамматики. Программа, написанная на языке Флойда-Эванса, определяет алгоритм разбора, принимающий решения под воздействием управляющего устройства с конечной памятью).

Анализатор, записанный на языке Флойда - Эванса, представляет собой список операторов определенного вида. Каждый оператор имеет метку, и этн метки можно рассматривать как состояния управляющего устройства. Предполагается, что разные операторы не могут иметь одну и ту же метку. Операторы работают над входной цепочкой и магазином и приводят к построению правого разбора. Текущее состояние процесса анализа можно представить в виде конфигурации

((?, $Х;„.. .Ху, йу.. я)

(1) q - метка текущего активного оператора;

(2) . .Ху - содержимое магазина, причем Ху - верхний символ (S-маркер дна магазина);

(3) йу.. .а - необработанная часть входной цепочки ($ используется также в качестве правого концевого маркера входной ленты);

(4) л - готовая к данному моменту часть выхода анализатора; ожидается, что полным выходом будет правый разбор входной цепочки для некоторой КС-грамматнки.

Оператор языка Флойда-Эванса имеет вид

<метка>: а\а-*-\ <действие>» <следугощая метка) причем метасимволов и * может не быть.

Допустим, что анализатор находится в конфигурации (L1, уа, ах, я)

и оператор L1 имеет вид L\. а 1 а

ЬЛ. ДРУГИЕ КЛАССЫ ГРАММАТИК

-* Р I выдача s » £2

) Можно было бы добавить, что это обстоятельство не дает окончательного обобщения понятия алгоритма типа „перенос - свертка". ЬК(/г)-алгоритм тоже использует управляющее устройство с конечной памятью, а дополнительную информацию хранит в магазине. Самой общей моделью алгоритма этого типа следовало бы считать ДМП-преобразователь. Однако в разд. 3.4 мы видели, что ДЛП-преобразователь вовсе ие обязан проводить разбор входной цепочки, делая свертки в соответствнн с грамматикой, для анализа которой он предназначен, как это делал ЬН(й)-алгоритм и алгоритмы из разд. 5.3 и 5.4.

Этот оператор говорит о том, что если наверху магазина расположена цепочка а и а - текущий входной символ, то надо заменить а на р, выдать цепочку s, сдвинуть входную головку на один символ вправо {на это указывает наличие символа *) и перейти к следующему оператору £2. Анализатор перейдет, таким образом, в конфигурацию {£2, ур, х, ns). Возможно, что ае. В этом случае текущий входной символ игнорируется, но головка сдвинется с него, если есть символ *.

Если оператор £1 нельзя применить из-за того, что ос не совпадает с верхней частью магазина или а не является текущим входным символом, то делается попытка применить оператор, непосредственно следующий в списке операторов за £1.

Обе метки у оператора тоже не обязательны (хотя для того, чтобы обозначать операторы в конфигурациях, предполагается, что они имеют имена). Если отсутствует символ ->, то магазин не меняется, и поэтому нет смысла указывать р. Если опущен символ v.-, то входная головка не сдвигается. Если опущена <следующая метка>, то после данного оператора применяется следующий в списке.

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

Первоначально анализатор находится в конфигурации {£, , w%, е), где W-анализируемая входная цепочка и L - выделенный оператор. Затем последовательно проверяются операторы, пока среди ннх не найдется применимый. После выполнения всех действий, предписываемых этим оператором, управление передается оператору, указанному меткой.

Анализатор продолжает работать до тех пор, пока не выполнится действие ошибка или допуск. Выход принимается во внимание только в случае допуска.

Мы покажем, как с помощью языка Флойда - Эванса описываются алгоритмы типа „перенос-свертка", но обращаем внимание читателя на то, что этот язык можно использовать и для реализации нисходящих алгоритмов разбора. Итак, предполагается, что люжно писать a - Kjaag и = а.уАа или р = ауЛаа, если есть ». При этом Л-уа-правило грамматики, для которой предпринимается разбор, а выход s-номер этого правила.

Язык Флойда - Эванса можно модифицировать так, чтобы действиями стали некоторые „семантические процедуры". Тогда вместо того, чтобы выдавать разбор, анализатор будет выполнять синтаксически управляемую трансляцию, вычисляющую перевод нетерминала А в терминах переводов составных частей цепочки а . Система такого рода описана Фельдманом [1966J.



1 выдача 6

1 -

1 выдача 3

1 -

1 выдача 4

: Г*

Е + Т#

1 -

выдача 1

1 -

выдача 2

(£)

выдача 5

1 -

допуск

Ш: $

1 -

ошибка

L11:

Для входной цепочки (a-f-n)»n анализатор пройдет такую последовательность конфигураций:

[Ы\, $, (й + а)*а$, e]I"[LO, $(, a + Q)*a$, £]

1-[L0, +й)»а$, е]

-[/2, ${Р+, а)«а$, 6] 1-LL3, $(Р + , 6]

h[M, 64]

hlX5, й)*а$, 64]

-[L6, $(Г + , n)*Q$, 64] а)*а$, 642] -[L0, + )*а$, 642] \-[L\, + )*а$. 642] h[L2, ${E+F), 6426] h [3, ${E + F), «a$, 6426] H[4, $(£ + Г), 64264] [-[/S, + *a$. 64264] 1-[L7, $(£), *a$. 642641]

[-[LS, $(£), *a$, 642641] \-[L2, Sfa$, 6426415] 1-[Z,3, $/*, a$, 6426415] h[£4, a$, 64264154]

hfzO, $, 64264154]

$7*, $, 64264154] -[L2, $r*PS> t. 642641546] (-[L4, , 6426415463]

l-[5, $7$, e, 6426415463] -[L6, $7$, £% 6426415463]

$£$, 64264154632] -[L8, $£$, , 64264154632] \-[L9, $£$, e, 64264154632] - допуск □

Заметим, что анализатор Флойда-Эванса можно промоделировать на ДМП-преобразователе. Поэтому любой анализатор Флойда-Эванса распознает только детерминированный КС-язык. Но распознаваемый пм язык может не совпадать с языком, определяемым грамматикой, для которой он должен строить разборы, поскольку передача управления операторами может привести к тому, что некоторые свертки не будут реализованы).

Пример 5.48. Пусть G состоит из правил

(1) 5-а5

(2) S-bS

(3) S-a

L (G) (a + b)* a. Приведем последовательность операторов, представляющую собой анализатор, который в соответствии с грамматикой G разбирает цепочки из языка Ь*а, но не допускает других цепочек:

1# -# Ь

aS\ -S bS\ -5 $S $-

LO LI L2 Z,3 L4 LS Lb L7

I выдача 3

{ошибка I выдача 1 [выдача 2 S$ I допуск j ошибка

L4 LO

L4 L4

1) Обсуждаемая здесь ситуация аналогична той, что рассматривалась в дополнении к разд. 5.1: анализатор Флойда - Эванса Мс JP"""" "° грамматике G, может быть ие адекватен G, т. е. L (Мо) {G).-/Р-"-перев.

Пример 5.47. Запишем на языке Флойда-Эванса анализатор для грамматики Go с правилами

{]) Е - Е + Т (2) Е-Т (3) ТТЕ (4) Т-Е (5) F~{E) (6) F-a

Символ # играет роль представителя любого символа. Предполагается, что с обеих сторон стрелки он обозначает один и тот же символ. Начальным оператором служит LI1.





0 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 [82] 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0035