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

- e.J. восходящий РАЭБОР С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ

" -. .1 II .1 -I-..- I -.......... .111 . -

В моменты сверток. Разумеется, правила типа (1) позволяют символам в любой момент . перемещаться из второго магазина в первый.

Конфигурацией двухмагазиниого анализатора Т называется тройка (а, р, п), где a$(NuS)*, P€(Nu2)*$, ая-цепочка пар, состоящих из целого числа и номера правила. Таким образом, п может быть частью разбора некоторой цепочки h3Z-(G). Мы пишем (а, р, я)!-j.(a, р, я), если

(1) aaag, PaPi, («а» Ра)-(V» б) -правило анализатора Т\

(2) а-ау, P = 6Pi;

(3) л = п, если («зрз)-(Vi б) -правило типа 1; если это- правило типа 2 и применяется i-e правило грамматики, то я = я(1. Я, где i-=la-Р).

Заметим, что верх первого магазина расположен справа, а второго магазина - слева.

Обычным образом по отношению определим отношения и Иг- Когда можно, будем опускать индекс Т.

Переводом, определяемым анализатором Г, назовем множество x(T){(w, л)($, ш$, £?)[-•(£, 5$, я)}. Назовем анализатор Т корректным для грамматики G, если для каждой цепочки wL{G) найдется такой ее восходящий разбор л, что (w, л) т (Т). Можно элементарно показать, что если {w, я)т(Т), то я - восходящий

разбор цепочки w.

Анализатор Т назовем детерминированным, если выполнено следующее условие. Пусть (а, р)-(у, 6i) и (а, Р)-Cta. я) - такие правила, что одна из цепочек aj, сс является суффиксом другой, а одна из цепочек Pi, Ра является префиксом другой; тогда У1 = У2 и 6i==62. Таким образом, для каждой конфигурации С существует не более одной такой конфигурации С, что С\~С.

Пример 6Л0. Рассмотри грамматику G с правилами

(1) S-aSA

(2) SbSA,

(3) S-*b

(4) А-а

Эта грамматика порождает иедетерминироваиный КС-язык \wba"\w{a-b)* тл n~\w\}.

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

вычитается потому, что цепочка а содержит концевой

1) Единица маркер.

Оп)еделение. Назовем цепочку пар вида (6.2.2) {о6о6щенным)Ш нисходящим разбором цепочки w. Ясно, что левый разбор-част! ный случай нисходящего разбора. Аналогично назовем обращение;-! цепочки вида (6.2.2), т. е. цепочку

(обобщенным) восходящим разбором цепочки ш. Таким образезм--! правый разбор-частный случай восходящего разбора.

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

6.2>2. Анализаторы с двумя магазинами

, В качестве модели некоторых алгоритмов с возвратами мы введем автомат с двумя магазинами, причем второй магазиивы-ступает также в роли входной ленты. Детерминированная версия этого устройства родственна анализатору с двумя магазинами, который применялся в алгоритмах 4.1 и 4.2 для общего нисхо* дящего и восходящего анализа. Мы наложим на это устройство ограничения, благодаря которым оно будет вести себя как восходящий анализатор, использующий предшествование.

Определение. Двухмаеазинным (восходящим) анализатором для грамматики G = (N, 2, Р, S) назовем конечное множество правил вида (а, 3)-(V, 6), где а, р, у и б-цепочки символов из Nu2u{$}, причем $-новый символ, концевой маркер. Каждое, правило (а, р) - (у, б) должно иметь один из двух видов: либо .

(1) р"Хб для некоторого XNu2 и у=аХ, либо

(2) а-=уе для некоторого 8€(Nu2)*, б -Лр- и Л -правило из Р.

В общем случае правило (а, р)-(у, б) говорит о том, что если а - верхняя цепочка первого магазина и р-верхняя цепочка второго магазина, то можно заменить а на у в первом магазине и р на б-во втором. Правило типа (1) соответствует переносу в алгоритме, анализирующем методом „перенос-свертка". Правило типа (2) соответствует шагу свертки. Существенное различие состоит в том, что символ Л, являющийся левой частью применяемого правила грамматики, помещается на верх второго магазина, а не первого. Это соглашение налагает ограничения на возвраты. Можно перемещать символы из первого магазина во второй (который функционирует как входная лента), но только



-аА Ва

G-неоднозначная грамматика для языка а". Если игнорировать нетерминал В и В-правила, то детерминированный двухмагазин-

ный анализатор для G образуется из правил

{е, а){а, е) (а, $) {е, Л$) (о, Л)-(аЛ, е) (аА, $) -(, Л$) ($, Л)--($Л, е)

$):-{$. 5$) П

6.2.3. Отношения предшествования Колмерауэра

Двухмагазинный анализатор можно устроить так, чтобы способ его работы был отчасти похож на разбор методом предшествования. Для этого надо предположить, что существуют три непересекающихся отношения Л, и •>, заданные на символах грамматики, из которых i> означает, что надо сделать свертку, а < и -перенос. Когда делается свертка, указывает левый конец некоторой составляющей (не обязательно основы). Следует подчеркнуть, что отношения <•, и •> по крайней мере временно не предполагаются связанными с правилами грамматики. Поэтому, например, может быть даже если X и У ие стоят рядом ни в какой правой части правила.

Определеиие. Пусть G--(N, 2, Я, S) -КС-грамматика и <, V>-три непересекающихся отношения HaNu2u{$}. где $ - новый,символ (концевой маркер). Двухмагазинный анализатор, индуцированныйотиоттмяич и •>, определяется правилами

(I) (X, К)-(ХК, ё) тогда и только тогда, когда Х<Кили X J?- К

Т2)(XZj.. .Zft, К)-(Х, ЛК) тогда и только тогда, когда ZkY, ZiZii для 1<г<, X<iZy и Л-Zj.. .Z-правило грамматики G.

Заметим, что если G -обратимая грамматика, то индуцированный двухмагазинный анализатор будет детерминированным,-и обратно.

Пример 6.12. Пусть G-грамматика с правилами

(1) S-*aSA (2) SbSA

(3) S-b

(4) Аа

как в примере 6.10.

Зададим отношения <:J, JL и •> таблицей на рис. 6,3.

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

Правила анализатора Т таковы:

(1) {е,Х)~{Х, е) для всех Х€{а, Ь, S, Л} (любой символ можно перенести из второго магазина в первый),

(2) (а, е)-{е. А) (а можно свернуть к А),

(3) (Ь, е){е, S) ф можно свернуть к 5),

(4) {aSA, е){е, S),

(5) (65Л, е)-(е, S).

(Последние два правила анализатора допускают свертки, соот-ветствугощие,пра?илам (1) и (2) грамматики G.)

Заметим, что анализатор Т недетерминированный и для каждой, входной цепочки можно получить много разборов. Один из восходящих разборов цепочки аЬЬаа представляется такой последовательностью конфигураций:

($, abbaa%, е) \-~ ($й, bbaa% е) \-{%аЬ, Ьаа%, е) \-{$abb, аа$, е) \-{$аЬ, Saa$, (3, 2)) \-{$abS,aa$, (3, 2)) \-{pbSa, а$, (3, 2)) f- {$abSaa, $, (3, 2)) \-{$abSa, Л$, (3,2) (4, 4))

\~ {$abS, ЛЛ$, (3, 2) (4 ,4) (4, 3))

\-{$abSA,. Л$, (3,2) (4, 4) (4,3)) h{$a, SA$, (3,2) (4, 4) (4,3) (2, I)) b($«S, Л$, (3,2) (4, 4) (4,3) (2, 1)) }-{$aSA, $, (3,2) (4, 4) (4, 3) (2, I)) M$. 5$, (3, 2) (4, 4) (4, 3)(2, 1)(1, 0)) Цепочка (3, 2) (4, 4) (4, 3) (2, I) (I, 0) образует восходящий разбор цепочки abbaUy соответствующий выводу

S=:aSA:=abSAAabSaAabSaa= abbaa □ Двухмагазшшый анализатор имеет особенность, отличающую его от обычных алгоритмов типа „перенос-свертка". Может оказаться, что такой анализатор работает и для неоднозначной грамматики, игнорируя некоторые из возможных в ней выводов. Пример 6.11. Пусть G определяется правилами

- S->A\B



гл. 6. АЛГОРИТМЫ РАЗБОРА С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ

6.2. восходящий pa3huf L. UI f лпу1Ч1д.п

Эти отношения индуцируют двухмагазинный преобразователь. правила которого определяются так:

(X, У){ХУ, е) для всех X€{$. а, Ь}, К!а, Ь} (Хй, У) -(X, ЛК) для всех Х€{$. с, У € Л} {Kb, К)-{Х, SK) для всех Хё{1 а. К€ $» Л}

(X, S)(XS, ) для всех ХК 6}

(XaSA, К) -(X, 5К) для всех Хе{$, а, } и Ге{Л, $} (XbSA, К)-(Х, 5К) для всех Х€ {$, Ь} и У{А, $)

Г допускает цепочку tfijba", у которой довательность тактов

--п, проделав после-

($, wba% e)\-*"($wba\ $, е)

&wb, А% (4, 2п)...(4, h- C&i. (4,2п)...(4, п+1)(3,п))

($. S$, (4, 2;0...(4,«+i)(3.«)(, «-!)...

(Ь. 0))

где {1. 2} для 1 Заметим, что на последних 3« тактах

чередуются переносы 5 и Л со свертками aSA либо bSA к S.

Легко проверить, что преобразователь Т детерминированный. Поэтому для каждой цепочки из L{G) возможна только одна

<•

<•

<•

<•

>

>

<

<•

•>

>

•>

>

Рис. Отношения „предшествования",

последовательность тактов. Так как все сверки преобразователя Т соответствуют правилам грамматики G, то Т-двухмагазинный анализатор для СП

В некоторых грамматиках можно так задать отношения "предшествования", Что индуцируемые ими двухмагазинные анализаторы будут одновременно детерминированными и корректными; Сейчас мы дадим соответствующее определение, а в следующем разделе, опишем простой тест, позволяющий установить, обладает ли грамматика нужным анализатором.

, Определение. Пусть G = (N, 2, Р, 5) -КС-грамматика. Назовем G грамматикой Колмерауэра, если

(1) она однозначная,

(2) приведенная,

(3) существуют непересекающиеся отношения ~ и •> на N и 2 и {$}, индуцирующие двухмагазинный анализатор, корректный для G.

Эти отношения назовем отношениями предшествования Колмерауэра. Заметим, что из условия (3) следует, что грамматика Колмерауэра должна быть обратимой.

Пример 6.13. Отношения на рнс. 6.3 являются отношениями предшествования Колмерауэра, и, значит, грамматики из примеров 6.10 и 6.12 - грамматики Колмерауэра. □

Пример 6.14. Каждая грамматика простого предшествования является грамматикой Колмерауэра. Пусть и •> -отношения предшествования Вирта - Вебера для грамматики G - = (N, 2, Я, S). Если G - грамматика простого предшествования, то она по определению приведенная и однозначная. Индуцируемый ею двухмагазинный анализатор действует почти как анализатор типа „перенос - свертка" для грамматик предшествования.

Однако, когда делается свертка правовыводимой цепочки (xw к цепочке aAw, мы заталкиваем $« в первый магазин, а Aw~ во второй, тогда как при разборе методом предшествования $аЛ находится в магазине, aw$ - на входе. Если X - последний символ цепочки щ, то по теореме 5.14 либо Х<»Л, либо XJLЛ. Поэтому на очередном шаге двухмагазинный анализатор должен перенести Л в первый магазин. Затем до следующей свертки двухмагазинный анализатор работает как анализатор простого предшествования.

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

6.2.4. Проверка условий предшествования Колмерауэра

Дадим теперь условие, необходимое и достаточное для того, чтобы однозначная приведенная грамматика была грамматикой Колмерауэра. Оно включает три отношения, определяемые ниже. Следует напомнить, что проблема выяснения однозначности КС-грамматики неразрешима и что, как мы видели в примере 6.12, существуют неодйозначные грамматики, обладающие детерминированными двухмагазиннымй анализаторами. Таким образом,





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.0018