Математическая теория формальных языков
Восходящий разбор
Определение 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 в грамматике .
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий