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

Рассмотрим следующее дерево:

+

T

E

*

(E)

F

T

E+T

E

Для этого дерева существует следующие неоднозначности: +≐T и +⋖T; (≐E и (⋖E.

Для простого предшествования это не пригодно, поэтому для нашего случая необходимо ввести символ, чтобы Т не совпадали, то есть введем стратификацию.

Для решения проблемы введём новые правила:

1. E: = E₁;

2. E₁: = E₁+T₁|T₁;

3. T₁: = T.

Теперь, учитывая эти новые правила, можно нарисовать следующее дерево:

E₁

E

T₁

+

T

Т

*

F

(E)

E₁

E₁+T

В итоге для этого дерева имеем следующие отношения:

1. +≐T₁ и +⋖T;

2. (≐E и (⋖E₁.

Для первого дерева без замены Т и ввода новых правил получим

E+T*F;

+⋖T*;

(⋖E+.

Для того чтобы отличать предшествование 2.1 от операторного, внесём символ «∘» за знак < . Пусть у нас есть три символа R, S, T , которые принадлежат словарю алфавита.

Этот путь решения проблемы называется стратификация.

RS>∘ T – S является хвостом основы.(2.1 предшествование).

RS =>∘ T – T принадлежит основе. (2.1 предшествование).

R∘<ST – S является головой основы. (1.2 предшествование).

R∘<= ST – R принадлежит основе. (1.2 предшествование).

R, S, TÎ VN∪VT.

Выводы к определениям:

1. RS>∘T тогда и только тогда, когда имеется вывод Z=>+…[R]UTx…=> =>+…RSTx…

Для этого необходимы следующие выводы: U=>+…S или U=>+…RS.

2. RS =>∘T тогда и только тогда, когда Z=>+…[R]Ux =>...RSTx .

Чтобы получился этот вывод, нужно: U: = ST.

3. R∘< ST тогда и только тогда, когда Z=>+…RUТx =>+…RSTx… .

Чтобы получился этот вывод, нужно: U: = S .

4. R∘<= ST тогда и только тогда, когда Z=>+…UТx =>…RSTx… .

Чтобы получился этот вывод, нужно: U: = RS .

Если цепочка # S₁ S₂ … S_i S_j … S_n # – сентенциальная форма, то основа этой сентенциальной формы будет цепочка S_i … S_j , если для неё выполняется условие

S_i-1∘< S_i S_i+1=>∘ S_i+2 … S_j-1S_j >∘ S_j+1.

=>∘ этот символ означает, что мы ищем хвост основы.

∘<= этот символ означает, что ищем голову основы.

S_i … S_j –основа.

# ∘<S # -условие, когда заканчивается поиск.

Может быть ситуация:

# S_j >∘ S_j+1 #;

# ∘<S_iS_j #;

# ∘<S #.

Если найден хвост, то можно просмотреть правила и сравнить правые части.

Алгоритм распознавания

Распознаватель использует единственную таблицу. Таблица содержит три столбца.

В первом столбце таблицы содержится содержимое стека в форме Tu, где Т - любой символ или ограничитель, а U-правая часть правила.

Второй столбец содержит соответствующие правые контексты (либо # - символ конца цепочки ).

В третьем столбце записан номер правила, которое использовано при редукции.

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

Если такая строка найдена, осуществляется редукция в соответствии с правилом, номер которого указан в третьем столбце.

Если такой строки нет, то редукция невозможна.

Последний сканируемый символ помещается в стек, и сканируется следующий символ предложения.

Предшествование m: n

Грамматика m,n предшествования это такая грамматика, которая удовлетворяет условиям:

1. Все правые части правил единственны.

2. Для любой пары цепочек xy таких, что |x| = m; |y| = n, выполняется не более одного из трех рассмотренных ниже отношений.

W = xy |x| = m; |y| = n.

x ∘< y, если первый символ цепочки y является головой основы.

x >∘ y, если последний символ цепочки x является хвостом основы.

x ≗ y, , если последний символ цепочки x и первый символ цепочки y принадлежат основе.