|
84 начального нетерминала, соответствующих основным параметрам качества синтезированного варианта стратегии, (программы) обучения, используются для сравнения с ограничениями, задаваемыми выбранным критерием. Если выполняются все ограничения и основной показатель превосходит соответствующие показатели для ранее сгенерированных и проверенных вариантов структур, то он включается в список допустимых вариантов с наивысшим приоритетом. Способ, реализующий выполнение генерации и синтаксического анализа ОП МГ заключается в последовательном выполнении следующих основных шагов для всех грамматик 1т и правил согласования в схеме Wap, m=l(l)M: 1. В грамматике 1т уровня т производится поиск наиболее вероятного (при использующейся записи-самого левого) из еще не использовавшихся n(m) ^(m) __ контекстносвободных правил подстановки вида ,т , где '»■*-» текущее состояние вектора разбора ОП МГ. Осуществляется вычисление унаследованных атрибутов и, если возможно, ряда синтезированных атрибутов, которые заносятся в вектора '»■ и . 2. Если в грамматике 1т уровня т есть входящие АР(ВР) правила согласования из грамматики z,"~1 уровня (ш-1), то также проверяется выделение множеств или одного правила подстановки (р) грамматике 1т~х , где вектора -текущее состояние |
172 К 4’ * ментов грамматик по правилам погружения в грамматиках всех страт, кроме последней (страт М). Для выбора очередных шагов синтаксического анализа применяются соответствующие правила управления и погружения. Реализация метода полного СА «снизу-вверх» отличается использованием инверсных правил вывода, управления и погружения. Определяемые в ходе синтаксического анализа значения отдельных параметров соответствуют синтезированным или унаследованным атрибутам терминальных или нетерминальных символов отдельных грамматик, входящих в ГС. Эти символы выдаются на выход синтаксического анализатора. Алгоритм, реализующий выполнение полного синтаксического анализа «сверху-вниз», заключается в последовательном выполнении следующих основных шагов для грамматики im произвольной страты т : (1) В грамматике im страты т производится поиск наиболее вероятного (при использующейся записи-самого левого) из еще не использовавшихся правил подстановки вида А^----------------где -текущее состояние вектора А^т). Осуществляется вычисление унаследованных атрибутов и, если возможно, ряда синтезированных атрибутов, которые заносятся в вектора и . (2) Если в грамматике im страты т есть входящие правила управления и погружения из грамматики /т_, уровня (w-1), то также проверяется наличие правила подстановки »в грамматике *m-i> где текущее состояние вектора . (3) Производится определение правила погружения вида где S1,^0-начальный нетерминал грамматики n-й страты, М> п> т. (4) В грамматике G^ производятся операции, аналогичные операциям, выполняемым на шагах (1)-{3) для грамматики G}^. (5) Выполнение подобных операций продолжается для всех грамматик, связанных правилами управления, вплоть до достижения страты М, т.е. после перехода aj,"’ ■—>5,(Л/). 174 к г» 4' терминальных символов отдельных грамматик, входящих в САГС. Эти символы подаются на выход синтаксического анализатора, который после вычисления синтезированных атрибутов начального нетерминала, соответствующих основным параметрам полученного варианта интерпретации анализируемых данных или знаний, используются для сравнения с ограничениями, задаваемыми выбранным критерием. Если выполняются все ограничения и основной показатель отбора превосходит соответствующие показатели для ранее сгенерированных и проверенных вариантов структур данных или знаний , то он включается в список допустимых вариантов с наивысшим приоритетом. При использовании процедур ППР проводится синтаксический анализ по полной системе правил согласования и продукций САГС и на выход подается лучший вариант интерпретации по выбранному основному показателю из множества допустимых. При поиске рациональных вариантов процедура останавливается при генерации первого варианта, отвечающего выбранному критерию. Рассматриваемый алгоритм синтаксического анализа ориентирован на применение регулярных САГС с комбинированными правилами управления. Для описания алгоритма, реализующего предложенный метод синтаксического анализа, введены следующие обозначения. Для записи алгоритма введено понятие состояния САГС Q вида б = (Ля,Р,В,£), где А = (а^ вектор текущих нетерминалов САГС; а = (а^ вектор текущих терминалов САГС; А 2? = (pJ,) вектор позиций концов цепочек, генерируемых (разбираемых, анализируемых) с использованием грамматик, входящих в САГС; |