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

<-

=

•>

<-

Рис, 5.12. Отношения (-1,1)-иредшествования.

наконец, рассмотрение 005 добавляет ООО. Вот все элементы множества

Чтобы построить <, рассмотрим цепочки из < с S па правом конце. Получим $$<0, $0<.0 и 00<»0. Для построения снова рассмотрим такие цепочки и найдем

$05, 051, 51=1, $01,011,005 и 001.

Чтобы построить •>, рассмотрим цепочки из (5, у которых 5 в середине. Из $5$ получится !!•>$, а из 051 получится 111.

Отноптения (2,1)-предшествования для грамматики G приведены на рис. 5,13. Цепочки длины 2, не принадлежащие области определения отношении , <• и , здесь опущены.

$0 OS 00 01 S]

<

<•

=

<

. ш.

•>

Рис. 5.13. Отношения (2,1)-иредшествоваиия.

Так как конфликтов между отношениями (2,1)-предшество-вания нет, то G -грамматика (2,1)-предшествования. □

Теорема 5.16. Алгоритм 5.13 правильно вычисляет отноиения

Доказательство. Сначала покажем, что правильно определяется множество т.е. что у 6 < тогда и только тогда, когда у =m + n и у - подцепочка цепочки apw, где 5т5$"=>аЛЕ1У=?>;.арЕ1У и w FIRST„ (ьу).

Необходимость. Доказательство проводится индукцией по порядку, в котором цепочки добавляются к множеству . Базис, когда в < содержатся только первые два элемента, получается сразу. Для доказательства шага индукции допустим, что у добавляется к потому, что aAxS и АР, т. е. у -подцепочка цепочки арх. Так как аАх содержится в , то по предположению индукции существует вывод $"5$" "аAwaf) uv, где u = FlRST„ (ьу) и af/u можно записать в виде баЛхбз для некоторых 6i и бз из (Nu 2 {$[)*. Так как G -приведенная грамматика, то найдется такая цепочка г/€(U {$})*, что 6=*У-Таким образом, $"5$"=> б,аЛл:г/у =:>. бархг/у. Так как у -подцепочка длины m + n цепочки арх, то она, конечно, является подцепочкой цепочки арг, где z = FIRST„ (xyv).

Достаточность. Индукцией по k можно показать, что если $«5$"=>JaAEiy=>;.apEiy, то каждая подцепочка длины т-\-п цепочки apw содержится в , где u = FlRST„{w).

Из определения отношений <•, и непосредственно следует, что они правильно вычисляются на шагах (4) - (6). П

Докажем теорему, которая лежит в основе анализатора типа „перенос - свертка" для обратимых грамматик {т, /г)-предшест-вования, аналогичного алгоритму 5.12,

Теорема 5.17. Пусть G = (N ,S, Р, S) -произвольная приведенная КС-грамматика, т и п - целые числа и

(5.3.1) $-5$"=:>;Х,Х, 1 ... ХуАа, .., а

j.XpXpi ... X+iXft ... Xii ... а

(1) Пусть р-mjk, а - последние т символов цепочки ХрХрУ ... + 1 и - первые п символов цепочки XjXj-i ... Хуау...а. Тогда если р € ( U {S[)*, то либо а<»р, либо

(2) XkXm + k-i • Xk+i<if>, sde р состоит из первых п символов цепочки Ай -. - XyUj ... а.

< = {$5$, $$5}. Рассмотрим $5$, добавляя к цепочки $05, OSI, 511, 11$ (это все подцепочки длины 3 цепочки $0511$) и sOl, Oil (подцепочки длины 3 цепочкн $011$). Рассмотрение цепочки $$5 приводит к добавлению $$0, рассмотрение $05 добавляет $00, 005 и 001, рассмотрение 051 добавляет ill, и,



(3) Пусть й>/1, а - последние т символов цепочки XpXp..i .., Xj+i и р-первые п символов цепочки XjXj ,.. Ха ... йр. Тогда ар.

Доказательство. Утверждения (2) -(4) непосредственно следуют из определений. Чтобы доказать (1), заметим, что так как j>k, р состоит не только из символов $. Поэтому вывод

(5.3.1) можно записать в виде

(5.3.2) $«5$"=>убг

rXpXp i ... Х.,,Ла ...а

~~г ХрХ- ... Xft+iX ... Хуа .., а

где i-наибольшее из чисел, для которых Ь.фе в правиле ббб, из В выводятся и Xj и уЬ = ХрХр ... Xj.

Если первый символ цепочки 6. терминальный, скажем 2 = пу то по правилу (26) определения отношения имеем Xj..,„Xj+i ... Xy+j,4,p, где р = ах и ;t G FIRST„ i (бдЬУ).

Если первый символ цепочки нетерминальный, положим бзСбз. Так как по предположению Ху -терминал, то из С после нескольких шагов вывода (5.3.2) должна получиться цепочка Ог для некоторых /)N и 8G(Nu2)*. Далее, D заменяется цепочкой Хуб, и по правилу (26) отсюда следует требующееся отношение <•. □

Следствие. Если в теореме 5.17 G-грамматика (т, п)-пред шествования, то теорему можно усилить, добавив к каждому из утверждений (!) -(4) слова о том, что между соответствую-иими цепочками не выполняются никакие другие отношения. П

Алгоритм разбора типа „перенос-свертка" для обратимых грамматик расширенного предшествования полностью аналогичен алгоритму 5.12 для грамматик простого предшествования, так что мы только вкратце скажем о нем. Первые п необработанных входных символов можно хранить наверху магазина. Если такими символами являются а ... а, и непосредственно под ними в магазине расположена цепочка Х ... Х, причем X„ ... Х i а . .. а„ или Хд ... Xj <• «1 ... а„, то надо сделать перенос. Если же Х,„ ... Xj •>«!... й, то делается свертка. Утверждение (1) теоремы 5.17 гарантирует, что один из первых двух случаев произойдет всегда, когда основа лежит вправо от Xi-В силу утверждения (4) этой теоремы правый конец основы достигается тогда и только тогда, когда происходит третий случай.

Чтобы сделать свертку, надо так же, как в алгоритме 5.12, вернуться назад, проходя через отношения JL, ь поисках отношения <•. Из утверждений (2) и (3) теоремы 5-17 вытекает, что основа будет выделена правильно.

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

Многие естественно встречающиеся грамматики не являются грамматиками простого предшествования, и попытки найти для данного языка грамматику простого предшествования часто приводят к довольно неуклюжим грамматикам. Можно расширить класс грамматик, анализируемых методом предшествования, ослабив ограничение, что отношения <• и = не должны пересекаться.

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

Для того чтобы эта схема разбора работала, надо уметь определить, какое правило применить в том случае, когда правая часть одного правила является суффиксом правой части другого правила. Например, пусть аруьу - правовыводимая цепочка, в которой правый конец основы лежит между у и w. Если А-у и В-ру-два разных правила, то не ясно, какое из них нужно применить для свертки.

Мы ограничимся применением самого длинного из применимых правил. Класс грамматик, для которых такое решение оказывается правильным, образуют грамматики слабого предшествования.

Определение. Пусть G = (N, S, Я, S) -приведенная КС-грамматика без е-правил. Назовем G грамматикой слабого предшествования, если

(1) отношение •> не пересекается с объединением отношений <? и ,

(2) для ЛаХр и бр из Р, где XNu, не выполняется ни Х<б, ни XJ=B.



Пример 5.37. Примером грамматики слабого предшествования может служить грамматика с правилами

F~(E)\a

Матрица предшествования для G приведена на рис. 5.14.

Заметим, что конфликты возникают только между отношениями <• и J=, так что условие (1) определения грамматики слабого предшествования удовлетворяется. Чтобы убедиться, что

•>

•>

>

->

•>

•>

•>

•>

>

>

•>

>

->

•>

•>

<•

<•

<-

<•

<

<•,=

<

<•

<-

<

<

<

<•

<•

<•

<•

<•

Рис. 5.14. Матрица предшествования,

условие (2) тоже не нарушается, рассмотрим сначала три правила Е-Е + Т, £-> + Г и E-i-T). Из матрицы предшествования видно, что между £ и а также между -j- и £ (т. е. когда -f рассматривается как левый аргумент отношения) нет никакого отношения предшествования. Таким образом, эти три правила не нарушают условия (2). Остальные правила, в которых одна правая часть служит суффиксом другой,- это Т ->Т-у--Р и 7-i-F. Так как между * и 7" нет отношения предшествования,

) Очевидно, что грамматика G тесно связана с нашей любимой грамматикой Gq. в самом деле, язык L(G) -это l(Gy) с лишними унарными знаками как, например, в цепочке * (4-о-Нй). Грамматика Gp-тоже обратимая грамматика слабого предшествования, но не грамматика простого предшествования.

) Случайно этн три правила имеют одну и ту же левую часть.

то и здесь условие (2) не нарушено. Итак, G - грамматика слабого предшествования.

Хотя G ие является грамматикой простого предшествования, она порождает язык простого предшествования. Позже мы увидим, что это верно всегда, т. е. каждая обратимая грамматика слабого предшествования порождает язык простого предшествования. □

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

Лемма 5.4. Пусть G = (N, 2, Я, 5)-граммат.ика слабого предшествования и Р содержит правило В->р. Пусть $5$=Ф*уСи=>,. бХр&У- Если сушестеует правило А ">аЛр, то последним в этом выводе применялось не правило б-р.

Доказательство. Допустим, что, напротив, С = В и у = ЬХ. Применив теорему 5.14 к выводу 5=?>*yCEiy, получим Х<« б или X А б. Это следует из того, что основа цепочки yCw оканчивается где-то правее символа С, и, значит, С - один из символов Х[ теоремы 5.14. Но тогда сразу нарушается условие слабого предшествования. □

Лемма 5.5. Пусть G-такая же грамматика, как в лемме 5.4, и пусть она к тому же обратимая. Если правила вида Д-аХр нет, то в выводе $5$ =>р уСьу =;.бХрьу должно быть С = В и у -бХ {т.е. последним применяется правило б->р).

Доказательство. Очевидно, что на последнем шаге заменяется символ С- Левый конец основы цепочки бХрьУ не может быть левее символа X, так как нет правила Л-аХр. Если основа оканчивается где-то правее первого символа цепочки р, то нарушается лемма 5.4, в которой б-н-р играет роль правила А -аХр. Поэтому основа - цепочка р, и нужный результат следует из обратимости грамматики G. □

Итак, суш.ность алгоритма разбора для обратимых грамматик слабого предшествования заключается в следующем. Мы просматриваем правовыводимую цепочку (ограниченную концевыми маркерами) слева направо до тех пор, пока впервые ие встретим отношение •>. Это отношение указывает правый конец основы. Затем по одному рассматриваем символы слева от •>. Допустим, что есть правило б->-р и слева от •> оказывается цепочка Хр. Если правила вида А-*-аХр нет, то по лемме 5.5 р-основа. Если такое правило есть, то по лемме 5.4 правило б-»-р неприменимо. Следовательно, решение о том, свертывать ли р, можно принять, рассмотрев только один символ слева от р.





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