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

Матрица предшествования 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

Рис. 5.14

С ледует, однако, сразу же отметить, что не для всякой матрицы функция предшествования существует. Нельзя линеаризовать, на пример, даже такую матрицу предшествования размером 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) Построим ориентированный граф , содержащий не более 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 для выяснения, циклический или нет ориентированный граф , можно применить следующий общий метод:

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

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

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

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

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

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

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

(3) Выбрать в  некоторую вершину 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 – длина самого длинного пути в .

Заметим, что факт наличия в графе циклов может быть обнаружен и без выполнения пункта (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  (  ) заданной грамматики.

(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. При использовании функций для обнаружения ошибки было выполнено на четыре шага больше, чем при использовании матриц. 