ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 81
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
программа на языке машины, записанная на внешнюю память (для выполнения она должна быть объединена с другими подпрограммами и затем загружена).
Первый вариант наиболее экономичен в отношении расходуемого времени. Главный недостаток этого варианта состоит в том, что нельзя предварительно и независимо протранслировать несколько подпрограмм и затем объединить их вместе дня выполнения, все подпрограммы должны транслироваться одновременно. Выигрыш во времени оборачивается проигрышем в гибкости. Проще всего получить объектную программу на автокоде. В этом случае не приходится формировать команды как последовательности битов; можно порождать команды, содержащие символические имена. Более того, можно формировать макроопределение. Это позволяет также уменьшить объем компилятора. Несмотря на очевидные достоинства, трансляция на автокод обычно считается наихудшим из вариантов. И в самом деле, к процессу трансляции добавляется еще один шаг, который часто требует столько же времени, сколько длится собственно компиляция. Большинство промышленных компиляторов вырабатывают объектную программу в виде объектного модуля. Как правило, объектный модуль содержит символические имена других программ (подпрограмм), к которым он обращается, и имена своих входных точек, к которым можно обращаться из других программ. Эта объектная программа "объединяется" с теми другими объектными программами, а затем загружается в некоторую область памяти для выполнения.
В этом варианте обеспечивается гораздо большая гибкость, и поэтому во многих системах он и принят в качестве стандартной процедуры. Следует, однако, заметить, что на объединение и загрузку также расходуется время.
Теперь покажем, как генерируются команды для последовательности четверок и постфиксной записи, используя в качестве примера выражение
А * ((А * В + С) – С * В).
Будем считать переменные А, В, С, В целыми.
Генерация кода для последовательности четверок.
Для рассматриваемого примера последовательность четверок имеет вид:
* A B I1
+ I1 C I2
* C D I3
– I2 I3 I4
* a I4 I5
В основе процедуры генерации кода лежит оператор саsе:
ргосеdure ГК;
саsе код операции четверки of
* : подпрограмма, соответствующая операции *;
+ : подпрограмма, соответствующая операции + ;
– : подпрограмма, соответствующая операции – ;
end;
Генерация кода для постфиксной записи. Для рассматриваемого примера постфиксная запись имеет вид:
A A B * C + C D * – A *.
Операторы и операнды просматриваются последовательно слева направо. Всякий раз, когда просматривается операнд, в стек заносится его имя. А когда встречается операция, генерируются команды для ее выполнения. При этом в качестве описаний операндов используются два верхних описания в стеке; затем эти два описания заменяются описанием результата. При этом необходимо сформировать временное имя Ti, которое заносится в стек. На практике стек можно отобразить на одномерный массив S(1), S(2), …, S(n). Для указания вершины стека можно использовать индекс i. При записи в стек указатель вершины будет сдвигаться в сторону конца массива, при чтении из стека указатель вершины будет перемещатьсяя в сторону начала массива
(рис. 14).
Рис. 14
Для обработки доступен только элемент S(i), т.е. вершина стека. Значение i = 0 перед чтением из стека служит признаком того, что стек пуст, а значение i = n перед записью в стек признаком того, что стек переполнен.
Контрольные вопросы
Лекция 3. ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ
План:
Ключевые слова: таблица символов, поиск, коллизия.
1. Способы организации таблиц символов
Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программе на исходном языке. Эти характеристики выясняются из описаний и из того, как идентификаторы используются в программе. Вся информация накапливается в таблицах символов.
Таблицы всех типов имеют общий вид (табл. 6). В нашем случае аргументами таблицы аргумент значение являются символы или идентификаторы, а значениями - их характеристики. Когда компилятор начинает трансляцию исходной программы, таблица символов пуста или содержит только несколько элементов для служебных слов и стандартных функций. В процессе компиляции для каждого нового идентификатора элемент добавляется только один раз, но поиск ведётся всякий раз, когда встречается этот идентификатор. Так как на этот процесс уходит много времени, важно выбрать такую организацию таблиц, которая допускала бы эффективный поиск.
Таблица 6 Таблица 7
Простейший способ организации таблицы состоит в том, чтобы добавлять элементы в порядке их поступления без каких-либо попыток упорядочения. Поиск в этом случае требует сравнения с каждым элементом таблицы, пока не будет найден подходящий. Для таблицы, содержащей N элементов, в среднем будет выполнено N/2 сравнений. Если N велико, такой способ неэффективен. Поиск может быть выполнен более эффективно, если элементы таблицы упорядочены согласно некоторому естественному порядку аргументов. В нашем случае, когда аргументами являются строки символов, наиболее естественным является упорядочение по алфавиту. Эффективным методом поиска в упорядоченном списке является так называемый бинарный поиск. Сортировка таблицы производится методом упорядоченных вставок.
Наиболее эффективный и широко применяемый в компиляторах метод при работе с таблицами символов – хеш-адресация. Механизм расстановки состоит из таблицы и хеш-функции (табл. 7). Таблица состоит из N элементов, где N заранее фиксировано. Метод хеш-адресации заключается в преобразовании символа в индекс элемента в таблице. Индекс получается хешированием символа – т.е. выполнением над ним некоторых операций. Если в процессе компиляции встретился объект а, то для поиска его в таблице можно воспользоваться следующим алгоритмом: если объект уже встречался ранее, то h(а) – ячейка в таблице, в которой хранится а. Если объект а ранее не встречался, то h(а) – пустая ячейка, в которую заносится информация для а.
Возникает, однако, затруднение, если результаты хеширования двух разных символов совпадают. Это называется коллизией. Очевидно, в данной позиции таблицы может быть помещён только один из этих символов, так что мы должны найти свободное место для второго. Желательно иметь такую хеш-функцию, которая распределяла бы объекты равномерно по всей таблице, так чтобы коллизии не возникали слишком часто. Но избежать их совсем, практически не удаётся, поэтому разработчику компилятора следует предусмотреть способы решения задачи коллизии. Существует два таких способа – рехеширование и метод цепочек. Подробнее в лабораторной работе рассматривается последний способ.
2. Метод цепочек
Метод цепочек использует хеш-таблицу, элементы которой первоначально равны 0, собственно таблицу символов, вначале пустую, и указатель
ук, который указывает на текущее положение последнего элемента в таблице символов. Элементы таблицы символов имеют дополнительное поле СНАIN, которое может содержать 0 или адрес другого элемента таблицы символов. Начальное состояние таблицы приведено на рис. 15.
Хеш-функция, применённая к символу, даёт индекс указателя в хеш-таблице. Указатель либо равен 0, либо указывает на первый элемент таблицы символов с данным значением хеш-функции. Поле СНАIN каждого элемента используется для того, чтобы связать в цепочку элементы, для которых хеширование символа приводит к тому же самому указателю. Например, в таблицу необходимо записать символ S1, Функция хеширования вырабатывает адрес элемента хеш-таблицы, например 4. Содержимое этой ячейки равно 0. Тогда выполняется следующее:
Рис. 15
Первый вариант наиболее экономичен в отношении расходуемого времени. Главный недостаток этого варианта состоит в том, что нельзя предварительно и независимо протранслировать несколько подпрограмм и затем объединить их вместе дня выполнения, все подпрограммы должны транслироваться одновременно. Выигрыш во времени оборачивается проигрышем в гибкости. Проще всего получить объектную программу на автокоде. В этом случае не приходится формировать команды как последовательности битов; можно порождать команды, содержащие символические имена. Более того, можно формировать макроопределение. Это позволяет также уменьшить объем компилятора. Несмотря на очевидные достоинства, трансляция на автокод обычно считается наихудшим из вариантов. И в самом деле, к процессу трансляции добавляется еще один шаг, который часто требует столько же времени, сколько длится собственно компиляция. Большинство промышленных компиляторов вырабатывают объектную программу в виде объектного модуля. Как правило, объектный модуль содержит символические имена других программ (подпрограмм), к которым он обращается, и имена своих входных точек, к которым можно обращаться из других программ. Эта объектная программа "объединяется" с теми другими объектными программами, а затем загружается в некоторую область памяти для выполнения.
В этом варианте обеспечивается гораздо большая гибкость, и поэтому во многих системах он и принят в качестве стандартной процедуры. Следует, однако, заметить, что на объединение и загрузку также расходуется время.
Теперь покажем, как генерируются команды для последовательности четверок и постфиксной записи, используя в качестве примера выражение
А * ((А * В + С) – С * В).
Будем считать переменные А, В, С, В целыми.
Генерация кода для последовательности четверок.
Для рассматриваемого примера последовательность четверок имеет вид:
* A B I1
+ I1 C I2
* C D I3
– I2 I3 I4
* a I4 I5
В основе процедуры генерации кода лежит оператор саsе:
ргосеdure ГК;
саsе код операции четверки of
* : подпрограмма, соответствующая операции *;
+ : подпрограмма, соответствующая операции + ;
– : подпрограмма, соответствующая операции – ;
end;
Генерация кода для постфиксной записи. Для рассматриваемого примера постфиксная запись имеет вид:
A A B * C + C D * – A *.
Операторы и операнды просматриваются последовательно слева направо. Всякий раз, когда просматривается операнд, в стек заносится его имя. А когда встречается операция, генерируются команды для ее выполнения. При этом в качестве описаний операндов используются два верхних описания в стеке; затем эти два описания заменяются описанием результата. При этом необходимо сформировать временное имя Ti, которое заносится в стек. На практике стек можно отобразить на одномерный массив S(1), S(2), …, S(n). Для указания вершины стека можно использовать индекс i. При записи в стек указатель вершины будет сдвигаться в сторону конца массива, при чтении из стека указатель вершины будет перемещатьсяя в сторону начала массива
(рис. 14).
Рис. 14
Для обработки доступен только элемент S(i), т.е. вершина стека. Значение i = 0 перед чтением из стека служит признаком того, что стек пуст, а значение i = n перед записью в стек признаком того, что стек переполнен.
Контрольные вопросы
-
Какова роль лексического анализатора? -
Что такое лексемы? -
Каким этапом компиляции является синтаксический анализ? -
Какими бывают методы синтаксического анализа? -
Какой этап предшествует синтаксическому анализу? -
Что означает данная запись <список переменных> -> ид{,ид}? -
Конечными символами грамматического дерева являются … -
В каком виде лексический анализатор должен представлять исходный текст? -
Во время какого этапа предложения распознаются как языковые конструкции используемой грамматики? -
Этот метод относится к восходящим, которые начинают разбор с конечных узлов грамматического дерева и пытаются объединить их построением узлов все более и более высокого уровня до тех пор, пока не будет достигнут корень дерева. -
В методе операторного предшествования переименование нетерминальных символов возможно? -
Чем отличаются способы нисходящего и восходящего грамматического разбора? -
Какие известны методы синтаксического анализа? -
В чём сущность метода рекурсивного спуска? -
Для чего применяется изменённый способ записи БНФ? -
В каком виде представляется программа на выходе синтаксического анализатора? -
В чём сущность метода операторного предшествования? -
Запись, в которой знак операции ставится непосредственно за операндами называется? -
Сколько возможно форм объектного кода? -
В какой форме объектного кода не приходится формировать команды как последовательности битов; можно порождать команды, содержащие символические имена? -
Почему программу на автокоде считают наихудшим из вариантов? -
В генерации кода для постфиксной записи для указания вершины стека обычно используют индекс i. какое значение i перед чтением стека будет означать, что стек пуст?
Лекция 3. ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ
План:
-
Способы организации таблиц символов -
Неупорядоченные и упорядоченные таблицы -
Хеш-адресация -
Рехеширование -
Метод цепочек
Ключевые слова: таблица символов, поиск, коллизия.
1. Способы организации таблиц символов
Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программе на исходном языке. Эти характеристики выясняются из описаний и из того, как идентификаторы используются в программе. Вся информация накапливается в таблицах символов.
Таблицы всех типов имеют общий вид (табл. 6). В нашем случае аргументами таблицы аргумент значение являются символы или идентификаторы, а значениями - их характеристики. Когда компилятор начинает трансляцию исходной программы, таблица символов пуста или содержит только несколько элементов для служебных слов и стандартных функций. В процессе компиляции для каждого нового идентификатора элемент добавляется только один раз, но поиск ведётся всякий раз, когда встречается этот идентификатор. Так как на этот процесс уходит много времени, важно выбрать такую организацию таблиц, которая допускала бы эффективный поиск.
Таблица 6 Таблица 7
| № | Аргумент | Значение | | | № | Аргумент | Значение |
| 1 | | | | | 0 | | |
| 2 | | | | | 1 | | |
| … | … | … | | | … | … | … |
| … | … | … | | | h(a) | | |
| … | … | … | | | … | … | … |
| N | | | | | N-1 | | |
Простейший способ организации таблицы состоит в том, чтобы добавлять элементы в порядке их поступления без каких-либо попыток упорядочения. Поиск в этом случае требует сравнения с каждым элементом таблицы, пока не будет найден подходящий. Для таблицы, содержащей N элементов, в среднем будет выполнено N/2 сравнений. Если N велико, такой способ неэффективен. Поиск может быть выполнен более эффективно, если элементы таблицы упорядочены согласно некоторому естественному порядку аргументов. В нашем случае, когда аргументами являются строки символов, наиболее естественным является упорядочение по алфавиту. Эффективным методом поиска в упорядоченном списке является так называемый бинарный поиск. Сортировка таблицы производится методом упорядоченных вставок.
Наиболее эффективный и широко применяемый в компиляторах метод при работе с таблицами символов – хеш-адресация. Механизм расстановки состоит из таблицы и хеш-функции (табл. 7). Таблица состоит из N элементов, где N заранее фиксировано. Метод хеш-адресации заключается в преобразовании символа в индекс элемента в таблице. Индекс получается хешированием символа – т.е. выполнением над ним некоторых операций. Если в процессе компиляции встретился объект а, то для поиска его в таблице можно воспользоваться следующим алгоритмом: если объект уже встречался ранее, то h(а) – ячейка в таблице, в которой хранится а. Если объект а ранее не встречался, то h(а) – пустая ячейка, в которую заносится информация для а.
Возникает, однако, затруднение, если результаты хеширования двух разных символов совпадают. Это называется коллизией. Очевидно, в данной позиции таблицы может быть помещён только один из этих символов, так что мы должны найти свободное место для второго. Желательно иметь такую хеш-функцию, которая распределяла бы объекты равномерно по всей таблице, так чтобы коллизии не возникали слишком часто. Но избежать их совсем, практически не удаётся, поэтому разработчику компилятора следует предусмотреть способы решения задачи коллизии. Существует два таких способа – рехеширование и метод цепочек. Подробнее в лабораторной работе рассматривается последний способ.
2. Метод цепочек
Метод цепочек использует хеш-таблицу, элементы которой первоначально равны 0, собственно таблицу символов, вначале пустую, и указатель
ук, который указывает на текущее положение последнего элемента в таблице символов. Элементы таблицы символов имеют дополнительное поле СНАIN, которое может содержать 0 или адрес другого элемента таблицы символов. Начальное состояние таблицы приведено на рис. 15.
Хеш-функция, применённая к символу, даёт индекс указателя в хеш-таблице. Указатель либо равен 0, либо указывает на первый элемент таблицы символов с данным значением хеш-функции. Поле СНАIN каждого элемента используется для того, чтобы связать в цепочку элементы, для которых хеширование символа приводит к тому же самому указателю. Например, в таблицу необходимо записать символ S1, Функция хеширования вырабатывает адрес элемента хеш-таблицы, например 4. Содержимое этой ячейки равно 0. Тогда выполняется следующее:
-
Прибавляем 1 к УК. -
Вносим элемент (S1, значение, 0) в позицию таблицы символов, на которую указывает ук. -
Заносим содержимое ук. в указатель 4 хеш-таблицы. -
Пока поступают символы, хеширование которых даёт индексы разных указателей, они заносятся в таблицу аналогичным образом. Так, если мы записываем в таблицу символы S2, S3, S4, хеширование которых даёт ссылки на указатели 1, 3, 6, таблица примет вид, представленный на рис. 16.
| № | Хеш-таблица | | № | Аргумент | Значение | CHAIN | Ук=0 |
| 0 | | | 1 | | | | |
| 1 | | | 2 | | | | |
| … | | | … | | | | |
| N-1 | | | N | | | | |
Рис. 15
| № | Хеш-таблица | | № | Аргумент | Значение | CHAIN | Ук=4 |
| 0 | | | 1 | S1 | … | 0 | |
| 1 | 2 | | 2 | S2 | … | 0 | |
| 2 | | | 3 | S3 | … | 0 | |
| 3 | 3 | | 4 | S4 | … | 0 | |
| 4 | 1 | | | | | | |
| 5 | | | | | | | |
| 6 | 4 | | | | | | |