Метод Рутисхаузера Первыми транслирующими программа - страница 5

^ 2.6Польская запись. Алгоритм Бауэра-Замельзона
Результат синтаксического анализа – дерево грамматического разбора – представляют в виде таблицы или обратной польской записи.

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

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

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

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

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

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

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

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

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

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

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

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

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


Таблица 11 – Таблица генератора

\

+

*

(

)





I

I

I

?

Вых

+

II

I

I

IV

IV

*

IV

II

I

IV

IV

(

I

I

I

III

?






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

? - ошибка;

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

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


Операции:

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

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

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

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

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

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

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

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

^ Стек операций

Символ

Действие

Команда



(

I




► (

a




Ka

► (

+

I




► ( +

b




Kb

► ( +

*

I




► ( + *

c




Kc

► ( + *

)

IV

K*

► ( +

)

IV

K+

► (

)

III






/

I




► /

d




Kd

► /



IV

K/





Конец




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

Ka Kb Kc K* K+ Kd K/ или abc*+d/

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

^ Стек операндов

Команда

Тройка



Ka




a

Kb




a b

Kc




a b c

K*

T1= b*c

a T1

K+

T2= a+T1

T2

Kd




T2 d

K/

T3= T2/d

T3









^ 3Распределение памяти
После распознавания конструкций и определения таблиц переменных, именованных констант и временных переменных осуществляют распределение памяти под эти данные и программы. При этом могут использоваться разные типы распределения памяти.

Различают:

  1. статическое;

  2. автоматическое;

  3. управляемое;

  4. базированное.

Статическое распределение памяти выполняется:

а) во время компиляции – для подпрограмм и для инициализированных переменных;

б) во время компоновки – для неинициализированных переменных.

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

Управляемое распределение памяти выполняется во время выполнения программы специальными подпрограммами, например, new и delete.

Базированное распределение памяти выполняется во время выполнения программы из выделенного буфера. Доступ к такой памяти осуществляется через вычисляемые адреса.

Кроме этого, различают:

  1. локальную память;

  2. глобальную память.

Локальная память предполагает ограниченный доступ (из подпрограммы, из файла и т. п.).

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

Mov AX,

Add AX,

Mov AX,

В такой последовательности команд выполняется подстановка адресов операндов и результата.

Очевидно, что код, полученный таким образом, является не оптимальным. Поэтому при генерации кода выполняется оптимизация.

Все способы оптимизации можно разделить на две группы:

  1. машинно-независимая оптимизация;

  2. машинно-зависимая оптимизация.

Машинно-независимая оптимизация включает:

а) исключение повторных вычислений одних и тех же операндов;

б) выполнение операций над константами во время трансляции;

в) вынесение из циклов вычисления величин, не зависящих от параметров циклов;

г) упрощение сложных логических выражений и т. п.

Машинно-зависимая оптимизация включает:

а) исключение лишних передач управления типа «память-регистр»;

б) выбор более эффективных команд т. п.

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

Литература

  1. Д. Грис. Конструирование компиляторов для цифровых вычислительных машин – М.: Мир, 1975. – 544 с.

  2. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты. Пер. с англ. – М.: «Вильямс», 2003.

  3. В. Дж. Рейуорд–Смит. Теория формальных языков. Вводный курс. – М.: Радио и связь, 1988. – 128 с.


0102880102617487.html
0103021962515847.html
0103095334428561.html
0103214468337785.html
0103340892372262.html