Польская запись. Алгоритм Бауэра-Замельзона

Результат синтаксического анализа – дерево грамматического разбора – представляют в виде таблицы или обратной польской записи.

Польская запись (в честь польского математика Лукасевича, предложившего этот вид записи выражений) представляет собой последовательность команд двух типов:

1) К_I,где I – идентификатор операнда – выбрать число по имени I и заслать его в стек операндов;

2) K _x, где x – операция – выбрать два верхних числа из стека операндов, произвести над ними операцию x и занести результат в стек операндов.

Рассмотрим алгоритм Бауэра-Замельзона, по которому осуществляется представление выражений в виде польской записи.

Алгоритм Бауэра-Замельзона. Грамматика, описывающая правила записи арифметических выражений, относится к классу грамматик операторного предшествования, т. е. порядок следования терминальных символов (знаков операций), однозначно определяет порядок выделения троек, причем нетерминальные символы (имена операндов) на этот порядок не влияют.

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

Согласно алгоритму Бауэра-Замельзона разбор выражения и формирование польской записи выполняется в два этапа:

1) разбор выражения и построение эквивалентной польской записи;

2) выполнение (или трансляция) польской записи.

При этом используется два стека: стек операций – на первом этапе и стек операндов – на втором этапе.

Построение польской записи выполняется следующим образом: транслятор читает выражение слева направо и вырабатывает последовательность команд по следующему правилу:

а) если символ – операнд, то вырабатывается команда К_I,

б) если символ – операция, то выполняются действия согласно таблице 11:

Обозначения:

? - ошибка;

h - верхний символ в стеке операций;

x - текущий символ.

Операции:

I – заслать x в стек операций и читать следующий символ;

II – генерировать K_h, заслать x в стек операций и читать следующий символ;

III – удалить верхний символ из стека операций и читать следующий символ;

IV – генерировать K_h и повторить с тем же входным символом.

На этапе выполнения польская запись читается слева направо и выполняется.

Польская запись может использоваться как промежуточная форма не только для выражений, но и для других операторов. Соответственно при этом для получения записи должен использоваться модифицированный алгоритм Бауэра-Замельзона.

Пример. Построить тройки для выражения (a + b * c)/ d.

1. Построение польской записи:

В результате получаем:

K_a K_b K_c K_* K₊ K_d K_/ или abc*+d/

2. Выполнение операций:

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