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

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


1 чел. помогло.
Смотрите также:
Рабочая программа по курсу “Программирование на языках высокого уровня” Факультет экономический...
Основные разделы программы Программирование на языке высокого уровня Операционные системы...
Роль и значение языка паскаль в эволюции языков программирования...
Данное пособие поможет написать сочинения для школьников. Внем собраны лучшие сочинения...
Эти произведения автора не относятся к относительно совершенным в литературно духовном и т п...
Параллельные программы главный тормоз 11 2 mpi 11 3 Реализации mpi 12 4 Средства...
«Теория игр и исследование операций» Направления нк, нп 4 курс, 1-й семестр (2008/09 уч год)...
Программы Организации Объединенных Наций по окружающей среде комитет высокого уровня министров...
Рабочая программа по дисциплине Основы алгоритмизации и программирования (язык С/C++) Для...
Составление программы на языке программирования...
Литература [Абрамов89] Абрамов С. А., Зима Е. В...
Алгоритмизация и программирование. Языки программирования высокого уровня...



Загрузка...
страницы:   1   2   3   4   5   6   7   8
скачать


  1. Основные фазы компиляции. Лексический анализ.


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

Транслятор - это программа, которая переводит исходную программу в эквивалентную ей объектную программу.

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

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

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

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

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

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

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

Сканер

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

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




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

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


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

Синтаксис - способ соединения слов (и их форм) в словосочетания и предложения.

Семантика - это значения единиц языка.

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

Когда встречается инструкция присваивания вида
<переменная>:= <выражение>
семантическая программа проверяет переменную и выражение на соответствие типов и затем заносит инструкцию присваивания в программу во внутреннем представлении.

<Основная задача синтаксического анализа - разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)-анализ (и его вариант - рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) - при использовании систем автоматического построения синтаксических анализаторов.

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

< Назначение фазы семантического анализа.


Ясно, что текст программы, точно соответствующий грамматике и правильно разобранный на фазе синтаксического анализа, может содержать множество ошибок. Естественно эти ошибки нельзя описать в рамках грамматики, так как они являются контекстными. Например, с точки зрения грамматики фраза cos(sin((int*)("Argument"))); может быть и правильной, хотя она абсолютно бессмысленна.

Семантические ошибки в основном относятся к:

  • неправильным типам аргументов функций и операторов;

  • несуществующими переменными, метками, функциями;

  • несуществующими полями объектов, функций;

  • неправильно сформированными строками;

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

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

Области видимости и списки идентификаторов. Для большинства языков, например Си, допускается объявление переменных внутри вложенных блоков. При переопределении имени в таком случае доступ производится к имени, определённому в самом вложенном блоке. Применение специального квалификатора позволяет иметь доступ к глобальному имени, скрытому за объявленным в локальном блоке именем. К этим сложностям в стандарте Си 1999 года добавляются пространства имён (namespace). Таким образом, идентификаторы организованы внутри каждого блока в виде таблиц со ссылками на блоки верхнего уровня. Каждое пространство имён также имеет свою таблицу, их которых обычно активна лишб одна. Доступ к идентификаторам внутри таблиц обычно осуществляется с помощью метода хеширования. В случае обращений к объектам, структурам и массивам дополнительно проверяется семантическая информация, связанная с правильностью обращения к полям класса, методам класса, правильности использования индексации массивов.

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

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

if (i=2) вместо if (i==2)

*p = i || FLAG_BIT; вместо *p = i | FLAG_BIT;

Оптимизации программы.В ряде случаев на этапе семантического анализа можно сделать простейшие вычисления, например 4*1024 или же убрать из дальнейшего рассмотрения конструкции типа if (0). Зачем это делать, все равно на следующих этапах эти случаи будут оптимизированы? Компиляция даже маленькой программы компилятором, агрессивно выполняющем оптимизации, требует памяти порядка 300Кбайт, большие программы могут требовать порядка 10-20 Мбайт. Логика выполнения компилятора трудно предсказуема (предсказание переходов не работает примерно в 10% случаев), кеш-память, тоже в силу принципиальных особенностей обработки данных в компиляторе, не влияет на увеличение производительности так сильно, как в других программах. Так как сложность выполнения оптимизаций обычно пропорциональна квадрату или кубу от величины внутреннего представления программы, лучше явные случаи оптимизации делать на более ранних эпатах, чем в общем потоке.

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

>


4^ .Генерация код

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

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

Подготовка к генерации команд

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

Генерация команд

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

В интерпретаторе эта часть компилятора заменяется программой, которая фактически выполняет (или интерпретирует) внутреннее представление исходной программы. Причем само внутреннее представление в этом случае мало чем отличается от того, которое получается при компиляции.
Естественно, возникает вопрос: в чем заключаются главные трудности реализации компилятора? Сканер - весьма прост и хорошо изучен. Синтаксические анализаторы, если речь идет о простых формальных языках, также довольно хорошо изучены. В действительности эту часть можно в значительной степени автоматизировать. (С тех пор, как синтаксис был формализован, большинство исследований по созданию компиляторов касалось именно синтаксиса, а не семантики.) Наиболее трудными и запутанными частями компилятора являются семантический анализ, программы подготовки генерации и программы генерации команд. Эти три части взаимозависимы, должны в значительной степени разрабатываться совместно и могут коренным образом измениться при переходе с одного объектного языка на другой или с одной машины на другую.

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

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

Язык программирования можно задать:

  • перечислив все цепочки символов;

  • написав программу-распознаватель, которая получает на вход цепочку символов и выдает ответ "да", если цепочка принадлежит языку и "нет" в противном случае;

  • с помощью механизма порождения - грамматики.

Чтобы задать грамматику, требуется указать:

  • множество символов алфавита (или терминальных символов)

  • множество нетерминальных символов (или метасимволов), не пересекающееся с терминальными символами

  • множество правил вывода, определяющих правила подстановки для цепочек

На практике применяется также другая форма записи, традиционно называемая нормальными формами Бэкуса-Наура (НФБН). Терминалы в НФБН записываются как обычные символы алфавита, а нетерминалы - как имена в угловых скобках <>.

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

<число> : <цифра> | <цифра> <число>
<цифра> : 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Рассмотрим язык простейших арифметических формул:

<формула> : (<формула>) | <число> | <формула><знак><формула>
<знак> : + | *

Почему "3+5*2" является формулой? Приведем последовательность
преобразований цепочек (так называемый "разбор" или "вывод"):



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



Изобразим выполняемые замены цепочек в виде т.н. "дерева разбора" (или дерева вывода).

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

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

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

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


^ 5. Операционная система: определение, структура, основные функции.

Операцио́нная систе́ма, ОС (англ. operating system) — базовый комплекс компьютерных программ, обеспечивающий интерфейс с пользователем, управление аппаратными средствами компьютера, работу с файлами, ввод и вывод данных, а также выполнение прикладных программ и утилит.

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

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

В pаботе Barron D операционная система определяется так:``Я не знаю, что это такое, но всегда узнаю ее, если увижу''.Эта фраза была сказана в первой половине 70-х, когда операционные системыдействительно отличались большим разнообразием структуры и выполняемыхфункций.

С тех времен положение существенно изменилось.Современные ОС - по крайней мере, широко распространенные системы -во многом похожи друг на друга.Прежде всего это определяется требованием переносимости программногообеспечения. Именно для обеспечения этой переносимости был принятPOSIX (Portable OS Interface based on uniX) - стандарт,определяющий минимальные функции по управлению файлами, межпроцессномувзаимодействию и т.д., которые должна уметь выполнять система.

Кроме того, за четыре с лишним десятилетия, прошедших с моментаразработки первых ОС, сообщество программистов достигло определенногопонимания того, что:

  • при разработке ОС возникает много стандартных проблем и вопросов;

  • для большинства из этих проблем и вопросов существует наборстандартных решений;

  • некоторые из этих решений намного лучше, чем все альтернативные.


*Многие из таких наилучших решений были реализованы в операционныхсистемах семейства Unix. Поэтому среди адептов этой ОС ходитпоговорка: ``Если вы не понимаете UNIX, вы должны будетезаново изобрести его''. Опыт систем OS/2 и Windows NTотчасти подтверждает ее.
*


По современным представлениям, ОС должна уметь делать следующее:

  • Обеспечивать загрузку пользовательских программ в оперативную памятьи их исполнение.

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

  • Предоставлять более или менее стандартный доступ к различнымустройствам ввода/вывода, таким как терминалы, модемы, печатающие устройства.

  • Предоставлять некоторый пользовательский интерфейс. Слово некоторыйздесь сказано не случайно - часть систем ограничивается командной строкой,в то время как другие на 90% состоят из средств интерфейса пользователя.




оставить комментарий
страница1/8
Дата02.10.2011
Размер0.79 Mb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4   5   6   7   8
хорошо
  1
отлично
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх