М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие
 Скачать 0.92 Mb.
|
1.1.Рефал и нормальные алгоритмы МарковаНормальные алгоритмы, предложенные А.А. Марковым для формализации и изучения понятия алгоритма [7], можно рассматривать как концептуальную основу модели вычислений языка Рефал. Нормальный алгоритм Маркова (НАМ) работает со словами (цепочками), составленными из символов некоторого конечного алфавита, и записывается как последовательность предложений-правил вида A → B или A  B, где A и B – некоторые слова в заданном алфавите. Каждое предложение-правило определяет некоторую замену слова A на слово B и может быть либо простым (A → B), после применения которого НАМ продолжает работу, либо заключительным (A B), после применения которого НАМ завершает работу. Порядок составляющих алгоритм предложений существенен. Применение алгоритма к заданному слову C состоит в общем случае из нескольких шагов-преобразований исходного слова: CC1C2 … Cn. Каждый шаг включает: Последовательный поиск применимого правила A → B или A B, начиная с первого правила НАМ и далее до последнего. Правило A → B или A B применимо, если его левая часть – слово A входит как подслово в обрабатываемое в текущий момент слово Cj. Преобразование слова Cj путём применения найденного правила: замены входящего в него слова A на слово B и получение таким образом слова Cj+1 . Если слово А входит в Cj несколько раз, то заменяется первое такое вхождение. Если применённое правило было заключительным, то работа НАМ заканчивается, и результатом алгоритма является полученное слово. В ином случае цикл «поиск-замена» продолжается, причём каждый последующий шаг применяется к результату предыдущего. Работа алгоритма завершается либо в случае применения заключительного правила, либо когда на одном из шагов цикла не было найдено ни одного применимого правила. Хотя описанная модель вычислений алгоритмически полна (т.е. любой алгоритм можно записать в виде НАМ), она бедна с точки зрения выразительных средств и поэтому не может служить инструментом практического программирования. Даже для записи простейших преобразований слов требуются специальные приёмы, к примеру, введение в преобразуемое слово дополнительных специальных символов (при этом исходный алфавит дополняется этими символами). Количество же правил НАМ получается довольно большим. Приведём в качестве примера три разных НАМ: первые два алгоритма работают со словами в исходном алфавите {a, b}, третий – со словами в исходном алфавите {0, 1, 2, 3}. НАМ, удаляющий первый символ слова:  Алгоритм использует дополнительный знак * для того, чтобы пометить удаляемый символ. Третье правило, вводящее в слово знак * вместо пустого подслова, намеренно помещено последним: поскольку это правило применимо всегда (пустое подслово входит в любое слово), его перемещение в начало приведёт к зацикливанию алгоритма. НАМ, удаляющий в слове все буквы, кроме первой:  Для записи этого алгоритма требуются уже два дополнительных знака: знак * используется для пропуска первой буквы слова, а знак $ – для прохода по оставшейся части слова (слева направо) и последовательного удаления нужных символов. НАМ, осуществляющий перевод целого числа без знака, записанного в четверичной системе счисления, в двоичное число:  Заметим, что с увеличением размера исходного алфавита для записи обрабатываемых слов растёт соответственно и число правил в нормальных алгоритмах Маркова. Язык Рефал имеет с НАМ общую ориентацию на преобразования символьных выражений (слов), а также похожее строение алгоритма: алгоритм записывается как последовательность предложений, каждое из которых выполняет замену некоторой части обрабатываемого символьного выражения. В тоже время Рефал имеет более сложную модель вычислений и предоставляет программисту широкий набор языковых средств. К средствам, обеспечивающим бóльшую его выразительную мощность (по сравнению с НАМ), в первую очередь относятся: Переменные, позволяющие записывать символы и их последовательности в общем виде и тем самым определять сразу целый класс символов. Переменные используются и в левой, и в правой части предложений Рефала, общий вид которых: выражение‑образец = выражение-замена. Структурные скобки, задающие иерархическую структуру обрабатываемых символьных выражений. Поскольку с помощью структурных скобок можно записывать деревья, язык Рефал ориентирован на обработку древовидных структур. Функции, с помощью которых указываются те предложения программы, среди которых ищется предложение, применимое на текущем шаге вычислений. Под рефал-функцией понимается последовательность из нескольких предложений, а рефал-программа – это несколько функций, как правило взаимосвязанных. Использование функций позволяет также указать в правой части предложения часть символьного выражения, подлежащую дальнейшей обработке. Приведём ниже три рефал-функции, реализующие те же символьные преобразования, что и представленные выше НАМ. Первые две функции состоят из одного предложения, а третья содержит 5 предложений. Строки, начинающиеся со знака *, являются строками комментария. * Функция удаления первого символа слова f1 s1 e2 = e2 * Функция удаления всех букв слова, кроме первой f2 s1 e2 = s1 * Функция перевода числа без знака, записанного в * четверичной системе счисления, в двоичное число f3 '0' e2 = '00' '1' e2 = '01' '2' e2 = '10' '3' e2 = '11' = В приведённых примерах f1, f2 и f3 – это имена функций, а s1 и e2 – переменные, обозначающие соответственно некоторый символ и произвольное символьное выражение. Знак равенства в каждом рефал-предложении отделяет его левую часть (выражение-образец) от правой части (выражение-замена). Угловые скобки в записи третьей функции означают вызов функции, имя вызываемой функции записывается сразу после угловой скобки <. Таким образом, функция f3 является рекурсивной. Последнее предложение этой функции (интерпретируемое как пусто заменить на пусто) обеспечивает окончание рекурсии. |