|
39 объектов с целью улучшения характеристик известных процедур или создания новых методов синтаксического анализа [41] при решении задач управления в жестких временных условиях. Оценочные характеристики эффективности (временная и емкостная сложность [52]) общих и частных методов синтаксического анализа КСГ, разработанные в рамках этих двух подходов, свидетельствуют о том, что использование известных типов формальных грамматик и соответствующих им методов не позволяет решать задачи моделирования большинства классов СиПО, используемых в АОС [20, 31]. Это обусловлено следующими основными причинами: высокой синтаксической неоднозначностью получаемых с использованием известных типов КСГ описаний СиПО, не отражающих специфику конкретных правил их построения; спецификой формирования элементов СиПО и их взаимосвязей для различных технологий обучения, определяемых иерархически связанной, многоуровневой структурой и представляющих собой более широкий класс формальных языков, чем специальные подклассы контекстно-свободных языков, порождаемых LL(k)-, ЬЯ(к)-грамматиками [52], допускающими эффективные процедуры разбора с линейной временной сложностью [41]. Кроме этого, даже в случае использования неполной системы синтаксических отношений, спецификации СиПО получаются громоздкими [20-27], что значительно затрудняет разработку эталонных грамматик, их модификацию при изменении структуры СиПО [28], усложняет построение соответствующих синтаксических генераторов и анализаторов. |
л» <*> (4 51 быть описан контекстно-свободными грамматиками (КСГ) [16]. Исследованию этого класса формальных грамматик и ориентированных на них методов синтаксического анализа в последние годы было посвящено большое число работ [101-112, 114, 119, 125, 132-191], направленных на решение ряда научных и практических задач. Анализ этих работ показал, что в использовании контекстно-свободных грамматик наблюдаются два, в определенной степени взаимодополняющих, подхода: 1. Использование полной мощности грамматик и их модификаций для описания синтаксиса и семантики распознаваемых и обрабатываемых классов объектов. При этом основным требованием является полнота и адекватность описаний реальным объектам (задачи анализа и синтеза протоколов, представления знаний и т.д.). К эффективности методов синтаксического анализа не предъявляются жесткие требования и, как правило, в этом случае допустимым является использование общих и специальных методов, имеющих квадратичную и более высокую временную сложность [125]. 2. Использование ограниченных по описательным возможностям специальных подклассов КСГ для описания объектов в задачах, в которых предъявляются повышенные требования к эффективности процедур синтаксического анализа (задачи распознавания, принятия решений и т.п.). В этом случае наиболее полно используется информация о специфике описываемого класса объектов с целью улучшения характеристик известных процедур или создания новых методов синтаксического анализа [125] при решении задач распознавания и обработки в жестких временных условиях. Оценочные характеристики эффективности (временная и емкостная сложность [119, 125]) общих и частных методов синтаксического анализа КСГ, разработанные в рамках этих двух подходов, свидетельствуют о том, 52 что использование известных типов формальных грамматик и соответствующих им методов не позволяет решать задачи распознавания большинства классов РСДЗ, используемых в РСУ [10, 11]. Это обусловлено следующими основными причинами: высокой синтаксической неоднозначностью получаемых с использованием известных типов КСГ описаний РСДЗ, не отражающих специфику конкретных правил их построения и передачи в РСУ; спецификой формирования и взаимного вложения элементов РСДЗ, включая специфику форматов кодировании и представления и протоколов передачи, определяемых иерархически связанной, многоуровневой системой протоколов обмена в РСУ и представляющих собой более широкий класс формальных языков, чем специальные подклассы контекстно-свободных языков, порождаемых LL(k)-, 1Л<(к)-грамматиками [119], допускающими эффективные процедуры разбора с линейной временной сложностью [125]. Кроме этого, даже в случае использования неполной системы синтаксических отношений, спецификации РСДЗ получаются громоздкими [16, 119-127], что значительно затрудняет разработку эталонных грамматик, их модификацию при изменении структуры РСДЗ [119], усложняет построение соответствующих синтаксических анализаторов. Проведенный анализ показал, что в последние годы в отечественных и зарубежных изданиях увеличилось число публикаций, посвященных постановке фундаментальных и прикладных работ (в первую очередь под эгидой правительства, силовых ведомств, крупных корпораций ведущих государств мира) по вопросам использования формальных грамматических структур и основанных на них структурно-лингвистических методов для решения достаточно-широкого спектра задач в области распознавания и |