Математическая теория формальных языков



             

Восходящий разбор


Определение 13.2.1.

Протоколом правостороннего вывода в контекстно-свободной грамматике

будем называть обращенную последовательность правил, примененных в этом выводе. Формально говоря, протоколом правостороннего вывода

является последовательность

где для каждого i<n, если

и

для некоторых , , , , то An-i = B и .

Пример 13.2.2.

Рассмотрим контекстно-свободную грамматику

и дерево вывода

из примера 13.1.3. Этому дереву вывода соответствует правосторонний вывод

Протоколом этого вывода является последовательность

Лемма 13.2.3.

Разным правосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют разные протоколы.

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

Например, протокол правостороннего вывода из примера 13.2.2 задает процесс постепенного конструирования дерева вывода, изображенный ниже.

Определение 13.2.5.

Правым разбором (right parse) слова w в контекстно-свободной грамматике G называется протокол любого правостороннего вывода слова w в грамматике G.

Пример 13.2.6.

Правым разбором слова aceaacecbecbb в грамматике из примера 13.2.2 является последовательность

Определение 13.2.7.

Процесс нахождения правого разбора слова w в~заданной контекстно-свободной грамматике G называется восходящим разбором (bottom-up parsing).

Определение 13.2.8.

Пусть даны контекстно-свободная грамматика

и МП-автомат . Будем говорить, что МП-автомат M - восходящий магазинный анализатор (bottom-up, left-to-right parser) для грамматики G, если

и существует такой гомоморфизм , что для каждого вычислительного процесса (МП-автомата M), допускающего слово , образ протокола этого вычислительного процесса при гомоморфизме r является протоколом некоторого правостороннего вывода слова w в грамматике .




Содержание  Назад  Вперед