Теория и реализация языков программирования



             

Атрибутная схема для алгоритма сопоставления образцов - часть 2


предыдущий раздел). Выбор оптимального покрытия может быть сделан еще одним проходом по дереву, аналогично тому, как это было сделано выше. Например, в правиле с '+' имеется несколько образцов для Reg, но реального выбора одного из них не осуществляется. Кроме того, не уточнены некоторые детали реализации. В частности, конкретный способ формирования векторов Match и Pattern. В тексте употребляется термин "добавить", что означает добавление к вектору образцов очередного элемента. Векторы образцов записаны в угловых скобках.

RULE Stat ::= '=' Reg Reg SEMANTICS Match<2>=<'+' Reg Const>; Match<3>=<Reg>; Pattern<0>[1]=Pattern<2>[1]&Pattern<3>[1].

Этому правилу соответствует один образец 2. Поэтому в качестве образцов потомков через их атрибуты Match передаются, соответственно, <'+' Reg Const> и <Reg>.

RULE Reg ::= '+' Reg Reg SEMANTICS if (Match<0> содержит Reg в позиции i) {Match<2>=<Reg,Reg,Reg>; Match<3>=<Const,Reg,<'@' '+' Reg Const>>; } if (Match<0> содержит образец <'+' Reg Const> в позиции j) {добавить Reg к Match<2> в некоторой позиции k; добавить Const к Match<3> в некоторой позиции k; } if (Match<0> содержит образец <'+' Reg Const> в позиции j) Pattern<0>[j]=Pattern<2>[k]&Pattern<3>[k]; if (Match[0] содержит Reg в i-й позиции) Pattern<0>[i]=(Pattern<2>[1]&Pattern<3>[1]) |(Pattern<2>[2]&Pattern<3>[2]) |(Pattern<2>[3]&Pattern<3>[3]).

Образцы, соответствующие этому правилу, следующие:

(4) Reg

'+' Reg Const, (5) Reg
'+' Reg Reg, (6) Reg
'+' Reg '@' '+' Reg Const.

Атрибутам Match второго и третьего символов в качестве образцов при сопоставлении могут быть переданы векторы <Reg, Reg, Reg> и <Const, Reg, <'@' '+' Reg Const>>, соответственно. Из анализа других правил можно заключить, что при сопоставлении образцов предков левой части данного правила атрибуту Match символа левой части может быть передан образец <'+' Reg Const> (из образцов 2, 3, 6) или образец Reg.




Содержание  Назад  Вперед