|
53 информации о синтаксических отношениях в моделируемых объектах. Это позволяет создавать достаточно эффективные процедуры синтаксического анализа за счет введения дополнительных правил и элементов в используемые грамматики (различные классы грамматик предшествования) или принятия допущений о свойствах анализируемых цепочек элементов, представляющих структуру моделируемых объектов (LR(k)-, LL(k)грамматики и т.п.). Аналогичными свойствами обладают и ТМГ. Это определяется, помимо возможности использования специальных типов грамматик, также возможностью привлечения дополнительной информации о структуре специфицируемых объектов, явно отражаемой в схеме правил согласования ТМГ; возможностью создания ТМГ, в которых часть грамматик явным образом управляет началом и окончанием трансляции кодов [31]). Проведенный анализ синтаксических, алгебраических и семантических особенностей типовых классов КТД, показал, что при решении большинства прикладных задач рассматриваемого класса можно ограничить спектр рассматриваемых МГ контекстносвободными линейными ТМГ. Это позволяет при моделировании КТД: специфицировать ряд правил и отношений, отражающих транслируемые значения КТД и создать таким образом формальную основу для эффективного решения рассматриваемого класса задач декодирования КТД; в ряде случаев существенно снизить сложность и громоздкость создаваемых моделей за счет исключения дублирования и согласования использования грамматик, входящих в ТМГ; исключить возможность порождения лишних (алгебраически неправильных) цепочек; |
моделей [22], а также эффективностью алгоритмов синтаксического анализа. В реальной практике решения близких прикладных задач обработки разнородных данных [25] этот выбор сводится к поиску компромисса между стремлением к наиболее полному формальному описанию синтаксических и семантических особенностей специфицируемых НПК (с уменьшением номера класса i (i=l(l)3) «выразительная мощность» грамматик увеличивается) и требованиями к эффективности процедур синтаксического анализа (в большинстве случаев с уменьшением номера класса i достаточно быстро возрастает сложность алгоритмов 1рамматического разбора [26]). С целыо разрешения этого противоречия в ряде работ [27-32] предложено использовать специальные подклассы формальных грамматик, ориентированные на привлечение дополнительной информации о синтаксических отношениях в моделируемых объектах. Это позволяет создавать достаточно эффективные процедуры синтаксического анализа за счет введения дополнительных правил и элементов в используемые грамматики (различные классы грамматик предшествования) или принятия допущений о свойствах анализируемых цепочек элементов, представляющих структуру моделируемых объектов (LR(k)-, LL(k)грамматики и т.п.). Аналогичными свойствами обладают и обычные МГ. Это определяется, помимо возможности использования специальных типов грамматик, таюке возможностью привлечения дополнительной информации о структуре специфицируемых объектов, явно отражаемой в схеме правил согласования МГ; возможностью создания МГ, в которых часть грамматик, явным образом управляет началом и окончанием порождения (синтаксического анализа) в других грамматиках (аналогично ряду подклассов комбинированных TS(3)~ и ТР(4)метаграмматик, программным грамматикам или контекстно-зависимым грамматикам [31]). Проведенный анализ синтаксических, алгебраических и семантических особенностей типовых классов НПК, используемых для передачи данных в GRID системах [19-30], показал, что при решении большинства прикладных 66 задач рассматриваемого класса можно ограничить спектр рассматриваемых МГ регулярными МГ. Это позволяет при моделировании НПК: специфицировать ряд правил и отношений, отражающих транслируемые значения префиксных кодовых слов и их комбинаций и создать таким образом формальную основу для эффективного решения рассматриваемого класса задач декодирования НПК; в ряде случаев существенно снизить сложность и громоздкость создаваемых моделей за счет исключения дублирования и согласования использования грамматик, входящих в МГ; исключить возможность порождения лишних (алгебраически неправильных) цепочек; при создании специальных модификаций правил согласования для атрибутных грамматик [25] существенно снизить сложность процедур синтаксического анализа цепочек НПК. В схеме МГ могут использоваться и другие известные модификации грамматик [26, 29, 33] и их комбинации при соответствующем использовании правил согласования. В ходе рассмотрения предложенной классификационной схемы для моделирования НПК могут быть использованы выделены стохастические и нечеткие МГ, аналогично [42]. Типизация правил согласования, их физическая интерпретация и вытекающие из этого свойства МГ достаточно полно представлены в работах [20-32]. Ряд других разновидностей грамматик, включая графовые, транслирующие, аналогичным образом может быть включен в МГ с соответствующей модификацией правил согласования. При классификации МГ необходимо выделить особенности схемы правил согласования МГ в целом наиболее интересные с точки зрения проводимых прикладных исследований (см. рис. 2.1). 67 |