1.3.4. ОБРАЗЦЫ

В языке Рефал Плюс основным средством анализа объектных выражений являются образцы. Образцы могут содержать символы, круглые скобки и переменные. Например:

A B C

tX (eY B)

Каждый образец изображает множество объектных выражений, которые могут быть получены из него путем замены переменных на произвольные значения, удовлетворяющие их типам. Например, образец

A eX

изображает множество объектных выражений, которые начинаются с символа A, а образец

sX sY

- множество объектных выражений, состоящих ровно из двух символов.

Если одна и та же переменная входит в образец несколько раз, то все ее вхождения должны иметь одно и то же значение. Например, образец tX tX изображает множество выражений, состоящих из двух одинаковых термов.

Если нам задано объектное выражение Oe и образец P, то всегда можно сопоставить Oe с P и установить, имеет ли Oe структуру, предписанную образцом P. Если да, то мы говорим, что Oe успешно сопоставляется с P, в противном случае мы говорим, что результатом сопоставления является неуспех.

В результате успешного сопоставления Oe с P переменные, входящие в P, связываются с соответствующими частями выражения Oe. Таким образом, результатом сопоставления Oe с P является некоторая среда Env. Например, если мы сопоставим

AAA BBB CCC с образцом eX sY,

результатом сопоставления будет среда {eX = AAA BBB, sY = CCC}.

Попробуем теперь сопоставить выражение A B C с образцом e1 sX e2. Мы обнаружим, что это можно сделать тремя различными способами, в результате чего получаются три разных среды:

{e1 = , sX = A, e2 = B C}

{e1 = A, sX = B, e2 = C}

{e1 = A B, sX = C, e2 = }

Что считать результатом сопоставления в подобных случаях? В Рефале Плюс эта проблема решается следующим образом. Считается, что правильными являются все варианты сопоставления, однако одни варианты "предшествуют" другим, т.е. имеют приоритет.

А именно, пусть Env1 и Env2 - два варианта сопоставления Oe с P. Рассмотрим все вхождения переменных в P. Если Env1 и Env2 не совпадают, они приписывают некоторым переменным различные значения. Найдем в P самое первое слева вхождение переменной которому Env1 и Env2 приписывают разные значения и сравним длину этих значений. Если значение, приписываемое средой Env1, короче, чем значение, приписываемое средой Env2, то считается, что Env1 "предшествует" Env2, т.е. имеет приоритет перед Env2, в противном случае считается, что Env2 "предшествует" Env1.

Например, сопоставим объектное выражение (A1 A2 A3)(B1 B2)

с образцом e1 (eX sA eY) e2.

В результате получится следующее множество вариантов сопоставления

{e1 = , eX = , sA = A1, eY = A2 A3, e2 = (B1 B2)}

{e1 = , eX = A1, sA = A2, eY = A3, e2 = (B1 B2)}

{e1 = , eX = A1 A2, sA = A3, eY = , e2 = (B1 B2)}

{e1 = (A1 A2 A3), eX = , sA = B1, eY = B2, e2 = }

{e1 = (A1 A2 A3), eX = B1, sA = B2, eY = , e2 = }

где варианты сопоставления перечислены в соответствии с их приоритетами, т.е. самый первый вариант находится на первом месте и т.д.

Описанный выше способ упорядочения вариантов сопоставления называется сопоставлением слева направо. Однако в Рефале Плюс имеется возможность упорядочивать варианты сопоставления и справа налево, при этом упорядочение происходит не по самому левому вхождению переменной, а по самому правому. Чтобы изменить порядок сопоставления, следует приписать к образцу слева ключевое слово $r. Например, если мы сопоставим объектное выражение

(A1 A2 A3)(B1 B2) с образцом $r e1 (eX sA eY) e2,

множество вариантов сопоставления будет упорядочено следующим образом:

{e1 = (A1 A2 A3), eX = B1, sA = B2, eY = , e2 = }

{e1 = (A1 A2 A3), eX = , sA = B1, eY = B2, e2 = }

{e1 = , eX = A1 A2, sA = A3, eY = , e2 = (B1 B2)}

{e1 = , eX = A1, sA = A2, eY = A3, e2 = (B1 B2)}

{e1 = , eX = , sA = A1, eY = A2 A3, e2 = (B1 B2)}