3Распределение памяти

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

Различают:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Глобальная память предполагает неограниченный доступ из любого места программы.

4Генерация и оптимизация кодов

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

Mov AX, <Op1>

Add AX, <Op2>

Mov AX, <Result>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

Содержание

Введение. Трансляция арифметических выражений. Метод Рутисхаузера 2

1 Основные понятия и определения 3

1.1 Классификация компилирующих программ 3

1.2 Синтаксис и семантика. Структура компилятора 3

2 Формальные грамматики и их использование при лексическом и синтаксическом анализе 5

2.1 Формальная грамматика и формальный язык 5

2.2 Понятие грамматического разбора 7

2.3 Расширенная классификация грамматик Хомского 11

2.4 Распознавание регулярных грамматик 12

2.4.1 Конечный автомат и его программная реализация 12

2.4.2 Построение лексических анализаторов 14

2.4.3 Построение синтаксических анализаторов 16

2.5 Распознавание КС-грамматик 17

2.5.1 Автомат с магазинной памятью 17

2.5.2 Синтаксические анализаторы LL(k)-грамматик. Метод рекурсивного спуска 19

2.5.3 Синтаксические анализаторы LR(k)-грамматик. Грамматики предшествования 24

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