|
52 правила aiAa2->aipa2, где Ае VNi, ab р, a2 е V*i, р^е (е-пустая цепочка), V\ итерация множества Vj = V№ uVT„ а остальные грамматики имеют схемы с более сильными ограничениями на тип правил подстановки (правила типа 2 и 3). 3. Грамматики типа 2-хотя бы одна грамматика содержит правила А-»р, где Ае VNi, ре V'1; V+jположительная итерация множества Vi = VNl ljVTi, а остальные грамматики имеют схемы с более сильными ограничениями на тип правил подстановки (правила типа 3). 4. Грамматики типа 3-грамматики содержат правила типа 3 А->аВ, или А^а, где A,Be VNl, ае VTj. Соответственно, ТМГ подобных типов будем обозначать Grc(i), где i-тип ТМГ, i=0(l)3. Применение МГ различных типов определяется особенностями синтаксической структуры специфицируемых КТД, требованиями к полноте, адекватности и структурной сложности создаваемых формальных моделей [22], а также эффективностью алгоритмов синтаксического анализа. В реальной практике решения близких прикладных задач обработки разнородных данных [25] этот выбор сводится к поиску компромисса между стремлением к наиболее полному формальному описанию синтаксических и семантических особенностей специфицируемых КТД (с уменьшением номера класса i (i=l(l)3) «выразительная мощность» грамматик увеличивается) и требованиями к эффективности процедур синтаксического анализа (в большинстве случаев с уменьшением номера класса i достаточно быстро возрастает сложность алгоритмов грамматического разбора [26]). С целью разрешения этого противоречия в ряде работ [27-32] предложено использовать специальные подклассы формальных грамматик, ориентированные на привлечение дополнительной |
Одним из наиболее важных классификационных признаков, определяющим выразительные возможности МГ и большинства других классов формальных грамматик и грамматических структур, является тип используемых правил подстановки (продукций) [19]. В соответствии с общепринятой классификацией формальных грамматик по Хомскому [23], выделяют 4 типа МГ, отличающихся ограничениями, накладываемыми на множество продукций: регулярные (тип 3), контекстно-свободные (тип 2), контекстно-зависимые ОП МГ (ОП МГ непосредственносоставляющих) (тип 1) и неограниченные ОП МГ (тип 0). Для этих случаев входящие МГ грамматики { Грамматики типа 0 нет ограничений на тип правил подстановки. 2. Грамматики типа 1—хотя бы одна грамматика содержит правила aiA a2—>otipa2, где A s V^, а\, (3, a 2 е V * j , р^е (е-пустая цепочка), V*; итерация множества V; = VNi uV-n, а остальные грамматики имеют схемы с более сильными ограничениями на тип правил подстановки (правила типа 2 и 3). 3. Грамматики типа 2-хотя бы одна грамматика содержит правила А->р, где Ае VNi, Ре V+j, V+jположительная итерация множества V, = VNi uV[i, а остальные грамматики имеют схемы с более сильными ограничениями на тип правил подстановки (правила типа 3). 4. Грамматики типа 3-грамматики содержат правила типа 3 А-»аВ, или А—»а, где А,Be Умь ае Уц. Соответственно, ОП МГ подобных типов будем обозначать Grc(i), где i-тип ОПМГ, i=0(l)3. Применение МГ различных типов определяется особенностями синтаксической структуры специфицируемых НПК, требованиями к полноте, адекватности и структурной сложности создаваемых формальных 65 моделей [22], а также эффективностью алгоритмов синтаксического анализа. В реальной практике решения близких прикладных задач обработки разнородных данных [25] этот выбор сводится к поиску компромисса между стремлением к наиболее полному формальному описанию синтаксических и семантических особенностей специфицируемых НПК (с уменьшением номера класса i (i=l(l)3) «выразительная мощность» грамматик увеличивается) и требованиями к эффективности процедур синтаксического анализа (в большинстве случаев с уменьшением номера класса i достаточно быстро возрастает сложность алгоритмов 1рамматического разбора [26]). С целыо разрешения этого противоречия в ряде работ [27-32] предложено использовать специальные подклассы формальных грамматик, ориентированные на привлечение дополнительной информации о синтаксических отношениях в моделируемых объектах. Это позволяет создавать достаточно эффективные процедуры синтаксического анализа за счет введения дополнительных правил и элементов в используемые грамматики (различные классы грамматик предшествования) или принятия допущений о свойствах анализируемых цепочек элементов, представляющих структуру моделируемых объектов (LR(k)-, LL(k)грамматики и т.п.). Аналогичными свойствами обладают и обычные МГ. Это определяется, помимо возможности использования специальных типов грамматик, таюке возможностью привлечения дополнительной информации о структуре специфицируемых объектов, явно отражаемой в схеме правил согласования МГ; возможностью создания МГ, в которых часть грамматик, явным образом управляет началом и окончанием порождения (синтаксического анализа) в других грамматиках (аналогично ряду подклассов комбинированных TS(3)~ и ТР(4)метаграмматик, программным грамматикам или контекстно-зависимым грамматикам [31]). Проведенный анализ синтаксических, алгебраических и семантических особенностей типовых классов НПК, используемых для передачи данных в GRID системах [19-30], показал, что при решении большинства прикладных 66 |