|
79 общих методов синтаксического анализа: нисходящий анализ ("сверху вниз") и восходящий анализ ("снизу вверх"). Существо каждой из этих стратегий состоит в следующем. В начале синтаксического анализа известны корень дерева вывода (он помечается символом начального нетерминала S) и крона дерева вывода (ее листья слева направо помечаются символами терминальной цепочки в порядке их следования). Стратегия нисходящего синтаксического анализа состоит в построении дерева вывода, двигаясь от корня дерева сверху вниз и слева направо и строя промежуточные вершины дерева вплоть до кроны. Стратегия восходящего синтаксического анализа состоит в построении дерева вывода, начиная от кроны и двигаясь снизу вверх слева направо вплоть до корня дерева. В случае нисходящего анализа процесс построения дерева вывода анализируемой цепочки отвечает ее левому выводу и приводит к получению левого анализа цепочки. В случае восходящего анализа цепочки построение ее дерева вывода осуществляется в порядке, обратном по отношению к порядку выбора подстановок в процессе ее правого вывода. Это означает, что восходящий анализ приводит к получению правого вывода цепочки. Для регулярных грамматик, не содержащих дополнительных правил и атрибутов, задача синтаксического анализа решается достаточно просто путем построения соответствующего конечного автомата. Для случаев использования регулярных и КСграмматических сетей необходима разработка соответствующих методов, дополнительно учитывающих специфику взаимосвязей между входящими в них грамматиками [42, 51]. С учетом того, что в области метаграмматик исследования и разработки находятся в начальной стадии, большинство ориентированных на них методов и алгоритмов синтаксического анализа являются |
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) и крона дерева вывода (ее листья слева направо помечаются символами терминальной цепочки в порядке их следования). Стратегия нисходящего синтаксического анализа • состоит в построении дерева вывода, двигаясь от корня дерева сверху вниз и слева направо и строя промежуточные вершины дерева вплоть до кроны. Стратегия восходящего синтаксического анализа состоит в построении дере 171 ва вывода, начиная от кроны и двигаясь снизу вверх слева направо вплоть до X корня дерева. к В случае нисходящего анализа процесс построения дерева вывода • анализируемой цепочки отвечает ее левому выводу и приводит к получению левого анализа цепочки. В случае восходящего анализа цепочки построение ее дерева вывода осуществляется в порядке, обратном по отношению к порядку выбора подстановок в процессе ее правого вывода. Это означает, что восходящий анализ приводит к получению правого вывода цепочки. Для регулярных грамматик, не содержащих дополнительных правил и атрибутов, задача синтаксического анализа решается достаточно просто путем построения соответствующего конечного автомата. Для случаев использования регулярных и КСграмматических сетей необходима разработка со• ответствующих методов, дополнительно учитывающих специфику взаимосвязей между входящими в них грамматиками [96]. В следующем подразделе представлены метод и алгоритмы полного и неполного СА «сверху-вниз» и «снизу-вверх» регулярных однородных и комбинированных ГС. 5.2.Основные особенности методов полного синтаксического анализа грамматических сетей • Рассматриваемые методы являются модификацией методов полного синтаксического анализа «сверху-вниз» и «снизу-вверх» и ориентированы на использование полных и неполных формальных описаний в виде регулярных стохастических атрибутных графовых ГС. Модификация направлена главным образом на учет структуры правил управления и погружения ГС, а для модификаций ГСи дополнительного набора стохастических синтаксических и атрибутных правил в грамматической сети. ф Суть метода полного СА «сверху-вниз» заключается в выполнении рекурсивной процедуры анализа по правилам управления генерации и последующего грамматического разбора с последовательным предсказанием эле |