М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие
 Скачать 0.92 Mb.
|
4.3.Обработка структурированного текстаВ этом подразделе рассматриваются задачи преобразования символьных выражений, в которых в результате предшествующей обработки появились структурные скобки, т.е. эти выражения были предварительно структурированы. Задача6. Задано рефал-выражение, которое можно рассматривать как запись двоичного дерева с узлами, помеченными буквами или цифрами. Структура дерева фиксирована структурными скобками и описывается следующими БНФ-правилами: дерево ::= узел (дерево ',' дерево) | узел узел ::= буква | цифра Необходимо заменить в узлах заданного дерева все символы 'А' на символы 'В', а символы '0' – на символы '1'.  К примеру, дерево, изображённое на рисунке 2 и записывающееся как выражение 'A'('С'('5,А')',0'), преобразуется в дерево, показанное на рисунке 3. В случае, когда синтаксис обрабатываемого выражения описывается с помощью БНФ-правил, рефал-программу можно строить по следующей общей методике: Каждому нетерминалу (структурной единице обрабатываемого выражения) соответствует обрабатывающая его рефал-функция. В нашей задаче нетерминалу дерево соответствует функция Tree, а нетерминалу узел – функция Node. Если БНФ-правило для рассматриваемого нетерминала содержит несколько альтернатив, то каждой альтернативе соответствует обычно одно или несколько предложений рефал-функции. В нашей задаче двум альтернативам в правиле для нетерминала дерево будут соответствовать два предложения функции Tree. При построении очередного предложения функции его левая часть получается из соответствующей альтернативы БНФ-правила заменой входящих в него нетерминалов подходящими рефал-переменными. В правой части предложения записываются необходимые преобразования над значениями этих переменных. Определим типы рефал-переменных для нашей задачи. Нетерминалу узел соответствует s‑переменная, т.к. узел – это буква или цифра, т.е. символ. Нетерминалу дерево нельзя поставить в соответствие s‑переменную или w‑переменную (в Рефале-5 – t‑переменную), поскольку первая альтернатива в правиле для этого нетерминала описывает более сложное выражение, чем символ или структурный терм. Это выражение состоит из символа (изображающего узел), за которым расположен терм (дерево ',' дерево). Поэтому нетерминалу дерево соответствует е‑переменная в Рефале-5 и v‑переменная в Рефале-2 (дерево не может быть пустым). Согласно рассмотренной методике получаем следующее определение функций языка Рефал-2: * Функция Tree обработки (анализа) дерева Tree sА (v1 ',' v2) = ( sА = * Функция замены символов в узлах дерева Node 'A' = 'B' '0' = '1' s1 = s1 Функция Tree осуществляет проход по структуре дерева, вызывая при этом функцию Node, которая осуществляет необходимую замену символов дерева. Правая часть первого предложения функции Tree содержит 2 рекурсивных вызова для обработки соответственно левого и правого поддерева. Поскольку сама структура дерева не меняется, то выражение в правой части этого предложения отличается от выражения в левой части только функциональными вызовами. Рассмотренное определение функции написано в предположении, что её аргумент синтаксически правилен (относительно заданных БНФ-правил), в ином случае в функцию следует добавить третье предложение, фиксирующее синтаксическую ошибку: Е1 = Рассмотрим изменение поля зрения рефал-машины при обработке приведённого выше примера дерева, задаваемого выражением 'A'('С'('5,А')',0'):
Таким образом, на шаге 11 в поле зрения рефал-машины получено преобразованное дерево. Задача 7. Преобразовать заданное арифметическое выражение из обычной инфиксной записи в ПОЛИЗ (польскую инверсную запись, при которой операция записывается после своих операндов). Арифметическое выражение состоит из чисел (уже преобразованных во внутреннее рефальское представление – символ-число для Рефала-2 или макроцифра для Рефала‑5), знаков операций сложения, вычитания, умножения и деления, а также круглых скобок. Например, для выражения в инфиксной записи 5*(2-3)+8/(2*4-7)-11*6 необходимо получить его ПОЛИЗ 5 2 3 ‑ * 8 2 4 * 7 - / + 11 6 * -. Предполагается, что скобки в заданном арифметическом выражении уже преобразованы в структурные. Структура выражения задаётся БНФ-правилами: выражение ::= выражение знак-add-sub слагаемое | слагаемое слагаемое ::= слагаемое знак-mul-div множитель | множитель множитель ::= число | (выражение) знак-add-sub::= '+' | '-' знак-mul-div::= '*' | '/' При описании нетерминалов выражение и слагаемое использована левая рекурсия. При синтаксическом разборе сверху вниз такое описание соответствует общепринятому порядку вычисления арифметических операций одного приоритета – слева направо. При таком порядке отсутствующие в выражении скобки, например, 7+12‑23+5 восстанавливаются следующим образом: ((7+12)-23)+5, и самый левый знак операции находится в глубине всех скобок, в то время как самый правый знак операции остался на верхнем уровне выражения. Если же необходимо выполнять вычисление операций справа налево, то при описании соответствующих нетерминалов следует использовать правую рекурсию. Приведённые БНФ-правила учитывают не только порядок вычисления операций одного приоритета, но и приоритеты операций – операции умножения и деления имеют больший приоритет, чем операции сложения и вычитания. Для преобразования арифметического выражения в ПОЛИЗ необходимо на всех его уровнях после выделения в нём очередного знака операции и соответствующих операндов преобразовать их в ПОЛИЗ, используя рекурсию, а знак операции записать после результатов преобразования операндов. Согласно методике построения рефал-программы, изложенной в задаче 6, для каждого из нетерминалов БНФ-правил выражение, слагаемое и множитель организуем отдельную функцию – соответственно PolizExp, PolizSum и PolizMult. Эти функции будут переводить в ПОЛИЗ соответствующую структурную единицу выражения. Количество рефал-предложений в теле каждой функции будет совпадать с количеством альтернатив в БНФ-правиле нетерминала, соответствующего этой функции. Левые части рефал-предложений строятся также согласно методике, но с учётом левой рекурсии в описании нетерминалов выражение и слагаемое – это означает, что следует выделять самый правый знак арифметической операции на рассматриваемом уровне обрабатываемого выражения. Заметим, что для нетерминалов знак-add-sub и знак-mul-div отдельные функции не заводятся (необходимые для их обработки действия будут выполнять обозначенные выше функции). Определим теперь соответствие типов рефал-переменных описанным нетерминалам. Нетерминалам знак-add-sub и знак-mul-div (символы операций) соответствуют s-переменные, в языке Рефал-2 – соответственно со спецификатором '+-' или '*/'. Нетерминалу множитель соответствует w-переменная в языке Рефал-2 и t-переменная в языке Рефал-5, поскольку множитель является либо числом, либо выражением в структурных скобках (т.е. термом). Нетерминалам выражение и слагаемое соответствует v-переменная языка Рефал-2 (поскольку они не могут быть пустыми) и е‑переменная языка Рефал-5. Чтобы в функции PolizExp выделить самый правый знак сложения или вычитания, в первом её предложении следует использовать правое согласование. В то же время в функции PolizSum нет необходимости использовать правое согласование – действующее по умолчанию левое согласование обеспечит выделение последнего знака умножения или деления, поскольку слагаемое состоит из множителей, а множитель является термом (однозначно проектирующимся жёстким элементом выражения). Функция PolizMult написана с учётом того, что ПОЛИЗ числа есть само число, а при переводе в ПОЛИЗ арифметического выражения в скобках эти скобки убираются. Таким образом, на языке Рефал-2 рассматриваемую задачу решают следующие функции: * Рефал-2: перевод в ПОЛИЗ арифметического выражения PolizExp R v1 s('+-')2 v3 = + s2 v1 = * Перевод в ПОЛИЗ слагаемого PolizSum v1 s('*/')2 w3 = s2 w1 = * Перевод в ПОЛИЗ множителя PolizMult s(N)1 = s1 (v1) = Отметим, что порядок следования рефал-предложений существенен лишь в функции PolizExp, поскольку образец её второго предложения может быть синтаксически отождествлён с теми же объектными выражениями, для обработки которых предназначено первое предложение этой функции. Рефал-предложения в телах функций PolizSum и PolizMult можно менять местами, поскольку множества выражений, с которыми могут отождествляться образцы этих предложений, не пересекаются. В частности, в функции PolizSum образец второго предложения отождествляется только с термом, в то время как образец первого предложения отождествляется только с выражениями, состоящими как минимум из трёх термов. Рассмотрим изменение поля зрения рефал-машины при переводе в ПОЛИЗ выражения /5/'*'(/2/'-'/3/)'+'/8/'/'/6/'-'/11/, с помощью рассмотренных функций языка Рефал-2:
Для решения рассматриваемой задачи перевода выражения в ПОЛИЗ на основе языка Рефал-5 опять же, как и в задаче 5, потребуется введение дополнительных условий в левых частях предложений и использование функции CheckInM: * Рефал-5: перевод в ПОЛИЗ арифметического выражения PolizExp { e.1 s.2 e.3 , '+-' : e.A s.2 e.B , s.2 ; e.1 = * Перевод в ПОЛИЗ слагаемого PolizSum { e.1 s.2 t.3 , '*/' : e.A s.2 e.B = s.2 ; t.1 = * Перевод в ПОЛИЗ множителя PolizMult { s.1 , (e.1) = * Функция проверки, что никакой символ из заданного * множества не входит в выражение CheckInM { (e.1 s.X e.2) e.3 s.X e.4 = False ; e.1 = True } Отметим, что из-за отсутствия в языке Рефал-5 правого отождествления и спецификаций переменных получившееся решение (как и решение задачи 5) состоит, по сравнению с решением на языке Рефал-2, из большего числа функций с более длинными предложениями. |