Математическая теория формальных языков
Нисходящий разбор
Определение 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.
