36.Назначение и особенности построения таблиц идентификаторов

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

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

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

или таблицами идентификаторов.

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

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

1. Для переменных: имя, тип данных, область памяти;

2. Для констант: название (если имеется), значение, тип данных;

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

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

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

37. Построение таблиц идентификаторов с помощью бинарного дерева и хэширования

• Для решения проблемы коллизии можно использовать много способов. Одним из них является метод рехеширования(или расстановка). Согласно этому методу, если для элементаAадресh(A), вычисленный с помощью хеш-функцииh, указывает на уже занятую ячейку, то необходимо вычислить значение функцииn1=h1(A) и проверить занятость ячейки по адресуn1. Если и она занята, то вычисляется значениеh2(A) и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значениеhi(A) совпадет сh(A). В последнем случае считается, что таблица идентификаторов заполнена, и места в ней больше нет — выдается информация об ошибке размещения идентификатора в таблице.

• Такую таблицу идентификаторов можно организовать по следующему алгоритму размещения элемента:

• Шаг 1:Вычислить значение хеш-функцииn=h(A) для нового элементаA.

• Шаг 2:Если ячейка по адресуnпустая, то поместить в нее элементAи завершить алгоритм, иначеi:=1 и перейти к шагу 3.

• Шаг 3:Вычислитьni=hi(A). Если ячейка по адресуniпустая, то поместить в нее элементAи завершить алгоритм, иначе перейти к шагу 4.

• Шаг 4:Еслиn=ni, то сообщить об ошибке и завершить алгоритм, иначеi:=i+1 и вернуться к шагу 3.

• Тогда поиск элемента Aв таблице идентификаторов, организованной таким образом, будет выполняться по следующему алгоритму:

• Шаг 1:Вычислить значение хеш-функцииn=h(A) для искомого элементаA.

• Шаг 2:Если ячейка по адресуnпустая, то элемент не найден, алгоритм завершен, иначе сравнить имя элемента в ячейкеnс именем искомого элементаA. Если они совпадают, то элемент найден и алгоритм завершен, иначеi:=1 и перейти к шагу 3.

• Шаг 3:Вычислитьni=hi(A). Если ячейка по адресуniпустая илиn=ni, то элемент не найден и алгоритм завершен, иначе сравнить имя элемента в ячейкеniс именем искомого элементаA. Если они совпадают, то элемент найден и алгоритм завершен, иначеi:=i+1 и повторить шаг 3.

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

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

• Для организации таблицы идентификаторов по методу рехеширования необходимо определить все хеш-функции hiдля всехi. Чаще всего функцииhiопределяют как некоторую модификации хеш-функцииh. Например, самым простым методом вычисления функции hi(A) является ее организация в виде hi(A) = (h(A) + pi) mod Nm, где pi — некоторое вычисляемое целое число, аNm— максимальное значение из области значений хеш-функцииh. В свою очередь, самым простым подходом здесь будет положитьpi=i. Тогда получаем формулуhi(A) = (h(A)+i)modNm. В этом случае при совпадении значений хеш-функции для каких-либо элементов поиск свободной ячейки в таблице начинается последовательно от текущей позиции, заданной хеш-функциейh(A).

• Этот способ нельзя признать особенно удачным — при совпадении хеш-адресов элементы в таблице начинают группироваться вокруг них, что увеличивает число необходимых сравнений при поиске и размещении. Но даже такой примитивный метод рехеширования является достаточно эффективным средством организации таблиц идентификаторов при неполном заполнении таблицы.

Построение таблиц идентификаторов по методу бинарного дерева

Можно сократить время поиска искомого элемента в таблице идентификаторов, не увеличивая значительно время, необходимое на ее заполнение. Для этого надо отказаться от организации таблицы в виде непрерывного массива данных.

Существует метод построения таблиц, при котором таблица имеет форму бинарного дерева. Каждый узел дерева представляет собой элемент таблицы, причем корневым узлом становится первый элемент, встреченный компилятором при заполнении таблицы. Дерево называется бинарным, так как каждая вершина в нем может иметь не более двух ветвей. Для определенности будем называть две ветви «правая» и «левая».

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

1. Выбрать очередной идентификатор из входного потока данных. Если очередного идентификатора нет, то построение дерева закончено.

2. Сделать текущим узлом дерева корневую вершину.

3. Сравнить имя очередного идентификатора с именем идентификатора, содержащегося в текущем узле дерева.

4. Если имя очередного идентификатора меньше, то перейти к шагу 5, если равно – прекратить выполнение алгоритма (двух одинаковых идентификаторов быть не должно!), иначе – перейти к шагу 7.

5. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе – перейти к шагу 6.

6. Создать новую вершину, поместить в нее информацию об очередном идентификаторе, сделать эту новую вершину левой вершиной текущего узла и вернуться к шагу 1.

7. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе – перейти к шагу 8.

7. Создать новую вершину, поместить в нее информацию об очередном идентификаторе, сделать эту новую вершину правой вершиной текущего узла и вернуться к шагу 1.

недостатками метода являются: необходимость хранить две дополнительные ссылки на левую и правую ветви в каждом элементе дерева и работа с динамическим выделением памяти при построении дерева.

Несмотря на указанные недостатки, метод бинарного дерева является довольно удачным механизмом для организации таблиц идентификаторов. Он нашел свое применение в ряде компиляторов.

38 Функции и принципы построения лексических и синтаксических анализаторов.

Лексема – структурная единица языка, которая состоит из элементарных символов языка и не содержит других структурных едениц (слов)

Идентификаторы, операторы языка, ключевые слова (примеры лексем как я понял)

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

Наличие лексического анализатора упрощают работу синтаксического анализатора

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

В некоторых языках лексический анализатор и синтаксический анализатор выполняются одновременно

Таблица лексем

Выдел. Элементы (лексическим анализатором) замен. на коды

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

Что должен делать лексический анализатор?

1)четко определять гран. Лексемы, которые явно не заданы (обычно границы лексем опред пробелом)

2)Сохранить информацию о лексеме (или выдать сообщение об ошибке, если лексема неправильна)

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

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

Это основано на грамматике входного языка (распознавателе).

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

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

39.Функции и принципы построения синтаксических и семантических анализаторов

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

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

Это основано на грамматике входного языка (распознавателе).

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

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

Семантический анализатор

Анализ исходного кода программы проверяет семантическую правильность программы

Выполняет следущие действия:

1. проверка соблюдение во входной программе соблюдения семантических соглашений входного языка

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

3. Проверка семантических норм программы на прямую не связанных с входным языком.

Каждая метка должна присваиваться в программе

Каждый идентификатор должен быть описан 1 раз

Все операнды имеют допустимые типы

Типы переменных должны быть согласованны

Количество параметров при вызове должно соответствовать количеству параметров в описании функции.

40. Генерация и оптимизация кода

Генератор кода порождается или программируется в машинном коде или на языке ассемблер.

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

Мы преобразуем сложные синтаксические структуры в линейные цепочки.

Для построения кода результирующей программы используется построение линейного кода.

Синтаксически управляемый перевод – основной метод получения кода результирующей программы на основании результатов синтаксического разбора (СУ – перевод)

В процессе СУ выполняются некоторые дополнительные действия выдача потока данных исходного кода и потока с сообщениями о ошибках.

41. Формы внутреннего представления программы

Все внутренние формы представления программ в трансляторе содержат элементы 2 видов:

-операторы

-операнды

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

Операнды – это переменные, константы, промежуточные данные, формируемые транслятором, переменные с индексом и другие данные над которыми выполняются соответствующие операторы.

В результате семантического анализа формируется программа, эквивалентная исходной программе и представленная во внутренней форме, удобной для дальнейшей оптимизации.

1. Семантическое дерево, 2 польская запись, 3 список тетрад.

1. Семантическое дерево (СД) – модифицированное дерево грамматического разбора из которого исключили вершины соответствующие нетерминальным символам. Листья СД соответствуют операндам, а вершины операторам. Расположение операторов по уровням дерева определяет порядок их выполнения.

СД удобно использовать для описания выражений и операторов их использующих.

2. Польская запись.

Просто и однозначно указывает порядок выполнения операторов.

Основные свойства:

1. не требует скобок;

2. оператор располагается непосредственно за своими операндами;

3. операторы следуют в том порядке, в котором они должны быть выполнены;

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

Списки тетрад. Удобной формой представления бинарных операций являются тетрады вида:

(<оператор>, <операнд1>, <операнд2>, <результат>)

A+B*C–D

(*, B, C, T1)

(+, A, T1, T2)

(–, T2, D, T3)

T1, T2, T3 –временные переменные формируемые транслятором.

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

42. Структура системы программирования

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

Язык программирования это система, служащая для точного описания алгоритмов для ЭВМ или по крайней мере достаточную для автоматического нахождения такого алгоритма. Эти языки являются искусственными языками со строго определенным синтаксисом.

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

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

Транслятор это программа, осуществляющая перевод текстов с одного языка на другой.

В системе программирования транслятор переводит программу с входного языка этой системы на машинный язык реальной ЭВМ (на которой функционирует данная система программирования или будет функционировать разрабатываемая программа) либо на промежуточный язык программирования, уже реализованный или подлежащий реализации.

Одной из разновидностей транслятора является компилятор, обеспечивающий перевод программ с языка высокого уровня (приближенного к человеку) на язык более низкого уровня (близкий к ЭВМ), или машинозависимый язык.

Другая разновидность транслятора - ассемблер , осуществляющий перевод программ с языка низкого уровня (языка Ассемблера) на машинный язык, имеющий примерно тот же уровень. Некоторые трансляторы служат для переноса программ с одной машины на другую.

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

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

Диаметрально противоположными характеристиками обладает альтернативное средство реализации языка - интерпретатор. Интерпретатор представляет собой программный продукт, выполняющий предъявленную программу путем одновременного ее анализа и реализации предписанных ею действий. При использовании интерпретатора отсутствует разделение на две стадии (перевод и выполнение) и, более того, отсутствует явный перевод программы даже по частям перед очередным этапом выполнения. В действительности же распознается очередная конструкция программы и интерпретатором выполняются определяемые ею действия.

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

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

Стилю (парадигме) программирования соответствует своя собственная (уникальная) модель вычислений.

43. Текстовый редактор и компилятор в системе программирования

Текстовый редактор – это редактор, который позволяет набрать текст программы на языке программирования.Для этой цели можно использовать любые текстовые редакторы, но лучше пользоваться специализированным текстовым редактором.

Компилятор– это транслятор, который исходный текст программы переводит вмашинный код. Если в тексте программы нет синтаксических ошибок, то машинный код будет создан. Но это, как правило, не работоспособный код, т.к. в этой программе не хватает подпрограмм стандартных функций, поэтому компилятор выдает промежуточный код, который называетсяобъектным кодоми имеет расширение.obj.

44.

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

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

4. Выполняет программы до достижения точки остановки

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

6. Просмотр содержания областей памяти

1. Группы системных программ1-2

2. Понятие операционной среды2

3. Понятие вычислительного процесса и ресурса3

4. Диаграмма состояний процесса4

5. Реализация понятия последовательного процесса в ОС5

6. Процессы и потоки6

7. Обработка прерываний7-8

8. Дисциплины обслуживания прерываний9

9. Обработка прерываний при участии супервизора ОС9

10. Основные виды ресурсов10-11

11. Классификация ОС12

12. Функции ОС по управлению задачами13-14

13. Планировщики, стратегии планирования15

14. Дисциплины диспетчеризации FCFS, SJN, SRT16-17

15. Дисциплина диспетчеризации RR, приоритеты, многоуровневая очередь18

16. Вытесняющие и не вытесняющие алгоритмы диспетчеризации19

17. Качество диспетчеризации, гарантии обслуживания20-21

18. Диспетчеризация задач с использованием динамических приоритетов21

19. Память и отображения, виртуальное адресное пространство22

20. Простое непрерывное распределение, оверлейные структуры23-24

21. Разделы с фиксированными границами25

22. Разделы с подвижными границами26

23. Сегментная организация виртуальной памяти27

24. Страничная организация виртуальной памяти28-29

25. Сегментно-страничная организация виртуальной памяти30

26. Основные понятия и концепции организации ввода/вывода в ОС31-32

27. Режимы управления вводом/выводом33

28. Закрепление устройств, общие устройства ввода/вывода34

29. Синхронный и асинхронный ввод/вывод35

30. Кэширование операций ввода/вывода при работе с HDD36-37

31. Стратегии обработки запросов к жесткому диску38

32. Функции файловой системы ОС и иерархия данных39-40

33. Транслятор, компилятор, интерпретатор.41-42

34. Общая схема работы транслятора43

35. Понятие прохода, особенности ассемблеров44

36. Простейшие способы построения таблиц идентификаторов.45

37. Построение таблиц идентификаторов с помощью бинарного дерева и хэширования 46-47

38. Функции и принципы построения лексических и синтаксических анализаторов 48

39. Функции и принципы построения синтаксических и семантических анализаторов 49

40. Генерация и оптимизация кода 49

41. Формы внутреннего представления программы50

42. Структура системы программирования51

43. Текстовый редактор и компилятор в системе программирования52

44. Функции компоновщика и отладчика52

1.

2Reenterable – (дословно) допускающий повторные обращения (к модулю).

3Time slice – квант времени.