|
108 двигаясь от корня дерева сверху вниз и слева направо и строя промежуточные вершины дерева вплоть до кроны. Стратегия восходящего синтаксического анализа состоит в построении дерева вывода, начиная от кроны и двигаясь снизу вверх слева направо вплоть до корня дерева. В случае нисходящего анализа процесс построения дерева вывода анализируемой цепочки отвечает ее левому выводу и приводит к получению левого анализа цепочки. В случае восходящего анализа цепочки построение ее дерева вывода осуществляется в порядке, обратном по отношению к порядку выбора подстановок в процессе ее правого вывода. Это означает, что восходящий анализ приводит к получению правого вывода цепочки. Для регулярных метаграмматик, не содержащих дополнительных правил и атрибутов, задача синтаксического анализа решается путем построения соответствующей сети взаимодействующих конечных автоматов или использования предложенных в работах [42, 51] алгоритмов синтаксического анализа. В то же время с учетом специфики КТД, пока не предложено эффективного алгоритма декодирования, учитывающего все основные особенности предложенной выше ТМГ и специфики кодовых структур рассматриваемого класса. Необходимо отметить преимущественно аппаратную ориентацию разрабатываемого алгоритма, требующего параллельный опрос ячеек специально заполняемой памяти. Ниже представлены результаты разработки алгоритма декодирования КТД, учитывающего особенности предложенной модели на основе ТМГ. |
("сверху вниз") и восходящий анализ ("снизу вверх"). Существо каждой из этих стратегий состоит в следующем. В начале синтаксического анализа известны корень дерева вывода (он помечается символом начального нетерминала S) и крона дерева вывода (ее листья слева направо помечаются символами терминальной цепочки в порядке их следования). Стратегия нисходящего синтаксического анализа состоит в построении дерева вывода, двигаясь от корня дерева сверху вниз и слева направо и строя промежуточные вершины дерева вплоть до кроны. Стратегия восходящего синтаксического анализа состоит в построении дерева вывода, начиная от кроны и двигаясь снизу вверх слева направо вплоть до корня дерева. В случае нисходящего анализа процесс построения дерева вывода анализируемой цепочки отвечает ее левому выводу и приводит к получению левого анализа цепочки. В случае восходящего анализа цепочки построение ее дерева вывода осуществляется в порядке, обратном по отношению к порядку выбора подстановок в процессе ее правого вывода. Это означает, что восходящий анализ приводит к получению правого вывода цепочки. Для регулярных метаграмматик, не содержащих дополнительных правил и атрибутов, задача синтаксического анализа решается путем построения соответствующей сети взаимодействующих конечных автоматов или использования предложенных в работах [42, 51] алгоритмов синтаксического анализа. В то же время с учетом специфики НПК, пока не предложено эффективного алгоритма декодирования, учитывающего все основные особенности предложенной выше МГМ и специфики реализуемой 77 |