Системное программирование part1

Введение

Assembler.

FORTRAN – 1957 г. (FORTRAN 2. 4).

ALGOL – 1958 – 1960 (58, 60 , 68) – Алгоритмический язык.

COBOL – 1959 – 1960 – Общий язык ориентированный на бизнес.

LISP 1959 – 1960

Бейсик 1963

FOURTH (форт)

Паскаль — 1972

Лого

Ада – 1970

Архитектуры ЭВМ – Отражает

Структурную.

Схематическую.

Логическую организацию.

В неё входят:

Структурная схема ЭВМ.

Средства и способы доступа к элементам структурной схемы ЭВМ.

Организация и разрядность интерфейсов ЭВМ.

Набор и доступность регистров ЭВМ.

Организация и способы адресации памяти.

Способы представления и форматы данных ЭВМ.

Набор машинных команд.

Форматы машинных команд.

Правила обработки не штатных ситуаций (прерываний).

Понятия архитектуры ЭВМ – Иерархическая.

Все современные компьютеры обладают индивидуальными архитектурными свойствами!

Трансляторы, компиляторы – общая схема работы. Этапы трансляции. Интерпретаторы.

Assembler – программа написанная на автокоде или на языке Assembler-а на язык вычислительной машины. Автокод очень близок к машинному коду или является копией команд машины.

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

Интерпретатор – это программа или устройство осуществляющее пооператорную трансляцию и выполнение исходной программы.

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

Перекодировщик – это программа или программное устройство переводящее программы написанные на машинном языке одной ЭВМ в программы на машинном языке другой ЭВМ.

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

Общая схема трансляций

Практически во всех трансляторах присутствуют следующие процессы:

Лексическим анализ

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

Семантический

Генерация внутреннего представления программы

Оптимизация

Генерация объектной программы

Процесс компиляции состоит из двух основных этапов:

Анализа

Синтеза

На этапе анализа выполняется:

Распознавания текста исходной программы

Создание и заполнение в таблице идентификаторов.

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

На этапе синтеза на основании внутренне программы и информации содержащейся в таблицах идентификаторов порождается текст результирующей программы. Результат этого этапа – ОБЪЕКТНЫЙ КОД.

Этап анализа фазы:

Лексический анализ (сканер) – это часть компилятора которая читает литеры программы на исходном языке и строит из них слова исходного языка. Фаза является не обязательной в основном используется для исключения из текста исходной программы комментариев, не значащих пробелов символов строки.

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

Выделение синтаксических конструкций в тексте программы

Проверяется синтаксическая правильность программы

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

Этап синтеза:

Подготовка к генерации кода – эта фаза на которой компилятором выполняются предварительные действия непосредственно связанные с синтезом текста результирующей программы но ещё не ведущее к порождению текста на родном языке: Распределение памяти, идентификация элементов языка и т.д.

Генерация кода – эта фаза непосредственно связанная с порождением результирующей программы. Это основная фаза на этапе синтеза.

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

Например:

Обратная Польская запись –все операции записываются непосредственно в порядке их выполнения. Эффективно в случаях для вычислений работы со стеком.

Тетрады операций – запись операций в форме из четырех составляющих

( )

Add ax bx

Тетрады используются редко так как требуют больше памяти, чем триады.

Триады ( )

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

A: = B*C+D-B*10 (пример)

1) *(В, С)

2) + (^1, D)

3) * (B, 10)

4) – (^2, ^3)

5) : (A, ^4)

Программы ассемблеры

Трансляторы

Транслятор обычно так же выполняет диагностику ошибок, ФОРМИРУЕТ словари идентификаторов, выдает для печати тексты программы.

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

Сам транслятор является программой.

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

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

! Важное требование в определении транслятора – эквивалентность входной и выходной программ.

Компилятор

Компиляция – это трансляция программы на язык близкий к машинному.

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

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

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

Интерпретатор

Существует несколько классификаций интерпретаторов.

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

Достоинства – мгновенная реакция. Недостаток – обнаруживает ошибки в тексте программы только при попытке выполнения команды с ошибкой.

Алгоритм работы простого интерпретатора:

Прочитать инструкцию (команду);

Проанализировать инструкцию (команду) и определить соответствующие действия;

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

Если не достигнуто условия завершения программы, прочитать следующую инструкцию (команду) и перейти к пункту 2.

Интерпретатор компилирующего типа – это система из компилятора, переводящего исходный код программы в промежуточное представление (байт — код) И собственно интерпретатора, который выполняет полученный промежуточный код.

Достоинство – Большее быстродействие за счёт выноса анализа исходного кода в отдельный проход и минимизации этого анализа в интерпретаторе.

Недостатки – 1) Большее требования к ресурсам. 2) Требование на корректность исходного кода.

Общие достоинства интерпретаторов и недостатки:

Достоинства

Большая переносимость интерпретируемых программ — программа будет работать на любой платформе на которой есть соответствующий интерпретатор.

Более совершенные и наглядные средства диагностики ошибок в исходных кодах.

Упрощение отладки исходных кодов программ

Меньшие размеры кода по сравнению с машинным кодом полученным после обычных компиляторов.

Недостатки:

Интерпретируемая программа не может выполняться отдельно от программы интерпретатора.

Интерпретируемая команда выполняется медленно.

Практически отсутствует оптимизация кода.

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

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

Реальные компиляторы осуществляют от 2-х до 5-ти проходов и является многопроходными.

Варианты взаимодействия блоков трансляции

Можно выделить 2 основных варианта взаимодействия блоков транслятора:

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

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

Многопроходная организация взаимодействия блоков трансляции.

(Схема1)

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

Достоинства такого подхода:

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

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

Возможность уменьшения объема оперативной памяти требуемой для работы транслятора за счет последовательного вызова фаз.

Недостатки такого подхода:

Наличие больших объемов промежуточной информации.

Замедление скорости трансляции из-за последовательного выполнения фаз.

Однопроходная организация взаимодействия блоков трансляции (схема 2)

Процесс трансляции протекает следующим образом:

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

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

Работает генератор кода (аналогичным образом). По окончанию исходного текста и завершении обработки всех промежуточных данных, получаем объектный код.

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

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

Достоинства однопроходной схемы:

Отсутствие больших объемов промежуточных данных.

Высокая скорость обработки из-за совмещения фаз в едином процессе и отсутствие обращений к внешним запоминающим устройствам.

Недостатки однопроходного варианта:

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

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

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

(Схема 1.10 «Классический интерпретатор»)

Комбинированные взаимодействия блоков транслятора

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

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

(Схема 1.11)

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

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

Существуют трансляторы допускающие их совместное использование (одновременно и генератор и эмулятор). Примером может служить язык программирования java.

Таблицы идентификаторов

Таблицы идентификатора – это специальным образом организованные наборы данных служащие для хранения информации об элементах исходной программы которые затем используются для порождения текста результирующей программы. Элементами исходной программы являются переменные, константы, функции и т.д. то есть конкретный состав набора элементов который зависит от конкретного входного языка. Проверка правильности семантики требует знания характеристик элементов языка встречающихся в программе на исходном языке. Все эти элементы в исходной программе обозначаются идентификаторами. Выделение идентификаторов происходит на фазе лексического анализа. ! А их характеристики определяются на фазах семантического и синтаксического анализа, а так же для генерации кода. Состав возможных характеристик и методы их определения зависит от семантики входного языка. Компилятор должен хранить все найденные идентификаторы и их характеристики в течении всего процесса компиляции чтобы использовать их на разных фазах компиляции, для этой цели в компиляторах используется специальное хранилище данных – таблицы идентификаторов (символов). Любая таблица идентификаторов состоит из набора полей количество которых равно числу различных идентификаторов найденных в исходной программе. Каждое поле содержит в себе полную информацию о данном элементе таблицы. Состав информации хранимый в таблице идентификаторов для каждого элемента зависит от семантики входного языка и типа элемента. Например:

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

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

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

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