М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие
 Скачать 0.92 Mb.
|
4.1.Посимвольная обработка текстаВ этом подразделе рассматриваются задачи обработки текста, рассматриваемого как простая последовательность символов (как строка). Задача 1. Определить функцию Erase, удаляющую все лишние пробелы в исходной строке символов, т.е. замещающую каждую группу подряд стоящих пробелов единственным пробелом. Далее для наглядности пробел будем изображать символом '└─┘'. Например, результатом применения функции Erase к строке 'He└─┘writes└─┘└─┘└─┘as└─┘└─┘└─┘well└─┘as└─┘she' будет строка 'He└─┘writes└─┘as└─┘well└─┘as└─┘she' Самым очевидным решением будет следующее: в любой обнаруженной внутри строки паре соседних пробелов следует удалить один, и повторять это до тех пор, пока имеются соседние пробелы. * Функция Erase удаляет в строке лишние пробелы, * вариант 1 Erase e1 '└─┘└─┘' e2 = e1 = e1 Полученная программа содержит два предложения: рекурсивное (удаляющее пробелы) и завершающее (применяющееся тогда, когда соседствующих пробелов уже нет). Каждое применение первого предложения удаляет один лишний пробел. Проанализируем работу этой функции. Так как по умолчанию при отождествлении используется левое согласование, то подстрока, являющаяся значением переменной е1, не содержит подряд стоящих пробелов. Но е1 входит в аргумент рекурсивного обращения, поэтому на следующем шаге работы рефал-машины эта подстрока снова будет просматриваться при отождествлении с образцом первого предложения и поиске пары соседних пробелов. Избежать повторного просмотра можно, вынося е1 за пределы функциональных скобок: * Функция Erase удаляет в строке лишние пробелы, * вариант 2 Erase e1 '└─┘└─┘' e2 = e1 e1 = e1 В этом более эффективном решении левую угловую скобку вызова функции Erase можно рассматривать как разделитель обработанной части строки от части, ещё не подвергавшейся обработке. Для второго варианта решения задачи приведём изменение поля зрения рефал-машины в процессе обработки строки 'He└─┘writes└─┘└─┘└─┘as└─┘└─┘└─┘well└─┘as└─┘she':
Задача2. Определить функцию Correct, исключающую из заданной строки любой символ, за которым следует знак #. Если в исходной строке стоят подряд несколько знаков #, функция должна исключать соответствующее число предшествующих им символов. Например, результатом применения этой функции к строке 'Children### is playe#ing' будет строка 'Child is playing'. Не задумываясь об эффективности, можно дать такое определение функции: * Функция Correct исключает всякий символ * перед знаком #, первый вариант решения Correct e1 sA '#' e2 = e1 = e1 Первое предложение функции находит в строке '#' и исключает его и предшествующий ему символ, продолжая рекурсивную обработку полученной строки. Второе предложение завершает рекурсию. Согласно этому определению обрабатываемая строка будет просматриваться полностью (в ходе её отождествления с образцом первого предложения функции) столько раз, сколько в ней встречается символов #. Но для исключения ненужных повторных просмотров нельзя уже просто вынести подстроку е1 за пределы функциональных скобок, т.к. её самые правые символы могут ещё удаляться. Возникает необходимость в отделении внутри функциональных скобок просмотренной части строки от непросмотренной. В языке Рефал для подобных целей обычно используются структурные скобки. В нашей задаче будем заключать в структурные скобки начальную, уже просмотренную часть строки, т.е. е1. Для введения в обрабатываемую строку структурных скобок определим функцию Correct, обращающуюся к функции удаления Cor и ставящую в начале выражения структурные скобки: * Функция Correct исключает всякий символ * перед знаком #, второй вариант решения Correct e1 = Cor (e1 sX) '#' e2 = (e1) e2 sX '#' e3 = (e1) e2 = e1 e2 Второе предложение функции Cor исключает символ перед первым слева (т.к. по умолчанию согласование левое) одиночным знаком # или перед первым из нескольких подряд стоящих знаков #, при этом правая структурная скобка сдвигается до позиции исключённого символа. Первое предложение Cor предназначено для случаев, когда в обрабатываемой строке было несколько подряд стоящих знаков #, и поэтому после применения второго предложения внутри структурных скобок остались ещё символы, подлежащие удалению. Третье предложение завершает обработку строки, убирая вспомогательные структурные скобки. Заметим, что в данном решении порядок предложений изменить нельзя. Поскольку структурные скобки являются жёсткими элементами, которые проектируются однозначно на соответствующие структурные скобки обрабатываемой строки, их использование ускоряет процесс отождествления при поиске применимого правила функции Cor, и поэтому рассмотренное решение более эффективно. Далее приводится изменение поля зрения рефал-машины в процессе обработки полученной функцией строки 'Children### is playe#ing'.
Задача 3. Определить функцию Count, подсчитывающую число вхождений в заданную строку символов 'A'. Например, результатом вычисления Приводимое ниже решение реализует рекурсивный алгоритм подсчёта символов: если найти первое вхождение в текст символа 'A', то общее число вхождений символа 'A' на 1 больше количества его вхождений в оставшуюся часть текста (для подсчёта этого количества используется рекурсивный вызов функции). Если же в тексте нет символов 'A', то результатом функции является число 0. * Функция Count подсчитывает количество * символов А в строке Count e1 'A' e2 = e1 = /0/ В процессе рекурсивной обработки исходного текста в поле зрения рефал-машины будут накапливаться вложенные рекурсивные вызовы функции Add – до тех пор, пока аргумент функции Count содержит символы 'A'. Когда же символов 'A' уже нет, функция Count выдаст результат /0/, и начнётся последовательное вычисление накопленных рекурсивных вызовов. Например, для текста 'CATS AND DOGS ARE NOT FRIENDS' изменение поля зрения рефал-машины будет происходить следующим образом:
Как видно из этого примера, максимальная глубина вложенности функциональных вызовов (функциональных термов) на единицу больше количества символов 'A' в исходном тексте. Напомним, что на каждом шаге работы рефал-машины ищется ведущий функциональный терм (самый левый из самых вложенных функциональных вызовов), и происходит его замена на правую часть применяемого предложения. Ясно, что с ростом глубины вложенности функциональных вызовов все больше и больше времени рефал-машина затрачивает на поиск очередного ведущего функционального терма. Каким образом можно избежать этого? Опишем соответствующий приём программирования, заключающийся в использовании накопителя – выражения, в котором накапливается нужный результат. Для хранения накапливаемого результата в Рефале обычно используют структурные скобки. Заметим, что в предыдущей задаче в структурных скобках накапливалась уже просмотренная часть обрабатываемого текста. Для получения решения рассматриваемой задачи заведём функцию CountR: в её аргумент будет входить ещё не просмотренная часть текста, а перед ней в структурных скобках будет храниться подсчитанное к текущему моменту количество встреченных символов 'A'. По окончании просмотра текста в этом накопителе окажется нужное нам значение. До начала процесса просмотра текста необходимо установить в накопителе начальное значение – число ноль, и это реализует главная функция CountB при обращении к вспомогательной функции CountR, которая и выполняет нужную работу: * Главная функция CountB: инициализация накопителя * и вызов функции подсчёта CountB e1 = * Вспомогательная функция подсчёта символов А CountR (s1)e2 'A' e3 = (s1)e2 = s1 Для этого решения с накопителем характерно то, что в поле зрения рефал-машины не происходит накопления функциональных вызовов – это видно при обработке той же самой строки текста 'CATS AND DOG ARE NOT FRIENDS' в поле зрения рефал-машины:
Как видно, глубина вложенности и количество функциональных термов не превосходит двух и не зависит от количества символов 'A' в исходной строке. Подчеркнём, что использование накопителя – один из основных приёмов эффективного программирования на Рефале. |