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

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

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

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

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

Метод. Суть метода состоит в том, что для каждого знака–разделителя (операции, скобки и т.п.) вводят два числа: сравнительный приоритет – 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, если символ ‘;’ перед ними необязателен). По ‘;’ из магазина выталкивается все вплоть до операции присваивания и она сама извлекается из магазина и переписывается в ПОЛИЗ. При этом, если символу присваивания в магазине предшествуют “открывающие скобки” иного рода, то это является признаком ошибки.

Атрибутные грамматики

Способ описания грамматик с помощью порождающих правил не единственный. Порождающие грамматики, рассмотренные ранее, не учитывают в формальной записи грамматик семантические правила. Семантические действия в таких грамматиках вводятся в виде процедур при построении анализаторов. Примерами грамматик, учитывающих семантику в правилах вывода, являются:

двухуровневые грамматики W-грамматики( с их помощью описан язык ALGOL-68),

венский метаязык ( описан PL/1),

атрибутные.
Ниже рассмотрен один из перечисленных видов грамматик, а именно – атрибутные грамматики [12]. Атрибут- это свойство объекта; под атрибутом в грамматиках понимаются значение или семантический смысл (значимость) объекта. Атрибутная грамматика – это КС-грамматика, с узлами дерева вывода которой связаны атрибуты (семантические правила). КС-правилам сопоставляются правила вычисления атрибутов. Правило вычисления значений атрибутов, соответствующее данному КС-правилу, применяется для всех вхождений этого правила в дерево вывода.

Атрибуты могут быть двух видов - синтезированные и унаследованные.

Синтезированные атрибуты вычисляются с учетом значений атрибутов узлов потомков.

Унаследованные атрибуты - это атрибуты, значение которых вычисляется с учетом значений атрибутов его предков.

Формально атрибутная грамматика – это пятёрка объектов:

, где

- множество терминальных символов;

- множество нетерминальных символов;

- начальный выделенный символ;

- это правила вывода.

,где

- это множество атрибутов

= где

- множество унаследованных атрибутов;

- множество синтезированных атрибутов.

È =Æ

=Æ

=Æ

" Î

Унаследованные атрибуты левой части КС-правила и синтезированные атрибуты правой части получают значения, переданные от окружающих ветвлений дерева вывода. Правила вычисления значений атрибутов, связанные с каким-либо КС-правилом, определяют метод вычисления значений других атрибутов, а именно – унаследованных атрибутов правой части и синтезированных атрибутов левой части. Значения этих атрибутов передаются окружающим узлам. Или иначе можно сказать, что синтезированные атрибуты некоторого узла содержат информацию, которая синтезируется из поддерева данного узла и передаётся вверх к корню дерева вывода, а в унаследованных атрибутах хранится информация, передаваемая вниз, от корня дерева к его листьям. Унаследованные атрибуты характеризуют контекст, в котором находится его узел и его поддерево. Правила вычисления значений атрибутов записываются разными способами. Аппарат атрибутных грамматик не является законченным методом формального описания языка. Для того, чтобы им можно было воспользоваться, его необходимо дополнить методом записи правил вычисления значений атрибутов.

Один из возможных методов записи правил вычисления значений атрибутов рассмотрим на примере атрибутной грамматики чисел в двоичной системе записи.

, , 0

Здесь нетерминал S используется для вывода числа в двоичной системе записи, нетерминал L – для вывода списка бит (0 и 1), нетерминал B – позволяет вывести один бит ( 0 или 1). В эту грамматику включим атрибуты (семантические правила), позволяющие в процессе анализа правильной цепочки получить значение двоичного числа в десятичной системе счисления. Для этого каждому нетерминалу припишем атрибуты следующим образом:

. Каждое число (нетерминал ) имеет один атрибут , равный значению числа в десятичной системе счисления.
. Каждый список битов (нетерминал ) имеет два атрибута - значение последнего бита и длину .
. Каждый бит (нетерминал ) имеет один атрибут- значение .

В общем случае каждому нетерминалу можно приписывать любое число атрибутов. Описанные выше семантические правила относятся к синтезированным атрибутам, така как значения атрибутов всех нетерминалов определяются через значения атрибутов потомков.

С учетом этих правил построим атрибутную грамматику:

;

L B ,

B 0

B 1

Здесь индексы у нетерминалов L1 и L2 использованы для того, чтобы различить вхождения одноименных нетерминалов в правой и левой частях правил вывода.

Ниже построено дерево вывода для числа 101.01, а в скобках получено значение числа в десятичной системе счисления.

101.01 (5.25)

Рисунок 7.6. Дерево вывода для числа 101.01

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