Функции предшествования

Матрица предшествования P может занимать слишком большой участок памяти. Если в языке 200 символов, нам понадобится матрица из 200 ´ 200 элементов, каждый длиной не менее двух битов. Однако, во многих случаях информация, задаваемая в матрице может быть представлена в сжатой форме парой векторов f и g с целочисленными значениями, называемых функциями предшествования, и такими, что

из x _i <· x _j (P _{i j} = <·) следует f _i < g _j;

из x _i x _j (P _{i j} = ) следует f _i = g _j;

из x _i ·> x _j (P _{i j} = ·>) следует f _i > g _j.

для всех символов грамматики. Это называется линеаризацией матрицы, и объем требуемой памяти сокращается с n ´ n ячеек до 2 ´ n.

	x	y
x		·>
y

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

f(x) > g(y), g(y) = f(y),

f(y) = g(x), g(x) = f(x),

что ведет к противоречивому утверждению f(x) > f(x).

Построение функции предшествования с помощью графа линеаризации

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

Алгоритм 5.2. Вычисление функции предшествования по графу линеаризации.

Вход. Матрица P размером n ´ m с элементами <·, , ·> и “пусто”.

Выход. Два целочисленных вектора f = (f ₁,..., f _m) и g = (g ₁,..., g _n), у которых

f _i < g _j при P _{i j} = <·

f _i = g _j при P _{i j} =

f _i > g _j при P _{i j} = ·>

или “нет”, если такие векторы не существуют.

Метод.

(1) Построим ориентированный граф G, содержащий не более n + m вершин называемый графом линеаризации для P. Сначала пометим m вершин буквами F₁, F₂,..., F_m для каждой строки матрицы, а оставшиеся n вершин буквами G₁, G₂,..., G _n для каждого столбца матрицы P.

(2) Если P _{i j} = , то построим новую вершину N, объединяя F _i с G _j.

(3) Если P _{i j} = ·>, проведем дугу из F _i в G _j. Если P _{i j} = <·, проведем дугу из G _j в F _i.

(4) Если полученный граф содержит циклы, выдать сообщение “нет” и завершить работу.

(5) Если граф линеаризации ациклический, положим значение f _i, равным длине самого длинного пути, начинающегося в F _i, а g _j – длине самого длинного пути, начинающегося в G _j. (Точнее, в качестве значений функций предшествования мы будем использовать в дальнейшем величины на единицу большие, чем длины самого длинного пути, зарезервировав нулевые значения для левого и правого ограничителей цепочки.). ƒ

На шаге (4) алгоритма 5.2 для выяснения, циклический или нет ориентированный граф G, можно применить следующий общий метод:

Пусть G – исходный граф.

(1) Найти в данном графе вершину N, не имеющую прямых потомков. Если таких вершин нет, граф G – циклический. В противном случае удалить вершину N вместе с дугами, входящими в нее.

(2) Если полученный граф пуст, то граф G – ациклический. В противном случае повторить шаг (1).

Установив в некоторый момент, что граф ациклический, воспользуемся для нахождения на шаге (5) алгоритма 5.2 длины самого длинного пути, начинающегося в произвольной вершине, следующим методом разметки вершин.

Пусть G – ориентированный ациклический граф.

(1) Сначала пометить все вершины графа G единицами.

(2) Повторять шаг (3) до тех пор, пока метки графа не перестанут изменяться. Метка при каждой вершине будет на единицу больше длины самого длинного пути, начинающегося в этой вершине.

(3) Выбрать в G некоторую вершину N. Пусть N имеет k прямых потомков N₁, N₂,..., N_k с метками p₁, p₂,..., p _k. Заменить метку вершины N на max (p₁, p₂,..., p _k) + 1. (Если k = 0, то меткой вершины N оставить 1.)

Ясно, что шаг (3) повторяется для каждой вершины не более p раз, где p – длина самого длинного пути в G.

Заметим, что факт наличия в графе циклов может быть обнаружен и без выполнения пункта (4) алгоритма 3.1. Если значение пометки, вычисляемой в пункте (5), у какой-либо вершины превысит 2 ´ n, где n – количество символов грамматики, то это говорит о том, что самый длинный путь из данной вершины превышает количество вершин данного графа, т.е. в графе присутствуют циклы.

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

Пример 5.12. На рис. 5.15 а представлен граф линеаризации для матрицы предшествования с рис. 5.9 б примера 5.9. В этой матрице совпадают строки для символов ‘ L’ и ‘ )’, поэтому на графе они представлены одной вершиной F _L,).

В процессе построения графа на шаге (2) алгоритма 5.2 были объединены вершины (F _M, G _b и G _a), (F_b, G _M), (F_a, G ₎ ) и (F₍, G _L).

После выполнения шага (3) алгоритма 5.2 и проведения всех необходимых дуг, определим, содержит ли полученный граф циклы, а заодно и вычислим функцию предшествования. На графе с рис. 5.15 а прямых потомков не имеют вершины (F _S), (G _S) и (F₍, G _L). Поставим на них пометку 1 и удалим эти вершины вместе с дугами, которые направлены к этим вершинам. После этого появится не имеющая потомков вершина (F_b, G _M). Поставим на ней отметку 2 и удалим вершину. В результате получим еще две вершины (G ₍) и (F_M, G _b, G _a), которые не имеют потомков. Поставив на них пометку 3 и удалив, мы получим две изолированные вершины (F_{L, )}) и (F_a, G ₎). Осталось пометить их цифрой 4 и после удаления этих двух последних вершин мы получим пустой граф, что говорит об ацикличности исходного графа. Более того, пометки вершин, которые расставлялись перед их удалением и составляют значения функции предшествования. Осталось только свести их в таблицу, приведенную на рис. 5.15 б. 

Метод пересчета для вычисления функции предшествования.

Достоинством рассмотренного выше алгоритма 5.2 является его наглядность, но с точки зрения машинной реализации гораздо эффективнее алгоритм пересчета, который приводится ниже.

Алгоритм 5.3. Вычисление функции предшествования методом пересчета.

Входом здесь является все та же матрица предшествования, а выходом вектора f и g.

(1) Вначале положим f(x _i) = 1 и g(x _i) = 1 для всех x _i Î (N È S) заданной грамматики.

(2) Просмотрим каждую строку предложенной матрицы предшествования. Если x _i ·> x _j, а f(x _i) £ g(x _j), то положим f(x _i) = g(x _j) + 1.

(3) Просмотрим все столбцы матрицы. Если x _i <· x _j, а f(x _i) ³ g(x _j), то положим g(x _j) = f(x _i) + 1.

(4) Рассмотрим все элементы матрицы с отношением . Если x _i x _j, а f(x _i) ¹ g(x _j), то положим f(x _i) и g(x _j) равными max (f(x _i), g(x _j)).

(5) Повторяем шаги (2), (3), (4) до тех пор пока либо:

а) одно из полученных значений f или g не превысит 2 ´ n, где n – количество символов матрицы и тогда функции предшествования не существует;

б) на очередном цикле выполнения шагов (2), (3), (4) ни одно из значений f и g не изменились и тогда функция предшествования найдена.

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

Ясно, что использование функции предшествования в алгоритме Вирта–Вебера, описанного в разделе 5.3, приведет к тому что входные символы будут переносятся в стек до тех пор, пока функция f для символа из вершины стека не станет больше функции g очередного входного символа и тогда хвост основы найден. Об преимуществах использования функции по сравнению с матрицей предшествования мы уже говорили – это меньший объем требуемой памяти ЭВМ. Но надо помнить, что выигрывая здесь мы где–то должны проиграть.

Когда компилятор обнаруживает в программе ошибку, он должен попытаться нейтрализовать ее и продолжить разбор, чтобы обнаружить другие ошибки. Поэтому иногда важно уметь обнаруживать ошибки как можно раньше. Из–за применения функций предшествования процесс обнаружения ошибки может затянуться. Линеаризация ведет к потере информации, потому что стало неизвестным, существует ли в действительности между двумя символами отношение. Утрачивается возможность обнаружения ошибки из–за отсутствия отношений. Эта ошибка в конечном итоге выявится при попытке выполнить свертку, когда окажется, что нет правила с такой правой частью, которая находится в вершине стека. Тем не менее, такая задержка в обнаружении ошибки может оказаться неприемлемо дорогой платой за удобство использования функций предшествования вместо матриц; это зависит от того, насколько важно раннее обнаружение ошибки в конкретном компиляторе.

Пример 15.13. Для иллюстрации вышесказанного попробуем в соответствии с грамматикой G5 из примера 5.8 провести разбор цепочки ba)))))b, используя сначала полную матрицу (см. рис. 5.16 а), а затем функции (рис. 5.16 б).

На рис. 5.16 б ошибка возникает из–за того, что для фрагмента a))))) нет правой части в грамматике G5. При использовании функций для обнаружения ошибки было выполнено на четыре шага больше, чем при использовании матриц. ›

5.2.3. Проблемы построения грамматик предшество­­­­ва­ния

Из определения грамматик простого предшествования следует, что далеко не всякая КС–грамматика является грамматикой простого предшествования. В частности, в произвольной КС–грамматике может не выполняться условие однозначной обратимости. Наличие нескольких одинаковых правых частей в продукциях грамматики приведет к неоднозначности при свертке основ, а следовательно и алгоритма разбора по такой грамматике станет недетерминированным. Но это не фатальная проблема, так как нетрудно показать, что каждый КС–язык порождается по крайней мере одной обратимой КС–грамматикой.

Действительно, если в грамматике имеются правила вида: A ® a и B ® a, то одно из них, например B ® a можно удалить, а все правила вида C ® jBy заменить парой правил: C ® jay и C ® jBy. Причем, последнее правило сохраняется только в том случае, если у нетерминала B есть и другая альтернатива, кроме B ® a.

Пример 5.14. Рассмотрим фрагмент правил грамматики, определяющий синтаксис заголовка процедуры:

<Заголовок проц.>::= PROCEDURE <имя проц.> ( <список параметров> );

<имя проц.>::= <идентификатор>

<список параметров>::= <идентификатор> ï

<идентификатор>, <список параметров>

Устраним правило <имя проц.>::= <идентификатор>и в результате получим обратимую грамматику:

<Заголовок проц.>::= PROCEDURE <идентификатор> ( <список параметров> );

<список параметров>::= <идентификатор> ï

<идентификатор>, <список параметров> š

Вторая проблема более существенна. Очень часто между двумя символами грамматики имеет место более одного отношения предшествования. Единственное, что мы можем тогда сделать, – это обработать и изменить грамматику так, чтобы обойти конфликт.

Обычно, наличие двух отношений между символами грамматики – это следствие рекурсии, в частности левосторонней. Предположим, что в грамматике существует некоторое правило U ® U.... Если есть другое правило вида V ®...XU..., то одновременно X U и в силу того, что U Î L(U), – X будет <· U. Иногда можно избавиться от такого конфликта, заменив правило

V ®... XU...

парой правил:

V ®... XU₁ ..., U₁ ® U,

где U₁ новый нетерминал. При этом получим, что X U₁ и X <· U. Такой прием называют стратификацией или разделением. Заметим, что аналогично может решаться и конфликт с отношениями ·> и при правосторонней рекурсии.

Пример 5.15. Чтобы показать, как делается стратификация, воспользуемся привычной уже грамматикой арифметических выражений:

E ® E+TïE-T½T½-T

T ® T*MïT/MïM

M ® (E)ïi

Из первой группы правил следует, что ‘ + ’ и ‘ - ’ T, а так как T леворекурсивен, получаем также, что ‘ +’ и ‘ - ’ <· T. Аналогичная проблема возникает и с символами ‘ ( ’ и ‘ E ’. Без ущерба для структуры цепочек языка изменим заданную грамматику на следующую:

E ® E+T₁ïE-T₁½T₁½-T₁

Т₁ ® T

T ® T*MïT/MïM

M ® (E₁)ïi

E₁ ® E.

Начальным символом грамматики при этом станет E₁, множество самых левых и самых правых символов для нетерминалов полученной грамматики представлено на рис. 5.17, а матрица и функции предшествования на рис. 5.18.

ž

Этот пример может создать впечатления, что при стратификации изменения не столь значительны. Однако, если в грамматике 100 правил и более 100 символов (а так оно и есть в языках типа Паскаль), то даже искушенный специалист затратит немало времени на то, чтобы переделать такую грамматику в грамматику простого предшествования. В результате может измениться вся структура языка, не говоря о том, что грамматика станет неудобочитаемой. Кроме того, стратификация не всегда спасает, так как она часто приводит к конфликтам иного рода. Если одновременно для двух символов грамматики x и y выполняются отношения x <· y и x ·> y, то лучший выход – применить другую технику.

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

Проиллюстрируем это на примере сентенциальной формы E+T*F исходной грамматики из примера 5.15. Поскольку отношения + <· T и + T противоречивы, мы не можем всего по двум символам, + и T, сделать вывод о том является ли T головой основы или + и T одновременно входят в основу и нужно выполнить сложение. Если же известно два символа + и * или же три символа +T*, то интуиция подскажет, что складывать нельзя и следовательно символ + в основу не входит.

Поиск по сайту: