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

В грамматиках алгоритмических языков число терминальных и нетерминальных символов превышает 200-300, поэтому таблица предшествования занимает большой объём памяти. Для уменьшения этого объёма было предложено вместо таблицы предшествования использовать функции предшествования - числовые функции нечислового аргумента, которые определяются следующим образом:

Рассмотрим метод графов построения функции предшествования.

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

,аналогично,

если , то

Рис. 6.6

После построения графа выполняется следующая последовательность действий:

1. Все вершины, для которых нет потомков, помечаются индексом “1” и удаляются из рассмотрения вместе с входящими в них дугами.

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

3

,то функция предшествования не существует.

. Пункт 2 выполняется до тех пор, пока все вершины не окажутся помеченными, при этом индекс вершины считается значением функции предшествования. Если в графе остаются циклы вида (рис.6.7):

Рис. 6.7

На рис. 6.8 показан граф и построена функция предшествования для таблицы предшествования из примера 6.2.

Рассмотрим ещё один способ построения функций предшествования - метод инкрементов:

1) Все значения иприравниваем к единице.

2) Значения функции предшествования изменяются в большую сторону следующим образом:

если , то=+1; если , то =+1;

увеличиваем

в большую

сторону

Рис.6.8

1 шаг

1 1 1 1 1 1

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

1 1 1 1 1 1

2 шаг

1 3 5 5 1 5

3 шаг

1 2 4 6 6 1

1 3 5 5 1 5

1 2 4 6 6 1

Функция предшествования не существует, если значения ее получаются больше, чем величина 2n, где n- общее число символов матрицы предшествования.

Упражнения

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

S  aSbcd.

6.2. Построить отношения простого предшествования и функцию предшествования, используя граф линеаризации, для грамматики с правилами S  aSSbcd. Покажите этапы свертки фраз aacdbcb , ab , acb.

	1	2	3	4
1				
2			
3			
4

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

E  E or TT

T  T and MM

M  a(E) not M

6.4. Постройте отношения простого предшествования для грамматики с правилами S  0S11011 и терминалами { 0, 1 }. Если данная грамматика не является грамматикой простого предшествования, то преобразуйте ее к такой грамматике.

6.5. Постройте отношения операторного предшествования и функцию предшествования, используя методы графов и инкрементов для грамматики из упражнения 6.4.

6.6. Преобразуйте грамматику S  E

E  TTBE(E)

T abz

B к грамматике простого предшествования Вирта. Покажите этапы свертки фразы a(b+c).

6.7. Написать матрицу предшествования Флойда для грамматики:

С0| …|9|0C|…|9C

и проанализировать цепочку: 1) aa(((039)))2)aa(497))