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

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

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

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

Определение Приведенная КС-грамматика 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 – крайний правый символ некоторой основы.