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

         

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


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

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

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

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

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

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

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

и

для некоторых , , , , то Ai+1 = B и .

Пример 13.1.3.

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

Дереву вывода

соответствует левосторонний вывод

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

Лемма 13.1.4.

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

Замечание 13.1.5.

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

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

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



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

Пример 13.1.7.

Левым разбором слова

aceaacecbecbb

в грамматике из примера 13.1.3 является последовательность

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

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

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

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

Пример 13.1.10.

Рассмотрим МП-автомат

из примера 10.2.8. Последовательность

является вычислительным процессом этого МП-автомата.

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

Если в некотором вычислительном процессе МП-автомата

первая конфигурация имеет вид , где

и , а последняя конфигурация имеет вид , где , то будем говорить, что этот вычислительный процесс допускает слово w.

Пример 13.1.12.

Вычислительный процесс из примера 13.1.10 допускает слово bab.

Замечание 13.1.13.

МП-автомат M допускает слово

тогда и только тогда, когда некоторый вычислительный процесс МП-автомата M допускает слово w.



Содержание раздела