МЕТОД ЗАМЕЛЬСОНА–БАУЭРА ДЛЯ ПЕРЕВОДА В ПОЛИЗ И ТЕТРАДЫ

Арифметические выражения чаще всего встречались при практическом программировании, особенно на ранних стадиях использования вычислительной техники. Поэтому для них немецкими математиками К. Замельсоном и Ф. Бауэром был предложен достаточно простой метод перевода инфиксных арифметических выражений в ПОЛИЗ с одновременным контролем отдельных ошибок. Предложенный ими метод не использует грамматик в явном виде но в основе приоритетов операций о которых речь пойдет ниже лежат традиционные функции предшествования.

Алгоритм 6.1. Метод Замельсона–Бауэра для перевода инфиксных арифметических выражений в ПОЛИЗ.

Вход. Строка, содержащая инфиксное арифметическое выражение.

Выход. Польская инверсная запись исходного выражения.

Метод. Суть метода состоит в том, что для каждого знака–разделителя (операции, скобки и т.п.) вводят два числа: сравнительный приоритет – P_C и магазинный приоритет – P_M. Исходное выражение просматривается один раз слева направо. При этом:

(1) Идентификаторы и константы переписываются в выходную строку ПОЛИЗа.

(2) При обнаружении разделителя его сравнительный приоритет P_C сравнивается с магазинным приоритетом P_M разделителя из вершины магазина операций. Если P_C > P_M, то разделитель входной строки помещается в магазин (разделитель из исходной строки поступает в магазин и в том случае, когда магазин пуст). Если P_C £ P_M, то символ извлекается из магазина и записывается в выходную строку ПОЛИЗа. Далее повторяется пункт (2) все для того же входного символа.

(3) Открывающая скобка – ‘ ( ’ имеет самый высокий сравнительный приоритет и поэтому всегда поступает в магазин. Закрывающая скобка – ‘ ) ’в ПОЛИЗ и магазин не записывается и поэтому магазинный приоритет для нее не важен. По закрывающей скобке входной строки из магазина извлекаются все операции и переписываются в строку ПОЛИЗа вплоть до первой открывающей скобки в магазине. Открывающая скобка также извлекается из магазина, но, как и закрывающая, в ПОЛИЗ не переписывается. После этого осуществляется переход к следующему символу входной строки. Ясно, что если для закрывающей скобки входной строки в магазине открывающая скобка не будет обнаружена, то это послужит сигналом о синтаксической ошибке.

(4) По окончании входной строки содержимое магазина переписывается в строку ПОЛИЗа. (Если при этом в магазине останутся открывающие скобки, то это также является признаком ошибки в записи исходного выражения). 

На рис. 6.11 представлена таблица приоритетов операций и скобок для упрощенных арифметических выражений, а на рис. 6.12 разобран по шагам пример перевода в ПОЛИЗ инфиксного выражения по методу Замельсона–Бауэра. (На рис. 6.12 вершина магазина операций расположена справа).

Предложенный метод можно модифицировать таким образом, что он позволит обрабатывать и операции сравнения, логические операции, операторы присваивания, управляющие конструкции типа IF–THEN–ELSE, WHILE–DO и т. п. Таблица приоритетов для этого случая представлена на рис. 6.13. То, что в ней приоритеты операций изменены, по сравнению с рис. 6.11, роли не играет. Важны отношения между значениями приоритетов, а не сами значения. Обработка скобок, к которым здесь можно отнести и операцию присваивания – ‘ := ’, и знак конца оператора – ‘; ’, и элементы управляющих конструкций (IF, THEN, ELSE, WHILE и т.п.) выполняется по особым алгоритмам, часть из которых была предложена в работе Л.Ф. Штернберга [17]. При дальнейших рассуждениях, для того чтобы упростить изложение, будем считать, что любая управляющая конструкция, будь то оператор IF–THEN–ELSE или WHILE–DO, не содержит BEGIN, но всегда завершается терминалом END, независимо от количества операторов в отдельной ветви или теле цикла. (Смотрите, например язык МОДУЛА–2).

Операция присваивания ‘ := ’ играет роль открывающей скобки для символа ‘; ’ (или управляющей конструкции, типа ELSE или END, если символ ‘; ’ перед ними необязателен). По ‘; ’ из магазина выталкивается все вплоть до операции присваивания и она сама извлекается из магазина и переписывается в ПОЛИЗ. При этом, если символу присваивания в магазине предшествуют “открывающие скобки” иного рода, то это является признаком ошибки. Пример перевода в ПОЛИЗ группы операторов присваивания представлен на рис. 6.14.

Как и всякая открывающая скобка, ключевое слово IF поступает в магазин. Логическое условие, следующее за IF, обрабатывается по общему алгоритму. Терминал THEN в соответствии со своим приоритетом выталкивает из магазина все вплоть до IF. (Если IF не обнаружено, или ему предшествуют другие “открывающие скобки” то это говорит об ошибке в исходном выражении.) Терминал IF также выталкивается из магазина и в ПОЛИЗ записывается операция УПЛ, где метка перехода пока не определена. Ключевое слово THEN помещается в магазин вместо IF вместе с номером позиции в строке ПОЛИЗа, соответствующей метке для УПЛ. В магазине THEN “ведет себя” как открывающая скобка для соответствующей “закрывающей скобки” (для ELSE или END).

Терминал ELSE выталкивает из магазина в ПОЛИЗ все вплоть до THEN, контролируя возможные ошибки. При извлечении из магазина THEN в строку ПОЛИЗа записывается операция БП с неопределенной меткой. На место метки оператора УПЛ, номер позиции которой был записан вместе с извлекаемым THEN, записывается значение индекса по строке ПОЛИЗа, соответствующее позиции, следующей за сформированным БП. Ключевое слово ELSE помещается в магазин вместе с номером позиции для метки операции БП и играет роль “открывающей скобки” для END данного IF – THEN – ELSE.

Терминал END - это “закрывающая скобка” для ELSE, THEN или DO в операторе WHILE - DO, о котором речь пойдет ниже. При встрече с END в исходной строке из магазина в ПОЛИЗ переписывается все вплоть до соответствующей “открывающей скобки”. Последняя также извлекается из магазина, а индекс, указанный вместе с ней, делает тривиальным процесс формирования метки в соответствующем операторе БП или УПЛ.

На рис. 6.15 представлены основные шаги перевода в ПОЛИЗ полного оператора IF - THEN - ELSE, а на рис. 6.16 - перевод в инверсную запись оператора ветвления, в котором ветвь ELSE отсутствует. (Чтобы подчеркнуть отдельные моменты перевода над строкой ПОЛИЗа в ряде случаев отмечаются номера позиций символов строки, а строчные буквы в ключевых словах используются для более компактной записи.)

На рис. 6.17 представлены отдельные шаги перевода в ПОЛИЗ простейшего оператора цикла.

Большинство шагов связанных с арифметикой и операторами присваивания здесь опущены, и внимание концентрируется на представлении самого цикла. Терминал WHILE переписывается из исходной строки в магазин с указанием очередной позиции строки ПОЛИЗа (while, 4). Начиная с этой позиции (позиции 4) будет в дальнейшем записано логическое условие для данного цикла и именно на эту позицию необходимо будет передать управление по завершении цикла. “Закрывающей скобкой” для WHILE, характеризующей завершение условия будет терминал DO. Он традиционно “вытолкнет из стека и перепишет в ПОЛИЗ” все операции предшествующие WHILE. В строку ПОЛИЗа запишется также операция УПЛ с неопределенной меткой, а WHILE в магазине заменит DO, который вместе с позицией начала условия сохранит и позицию для последующего формирования метки перехода для УПЛ (в примере с рис. 6.17 - ‘ do, 4, 7 ’). Это DO станет “открывающей скобкой” для терминала END, завершающего цикл и приводящего, кроме обычных действий по переносу операций из магазина в ПОЛИЗ, формирование операции безусловного перехода на начало цикла - БП, метка перехода для которого уже известна и хранится вместе с DO в магазине. Кроме того, по END в сформированную ранее операцию УПЛ из начала цикла в качестве метки заносится значение индекса конца цикла (позиция в строке ПОЛИЗа, следующая за БП).

Читателям пособия предлагается в качестве упражнения подумать над алгоритмами перевода в ПОЛИЗ циклов с параметром FOR - TO - BY - DO, циклов REPEAT - UNTIL, операторов выбора CASE или переключателей SWITCH и операций индексирования переменных.

Хорошим упражнением может стать и разработка алгоритмов и программ перевода арифметических выражений, да и других элементов программ в тетрады, с использованием обсуждаемых здесь подходов. Сама структура алгоритма останется неизменной. Отличие состоит в том, что имена операндов (или их значения для констант) вначале будут поступать во вспомогательный стек имен (в дальнейшем имена операндов в этом стеке будут замещаться на формируемые имена для промежуточных результатов). Как только будет выполняться условие P_C £ P_M и операция всплывет из магазина может формироваться тетрада, соответствующая данной операции и использующая в качестве операндов элементы из вспомогательного стека. Более того, если задачи оптимизации кода перед нашим компилятором не стоят, то никто не мешает нам вместо тетрады генерировать фрагмент машинного кода, соответствующий извлекаемой из магазина операции. Именно такой подход практикуется при создании однопроходных компиляторов.

Поиск по сайту: