|
78 Синтаксический анализ (СА)это процедура, которая для любой цепочки символов из некоторого терминального алфавита определяет, принадлежит ли она языку L(G), порождаемому формальной грамматикой (в данном случаеОП МГ) G, и строит хотя бы одно дерево вывода этой цепочки в грамматике G, если ответ на первый вопрос положительный. По результатам синтаксического анализа принимается решение о выборе или отвержении сгененрированного варианта СиПО, а конкретное дерево вывода соответствует необходимым цепочкам элементов программ обучения (терминалы грамматик ОП МГ) и управляющим воздействиям (нетерминалы грамматик ОП МГ). Общие принципы синтаксического анализа и его конкретные особенности рассмотрены в работах [42, 51-93]. Пусть G некоторая грамматика и coeL(G) цепочка. Цепочка со (синтаксически) проанализирована, если построено хотя бы одно из ее деревьев вывода в грамматике G. Пусть G= < VH, VT, Р, S > грамматика, подстановки которой занумерованы числами 1, 2,... . Левым анализом цепочки со называется последовательность номеров подстановок, примененных при левом выводе цепочки со из начального нетерминала S. Правым анализом цепочки со называется обращение последовательности номеров подстановок, примененных при правом выводе цепочки со из начального нетерминала S. Существуют различные стратегии синтаксического анализа различных классов грамматик и грамматических структур. Для большинства классов контекстносвободных и НС грамматик, а также соответствующих грамматических структур можно выделить две основные стратегии для |
169 5.1.Основные особенности методов и алгоритмов синтаксического анализа (грамматического разбора) разнородных сложноструктурированных данных и знаний Выше были рассмотрены основные особенности используемых при решении задач распознавания и обработки формальных грамматик и грамматических структур, известных процедур их восстановления. Формальные грамматики и грамматические структуры служат средством задания синтаксиса и семантики формальных языков, т.е. правил соединения отдельных терминальных символов в цепочки, описывающие структурные особенности рассматриваемых классов объектов. Синтаксическая структура каждой отдельной терминальной цепочки языка, порождаемого данной формальной грамматикой, характеризуется ее деревом вывода, которое является графическим представлением последовательности подстановок, используемых при выводе этой терминальной цепочки из начального нетерминала грамматики или грамматической структуры. Синтаксический анализэто процедура, которая для любой цепочки символов из некоторого терминального алфавита определяет, принадлежит ли она языку L(G), порождаемому формальной грамматикой или грамматической структурой G, и строит хотя бы одно дерево вывода этой цепочки в грамматике G, если ответ на первый вопрос положительный. В данном подразделе рассматриваются лишь основные особенности используемых при распознавании и обработке сложноструктурированных сигналов и сообщений методов синтаксического анализа, общие принципы построения соответствующих синтаксических анализаторов. С учетом того, что в области грамматических структур исследования и разработки находятся в начальной стадии, большинство ориентированных на них методов и ал 170 горитмов синтаксического анализа являются модификациями известных методов анализа формальных грамматик, дополнительно учитывающих взаимок связи между грамматиками, а для ряда классов грамматических структур в Ф известных работах пока не предложено формализованных методов синтаксического анализа. Общие принципы синтаксического анализа и его конкретные особенности рассмотрены в работах [96, 129, 125, 133-191]. Пусть G некоторая грамматика и coeL(G) цепочка. Цепочка со (синтаксически) проанализирована, если построено хотя бы одно из ее деревьев вывода в грамматике G. Пусть G= < Vh, Vt, Р, S > грамматика, подстановки которой занумерованы числами 1, 2,... . Левым анализом цепочки со называется после• довательность номеров подстановок, примененных при левом выводе цепочки со из начального нетерминала 5. Правым анализом цепочки со называется обращение последовательности номеров подстановок, примененных при правом выводе цепочки со из начального нетерминала S. Существуют различные стратегии синтаксического анализа различных классов грамматик и грамматических структур. Для большинства классов контекстносвободных и НС грамматик, а также соответствующих грам• матических структур можно выделить две основные стратегии для общих ме> тодов синтаксического анализа: нисходящий анализ ("сверху вниз") и восходящий анализ ("снизу вверх"). Существо каждой из этих стратегий состоит в следующем. В начале синтаксического анализа известны корень дерева вывода (он помечается символом начального нетерминала S) и крона дерева вывода (ее листья слева направо помечаются символами терминальной цепочки в порядке их следования). Стратегия нисходящего синтаксического анализа • состоит в построении дерева вывода, двигаясь от корня дерева сверху вниз и слева направо и строя промежуточные вершины дерева вплоть до кроны. Стратегия восходящего синтаксического анализа состоит в построении дере |