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

Отношения предшествования такие же отношения, как и логические конъюнкция, дизъюнкция, и несут смысл определённых операций.

Примечание. Здесь и в дальнейшем будем рассматривать пару рядом стоящих символов R,SÎV=V_tÈV_n, то есть считать эти символы терминальными или нетерминальными.

Определение 5.3. Говорят, что R предшествует S (R·>S) (то есть R сворачивается раньше, чем S), если R является частью основы синтаксического дерева, а S нет (рис. 5.22).

Рис. 5.22. R·>S

Определение 5.4. Говорят, что R сворачивается одновременно с S (R S), если оба символа входят в основу одновременно (рис. 5.23).

Рис. 5.23. R S

Определение 5.5. Говорят, что S предшествует R (R<·S), или R сворачивается позже, чем S, если S в основе, а R ещё нет (рис.5.24).

Рис. 5.24. R<·S

Свойства отношения предшествования. Отношения предшествования в отличие от всех основных отношений, не обладают коммутативными свойствами, то есть нельзя применять свойства симметрии к отношениям предшествования. Действительно, если мы говорим что R предшествует S (R·>S), то это совсем не означает, что S<·R. Хотя для определённых символов словаря это имеет место, но только в частном случае.

Сформулируем аналитические определения отношений.

Определение 5.6. Отношение U FIRST S имеет место, тогда и только тогда, когда имеет место выводимость: U®Sa, SÎV_N, aÎV*. (Иначе говоря, S – первый нетерминал.)

Определение 5.7. ОтношениеU FIRST⁺ S имеет место, тогда и только тогда, когда существует итерационная выводимость: UÞ⁺Sa, SÎV_N, aÎV*.

Определение 5.8. ОтношениеU LAST S имеет место, тогда и только тогда, когда имеет место выводимость: U®aS, SÎV_N , aÎV*.

Определение 5.9. Отношение U LAST⁺ S имеет место, тогда и только тогда, когда существует итерационная выводимость: UÞ⁺aS, SÎV_N , aÎV*.

Определение отношений предшествования между символами по заданной грамматике производится в соответсвии со свойствами отношений:

Свойство 1. R S, когда в грамматике существуют следующие отношения:

U®aRSbÎP; причём

a,bÎV*; R,SÎV.

Свойство 2.. R<·S, если в грамматике существуют или имеют место следующие отношения:

U®aRWb; причём

a,bÎV*; W FIRST⁺ S; R,S,WÎV.

Свойство 3.. R·>S, если в грамматике существуют или имеют место следующие отношения:

U®aQWb; причём

a,bÎV*; Q LAST⁺ R; W FIRST⁺ S; R,S,W,QÎV.

Для иллюстрации рассмотрим грамматику G [Z]:

1. Z ® bMb

2. M ® (L | a

3. L ® Ma)

Легко видеть, что G [Z] является грамматикой простого предшествования. (Легко доказывается!)

Язык, порождаемый данной грамматикой:

L (G [Z])={bab, b(aa)b, b((aa)a)b,....}

Построим сентенциальные деревья из цепочек принадлежащих L (G [Z]) (рис. 5.25…5.27)

Рис. 5.25. 1-е сентенциальное дерево

Рис. 5.26. 2-е сентенциальное дерево

Рис. 5.27. 3-е сентенциальное дерево

В данном случае отношения предшествования между символами грамматики установлено графически, то же самое можно было бы сделать используя свойства 1,2,3 отношения FIRST, LAST, но аналитически.

Матрица предшествования.

Алгоритм разбора для восходящего распознавателя с использованием грамматик предшествования. Алгоритм Флойда (1963)

Матрица предшествования представляется в виде таблицы Q c элементами q_ij такими, что:

q_ij=0, если S_i и S_j несравнимы;

q_ij=1, если S_i<·S_j;

q_ij=2, если S_i S_j;

q_ij=3, если S_i·>S_j.

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

Алгоритм Флойда. Символы входной цепочки просматриваются слева направо и помещаются в стек S до тех пор, пока символ вершины стека S_i не окажется в отношении предшествования “·>” с очередным анализируемым символом R, это означает, что верхний символ стека является “хвостом” основы и, следовательно, основа уже в стеке.

Основу находят в списке правил приготовленной таблицы редукций и заменяют нетерминалом U. Процесс повторяется до тех пор, пока в качестве U не окажется Z (рис. 5.28).

Рис. 5.28. К алгоритму Флойда

Рис. 5.29. Блок-схема распознавателя

Блок-схема распознавателя изображена на рис. 5.29.

Здесь S — стек; i — счетчик стека; j — индекс адресации внутренних элементов стека; $t₁,...,t_n$ — формат анализируемого предложения; U — нетерминал, к которому приводится основа, найденная на шаге разбора; Z — начальный символ грамматики.

Значение блоков:

1,2 — задание начальных условий;

3,4 — выполнение условия: если S_i и R не находятся в отношении S_i·>R, то не вся основа в стеке, поэтому символ R заносится в стек и поиск продолжается.

5,6,7 — S_i предшествует R (S_i·>R), следовательно, основа уже в стеке. Необходимо найти “голову” основы (то есть такое j, что S_j-1<·S_j).

8,9 — проверка цепочки S_j...S_i; если она не является правой частью редукции, то работа закончена с авостом (ошибкой), в противном случае исключить из стека S_j...S_i, и занести в стек символ U, который является левой частью (U®S_j... S_i).