Системное программное обеспечение
.pdfправило для error, некоторым специальным образом: символы из стека выталкиваются до тех пор, пока на верхушке стека не будет обнаружено состояние, для которого набор ситуаций содержит ситуацию вида [A 
:error w]. После чего в стек фиктивно помещается символ error, как если бы он встретился во входной строке.
Если w пусто, делается свертка. После этого анализатор пропускает входные символы, пока не найдет такой, с которым можно продолжить нормальный разбор.
Если w не пусто, просматривается входная строка и делается попытка свернуть w. Если w состоит только из терминалов, эта строка ищется во входном потоке.
Литература
Основная:
1.Молчанов А.Ю. Системное программное обеспечение. Учебник для вузов.
— СПб.: Питер, 2003. — 396 с.
2.Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум.- СПб.: Питер, 2005.- 284 с.
3.Юров В.И. Assembler. Учебник для вузов. 2-е издание - СПб.: Питер.- 2004.-
637с.
4.Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование: Основы построения трансляторов + FD.- М.: КОРОНА принт.- 2004.- 255 с.
5.Фельдман Ф.К. Системное программирование на персональном компьютере.- 2004.- 512
6.Ахо А.,Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 768 с.
7.Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. —
СПб.: Питер, 2002. — 734 с.
8.Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002. — 544
Дополнительная:
1.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2001. – Ч. 1. – 96 с.
2.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2002. – Ч. 2. – 96 с.
3.Ф.Льюис, Д. Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. М., Мир, 1979.
4.Л. Бек. Введение в системное программирование. М.,Мир, 1988.
5.В.Е.Котов, В.К.Сабельфельд. Теория схем программ. -М.: Наука, 1978
6.Автоматное управление асинхронными процессами в ЭВМ и дискретных системах /Под ред. В.И.Варшавского. -М.:Наука.
7.Питерсон Дж. Теория сетей Петри и моделирование систем.- М.: Наука.
1984.
8.Минский М. Вычисления и автоматы. - М.: Мир.- 1971.
9.Котов В.Е. Сети Петри. - М.: Наука. - 1984.-
10.Ахо А.,Хопкрофт Дж., Ульман Дж.Построение и анализ вычислительных алгоритмов. - М.: Мир. -1979.
11.Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. –
М.: Мир, 1984. – 264 с.
Лекция 11 Общая схема работы трансляторов и интерпретаторов.
План
1.Этапы трансляции. Общая схема работы транслятора.
2.Понятие прохода. Многопроходные и однопроходные компиляторы.
1.Этапы трансляции. Общая схема работы транслятора.
Транслятор – это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке.
В определение транслятора, как и в его работе, участвует три программы. Во-первых, сам транслятор – программа. Он входит в состав СПО, представляет собой набор машинных команд и данных и выполняется
компьютером в рамках ОС.
Во-вторых, исходными данными для транслятора является текст входной программы. Как правило, это системный файл, содержащий текст программы и удовлетворяющий синтаксическим и семантическим требованиям входного языка.
В-третьих, выходными данными транслятора является текст результирующей программы, которая строится по синтаксическим правилам, заданным в выходном языке транслятора.
Важным требованием в определении транслятора является эквивалентность программ на входе и выходе. Нарушение этого требования делает работу транслятора бесполезной.
С точки зрения принципа работы транслятор выступает как переводчик: преобразует предложения входного языка в эквивалентные им предложения выходного языка. Кроме того, само слово «транслятор» означает «переводчик».
Кроме понятия «транслятор» широко применяется близкое понятие «компилятор».
Компилятор – это транслятор, осуществляющий перевод исходной программы в эквивалентную ей объектную программу на языке ассемблера. Отличие компилятора от транслятора состоит в том, его входная (результирующая) программа должна быть написана на языке машинных команд или на ассемблере. Результат работы транслятора может быть написан на любом языке.
Всякий компилятор является транслятором, но не всякий транслятор является компилятором.
Слово «компилятор» соответствует английскому «составитель», «компоновщик». Выданная компилятором программа не может непосредственно выполняться на компьютере из-за того, что не привязана к конкретной области памяти с кодами и данными. Компиляторы – самый
распространенный вид трансляторов. Если трансляторы и компиляторы во многом похожи, то существуют принципиально отличное от них понятие интерпретатора.
Интерпретатор – это программа, которая воспринимает входную программу на исходном языке и выполняет ее.
Интерпретатор в отличие от транслятора не выдает результирующую программу или код. После анализа текста исходной программы. Интерпретатор сразу же ее выполняет в соответствии с ее смыслом. Интерпретатор преобразует исходную программу в машинные коды, которые не доступны пользователю. Машинные коды порождаются интерпретатором, исполняются и уничтожаются.
Этапы трансляции. Общая схема работы транслятора.
Процесс компиляции состоит из двух основных этапов – анализа и синтеза.
Рис.18. Компиляция программ.
На этапе анализа распознается текст исходной программы, создаются и заполняются таблицы идентификаторов. Результатом анализа является некое внутреннее представление программы, понятное компилятору.
На этапе синтеза из внутреннего представления программы и информации из таблицы идентификаторов, получается результирующая объектная программа.
В составе компилятора присутствует часть, ответственная за анализ и исправление ошибок. При наличии ошибок в тексте исходной программы пользователь должен получить максимально полную информацию о типе ошибки и месте ее возникновения.
Компилятор с точки зрения теории формальных языков выполняет две основные функции:
1.Он является распознавателем для языка исходной программы, он получает на вход цепочку символов входного языка, проверяет ее принадлежность языку и выявляет правила, по которым эта цепочка построена;
2.Он генерирует результирующую программу. На выходе создается цепочка выходного языка по определенным правилам. Распознавателем сгенерированной цепочки объектной программы будет выступать вычислительная система.
Кратко представим функции основных фаз компиляции:
Лексический анализ. Эту часть компилятора выполняет сканер, который читает литеры программы (символы) на исходном языке и строит из них слова (лексемы) исходного языка. На выходе сканера (лексического анализатора) текст исходной программы, выходная информация передается для дальнейшей обработки на этап синтаксического разбора.
Синтаксический разбор – это основная часть компилятора на этапе анализа. Здесь в тексте исходной программы выделяются синтаксические конструкции. Кроме того, проверяется синтаксическая правильность программы.
Семантический анализ – это часть компилятора, проверяющая часть текста исходной программы с точки зрения семантики входного языка.
Подготовка к генерации кода – на этой фазе компилятор выполняет предварительные действия, непосредственно связанные с синтезом текста результирующей программы. Эта подготовка еще не ведет к порождению текста на выходном языке. К этой фазе относят: идентификация элементов языка, распределение памяти и т.п.
Генерация кода – это фаза, на которой непосредственно порождаются команды, составляющие предложения выходного языка и текст результирующей программы в целом. Фаза генерации кода, основанная на этапе синтеза результирующей программы. Кроме этого, генерация обычно включает в себя и оптимизацию. Оптимизация – это процесс, связанный с обработкой уже порожденного текста и оказывающий существенное влияние на качество и эффективность результирующей программы.
Таблицы идентификаторов.
Специальным образом организованные наборы данных, которые хранят информацию об элементах исходной программы. Содержимое таблицы идентификаторов используется для порождения текста результирующей программы. В процессе компиляции нужно хранить информацию о переменных, константах, функциях и т.п. конкретный состав таблиц идентификаторов зависит от используемого входного языка программирования.
2.Понятие прохода. Многопроходные и однопроходные компиляторы.
Порядок выполнения фаз компиляции может меняться в разных вариантах компиляторов. В одних компиляторах просмотр текста исходной программы сопровождается выполнением всех фаз компиляции и получением результата – объектного кода. В других – над исходным текстом выполняются только некоторые фазы компиляции, и получается не конечный результат, а набор некоторых промежуточных данных, которые снова подвергаются обработке. Причем несколько раз. Реальные компиляторы транслируют текст исходной программы за несколько проходов. Проход – это процесс последовательного чтения компилятором данных из внешней памяти, их обработки и записи результата во внешнюю память. Чаще всего один проход включает в себя выполнение одной или нескольких фаз компиляции. В качестве внешней памяти могут выступать любые носители информации – ОП, накопители на магнитных дисках, лентах и т.д. при выполнении каждого прохода компилятору доступна информация, полученная в результате всех предыдущих проходов. Но как правило, в первую очередь используется информация, полученная на проходе, непосредственно предшествующему текущему. Информация, получаемая компилятором при выполнении проходов, недоступна пользователю. Человек, компилирующий свою программу, видит только исходный текст программы и результирующую исходную программу. Очевидно, что цель разработчиков компиляторов – максимально сократить количество проходов. Это необходимо для увеличения скорости работы компилятора и уменьшения объема необходимой ему памяти. Идеал – однопроходный компилятор, получающий на вход исходную программу и сразу же генерирующий результирующую программу. Но сократить число проходов не всегда возможно. Качество проходов определяется, прежде всего, грамматикой и семантическими правилами исходного языка и чем больше вариантов предполагают семантические правила – тем больше проходов будет выполнять компилятор. Например, компиляторы с языка Pascal работают быстрее, чем компиляторы с языка С из-за того, что грамматика языка Pascal более проста, а семантические правила более жесткие. Однопроходные компиляторы – редкость, они возможны только для очень простых языков. Реальные компиляторы выполняют от двух до пяти проходов и являются многопроходными.
Например, трехпроходный компилятор работает так:
первый проход – лексический анализ, второй – синтаксический разбор и семантический анализ, третий – генерация и оптимизация кода.
Особенности построения интерпретаторов Интерпретатор – это программа, которая воспринимает входную
программу на исходном языке и выполняет ее.
Термин «Интерпретатор» как и «транслятор» означает «переводчик». Но с точки зрения формальных языков, отличаются они принципиально. Большинство интерпретаторов действует следующим образом:
Последовательно исполняют исходную программу по мере поступления ее на вход интерпретатора. При этом пользователю нет смысла ждать
завершения компиляции всей исходной программы. Исходя из этой особенности (исполнение команд по мере их поступления) в интерпретаторах отсутствует фаза оптимизации. А также на последнем этапе – этапе генерации кода – машинные команды не записываются в объектный файл, а выполняются.
В интерпретаторах отсутствует оптимизация из-за вида внутреннего представления программы. Кроме того, далеко не все языки программирования допускают построение интерпретаторов, которые выполняли бы исходные программы по мере поступления команд.
Последнее требование предусматривает существование компилятора, разбирающего исходную программу за один проход.
Основное требование интерпретаторов – обработка программы по мере поступления – нарушается, если язык допускает обращения к функциям и структурам данных раньше их непосредственного описания. По этой причине таким образом не могут интерпретироваться такие языки, как С и Паскаль.
Из-за отсутствия в интерпретаторах фазы оптимизации выполнение программы с помощью интерпретатора менее эффективно, чем с помощью аналогичного компилятора. В добавок, интерпретируемая программа должна разбираться каждый раз при выполнении, а при компиляции она разбирается единожды. Затем используется объектный код или файл. Поэтому интерпретаторы всегда уступают компиляторам в производительности.
Преимуществом интерпретаторов является независимость выполнения программы от архитектуры целевой вычислительной системы. При переходе на другую архитектуру в случае компилятора требуется откомпилировать программу заново, т.к. объектный код всегда ориентируется на определенную архитектуру.
Долгое время интерпретаторы были менее распространены, чем компиляторы, и существовали для относительно простых языков программирования (Basic). Профессиональные средства разработки ПО с высокими требованиями к производительности строились на базе компиляторов.
Такое положение существовало до момента широкого распространения глобальных вычислительных сетей. Как правило, такие сети представляют собой набор ЭВМ различной архитектуры. Из-за этого на первый план выходит требование единообразного выполнения на каждой ЭВМ сети исходной программы.
Литература
Основная:
1.Молчанов А.Ю. Системное программное обеспечение. Учебник для вузов. —
СПб.: Питер, 2003. — 396 с.
2.Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум.- СПб.: Питер, 2005.- 284 с.
3.Юров В.И. Assembler. Учебник для вузов. 2-е издание - СПб.: Питер.- 2004.-
637с.
4.Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование: Основы построения трансляторов + FD.- М.: КОРОНА принт.- 2004.- 255 с.
5.Фельдман Ф.К. Системное программирование на персональном компьютере.- 2004.- 512
6.Ахо А.,Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 768 с.
7.Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. — СПб.:
Питер, 2002. — 734 с.
8.Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002. — 544
Дополнительная:
1.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2001. – Ч. 1. – 96 с.
2.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2002. – Ч. 2. – 96 с.
3.Ф.Льюис, Д. Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. М., Мир, 1979.
4.Л. Бек. Введение в системное программирование. М.,Мир, 1988.
5.В.Е.Котов, В.К.Сабельфельд. Теория схем программ. -М.: Наука, 1978
6.Автоматное управление асинхронными процессами в ЭВМ и дискретных системах /Под ред. В.И.Варшавского. -М.:Наука.
7.Питерсон Дж. Теория сетей Петри и моделирование систем.- М.: Наука.
1984.
8.Минский М. Вычисления и автоматы. - М.: Мир.- 1971.
9.Котов В.Е. Сети Петри. - М.: Наука. - 1984.-
10.Ахо А.,Хопкрофт Дж., Ульман Дж.Построение и анализ вычислительных алгоритмов. - М.: Мир. -1979.
11.Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. –
М.: Мир, 1984. – 264 с.
Лекция 12 Современные компиляторы и интерпретаторы.
План
1.Компиляторы с языков высокого уровня. История развития компиляторов. 2.Компиляторы в составе систем программирования
1.Компиляторы с языков высокого уровня. История развития компиляторов.
Первые программы, которые создавались еще для ЭВМ первого поколения, писались непосредственно на языке машинных кодов. Это была поистине адская работа. Сразу стало ясно, что человек не должен и не может говорить на языке машинных команд, даже если он специалист по вычислительной технике. Однако все попытки научить компьютер говорить на языках людей успехом не увенчались и вряд ли когда-либо увенчаются (на что есть определенные объективные причины, рассмотренные в первой главе данной книги).
С тех пор все развитие программного обеспечения компьютеров неразрывно связано с возникновением и развитием компиляторов.
Первыми компиляторами были компиляторы с языков ассемблера, или, как они назывались, мнемокодов. Мнемокоды превратили «филькину грамоту» языка машинных команд в более-менее доступный пониманию специалиста язык мнемонических (преимущественно англоязычных) обозначений этих команд. Создавать программы уже стало значительно проще, но исполнять сам мнемокод (язык ассемблера) ни один компьютер не способен, соответственно возникла необходимость в создании компиляторов. Эти компиляторы элементарно просты, но они продолжают играть существенную роль в системах программирования по сей день. Более подробно о языке ассемблера и компиляторах с него рассказано далее в соответствующем разделе.
Следующим этапом стало создание языков программирования высокого уровня. Языки высокого уровня (к ним относится большинство языков программирования) представляют собой некоторое промежуточное звено между чисто формальными языками и языками естественного общения людей. От первых им досталась строгая формализация синтаксических структур предложений языка, от вторых — значительная часть словарного запаса, семантика основных конструкций и выражений (с элементами математических операций, пришедшими из алгебры).
Появление языков высокого уровня существенно упростило процесс программирования, хотя и не свело его до «уровня домохозяйки», как самонадеянно полагали некоторые авторы на заре рождения языков программирования. Сначала таких языков были единицы, затем десятки, сейчас, наверное, их насчитывается более сотни. Процессу этому не видно