М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие
 Скачать 0.92 Mb.
|
1.5.Правила синтаксического отождествленияСинтаксическое отождествление выражения-образца и объектного выражения является наиболее сложной операцией, выполняемой рефал-машиной. Отождествление означает, что объектное выражение является частным случаем выражения-образца, как в рассмотренных выше и приводимых ниже примерах. Выражение-образец 'for ' e1 '=' e2 'to' e3 'do' e4 отождествимо со строкой литер 'for i=1 to 12 do n:=n+1' при значениях переменных: e1 ↔ 'i', e2 ↔ '1 ' (значение е2 – два символа, знак единицы и знак пробела), e3 ↔ ' 12 '(значение е3 – четыре символа: пробел, 1, 2, пробел), e4 ↔ ' n:=n+1'. Выражение-образец s1 e2 ')' e3 отождествимо со строкой 'A*(B+C)-D' при значениях переменных: s1 ↔ 'A', e2 ↔ '*(B+C', e3 ↔ '-D' (скобка в выражении-образце не является структурной, в нём указана литера круглой скобки). Выражение-образец e1 '+' t2 e3 синтаксически отождествимо со строкой литер 'X‑5*Y+8/Z' при таких значениях переменных: e1 ↔ 'X‑5*Y', t2 ↔ '8', e3 ↔ '/Z'. Сформулируем общие правила выполнения синтаксического отождествления. Синтаксическое отождествление выражения-образца и объектного выражения выполняется последовательно по входящим в них атомарным элементам и всем парам структурных скобок. При этом должны выполняться следующие условия: Символ-литера синтаксически отождествим только с таким же символом-литерой, например, 'g' отождествим с 'g'. Переменная отождествима только с выражением, вид и структура которого соответствует типу переменной. В частности, e-переменная отождествима с любым рефальским выражением, в том числе пустым; t-переменная отождествима с термом; s-переменная отождествима с любым символом-литерой. Все вхождения в выражение-образец одной и той же переменной должны получить одно и то же значение. Поэтому, к примеру, выражение-образец s1 e2 s1 отождествимо со строкой 'abca' (s1 ↔ 'a', e2 ↔ 'bc'), но не со строкой 'abcd'. При отождествлении левых структурных скобок выражений должны отождествляться и соответствующие (парные к ним) правые структурные скобки этих выражений. Это означает, что при отождествлении баланс структурных скобок не может быть нарушен. Реализованный в рефал-интерпретаторе алгоритм, выполняющий синтаксическое отождествление выражений и в случае успеха определяющий значения употреблённых в выражении-образце переменных, называется алгоритмом проектирования выражения-образца на объектное выражение. Для написания эффективных рефал-программ необходимо понимать важные особенности этого алгоритма. В общем случае выражение-образец содержит так называемые жёсткие элементы – элементы, которые однозначно проектируются на соответствующие элементы объектного выражения. Символы-литеры, структурные скобки, s- и t-переменные – это жёсткие элементы выражения, и если у такого элемента спроектирован один конец, то однозначно проектируется и второй, либо делается вывод о невозможности дальнейшего отождествления. Для символов-литер, структурных скобок и s-переменных это очевидно. Для t‑переменных возможная проекция – это либо символ (тоже очевидный случай), либо выражение в структурных скобках (но в этом случае однозначно находится парная скобка). На всех шагах проектирования действует общий принцип: если спроектирован один конец жёсткого элемента, то делается попытка спроектировать и его второй конец, т.е. весь элемент в целом. Например, выражение-образец 'A'(e1 t2)s3 будет отождествляться с объектным выражением 'A'(('2В'))'7' следующим образом (см. Рис. 1): символ-литера 'A' отождествится с символом-литерой 'A'; первая открывающаяся структурная скобка из объектного выражения отождествится с открывающейся скобкой из выражения-образца; парная ей последняя закрывающаяся скобка из объектного выражения отождествится с закрывающейся структурной скобкой из выражения-образца; переменная t2 выражения-образца отождествится со структурным термом ('2В'); переменная e1 отождествится с пустым выражением; переменная s3 отождествится с символом-литерой '7'.  Рассмотрим дополнительные примеры. Выражение-образец s1(e2 ',' e3) синтаксически отождествим с объектным выражением 'c'('ga,d'), при значениях переменных s1 ↔ 'c', e2 ↔ 'ga', e3 ↔ 'd'. Образец sx ty отождествим с тем же объектным выражением при sx ↔ 'c', ty ↔ ('ga,d'). Выражения ')' и '(' являются обычными символами-литерами и могут быть значениями s-переменных, в отличие от структурных скобок. Баланс символов-литер скобок при отождествлении не проверяется. Поэтому единственным вариантом отождествления образца (e1(s2'(')) с объектным выражением ('a)'('b(')) являются значения переменных e1 ↔ 'a)' и s2 ↔ 'b'. Можно заметить, что в ряде случаев при использовании в выражении-образце нескольких e‑переменных синтаксическое отождествление возможно для нескольких вариантов приписывания этим переменным значений. К примеру, при отождествлении образца e1'+'e2 и выражения 'a+b+c' возможны два варианта: e1 ↔ 'a', e2 ↔ 'b+c' и e1 ↔ 'a+b', e2 ↔ 'c'. Возникновение таких неоднозначностей связано с тем, что е-переменные не ограничиваются по длине, их значениями могут быть произвольные последовательности термов. Ясно, что алгоритм проектирования должен устранять неоднозначности такого типа в случае их возникновения. Возможны два способа, которые называются соответственно отождествление слева направо и отождествление справа налево, или левое и правое согласование. При левом согласовании рефал-машина выбирает тот вариант отождествления (вариант приписывания переменным значений), при котором первая слева е-переменная выражения-образца принимает самое короткое возможное для неё значение. Если это не устраняет неоднозначности, то такой же отбор производится по второй слева е-переменной, затем третьей слева и т.д. При правом согласовании рефал-машина выбирает тот вариант отождествления, при котором первая справа е-переменная принимает самое короткое возможное значение. Если же это не снимает неоднозначности, то такой же отбор производится по второй справа е-переменной, затем третьей справа и т.д. В нашем примере первый вариант отождествления соответствует левому согласованию, а второй – правому. По умолчанию рефал-машина реализует левое согласование. Заметим, что при отождествлении образца е1 е2 с тем же выражением 'a+b+c' при левом согласовании переменные получат значения: e1 ↔ пусто, e2 ↔ 'a+b+c'; а при правом: e1 ↔ 'a+b+c', e2 ↔ пусто. Рассмотрим вновь функцию ChangeAllPlus, определённую в разделе 1.3, и приведём пример её работы. Пусть в поле зрения рефал-машины помещено выражение Поскольку это выражение содержит только один функциональный терм, он будет ведущим, и к входящему в него выражению 'А-B+C' на втором шаге работы рефал-машины будет вновь применено первое предложение функции ChangeAllPlus, но уже при значениях переменных e1 ↔ 'А‑B', e2 ↔ 'C'. Поле зрения после выполнения этого шага примет вид: На третьем шаге работы рефал-машины единственный (и ведущий) функциональный терм заменится на выражение 'А-В-C', так как применимым будет только второе предложение функции при е1 ↔ 'А‑В‑C' (в аргументе функционального обращения нет символа +). На четвёртом шаге произойдёт останов рефал-машины, поскольку в поле зрения нет функциональных термов, а оставшееся в нём выражение 'A-В-С' является результатом вычисления функционального вызова |