|
86 Входная цепочка считается сгенерированной и разобранной, если возможны ее генерация и анализ, начиная с исходного состояния ~0, и в G(m) = G(I) случае, если '< . Использование векторов состояний позволяет производить возвраты в случае неудачи с разбором очередной части цепочки и проверить новую ветвь разбора. Для реализации записи векторов состояний использованы магазины со специальной стековой организацией доступа к содержимому ячеек. Данный способ может быть реализован с использованием различных вычислительных архитектур, в частности при использовании стандартных вычислительных систем целесообразно реализовать его при использовании для хранения промежуточных результатов генерации и СА отдельных строк памяти или стеков. Для этого необходимо модифицировать понятие состояния МГ и ввести понятие состояния ОП МГ— вида Q = {A,a,D,^,E) А = U(1) Л(2),Л(2),...,Л<2) ... А(т), А(т),...,А(т) \ А(М),А(М) А)где \ 'i 1 1 ’ i ’ 5 1 1 1 ’ 2 5 ’ ■.» 1 1 5 г да» / _ вектор текущих нетерминалов САГС; п = (а(1> ]ат,ат,...,а<» \ ,...,aw\а<-и\ат,\ 1 I ’ 2 ’ 5 у2 1 1 1 2 ,vm 1 1 2 да» ) _ вектор текущих терминалов САГС; D = Ь; (1) I D(2),D(2),...,D(2) I ...I D{m\D™ I\ А 1 I 2 5 5 .V2 * 1 1 ’ 2 5 ’ 1 1 ? 2 ’ NM / вектор позиций концов цепочек, генерируемых (разбираемых, анализируемых) с использованием грамматик, входящих в САГС; В = (в‘п В(2),В(2),...,В(^ ...B( j w),B(”),...,B(") IB^B^,...^) вектор текущих значений унаследованных атрибутов; |
173 (6) Грамматика страты М используется для генерации и анализа соотk ветствующеи подсистемы, при этом используются количественные характек ристики унаследованных атрибутов, занесенные в вектор • • (7) В случае возможности генерации и разбора проводится предсказание в грамматике G^ следующего состояния А$ и продолжение анализа вплоть до достижения заключительного состояния в грамматике. В этом случае вычисляются и синтезированные атрибуты для терминалов и нетерминалов данной грамматики, выдается сигнал в грамматику G™ об успешном выполнении разбора, синтезированные атрибуты, А$я, и позиция конца последней разобранной цепочки заносятся в соответствующие вектора , А^, , и далее продолжается, начиная с этого состояния, анализ ф цепочки в соответствии с шагами (1)-(7). Входная цепочка считается разобранной, если возможен ее полный анализ, начиная с исходного состояния Qo, и в случае, если G^ = G™. Использование векторов состояний позволяет производить возвраты в случае неудачи с разбором очередной части цепочки и проверить новую ветвь разбора. Для реализации записи векторов состояний использованы магазины со специальной стековой организацией доступа к содержимому ячеек. Для реализации данного метода предложены различные алгоритмы, от• личающиеся процедурами отсечения неправильных ветвей генерации и синтаксического анализа, использованием экстралингвистических правил остановки генерации, спецификой использования вероятностных мер на множествах правил подстановки и особенностями применения правил управления и погружения в схеме ГС. Ниже рассмотрен конкретный алгоритм полного СА, ориентированный на регулярные стохастические атрибутные ГС (САГС), аналогичные испольф зованным в четвертом разделе. В отличие от обычных ГС, определяемые в ходе синтаксического анализа значения отдельных параметров соответствуют синтезированным или унаследованным атрибутам терминальных или не |