Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ

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

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

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

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

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

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

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

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

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

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

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

При дальнейших рассуждениях, для того чтобы упростить изложение, будем считать, что любая управляющая конструкция, будь то оператор IF–THEN–ELSE или WHILE–DO, не содержит BEGIN, но всегда завершается терминалом END, независимо от количества операторов в отдельной ветви или теле цикла. (Смотрите, например язык МОДУЛА–2).

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