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

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

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

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

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

если , то

Рис. 6.6.

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

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

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

3

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

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

Рис. 6.7.

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

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

2

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

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

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))