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

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

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

ЬК()-анализатор, построенный в предыдущем разделе, можно рассматривать как алгоритм типа „перенос-свертка", в котором магазинный алфавит дополнен ЬК()-таблицами. Если трактовать его так, то можно заметить, что его функция переноса зависит только от верхнего символа магазина (текущей LR()-таблицы) и следующих k входных символов. Функция свертки зависит только от таблицы, расположенной в магазине непосредственно ниже основы, и не зависит от следующих входных символов. Однако, согласно данному нами формальному определению, надо исследовать все содержимое магазина, чтобы выяснить, какова верхняя таблица. Алгоритмам, излагаемым в этом разделе, требуется только та информация, которая хранится „почти" на самом верху магазина. Поэтому мы принимаем такое соглашение;

Соглашение. Если f и g -функции алгоритма разбора типа „перенос - свертка" и значение f {а, w) определено, то f (ра, wx) = f (а, w) для всех р и х, если не оговорено противное. Аналогичное утверждение касается функции g.

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

Простейший класс алгоритмов типа „перенос-свертка" основан па так называемых „отношениях предшествования". Для грамматики предшествования границы основы правовыводимой цепочки можно определить с помощью некоторых отношений (предшествования) между символами, входящими в эту цепочку.

Техника разбора, ориентированная на отношения предшест-вовапия, использовалась при построении анализаторов для языков программирования одной из первых, и с тех пор в литературе появилось несколько вариантов грамматик предшествования. Мы рассмотрим основанный на отношениях предшествования детерминированный анализ слева направо, производящий правый

Функцию переноса f зададим так; для всех ссК* и х (2 и {$})

(1) f(aS, сл:) = перенос, если с{а, Ь],

(2) dx) = свертка, если с{а, Ь} и d{a, b},

(3) ах) свертка,

(4) f ($, Ьл:)-ошибка,

(5) ЦаХ, $)-ошибка для X{S, а},

(6) f{ab, $)-свертка,

(7) f{$S, $) = допуск.

(8) f(S,S)=-ошибка.

Функцию свертки g зададим так: для всех <xV* и х (2 (J {$})*

(1) g{, ах)==2,

(2) g{aa, сх)-2 для с£{а, Ь],

(3) giSaSb, сх)=\ для с€{а, $},

(4) glaaSaSb, сх) = \ для с{а, Ь},

(5) g{a,, X) -ошибка в остальных случаях.

Разберем с помощью алгоритма Л входную цепочку aabb. Он приступает к работе в начальной конфигурации

($, aabb$, е)

Первый шаг определяется значением /=($, aabb$), которое, как видно из определения функции f, равно свертке. О том, какую делать свертку, говорит значение g ($, aabb$), равное, очевидно, 2. Поэтому первым шагом будет свертка

{$, aabb$, )Н($5, aabb$, 2)

Следующий шаг определяется значением f($S, ааЬЬ$) = перенос. Таким образом, это шаг переноса

($S, aabb$, 2)\-{$Sa, аЬЬ%, 2)

Продолжая в том же духе, алгоритм Л сделает такую последовательность шагов:

{$, aabb%, e)K($5, aabb%, 2) abb, 2) [-($SaS, аЬЬ%, 22) \-{%SaSa, bb%, 22) -{SaSaS, bb$, 222) [~{%SaSaSb, b$, 222) l-iSaS, b$, 2221) [~{SaSb, 2221) \-{$S, $, 22211) - допуск

Таким образом, Л [aabb) 22211. Ясно, что 22211-правый разбор цепочки ааЬЬ. □



(1) ХУ, если В Р есть такое правило Л-аХВр, что S =Ф Гу;

(2) если в Р есть правило Л-аХКр;

(3) отношение •> определяется на (Nu2)x2, так как непосредственно справа от основы в правовыводимой цепочке может быть только терминальный символ; полагаем Х*>а, если в Я есть правило Л-а5Кр, В =Ф + уХ и У=*а6 (заметим, что Уа, если У=аЩ.

Анализируя входную цепочку методом предшествования, удобно добавлять к ней левый и правый концевые маркеры, "в качестве такого концевого маркера возьмем символ $ и будем считать, что <iX для всех Х, для которых S=+ Ха, и К*>$ для всех К, для которых 5=?>+аК.

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

Определение. КС-грамматика G = (N, Е, Я, S) называется грамматикой предшествования, если она приведенная ), не содержит -правил и для любой пары символов из N U 2 выполняется не более одного отношения предшествования Вирта - Вебера. Обратимая грамматика предшествования называется грамматикой простого предшествования.

Как обычно, язык, порождаемый грамматикой (простого) предшествования, назовем языком [простого] предшествования.

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

5 aSSb \ с

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

Опишем теперь систематический подход к построению отношений предшествования. Отношение 4, вычисляется легко: просматриваются правые части правил и обнаруживается, что S, SJ=S и Sb.

Чтобы вычислить отношение будем искать в правых частях правил пары смежных символов ХС. Тогда X находится

Напомним, что КС-грамматика G называется приведенной, если в ней нет выводов вида А Л, бесполезных символов и е-правнл, за исключением, быть может, S-причем в этом случае S ие встречается в правых частях правил.

разбор. При этом будут введены грамматики предшествования следующих типов:

(1) простого предшествования,

(2) расширенного предшествования,

(3) слабого предшествования,

(4) смешанной стратегии предшествования,

(5) операторного предшествования.

Ключ к пониманию метода разбора по отношениям предшествования дает определение отношения •> между символами грамматики, которое при просмотре слева направо правовыводимой цепочки арш, где р - основа, впервые оказывается выполненным для последнего символа цепочки р и первого символа цепочки w.

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

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

Техника анализа, основанная на так называемом „простом предшествовании", использует для выделения основы правовыводимой цепочки арш три отношения предшествования: =L и i>. Если р - основа, то между всеми смежными символами цепочки а выполняется либо отношение либо =L, между последним символом цепочки а и первым символом цепочки р выполняется <•, между смежными символами основы - отношение JL и между последним символом цепочки р и первым символом цепочки W - отношение •>.

Итак, основу правовыводимой цепочки грамматики простого предшествования можно выделить, просматривая эту цепочку слева направо до тех пор, пока впервые не встретится отношение >>. Для нахождения левого конца основы надо возвращаться назад, пока не встретится отношение Цепочка, заключенная между <• и будет основой. Если грамматика предполагается обратимой, то основу можно однозначно свернуть. Этот процесс продолжается до тех пор, пока входная цепочка не свернется к начальному символу (либо пока дальнейшие свертки окажутся невозможными).

Определение. Отношения предшествования Вирта-Вебера <V, л= и •> для КС-грамматики G--(N, 2, Р, S) определяются на множестве NU2 следующим образом:



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

<•

<•

<•

<•

•>

>

•>

•>

•>

>

•>

•>

<•

<•

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

роль с играет S, причем из S выводятся цепочки, начинающиеся символом а или с. Поэтому X <• К, где Х{а, S} и

Чтобы вычислить снова ищем в правых частях правил пары смежных символов, на этот раз вида СХ. Затем ищем символы У, которые могут оказаться на правом конце цепочки, выводимой из С за один или более шагов, и терминалы d, которые могут находиться в начале цепочки, выводимой из X за нуль или более шагов. Если X - терминал, то единственная возможность; X d. В данном примере парами такого вида будут 5S и Sb. Поэтому У*>, где У{Ь, с] и d£{a, с] для первого правила, d = b-для второго.

Подчеркнем, что отношения J, <i и £> не обладают свойствами, которые обычно приписываются отношениям -, < и >, заданным на вещественных числах, целых и т. п. Например, L, обычно не является отношением эквивалентности, <V и вообще говоря, не транзитивны, но могут быть симметричными или рефлексивными.

Так как в каждой ячейке матрицы на рис. 5.11 записано не более одного отношения предшествования, то G - грамматика предшествования. Кроме того, правые части всех правил в G различны, так что G - грамматика простого предшествования, а L (G) - язык простого предшествования.

Рассмотрим правовыводимую цепочку $ассЬ грамматики G, ограниченную концевыми маркерами. Имеем $<»а, а <»с я с*>с. Основой цепочки ассЬ служит первый символ с, а отношения предшествования как раз и выделяют эту основу. □

Всю существенную информацию, содержащуюся в матрице предшествования пХп, часто можно представить в виде двух

я-мериых векторов. Такие представления матриц предшествования будут изучаться в разд. 7.1.

Теорема 5.14, сформулированная ниже, показывает, что отношение < встречается в начале основы правовыводимой цепочки, отношение J= - между смежными символами основы, а отношение •>-на правом конце основы. Это верно для любой грамматики без -правил, но только в грамматиках предшествования любые два смежных символа активного префикса правовыводимой цепочки связаны не более чем одним отношением предшествования.

Сначала выведем одно следствие из существования отношения предшествования для двух данных символов.

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

(1) Если Х<А или ХЛ и А-Уа содержится в Я, то

(2) Если Л<*й:, Аа или А*>а и А-аУ содержится в Ру то У а.

Доказательство. Мы докажем (2), а (1) оставим в качестве упражнения. Если А<а, то существует такая правая часть р1ЛВ32, что В ==> ау для некоторой цепочки у. Так как А аК, то отсюда сразу получаем Уу>а. Если А а, то существует правая часть рЛгра- Поскольку а=*а и Л =>+аК, отсюда снова получаем У}>а. Если А}>а, то существует правая часть pjSXpg, где й=Ф+уЛ и Х=:*аЬ для некоторых у и б. Так как S=>+yaK, то опять получаем нужное заключение. □

Теорема 5.14. Пусть G(N, 2, Я, S) -приведенная КС-грамматика без е-правил. Если

$8=:XpXpi.. .Xk+iAa.. .а

гХрХр-у.. .fyXk.. .Х-ау... а

(1) Х/4<Х,- или XiiJXf для p<,i<kt

(2) Xfe ii<Xfe,

(3) Xiy=Xi для k>i\,

(4) Х,}>а,.

Доказательство. Доказательство проведем индукцией по п. Для п = 0 имеем $5$ =:5>;. .. .Ху$. По определению отношений предшествования j <• Х, =1, Xi для k> il и i>$- Заметим, что Xf...Xi не может быть пустой цепочкой, так как по условию в G нет -правил.





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