|
38 непосредственно-составляющих (НСГ). Однако для НСГ в настоящее время не создано общих методов синтаксического анализа, имеются только частные методы, реализованные на отдельных подклассах объектов и имеющие экспоненциальную вычислительную сложность, которые не могут быть применены для решения задач управления рассматриваемых классов. Ряд правил, описывающих синтаксис СиПО для АОС, может быть описан контекстно-свободными грамматиками (КСГ) [52]. Исследованию этого класса формальных грамматик и ориентированных на них методов синтаксического анализа в последние годы было посвящено большое число работ, направленных на решение ряда научных и практических задач. Анализ этих работ показал, что в использовании контекстно-свободных грамматик наблюдаются два, в определенной степени взаимодополняющих, подхода: 1. Использование полной мощности грамматик и их модификаций для описания синтаксиса и семантики объектов. При этом основным требованием является полнота и адекватность описаний реальным объектам (задачи анализа и синтеза протоколов, представления знаний и т.д.). К эффективности методов синтаксического анализа не предъявляются жесткие требования и, как правило, в этом случае допустимым является использование общих и специальных методов, имеющих квадратичную и более высокую временную сложность [52]. 2. Использование ограниченных по описательным возможностям специальных подклассов КСГ для описания объектов в задачах, в которых предъявляются повышенные требования к эффективности процедур синтаксического анализа (задачи принятия решений и т.п.). В этом случае наиболее полно используется информация о специфике описываемого класса |
50 С4, ГФ составляют современный арсенал теории формальных грамматик и структурнолингвистического распознавания образов. В настоящее время принято разделять структурно-лингвистические методы распознавания в соответствии с типом используемых в них формальных грамматик как наиболее важного типизационного признака, определяющего сложность структуры распознаваемых и обрабатываемых объектов и эффективность используемых процедур синтаксического анализа [119, 125]. В соответствии с этим классификационным признаком известные методы структурно-лингвистического распознавания подразделяются на большое число классов, ориентированных на конкретные типы грамматик, отличающиеся используемыми правилами подстановки (классификация по Хомскому [119]), применением различного рода экстралингвистических отношений (атрибутные грамматики, категориальные грамматики [111, 114] и т.д.), использованием специально задаваемых отношений между элементами грамматик (грамматики предшествования, программные и индексные грамматики [119, 132-191]), заданием различных мер (нечетких, вероятностных [119, 177]) на множестве используемых продукций. В работах, посвященных РО РСДЗ, анализу и синтезу форматов представления и протоколов их передачи, показано [132], что для описания свойственным им основных синтаксических отношений, определяющих структуры и порядок передачи различных уровней, взаимную вложенность сигналов различных уровней эталонной модели взаимодействия открытых систем и т. п., достаточно мощности множества языков, порождаемого грамматиками непосредственно-составляющих (НСГ) [119]. Однако для НСГ в настоящее время не создано общих методов синтаксического анализа, имеются только частные методы, реализованные на отдельных подклассах распознаваемых объектов и имеющие экспоненциальную вычислительную сложность, которые не могут быть применены для распознавания и обработки РСДЗ. Ряд правил, описывающих синтаксис РСДЗ для РСУ, может л» <*> (4 51 быть описан контекстно-свободными грамматиками (КСГ) [16]. Исследованию этого класса формальных грамматик и ориентированных на них методов синтаксического анализа в последние годы было посвящено большое число работ [101-112, 114, 119, 125, 132-191], направленных на решение ряда научных и практических задач. Анализ этих работ показал, что в использовании контекстно-свободных грамматик наблюдаются два, в определенной степени взаимодополняющих, подхода: 1. Использование полной мощности грамматик и их модификаций для описания синтаксиса и семантики распознаваемых и обрабатываемых классов объектов. При этом основным требованием является полнота и адекватность описаний реальным объектам (задачи анализа и синтеза протоколов, представления знаний и т.д.). К эффективности методов синтаксического анализа не предъявляются жесткие требования и, как правило, в этом случае допустимым является использование общих и специальных методов, имеющих квадратичную и более высокую временную сложность [125]. 2. Использование ограниченных по описательным возможностям специальных подклассов КСГ для описания объектов в задачах, в которых предъявляются повышенные требования к эффективности процедур синтаксического анализа (задачи распознавания, принятия решений и т.п.). В этом случае наиболее полно используется информация о специфике описываемого класса объектов с целью улучшения характеристик известных процедур или создания новых методов синтаксического анализа [125] при решении задач распознавания и обработки в жестких временных условиях. Оценочные характеристики эффективности (временная и емкостная сложность [119, 125]) общих и частных методов синтаксического анализа КСГ, разработанные в рамках этих двух подходов, свидетельствуют о том, |