М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие
 Скачать 0.92 Mb.
|
4.2.Структурирование текстаЯсно, что использование структурных скобок (являющихся собственными знаками языка Рефал) позволяет упростить и сделать эффективной обработку текстов, в том числе текстов со сложной структурой. Однако в исходных текстах такие скобки изначально отсутствуют. В то же время обрабатываемый текст, например, алгебраические и логические выражения, часто содержит символы круглых скобок, задающих его структуру, учесть которую необходимо при его обработке. Таким образом, возникает важная вспомогательная задача замены символов круглых скобок на структурные скобки Рефала. Задача 4. В тексте, рассматриваемом как последовательность символов, заменить литеры скобок '(' и ')' на соответствующие структурные скобки, например, текст '5/((A+B)^2-(A-B)^3)+8*A' преобразовать в '5/'(('A+B')'^2-'('A-B')'^3')'+8*A'. Если в исходном тексте баланс символьных скобок нарушен, то выдать сообщение об ошибке. Для решения задачи необходимо последовательно находить соответствующие пары символов открывающей и закрывающей скобки и заменять их структурными скобками. Особенность решения состоит в том, что поиск надо начинать с самых внутренних скобок и сначала надо находить закрывающую скобку, а потом – парную ей открывающую, а не наоборот, поскольку иначе поиск парной скобки сложнее. Действительно, любой закрывающей скобке соответствует ближайшая слева от неё свободная (не имеющая на данный момент пару) открывающая скобка, в то же время открывающей скобке в общем случае соответствует вовсе не ближайшая к ней справа закрывающая скобка. Баланс скобок может быть нарушен в двух случаях: если была найдена закрывающая скобка, а перед ней не нашлось соответствующей ей открывающей скобки, и если была найдена открывающая скобка, а нужной закрывающей скобки не обнаружено. Будем считать, что вспомогательная функция Error обрабатывает ситуации, когда нарушен баланс скобок, и производит корректное завершение работы программы. На языке Рефал-2 решение задачи замены символов скобок на структурные скобки состоит из двух взаимосвязанных функций: функция RBrac выделяет очередную закрывающую скобку, а LBrac – парную ей открывающую. * Рефал-2: преобразование пар скобок в структурные * Функция RBrac выделения закрывающей скобки RBrac e1 ')' e2 = e1 '(' e2 = e1 = e1 * Функция LBrac поиска парной открывающей скобки * и перевода пары скобок в структурные LBrac R e1 '(' e2 = e1(e2) e1 = Заметим, что первое предложение функции LBrac содержит знак правого согласования, что означает проведение отождествления справа налево, а значит, нахождение самой правой (и ближайшей к закрывающей) открывающей скобки. В первом предложении функции RBrac знак согласования не указан, по умолчанию будет применено левое согласование, и поэтому найдена первая слева самая внутренняя закрывающая скобка. Соответствующая ей открывающая скобка ищется в части текста е1, расположенной слева от найденной закрывающей скобки, при помощи функции LBrac, которая и преобразует найденную пару символьных скобок в структурные скобки. После обращения к LBrac функция RBrac рекурсивно продолжает работу – для поиска новой закрывающей скобки, и поскольку уже найденные пары скобок преобразованы в структурные, они в дальнейшем не учитываются. Заметим, что второе предложение функции RBrac необходимо для обработки случаев, когда в обрабатываемом тексте нет закрывающей, но есть открывающая скобка, а второе предложение LBrac – когда нет открывающей, но есть закрывающая скобка. На языке Рефал-5 функция RBrac будет выглядеть таким же образом. В то же время, поскольку в Рефале-5 отсутствует возможность правого отождествления, первое предложение функции LBrac необходимо изменить. Заметим, что выделения самого правого символа '(' можно добиться, задав для отождествляемого выражения в образце предложения дополнительное условие, что выражение е2 не должно содержать символов '('. Для проверки этого условия понадобится ввести вспомогательную функцию Check. В итоге получаем следующее решение на языке Рефал-5: * Рефал-5: преобразование пар скобок в структурные * Функция RBrac выделения закрывающей скобки RBrac { e.1 ')' e.2 = e.1 '(' e.2= e.1 = e.1 } * Функция LBrac поиска парной открывающей скобки * и перевода пары скобок в структурные LBrac { e.1 '(' e.2 , e.1 = * Вспомогательная функция проверки, что выражение- * аргумент не содержит открывающей скобки Check { e.А '(' e.В = False ; e.А = True } Покажем изменение содержимого поля зрения рефал-машины при применении написанных функций языка Рефал-2 для обработки текста арифметического выражения '5/((A+B)^2-(A-B)^3)+8*A':
Задача 5. Исходный текст содержит символы скобок трёх видов: круглые, квадратные и фигурные. Необходимо заменить круглые скобки структурными, а выражения в парных квадратных и фигурных скобках заключить в структурные скобки, при этом оставляя на своём месте исходные символы квадратных и фигурных скобок. Например, текст '5/([A+B]^2-{A-B}^3)+8*A' следует преобразовать в выражение '5/'(('[A+B]')'^2-'('{A-B}')'^3')'+8*A'. По сути, эта задача – обобщение и усложнение предыдущей, но основная идея обработки выражения аналогична: нужно сначала найти первую от начала текста закрывающую скобку любого вида, после чего выделить ближайшую к ней слева открывающую скобку любого вида. Для найденной пары скобок проверить, являются ли они парой скобок одного вида, и если да, то заменить их на структурные (если была пара круглых скобок) или заключить в структурные скобки (для пар скобок других видов). Если же скобки разного вида, то сообщить об отсутствии баланса скобок. При такой обработке используется свойство правильных многоскобочных выражений: выражения в разных скобках не могут пересекаться друг с другом, а могут только вкладываться друг в друга. * Рефал-2: структурирование выражения, содержащего * скобки разного вида * Функция RBrac выделения первой закрывающей * скобки любого вида RBrac e1 s(')]}')A e2 = e1 s('([{')B e2 = + Баланс скобок нарушен'> e1 = e1 * Функция LBrac поиска ближайшей слева открывающей * скобки любого вида LBrac R e1 s('([{')В e2 = e1 e1 = * Функция EqBr проверки, является ли найденная * пара скобок скобками одного вида, и расстановки * структурных скобок EqBr '(' e1 ')' = (e1) '[' e1 ']' = ('[' e1 ']') '{' e1 '}' = ('{' e1 '}') e1 = Покажем изменение содержимого поля зрения при обработке рассмотренными функциями текста '5/([A+B]^2-{A-B}^3)+8*A':
В рассмотренных функциях языка Рефал-2, решающих задачу преобразования скобок, использовались переменные со спецификатором: переменная s(')]}')A для поиска закрывающей скобки и переменная s('([{')B – для поиска открывающей скобки. Поскольку в языке Рефал‑5 спецификаторы и правое согласование отсутствуют, потребуется использовать условные конструкции и дополнительную функцию CheckInM для проверки, что между найденной парой скобок нет других скобок. Аргумент функции CheckInM имеет вид (множество)выражение, её результатом будет True, если никакой символ из заданного множества символов не входит в выражение, и False иначе. * Рефал-5: структурирование выражения, содержащего * скобки разного вида * Функция RBrac выделения первой закрывающей скобки * любого вида RBrac { e.1 s.A e.2 , ')]}' : e.3 s.A e.4 = e.1 s.B e.2 , '([{' : e.3 s.B e.4 = e.1 = e.1 } * Функция LBrac поиска ближайшей слева (парной) * открывающей скобки любого вида LBrac { e.1 s.B e2 , '([{' : e.3 s.B e.4 , = e.1 e.1 = * Функция EqBr проверки, является ли выделенная * пара скобок скобками одного вида, * и расстановки структурных скобок EqBr { '(' e.1 ')' = (e.1) ; '[' e.1 ']' = ('[' e.1 ']') ; '{' e.1 '}' = ('{' e.1 '}') ; e.1 = * Вспомогательная функция CheckInM: возвращает True, * если никакой символ из заданного множества * не входит в выражение, иначе возвращает False CheckInM { (e.1 s.X e.2) e.3 s.X e.4 = False ; e.1 = True } |