r7 - 20 Apr 2005 - 09:02:24 - Luba ParmyonovaYou are here: TWiki >  Refaldevel Web > SynIdent
Сопоставение с образцом (синтаксическое отождестление) в Рефале является одним из основных изобразительных средств языка. Этот раздел посвящен описанию классических оптимизаций синтаксического отождествления.
При составлении этого материала использовались следующие источники:
В.Ф. Турчин. Базисный РЕФАЛ и его реализация на вычислительных машинах (методические рекомендации). ЦНИПИАСС Госстроя СССР, Москва, 1977.
С.А. Романенко. Язык прогрммирования Рефал Плюс. "Интертех", Москва, 1991.
С.А. Романенко. Машинно-независимый компилятор с языка рекурсивных функций. Диссертация на соискание ученой степени кандидата физико-математических наук.

Минимальной синтаксической единицей языка, не расчленимой на составные части, является знак. Все знаки языка делятся на собственные и объектные. Набор объектных знаков ограничен (используются буквы русского и латинского алфавитов, цифры, +, -, =, /, *). К собственным знакам относятся, например, конкретизационные (функциональные) скобки <, >, знак кавычка ', структурные скобки ( ). В языке Рефал минимальная семантическая единица языка - символ, который может состоять из одного объектного знака или последовательности объектных знаков, взятой в кавычки (составной символ).

Выражение - это последовательность знаков, правильно построенная относительно скобок ( ), < > и ' '.

  1. Пустой объект есть выражение.
  2. Символ есть выражение. Свободная переменнная есть выражение.
  3. Последовательность выражений есть выражение.
  4. Выражение, взятое в структурные или функциональные скобки есть выражение.

Терм - частный случай выражения. Он представлет собой либо символ, либо выражение, взятое в структурные или конкретизационные скобки. Таким образом, выражение - это последовательность (возможно пустая) из некоторого числа термов.

Свободные переменные изображаются парой знаков, первый из которых является признаком типа (e - признак выражения, t - признак терма, s - признак символа) и следующего за ним индекса. Свободная переменнная может принять в качестве значения любое выражение соответствующего типа.

Предложение (или правило конкретизации) состоит из левой части (заменяемый объект) и правой части (заменяющий левую часть объект).

Рефал-машина, выполняющая конкретизацию, обладает полем зрения, где находится выражение, которое обрабатывается (конкретизируется) в данный момент, и полем памяти, где хранятся предложения.

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

  1. и образец, и объект - симметричные, то есть в процессе отождествления возможно движение как слева направо, так и справа налево;
  2. и образец, и объект являются деревьями, которые изображаются с помошью скобок; скобки играют выделенную роль, служат для выделения синтаксической структуры объектов, что используется для ускорения отождествления;
  3. существуют такие пары образец-объект, для которых синтаксическое отождествление возможно несколькими различными способами, из-за чего в процессе отождествления возможен комбинаторный перебор;
  4. правило отождествления определяется аксиоматически.

Синтаксическое отождествление представляет собой действие Рефал-машины, описанное ниже.

Рефал-машина, решая, применимо ли данное предложение к данному конкретизируемому выражению, определяет, можно ли придать свободным переменным в левой части предложения такие значения, чтобы левая часть совпала с конкретизируемым выражением. Разные вхождения одной и той же переменной должны должны заменяться на одно и то же значение. В случае успешного синтаксического отождествления свободные переменные, входящие в левую часть, принимают определенные значения, соответствующие их типу:

  • значением s-переменной может быть только символ;
  • значением t-переменнной может быть только терм;
  • значением e-переменной может быть произвольное выражение;
и при подстановке правой части предложения в поле зрения на место свободных переменных вписываются их значения. В правой части предложения можно использовать только те свободные переменные, которые входят в левую часть. Если синтаксическое отождествление невозможно, то предложение неприменимо. Значение, которое принимает переменная в процессе отождествления, сохраняется, пока выполняется данный шаг, и теряется при переходе к следующему шагу.

В случае, когда существует несколько вариантов синтаксического отождествления предложения с конкретизируемым выражением , приоритет одного варианта сопоставления над другим определяется следующим образом: пусть имеется два варианта синтаксического отождествления предложения с конкретизируемым выражением; если они не совпадают, то, значит, они сопоставляют некоторым переменным из предложения различные значения; в предложении ищется самое первое слева вхождение переменной, которому эти варианты отождестления сопоставляют разные значения и сравниваются длины этих значений; вариант отождествления, который сопоставляет переменной из предложения значение меньшей длины, имеет более высокий приоритет над другими вариантами отождествления. Такой вариант отождествления назывется отождествлением слева направо.

Пример:

предложение:
A (e1 t2) s3
выражение:
A ((2 3)) B
свободные переменные примут следующие значения:
e1 := ; t2 := (2 3); s3 := B

-- Luba Parmyonova - 18 Feb 2005

A>>> И я бы обозначал символы с помощью последовательностей знаков, заключенных в двойные, а не в одинарные кавычки. А одинарные кавычки -- это уже последовательность символов. Как в Рефале+.

L>> Здесь говорится именно о последовательности символов, из которой состоит составной символ, она и заключается в одинарные кавычки.

A> Точнее, говорится о последовательности знаков. В Рефале+ для создания символа из нескольких знаков используются двойные кавычки (получается символ-слово). И я предложил здесь тоже использовать их, чтобы не возникло путаницы. А одинарные кавычки используются в Рефале+ для обозначения последовательности из нескольких символов (литер).

A> Я думал, что в Рефале-5 всё то же самое. Сейчас посмотрел -- и был очень удивлён. Оказывается, там и одинарные, и двойные кавычки используются для создания последовательности символов. А создать символ из последовательности знаков можно только если эта последовательность удовлетворяет определённым условиям (начинается с заглавной буквы и может включать только буквы, цифры, черточки - и подчеркивания _).

Ок. Во избежание путаницы для создания символа из нескольких знаков используем двойные кавычки, как в Рефале+.

Алгоритм Проектирования

Рефал-машина

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r7 < r6 < r5 < r4 < r3 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback