Восходящие распознаватели языков

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

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

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

Определение Приведенная КС-грамматика G (V_N, V_T, P, S) называется грамматикой простого предшествования, если выполняются следующие условия.

1) Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования:

а) B_i =× B_j (" B_i, B_j Î V), если и только если существует правило A®xB_iB_jy Î P, где x, y Î V^*;

б) B_i < × B_j (" B_i, B_j Î V), если и только если существует правило A®xB_iDy Î P и вывод DÞ *B_jz, где A, D Î V_N, x, y, z Î V^*;

в) B_i × > B_j (" B_i, B_j Î V), если и только если существует правило A®xCB_jy и вывод СÞ *zB_i или существует правило A®xCDy Î P и вывод СÞ *zB_i и DÞ *B_jw, где A, C, D Î V_N, x, y, z, w Î V^*.

2) Различные правила в грамматике имеют разные правые части.

Определение Отношения =×, < ×, × > называют отношениями простого предшествования для символов грамматики.

В основе распознавателя для грамматик простого предшествования лежит правосторонний разбор строки языка. Исходной сентенциальной формой является заданная строка языка, а целевой – начальный символ грамматики. На каждом шаге разбора в исходной цепочке символов пытаются выделить подцепочку, совпадающую с правой частью некоторого правила вывода грамматики, и заменить ее нетерминалом, стоящим в левой части этого правила. Данная операция называется сверткой к нетерминалу, а заменяемая подстрока – основой сентенции. Описанный процесс разбора соответствует построению дерева вывода цепочки снизу вверх (от листьев к корню).

Метод предшествования основан на том факте, что отношения между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:

- B_i =× B_i+1, если символы B_i и B_i+1 принадлежат основе;

- B_i < × B_i+1, если B_i+1 – крайний левый символ некоторой основы;

- B_i × > B_i+1, если B_i – крайний правый символ некоторой основы.

 

Поиск основы сентенции грамматики

Если грамматика является грамматикой простого предшествования, то для поиска основы каждой ее сентенции надо просматривать элементы сентенции слева направо и найти самую левую пару символов x_j и x_j+1, такую что x_j× > x_j+1. Окончанием основы сентенции будет x_j.Далее просматривать элементы сентенции справа налево, начиная с символа x_j до тех пор, пока не будет найдена самая правая пара символов x_i-1 и x_i, такая что x_i-1 < × x_i. Заголовком основы будет символ x_i. Таким образом, будет найдена основа сентенции, имеющая вид x_i x_i+1…x_j-1 x_j. Схема поиска основы сентенции грамматики представлена на рисунке 3.4.

 

 

x1

x2

…

xi-1

xi

xi+1

…

xj-1

xj

xj+1

…

xn

< × … < × =× … =× × > … × >

 

Рисунок 3.4 – Схема поиска основы сентенции грамматики

 

На основе отношений предшествования строят матрицу предшествования грамматики. Строки и столбцы матрицы предшествования помечаются символами грамматики. Пустые клетки матрицы указывают на то, что данные символы не связаны отношением предшествования.

Определение Построение матрицы предшествования основано на двух вспомогательных множествах, определяемых следующим образом:

- L(A) = {X | $ AÞ *Xz}, AÎ V_N, XÎ V, zÎ V^* - множество крайних левых символов относительно нетерминального символа А;

- R(A) = {X | $ AÞ *zX}, AÎ V_N, XÎ V, zÎ V^* - множество крайних правых символов относительно нетерминального символа А.

 

Определение Отношения предшествования можно определить с помощью введенных множеств следующим образом:

 

- B_i =× B_j (" B_i, B_j Î V), если и только если существует правило A®xB_iB_jy Î P, где AÎ V_N, x, y Î V^*;

- B_i < × B_j (" B_i, B_j Î V), если и только если существует правило A®xB_iDyÎ P и B_j Î L(D), где A, D Î V_N, x, y Î V^*;

- B_i × > B_j (" B_i, B_j Î V), если и только если существует правило A®xCB_jy и B_i Î R(C) или существует правило A®xCDy Î P и B_i Î R(C), B_jÎ L(D), где A, C, D Î V_N, x, y Î V^*.

Матрицу предшествования дополняют символами ^_н и ^_к (начало и конец цепочки). Для них определены следующие отношения предшествования:

- ^_н < × X, " X Î V, если X Î L(S);

- ^_к × > X, " X Î V, если X Î R(S).

 

3.5.1.1.3 Построение множеств L(A) и R(A)

Шаг 1. Для каждого нетерминального символа А ищем все правила, содержание А в левой части. Во множество L(A) включаем самый левый символ из правой части правил, а во множество R(A) – самый крайний правый символ из правой части, т.е.

" A Î V_N: L₀(A) = {X | A®Xy, X Î V, y Î V^*},

R₀(A) = {X | A®yX, X Î V, y Î V^*}.

Шаг 2. Для каждого нетерминального символа А: если множество L(A) содержит нетерминальные символы грамматики А¢ , A² , …, то множество L(A) надо дополнить символами, входящими в соответствующие множества L(А¢ ), L(A² ) и т.д., … и не входящими в L(A). Аналогичную операцию выполнить для множеств R(A), т.е.

" A Î V_N: L_i(A) = L_i-1(A)È L_i-1(B), " B Î (L_i-1(A)Ç V_N),

R_i(A) = R_i-1(A)È R_i-1(B), " B Î (R_i-1(A)Ç V_N).

Шаг 3.Если на предыдущем шаге хотя бы одно множество L(A) или R(A) для некоторого символа грамматики изменилось, то вернуться к шагу 2, иначе построение закончено. Т.е. если существует AÎ V_N: R_i(A)¹ R_i-1(A) или L_i(A)¹ L_i-1(A), то положить i: =i+1 и вернуться к шагу 2, иначе построение закончено и R(A) = R_i(A) и L(A) = L_i(A).

 

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться:

Популярное:

1. БИЛЕТ 1. Перевод как разновидность межъязыковой и межкультурной коммуникации. Общественное предназначение перевода.
2. Билет№16 Уровень понимания текста. Контроль уровня сформированности языковых навыков.
3. Ж.-Ж. Руссо. Опыт о происхождении языков, а также о мелодии и музыкальном подражании.
4. Кафедра иностранных языков ФИиМО
5. Кафедра латинского и иностранных языков
6. Коммуникация и языковые барьеры
7. Концепт вторичной языковой личности.
8. Механизмы распознавания языков
9. Обобщённые схемы процесса формирования народов и языков
10. Оценка - это объективно-субъективное или субъективно-объективное отношение человека к объекту, выраженное языковыми средствами эксплицитно или имплицитно.
11. Понятие «грамматический навык», его операционный состав и его характеристика; языковые и речевые навыки.