Основной блок компилятора


Содержание

Основной блок компилятора

Содержание раздела PASCAL

Введение. Общая характеристика языка. 1 Основы языка PASCAL 2. Структура программы 2.1 Раздел объявлений и соглашений, основной блок 2.2 Типы переменных 3 Операторы языка PASCAL 4 Простые и структурные типы данных 5 Процедуры и функции 6 Динамическая память 7 Модули 8 Ключи и директивы компилятора 9 Файлы 10 Другие возможности Турбо-Паскаля 1 0 .1 Оверлей 10. 2 Прямое обращение к памяти и портам 11 Турбо-Паскаль 6.0 и структурное программирование 12 ТурбоПаскаль и ООП 13 Объектно-ориентированная библиотека Turbo Vision 14 Встроенная справочная система

Раздел объявлений и соглашений

В этом разделе программы компилятору можно дать указания, определяющие режимы его работы при трансляции последующей программы. Эти указания оформляются в тексте программы как комментарии, начинающиеся парой символов “<$” и заканчивающиеся символом “>”. Такие указания могут содержать указания на включение в текст программы фрагментов других программ (из соответствующих файлов), информацию для отладчика или сведения о необходимости использования арифметического сопроцессора.

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

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

Например: USES Crt, Graph, String, Overlay;

Следом за строкой, содержащей оператор USES, идут строки объявляющие:

метки (LABEL) (хотя их использование противоречит классической технике программирования на Паскале, дающей превосходную стройность и однозначность понимания кода программы);

определенные пользователем типы данных (TYPE);

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

В разделе описания меток LABEL содержатся перечисленные через запятую имена меток переходов. Следует помнить, что имена меток переходов не должны дублировать друг друга. Имя метки перехода может представлять собой целое число (от 0 до 9999), строку символов или символьно-цифровую конструкцию.

Например: LABEL, 1, 5, 9999, h2, 4t32e, metka_l;

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

CONST
Year=1995;
Month=’Июль’;
Day=’Понедельник’;

Примечание: Заметьте, что при присвоении значений константам вместо оператора присвоения “:=” используется просто знак равенства “=”. Тип константы определяется автоматически по виду значения, присваемового константе и не может быть сложным.

Раздел описания типов TYPE позволяет программисту определить новый тип в программе. В данном разделе могут быть использованы ранее определенные в разделе CONST константы.

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

Примечание: Разделы LABEL, CONST, TYPE и VAR могут располагаться в произвольном месте программы. При этом каждый из этих разделов может встречаться в программе несколько раз или вообще не встречаться в ней.

Непосредственно за заголовком программы следует основной блок программы, ограниченный операторами BEGIN и END.. Как уже говорилось, оператор END. указывает компилятору, что программа закончена, в отличие от операторов END;, которые завершают блоки, процедуры, модули и т.п.
Текст, следующий за оператором END., игнорируется транслятором.

Объем основного блока программы, написанной нами, невелик:
writeLn (‘ привет. Ваня !’ );
writeLn;
Wlitelin(‘ Я надеюсь, что мы отлично’);
WrlteLn (‘ сработаемся !’);

Оператор WriteLn (Write Line — записать строку) — представляет собой стандартную процедуру, с помощью которой можно вывести на экран или на другие носители и средства отображения информации текст и числа. Подробное истолкование применения этой процедуры в первом операторе программы может быть, например, таким: «Вывести ( Write ) строку символов (String) «Привет, Ваня!» на экран и перевести курсор на начало следующей строки (Line) экрана». Перевод курсора на начало следующей строки вызван окончанием Ln в имени процедуры. Существует также стандартная процедура Write для вывода информации на экран без перевода курсора. После выполнения оператора WriteLn последующий вывод приведет к выдаче информации в следующую строку экрана, а после оператора Write — в ту же строку, следом за уже выведенным текстом, пока хватит места, а затем вывод продолжится уже на следующей строке экрана. Оператор WriteLn; без параметров просто переведет курсор на начало следующей строки. Операторы WriteLn и Write присутствуют практически в каждой Паскаль-программе. Скобки, следующие за оператором, необходимы для задания параметров процедуры. Причем, компилятор не рассматривает слова «Привет» и «Ваня» как идентификаторы для каких-либо переменных, т.к. они стоят внутри фрагмента текста, ограниченного апострофами. Заканчивается этот оператор, как и любой другой, точкой с запятой.

Еще одна характерная особенность Паскаль-программ — ступенчатая форма записи. Строки, относящиеся к одной конструкции или связанные по смыслу, записываются с одной и той же позиции. Строки, относящиеся к подчиненной конструкции, записываются правее («глубже»), например, на две позиции, благодаря чему наглядно представляется структура программы. В длинных программах этот подход позволяет фиксировать соответствие пар операторов BEGIN — END. Редактор текста в ИПО поддерживает такую технологию оформления текстов программ: после нажатия клавиши [Enter] курсор переходит на следующую строку в ту позицию, с которой начинается текст в предыдущей, а клавиша [Backsрасе] из этого положения переводит курсор на конец предыдущей строки.

Примечание: Ступенчатое оформление программы преследует только «эстетические» цели и не влияет на эффективность работы компилятора или программы. Компилятор обрабатывает Паскаль-программы с любым расположением операторов: как разделенные построчно нажатием клавиши [Enter] при подготовке текста программы, так и записанные подряд в одну строку.

Например:
program hello; begin writeln(‘Привет, Ваня!’); writeln;
writeln(‘Я надеюсь, что мы отлично’); writeln (‘
сработаемся!’); end.

Однако «воспитанные» программисты не могут себе позволить оформлять программы подобным образом, ведь таже программа, записанная с табуляцией, читается гараздо легче:
program hello;
<заголовок программы>
begin
<начало сегмента команд программы>
writeln(‘Привет, Ваня!’);
<вывод строки>
writeln;
<перевод позиции курсора на строку ниже>
writeln(‘Я надеюсь, что мы отлично’);
<вывод строки>
writeln(‘сработаемся!’);
<вывод строки>
end.

Вернемся еще раз к символу точка с запятой, завершающему каждый оператор. Наличие точки с запятой обязательно, т.к. этот символ показывает Паскаль-компилятору, где заканчивается один оператор и начинается следующий. Благодаря тому, что Паскаль — язык со «свободной формой записи», можно без опасений «растянуть» оператор на несколько строк. С помощью символа точка с запятой Вы сообщаете Паскаль-компилятору, какую часть текста программы следует рассматривать как цельный, неделимый фрагмент. Зарезервированное слово BEGIN, с которого начинаются блоки программы, не требует после себя символа точка с запятой.

Diplom Consult.ru

Ответы к экзамену по программированию 1 семестр.

Главные блоки компьютера и их назначение.

Компьютер имеет следующие основные блоки: Системный блок.Монитор.Клавиатура.Манипуляторы.

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

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

Назначение программы-компилятора

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

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

Назначение программы-интерпретатора

Интерпрета́тор (языка программирования) —Программа или техническое средство, выполняющее интерпретацию. Вид транслятора, осуществляющего пооператорную (покомандную) обработку и выполнение исходной программы или запроса (в отличие от компилятора, транслирующего всю программу без её выполнения).

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

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

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

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

Основные идеи методики «структурное программирование»

Структу́рное программи́рование — методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX века Э. Дейкстрой, разработана и дополнена Н. Виртом В соответствии с данной методологией

Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:

последовательное исполнение — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;

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

цикл — многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие (условие продолжения цикла).

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

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

Разработка программы ведётся пошагово, методом «сверху вниз».

Блочное программирование для новичков

Это оказалось действительно просто и понятно для детей. Scratch, первопроходца в данной области, быстро внедрили во многих американских школах сразу после официального запуска в 2007. Однако популярность превзошла самые смелые ожидания — вузы стали вводить целые курсы для базового обучения программированию студентов, а многие IT-гиганты взялись за производство адаптаций. В итоге простой программный конструктор для самых маленьких превратился в феномен.

Исследование, проведенное сразу в 4 американских вузах (MIT CSAIL, University of Alabama, Washington University и Wellesley College) выявило сразу 3 причины этого:

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

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

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

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

При этом не стоит впадать в эйфорию и считать, что с помощью блочного программирования реально создать что-то сложное. Формально это возможно, но для профессиональной разработки есть ограничения:

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

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

Снижение эффективности. Ограниченный синтаксис блочного программирования «свяжет вам руки» в желании выйти за рамки стандартных задач. Увеличивать синтаксис при этом смысла мало — в этом случае теряются все прелести блочного подхода.

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

Чтобы упростить обучение программированию, педагоги и разработчики создавали особые языки исключительно для получения базовых представлений (Pascal, Basic), потом взялись за визуализацию текста (Logo, Squeak Etoys). Последнее веяние — блочное программирование. Это своего рода детский конструктор из цветных деталей, каждая из которых имеет свое имя. Правильно собранный конструктор приводит к появлению настоящего рабочего кода.

Это оказалось действительно просто и понятно для детей. Scratch, первопроходца в данной области, быстро внедрили во многих американских школах сразу после официального запуска в 2007. Однако популярность превзошла самые смелые ожидания — вузы стали вводить целые курсы для базового обучения программированию студентов, а многие IT-гиганты взялись за производство адаптаций. В итоге простой программный конструктор для самых маленьких превратился в феномен.

Исследование, проведенное сразу в 4 американских вузах (MIT CSAIL, University of Alabama, Washington University и Wellesley College) выявило сразу 3 причины этого:

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

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

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

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

При этом не стоит впадать в эйфорию и считать, что с помощью блочного программирования реально создать что-то сложное. Формально это возможно, но для профессиональной разработки есть ограничения:

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

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

Снижение эффективности. Ограниченный синтаксис блочного программирования «свяжет вам руки» в желании выйти за рамки стандартных задач. Увеличивать синтаксис при этом смысла мало — в этом случае теряются все прелести блочного подхода.

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

Основные блоки в блок-схемах.

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

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

Основные блоки в блок-схемах:

(5)Цикл(ромб с кругом); 6)Подпрограмма(прямоугольник, по бокам отступы))


• Основные компоненты системы программирования: язык программирования, транслятор, компилятор. Характеристика языков высокого и низкого уровней. Примеры.

Язык программи́рования — формальный язык, предназначенный для записи компьютерных программ.

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

Транслятор — это программа-переводчик. Она преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд. Трансляторы делятся на две группы по их работе – компиляторы и интерпретаторы.

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

Базовая единица действия в любом ЯП- оператор

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

ЯП делятся на: языки высокого и низкого уровня.

ЯНУ являются машинно зависимыми языками, потому что содержат в том или ином виде операторы определенные для конкретного ЦП или для определенной архитектуры.

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

Языки низкого уровня — это машинный язык, язык Ассемблера.

Машинный язык состоит из двух символов — 0 и 1 (программа строится в двоичной системе счисления).

А вот языки высокого уровня ориентированы на человека (на пользователя ПК). Это такие языки программирования: Бейсик, Паскаль, Турбо Паскаль, С++ и другие.


• Оператор. Операнд. Общая характеристика и классификация данных. Элемент данных. Константы и переменные. Примеры. Идентификатор. Правило именования идентификатора. Примеры.

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

Операнд — это аргумент операции,это значение, переменная или выражение, которое расположено слева или справа от оператора(Для понимания 1 + 2 Здесь 1 и 2 — это операнды, а знак ПЛЮС (+) — это оператор. )

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

Классификация типов данных

Знаковые/беззнаковые( целые или вещественные)

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

Константа- это элемент данных, сохраняющий значение заданное программистом при её описании неизменным до конца выполнения программы, в которой она определена) [const m = -50;]

Переменная- это элемент данных, значение которого может быть изменено в процессе программы( причём, пока программа не начала работать, переменная не определена)[int a, b, c;]

Идентификатор- это имя какого-либо элемента программы( а не только элемента данных!), заданное программистом при его описании, в соответствии с правилом определения имён для данного языка программирования.

Правило определения идентификатора:

1) Первый символ- символ латинского алфавита

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

3) Длинна не может превышать 30 символов


• Понятие типа данных. Именные и типизированные константы. Примеры. Базовые структуры: массивы, записи (структуры). Преимущества использования массивов. Использование констант при описании массивов.

Тип данных — множество значений, которые может принимать эта переменная.

Именные константы — это константа, тип которой определяется по значению( У=23, Е=х), типизированные константы- это константы, которые программист задает сам(float, int).

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

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

Преимущества использования массивов:

Удобный способ хранения нескольких элементов под одним именем,Быстрота изменения элементов,Легкость в использовании .

Имя массива является константным указателем. Именно поэтому и невозможно копирование массивов с помощью простого оператора присвоения. Константный указатель «охраняет» область памяти, выделенную для размещения данного массива. При этом значения элементов массива можно изменять в ходе выполнения программы. Защитить их от изменения можно с помощью дополнительного спецификатора типа const. При этом массив должен быть проинициализирован непосредственно в момент определения:


• Понятие типа данных. Основные типы данных языка С: описание, размер, примеры использования.

Тип данных — множество значений, которые может принимать эта переменная.

Логический тип- состоит всего из двух значений : False (ложно) и True (истинно). Эти слова определены в языке и являются, по сути, логическими константами. Минимальный размер для bool- 8 бит

char- символьный тип(1 байт)(0. 255)

int — целый тип(4 байта)(зависит от системы, обычно около -32к. 32к)(int a=10)

float- вещественный тип одинарной точности(4 байта)(float b=1.5)

double, real- обозначают множества вущественных чисел в различных диапазонах(8 байт)(double b = 0.00105)
• Массивы. Принципы организации массивов. Одномерные и двумерные массивы. Физическая организация массивов в памяти ЭВМ. Примеры описания и использования на языке С.

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

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

Двумерный массив-это своеобразная матрица, состоящая из Н-ого количества строк и М-ого количества столбцов.

Принципы организации массивов(основные характеристики при определении массива)?:

2. тип элемента (массива)

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

4. количество элементов или длинна массива

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

Одномерный массив (пример описания и пример использования):

Объявление массива- int array1 [10];

Пример использования- for (int i=0; i >

вывод printf cout y) && (x>z))

Дизьюнкция или or в Си.

Пример применения: if ((x>y) || (x>z))

Исключающее ИЛИ или xor в Си.

Пример применения: if ((x>y) ^(x>z))


• Оператор выбора. Синтаксис, принцип и особенности функционирования, примеры использования. Эквивалентное представление оператора выбора с помощью ветвления.

Оператор выбора языка Си –switch

В круглых скобках после оператора выбора языка Си switch находится переменная типа int или char (не строковая), следом расположен блок, заключенный в фигурные скобки; в блоке содержатся ветви условий case. Каждая ветвь case выполняет конкретные инструкции, если значение переменной совпадает с указанным. Если это значение является символом, то символ заключается в одинарные кавычки.

Эквивалентное представление оператора выбора с помощью ветвления.


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

Циклы— многократно повторяемые участки вычислений, при соблюдении заданных условий; а сами повторяемые участки- тело цикла.

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


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

В языке Си следующие виды циклов:

while — цикл с предусловием;

do. while — цикл с постусловием;

Цикл с предусловием while:

Общая форма записи:

Если Условие выполняется (выражение, проверяющее Условие, не равно нулю), то выполняется Блок Операций, заключенный в фигурные скобки, затем Условие проверяется снова.

Последовательность действий, состоящая из проверки Условия и выполнения Блока Операций, повторяется до тех пор, пока выражение, проверяющее Условие, не станет ложным (равным нулю). При этом происходит выход из цикла, и производится выполнение операции, стоящей после оператора цикла.

(Посчитать сумму чисел от 1 до введенного k)

#define _CRT_SECURE_NO_WARNINGS // для возможности использования scanf

int k; // объявляем целую переменную key

int sum = 0; // начальное значение суммы равно 0

scanf(«%d», &k); // вводим знчение переменной k

#include // для использования функции system()

int num; // объявляем целую переменную для числа

system(«chcp 1251»); // переходим на русский язык в консоли

system(«cls»); // очищаем экран

printf(«Введите число от 0 до 10: «); // приглашение пользователю

scanf(«%d», &num); // ввод числа

> while ((num 10)); // повторяем цикл пока num 10

printf(«Вы ввели число %d», num); // выводим введенное значение num — от 0 до 10


• Цикл со счетчиком. Реализация цикла со счетчиком с использованием операторов цикла с пред и постусловием.

В большинстве процедурных языков программирования реализуется оператором for, в котором указывается счётчик (так называемая «переменная цикла»), требуемое количество проходов (или граничное значение счётчика) и, возможно, шаг, с которым изменяется счётчик. Например, в языке Оберон-2 такой цикл имеет вид:

FOR v := b TO e BY s DO

здесь v — счётчик, b — начальное значение счётчика, e — граничное значение счётчика, s — шаг).

Цикл с предусловием

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

Илон Маск рекомендует:  mix-blend-mode в CSS

Цикл с постусловием

Цикл с постусловием — цикл, в котором условие проверяется после выполнения тела цикла. Отсюда следует, что тело всегда выполняется хотя бы один раз. В языке Паскаль этот цикл реализует оператор repeat..until; в Си — do…while.

На языке Pascal цикл с постусловием имеет следующий вид::


• Простые и вложенные циклы: особенность организации, примеры на языке С. Досрочное завершение цикла.

Если мы знаем точное количество действий (итераций) цикла, то можем использовать цикл for. Синтаксис его выглядит примерно так:

for (действие до начала цикла;

условие продолжения цикла;

действия в конце каждой итерации цикла) <

инструкция цикла 2;

инструкция цикла N;

Итерацией цикла называется один проход этого цикла

Существует частный случай этой записи, который мы сегодня и разберем:

for (счетчик = значение; счетчик

using namespace std;

int i; // счетчик цикла

int sum = 0; // сумма чисел от 1 до 1000.

using namespace std;

int i = 0; // инициализируем счетчик цикла.

int sum = 0; // инициализируем счетчик суммы.

using namespace std;

int i = 0; // инициализируем счетчик цикла.

int sum = 0; // инициализируем счетчик суммы.

do <// выполняем цикл.

> while (i 2 then x:=10; <При y>2 цикл нужно завершить>

Однако, во избежание трудноуловимых ошибок, управляющую переменную не принято менять иначе, чем для выполнения шага цикла. Например, после оператора if y>2 then x:=10; в нашем листинге выполнение текущего шага продолжится, что чревато лишними или неправильными вычислениями. Кроме того, текст такой программы воспринимается нелегко.

Поэтому для досрочного выхода из цикла существует оператор break (от англ. «to break» — прервать), немедленно прекращающий его выполнение:

while x 2 then break; <При y>2 цикл нужно завершить>

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

Для немедленного продолжения цикла со следующего шага используется оператор continue (от англ. «to continue» – продолжить):

writeln (‘Введите положительное число:’);

if n 100) printf («greater»);

for (ch=getchar(); isdigit(ch); ) . ;

Тем не менее функция не может стоять с левой стороны оператора присваивания. Оператор типа

swap (х, у) = 100; /* некорректный оператор */

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

Если функция объявляется как void, она не может использоваться в выражениях. Например, предположим, что f() объявлена как void. Следующие операторы не будут компилироваться:

t = f(); /* нет значения для присваивания t */

f() + f(); /* нет значений для сложения */

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


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

Передача параметров по значению

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

procedure Test(s: string);

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

procedure ChangeMe(var x: longint);

x := 2; // Параметр х изменен вызванной процедурой

Вместо создания копии переменной x, ключевое слово var требует передачи адреса самой переменной x, что позволяет процедуре непосредственно изменять ее значение.


• Массивы как параметры процедур (функций). Примеры организации передачи параметров в виде массива на языке С.

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

тип_функции имя_функции ( тип_массива имя_массива [ n ] )

n – количество элементов в массиве

Вызов функции: имя_функции (имя_массива);

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

Пример: Написать функцию нахождения минимума в одномерном массиве.

Внутреннее устройство и оптимизации компилятора GCC

Взаимодействие компонентов toolchain-а

Компоненты проекта GCC

  • Собственно компиляторы нескольких языков
  • Стандартные библиотеки этих языков
  • Вспомогательные низкоуровневые библиотеки
  • Библиотеки для взаимодействия с компоновщиком и отладчиком
  • Инструменты для анализа покрытия кода
  • Программа-драйвер

Драйвер

g++ hello.cc get_name.cc ‑o hello

На заметку: полезные возможности драйвера

  • Выполнить компиляцию, вывести список исполненных команд:

Компилятор GCC и его архитектура

Задачи компилятора

  • Трансляция кода из ЯВУ в язык ассемблера
  • Валидация программы, вывод сообщений об ошибках
  • Статический анализ, вывод предупреждений
  • Оптимизация
  • Инструментальная обработка программы (профилирование, динамические проверки)
  • Генерация отладочной информации
  • Взаимодействие со сторонними программами (система сборки, отладчик, IDE)

Перенастраиваемость

Структура сферического компилятора в вакууме

Front end, промежуточное представление

Задачи фронтэнда

  • Разбор программы, семантический анализ
  • Валидация и выдача сообщений об ошибках
  • Выдача предупреждений
  • Трансляция в промежуточное представление, в т.ч.:
    • Генерация служебного кода
    • Упрощение конструкций языка
    • Сохранение отладочной информации

    Разбор, семантический анализ

    Подробнее про разбор и семантический анализ

    Классика: «Книга Дракона»

    Трансляция

    Если в программе не выявлено ошибок, начинается процесс её перевода в промежуточное представление, которое:

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

    Упрощение конструкций языка

    На примере языка C++:

    Пример: методы классов

    Пример: составные выражения

    Области видимости

    Вложенные блоки

    Циклы

    SSA: Static Single Assignment

    SSA: Static Single Assignment

    SSA: Static Single Assignment

    Характеристики промежуточного представления

    • Код функции представлен в виде графа потока управления
    • Вершины графа (базовые блоки) состоят из линейных списков инструкций
    • Все вычисления представлены в виде трёхадресного кода
    • Скалярные переменные переведены в SSA-форму
    • Типы данных и операции согласуются с наборами инструкций современных процессоров

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

    • Граф потока управления в формате dot:

    Оптимизации компилятора

    Понятие оптимизации

    Оптимизация, выполняемая компилятором — улучшение (в отличие от понятия оптимизации в математике).

    Изначальные источники не оптимальности:

    • Код, генерируемый макросами или другими программами
    • Выбор, сделанный в пользу читаемости, лёгкости поддержки и скорости разработки
    • Ограничения языка

    Конвейер оптимизатора

    • Разные проходы используют (по возможности) общее промежуточное представление
    • Конкретный набор проходов зависит от настроек и целевой архитектуры
    • Всего проходов около 250

    Общие принципы и подходы

    • Поиск инвариантов и упрощение кода на их основе
    • Удаление избыточных операций
    • Перемещение кода для избегания избыточных вычислений
    • Дублирование и специализация кода
    • Использование знаний об архитектуре процессора для генерации более оптимального кода
    • Эвристики: оптимизация более вероятного случая за счёт пессимизации менее вероятного

    Классификация оптимизаций

    По охватываемой области:

    • Локальные (базовый блок)
    • Глобальные (функция)
    • Межпроцедурные (модуль или программа)

    Отдельно можно выделить машинно-зависимые оптимизации, оптимизации циклов и др.

    Примеры локальных оптимизаций

    • Свёртка полностью константных выражений
    • Упрощения, основанные на алгебраических тождествах, например:
      • x + 0x
      • 1 && yy
      • x - x
    • Оптимизации последовательностей инструкций процессора по шаблону

    DSL для описания тождеств

    Глобальные оптимизации

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

    • Распространение констант и копий
    • Устранение мёртвого кода
    • Устранение избыточных вычислений
    • Устранение общих подвыражений
    • Перемещение кода

    Пример: распространение диапазонов значений

    Пример: распространение диапазонов значений

    Пример: распространение диапазонов значений

    Оптимизация циклов

    Состоит из несколько фаз (проходов). Анализ циклов включает в себя:

    • Нахождение переменной индукции
    • Оценку количества итераций цикла
    • Анализ зависимости данных

    Полученные данные позволяют выполнять преобразования циклов, которые:

    Пример: размыкание цикла

    Пример: размыкание цикла

    Пример: размыкание цикла

    Межпроцедурные оптимизации

    Распространяют по графу вызовов информацию:

    • Константность и диапазоны значений параметров
    • (не)использование параметров в функции
    • Выравнивание указателей
    • Динамические типы объектов

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

    Встраивание

    Встраивание: польза в простейшем случае

    Встраивание и C++

    Эвристики встраивания

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

    1. Ранний этап: граф вызовов обходится в топологическом порядке, основной критерий — размер вызываемой функции.
    2. Поздний этап: для каждого вызова (ребра в графе) рассчитывается сложная метрика, которая моделирует пользу от встраивания вызова. Используется очередь с приоритетами.

    Back end и машинно-зависимые оптимизации

    Пример: выбор инструкции для 8-битного деления

    Попробуем скомпилировать программу:

    Описание архитектуры процессора содержит таблицы поддерживаемых стандартных операций. Компилятор попытается найти в них что-нибудь подходящее, например:

    • umod
    • udivmod
    • udiv и вычислить по формуле a - (a/b)
    • то же самое, но для типов большей разрядности

    В итоге (на x86) удастся найти шаблон udivmod для uint8_t

    Выбранный шаблон и реальная инструкция

    Описание инструкции деления в компиляторе

    И так для каждой инструкции.

    Примеры машинно-зависимых оптимизаций

    • Переупорядочение базовых блоков
    • Выделение регистров
    • Планирование инструкций

    Переупорядочение базовых блоков

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

    • показать ключи, отвечающие за оптимизацию и их состояния:
      gcc -O3 -Q —help=optimizers test.c
    • показать список активных проходов с оптимизацией -O2:
      gcc -fdump-passes -O2 file.c
    • вывести промежуточное представление после каждого прохода в отдельный файл файл:
      gcc ‑fdump‑tree‑all ‑fdump‑ipa‑all ‑fdump‑rtl‑all -O2 file.c

    Практическая применимость

    The real problem is that programmers have spent far too much time worrying about efficiency in the wrong place and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

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

    Чем может помочь программисту знание устройства компилятора

    • Не усложнять код ручной оптимизацией без необходимости
    • Уметь оптимизировать критичные участки кода (в том числе, используя возможности компилятора)

    Разработчики GCC и пользователи

    Корпоративные разработчики GCC

    Корпоративные разработчики GCC

    Поддержкой back-end компонентов обычно занимаются разработчики железа:

    Языки Go и Ada также поддерживаются крупными компаниями:

    Сообщество разработчиков GCC

    • Списки рассылки (gcc-help)
    • Баг-трекер
    • GCC Wiki
    • Тэг на Stack Overflow

    Тестирование GCC — взаимовыгодное сотрудничество

    Попробуйте использовать для сборки вашего кода еженедельные снэпшоты GCC (и прогонять unit-тесты).

    Взамен за потраченные усилия вы:

    • раньше получите доступ к новым предупреждениям компилятора
    • сможете указать на ошибку, которая проявляется именно на вашем коде (и рассчитывать на её исправление до релиза)
    • отслеживать регрессии в производительности генерируемого кода

    Новым процессорам — новые компиляторы

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

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

    Начиная с середины прошлого десятилетия ведущие производители микроэлектроники (Intel, AMD, Nvidia, IBM, Tilera и др.) наладили выпуск многоядерных процессоров — параллельные вычисления стали массовыми. Предлагаемые рынку архитектуры отличаются не только количеством ядер, но и способом их соединений, видами параллельных вычислений (SIMD, MIMD, pipeline), организацией используемой памяти и т. п., причем как только на рынок выходит новый высокопроизводительный процессор или ускоритель, тут же появляется соблазн объединить несколько таких устройств и получить еще большую производительность. И вот здесь возникает проблема разработки программного обеспечения, использующего весь потенциал вычислительной системы [1]. Разработка такого ПО требует много ресурсов (программистов высокой квалификации, времени, средств), а планы по переносу прикладных программ на новую систему обычно обречены на провал — перенос программ между архитектурами обычно возможен только в рамках семейств схожих архитектур.

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

    Оптимизирующие компиляторы

    Распараллеливающий компилятор — частный случай оптимизирующего, который условно можно разделить на блок синтаксического разбора текста, блок оптимизации и генератор кода. До наступления эпохи массового параллелизма проблему разработки эффективных программ решали семейства оптимизирующих компиляторов: GCC, LLVM, Intel С++/Fortran Compiler, Microsoft Visual Studio. В основе каждого семейства компиляторов лежит его внутреннее («промежуточное») представление, и при появлении нового процессора в этих семействах разрабатывался генератор кода из внутреннего представления к архитектуре нового процессора. Для нового процедурного языка программирования создавалась процедура синтаксического разбора с этого языка во внутреннее представление. И в одном и в другом случае иногда приходилось расширять блок оптимизации.

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

    Автоматизировать, а значит, ускорить, удешевить и повысить надежность разработки компиляторов стремятся десятилетиями. Автоматизация основана на формальном описании входа и выхода компилятора — например, средствами формы Бэкуса-Наура, на основе которых построены известные «генераторы компиляторов» YACC, BIZON, ANTLER, GoldParser, на самом деле являющиеся генераторами парсеров.

    Имеется много компилирующих систем (C-to-Verilog, Catapult C, Impulse CoDeveloper, MathLab и др.), генерирующих код HDL (Hardware Description Language) и ориентированных на автоматизацию проектирования электронных схем. В перспективе такие системы могут быть использованы при разработке компиляторов для вычислительных систем с программируемыми процессорами или ускорителями на ПЛИС. Кроме этого есть еще компилирующие системы для одновременного проектирования вычислительной системы и программ к ней, но они ориентированы на создание встроенных систем.

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

    Все перечисленные семейства компиляторов имеют генераторы параллельного кода OpenMP для работы на системах с общей памятью (многоядерные или SMP-архитектуры), однако само по себе распараллеливание не самоцель.

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

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

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

    Память против параллельности

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

    Можно выделить несколько типов алгоритмов:

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

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

    Работа компиляторов с памятью

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

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

    Когда время доступа к данным превысило время их обработки, в процессорах появилась кэш-память, более быстрая, чем оперативная. Данные из оперативной памяти в кэш передаются рядом лежащими группами — «кэш-линейками». Актуальными здесь стали задачи такого распределения данных в оперативной памяти, чтобы в подгружаемых кэш-линейках было мало лишних данных. Важным фактором оптимизации работы с памятью является выравнивание массивов (размещение в памяти, начиная с адреса, кратного определенному числу) — при обращении к элементам выравненного массива (в случае, когда адрес массива кратен размеру кэш-линейки) происходит меньше кэш-промахов. Также на некоторых типах процессоров векторные команды работают только с выравненными массивами (когда адрес массива кратен размеру векторного регистра). Автоматическое выравнивание данных реализовано во всех компиляторах, поддерживающих автоматическую векторизацию (GCC, Intel, LLVM, MSVC 2012). В некоторых компиляторах семейства PGI реализованы операции копирования массивов (copyin) на графический ускоритель и выгрузка результатов с ускорителя в оперативную память (copy).

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

    Распределение массивов в оперативной памяти

    Практически все современные компьютеры имеют аппаратную поддержку виртуальной и кэш-памяти. Трансляция адреса виртуальной памяти в адрес физической может занять значительное время (10–100 тактов), поэтому, чтобы каждый раз не высчитывать физические адреса к одним и тем же виртуальным страницам, некоторые современные процессоры, поддерживающие страничную организацию памяти, включают в себя отдельный кэш (буфер ассоциативной трансляции TLB). Если данные, к которым происходит обращение, находятся в разных виртуальных страницах, то это приводит к большому количеству промахов к TLB-кэшу и, как следствие, простаиванию процессора. Кэш данных предназначен для уменьшения времени обработки запросов к часто используемым данным. Перед тем как данные попадают в процессор, они сохраняются в кэше. Таким образом, повторное обращение к ним не требует участия оперативной памяти.

    Считывание данных из оперативной памяти в кэш происходит линейками длинной 32 или 64 байта, что, как правило, превышает длину используемых в программе данных, поэтому вместе с каждым считываемым куском данных в кэш-память попадают и соседние данные. Таким образом, для уменьшения обращений к памяти желательно, чтобы данные, которые используются соседними по времени исполнения операциями, размещались в оперативной памяти по соседству. Одним из способов увеличения производительности является выбор правильного метода хранения данных, но матрицы (массивы) в оперативной памяти распределяются компилятором, как и 50 лет назад, по столбцам (Фортран) либо по строкам (Си, Паскаль), независимо от исполняемого кода, что не всегда приводит к эффективному использованию кэш-памяти. В некоторых случаях логично использовать размещение массивов по блокам, которое в некоторых блочных алгоритмах может дать ускорение до 40%. Следует подчеркнуть, что блочное размещение массивов уместно только для блочных алгоритмов. Хранение матриц по блокам дает преимущество при реализации численных методов линейной алгебры и математической физики, в задачах кодирования и обработки сигналов.

    Таким образом, компиляторы могли бы повысить эффективность генерируемого кода, если бы сами определяли способ распределения массивов в зависимости от исполняемого кода (либо автоматически, либо по директивам пользователя, либо в диалоге), однако современные компиляторы делать этого пока не умеют.

    Размещение в распределенной памяти

    Автоматическое распараллеливание программ выполняется современными распараллеливающими компиляторами в основном для вычислительных систем с общей памятью (векторные, VLIW, многоядерные, SMP), однако для систем с распределенной памятью задача автоматического распараллеливания существенно сложнее — помимо автоматического определения параллельно выполняемых операций следует автоматически разместить данные в распределенной памяти так, чтобы минимизировать межпроцессорные пересылки.

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

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

    Пересылки данных возникают не только между процессорами, но и между модулями локальной памяти процессорных элементов, расположенных на одном кристалле (типа Tile64 или Cell BE).

    Автоматическое распараллеливание на вычислительные системы с распределенной памятью — еще один резерв распараллеливающих компиляторов.

    Внутреннее представление

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

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

    Большинство известных систем автоматической оптимизации и распараллеливания программ имеют внутреннее представление низкого уровня (GCC, LLVM, Intel С++/Fortran Compiler, Microsoft Visual C++), близкое к ассемблеру и ориентированное на генерацию команд x86. Низкий уровень внутреннего представления удобен для создания оптимизирующих компиляторов с широкого класса языков, даже далеких от Си и Фортрана, — таких как Java и Lisp. Однако эти внутренние представления неудобны для генерации кода для других архитектур, далеких от х86, — например, CUDA, Tile64, Мультиклет и др. Также представления ассемблерного уровня неудобны для генерации HDL-кода.

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

    Контроль корректности преобразований

    Анализ информационных зависимостей в программе — это основа контроля корректности автоматических преобразований программ, однако, несмотря на обилие методов определения информационных зависимостей, эти зависимости во многих случаях определяются неточно или долго. Сложности с реализацией анализа информационных зависимостей имеются в семействе компиляторов компании Portland Group (PGI), где в виде директив (OpenAcc) реализована поддержка вычислений на графическом ускорителе. Данные директивы по своему использованию похожи на директивы OpenMP, в частности, если имеется цикл с независимыми итерациями, то его можно выполнить параллельно, прописав перед ним директиву acc parallel for. Однако анализатор зависимостей не всегда может определить, являются ли итерации цикла независимыми, поэтому разработчики PGI добавили в состав своих компиляторов возможность явно указывать, что конкретный цикл не имеет зависимостей между итерациями (директива acc loop independent).

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

    Для хранения решетчатого графа не подходят такие традиционные структуры, как матрица смежности или список дуг графа. Это происходит из-за того, что множество вершин решетчатого графа совпадает с итерационным пространством программы. Затраты памяти на хранение такого количества вершин или дуг для реальных программ неприемлемы. Кроме того, время просмотра такого графа будет сопоставимо со временем исполнения программы, что также недопустимо. Впервые эффективный способ хранения и быстрый алгоритм построения решетчатого графа были предложены В. В. Воеводиным и Полем Фортье [2]. Граф можно описать набором функций, заданных на некоторых подмножествах пространства итераций. Такое описание решетчатого графа позволяет автоматически проводить анализ программ, выявлять распараллеливаемые циклы, расщеплять гнезда циклов, проводить оптимизацию по памяти и уточнять информационные зависимости в программе (см. рисунок).

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

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

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

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

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

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

    Диалоговый режим компиляции имеется у распараллеливающей коммерческой системы Parawise , преобразующей код на языке Фортран в параллельный код с использованием библиотеки MPI или директив OpenMP. Параллельный код может генерироваться также с применением специальной библиотеки коммуникаций CAPLib, которая позволяет использовать библиотеку межпроцессорных коммуникаций SHMEM. Диалог используется для определения значений некоторых переменных в программе. На основе полученной информации компилятор принимает решение о возможности распараллеливания.

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

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

    Система ДВОР (Диалоговый высокоуровневый оптимизирующий распараллеливатель программ), разработанная в Южном федеральном университете, позиционируется как основа для создания инструментов разработки распараллеливающих компиляторов.

    На вход системы подаются тексты на языках Си и Фортран, а на выходе могут быть получены программы с функциями библиотеки MPI или OpenMP. В системе реализованы блочно-аффинные распределения данных в распределенной памяти и блочное размещение в оперативной памяти, а также размещение данных с перекрытиями. Используются решетчатые графы (аналог библиотеки PipLib, piplib.org), позволяющие точно определять информационные зависимости, строить преобразования программ и определять задержки между стартами конвейеров многоконвейерной системы.

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

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

    Новое поколение компиляторов

    Ручное программирование для современных процессоров и ускорителей — долгий и дорогостоящий процесс, и сегодня требуется новое поколение компиляторов, основные черты которых таковы:

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

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

    Литература

    1. Mycrost A. Programming Language Design and Analysis motivated by Hardware Evolution (invited Presentation)
    2. Feautrier Paul. Parametric Integer Programming. Laboratoire MASI, Institut Blaise Pascal, Universite de Versailles St-Quentin, 1988.

    Борис Штейнберг (borsteinb@mail.ru) — профессор, Михаил Юрушкин (m.yurushkin@gmail.com) — аспирант Южного федерального университета (Ростов-на-Дону). Статья подготовлена на основе материалов доклада «Автоматическое отображение высокоуровневых программ на современные параллельные вычислительные системы со сложной архитектурой» (Б. Я. Штейнберг), представленного на III Московском суперкомпьютерном форуме (МСКФ-2012, грант Российского фонда фундаментальных исследований 12-07-06085-г).

    Поделитесь материалом с коллегами и друзьями

    Реализация компилятора. Организация лексического блока

    Страницы работы

    Содержание работы

    Реализация компилятора

    Организация лексического блока

    Назначение лексического блока

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

    Т.о. ЛБ представляет собой программу, в которой:

    1) открывается на чтение файл с текстом программы на исходном языке программирования;

    2) открывается на запись файл, в который будем заносить версию программы на исходном языке программирования в виде кодов символов;

    3) читаем построчно файл с исходным текстом программы;

    4) обрабатываем строку:

    · выделяем очередную цепочку литер до ближайшего разделителя, распознаем ее и записываем в файл в виде кода;

    · все это продолжаем, пока не дойдем до конца считанной строки;

    5) пункты 3,4 повторяем до тех пор, пока не дойдем до конца файла.

    Реализация лексического блока

    Прежде чем рассматривать вопросы программной реализации ЛБ необходимо задать коды символов (лексем). Всего может быть 4 группы символов:

    1) служебные слова;

    Коды всех этих символов лучше всего задать символическими константами и потом использовать их в программе. Это можно сделать, например, т.о.:

    #define Int 6 //имя INT C++Builder уже использует

    или через перечисляемый тип:

    #define MINUS 17

    #define UMINUS 18

    #define COMMA 28

    #define BEGTBL 31

    #define ENDTBL 59

    #define BEGLIT 61

    #define ENDLIT 99

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

    Головная функция для ЛБ

    for (int i = 0; i Lines->Count; i++)<

    if (lerr) Memo2->Visible = true;

    void Lex(char *s, int ns)<

    char ls[80], str[160], *pstr, *ps, errstr[80];

    /*можно: pos= sprintf(pstr,»%02d «,lcod); pstr += pos;

    Где локальная переменная : int pos;*/

    sprintf(pstr,»00 %s»,ps); //Чтобы вывести после кодов исходный текст

    Здесь предполагается, что имелись глобальные описания и функции:

    FILE *out; //выходной файл с кодами лексем

    int lcod; //содержит код лексемы ( норма >0)

    int lerr=0; //количество ошибок лексического блока

    int LexRecogn(char *); //функция, распознающая лексему и возвращающая ее код >0

    Form1->Memo2 – для вывода сообщений об ошибках, если они будут.

    if((cod=TermRecogn (s)) = = 0)

    if((cod=LitRecogn (s)) = = 0)

    if((cod=DlmRecogn (s)) = = 0)

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

    Конечные автоматы

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

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

    где K — конечное множество состояний;

    T — конечный входной алфавит;

    d- множество переходов;

    S — начальное состояние (S Î K);

    F — множество конечных, допускающих состояний (F Ì K).

    Рассмотрим пример реализации конечного автомата для распознавания идентификатора.

    Основной блок компилятора

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

    Цели и задачи дисциплины

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

    Несмотря на то, что к настоящему времени разработаны тысячи различных языков и их трансляторов, процесс создания новых приложений в этой области не прекращается. Это связно как с развитием технологии производства вычислительных систем, так и с необходимостью решения все более сложных прикладных задач. Кроме того, элементы теории языков и формальных грамматик применимы и в других разнообразных областях, например, при описании структур данных, файлов, изображений, представленных не в текстовом, а двоичном формате. Эти методы полезны и при разработке своих трансляторов даже там, где уже имеются соответствующие аналоги. Такая разработка может быть обусловлена различными причинами, в частности, функциональными ограничениями, отсутствием локализации, низкой эффективностью. Например, одной из последних разработок компании Microsoft является язык программирования C#, а одной из причин его создания является стремление к снижению популярности языка программирования Java. Можно привести множество других примеров, когда разработка своего транслятора может оказаться актуальной. Поэтому, основы теории языков и формальных грамматик, а также практические методы разработки трансляторов лежат в фундаменте инженерного образования по информатике и вычислительной технике.

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

    Цель дисциплины: предоставить знания по основам теории языков и формальных грамматик, теории автоматов, методам разработки трансляторов.

    Для достижения поставленной цели в ходе преподавания дисциплины решаются следующие задачи:

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

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

    Основные понятия и определения

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

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

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

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

    Компилятор — это обслуживающая программа, выполняющая трансляцию на машинный язык программы, записанной на исходном языке программирования . Также как и ассемблер, компилятор обеспечивает преобразование программы с одного языка на другой (чаще всего, в язык конкретного компьютера). Вместе с тем, команды исходного языка значительно отличаются по организации и мощности от команд машинного языка. Существуют языки, в которых одна команда исходного языка транслируется в 7-10 машинных команд. Однако есть и такие языки, в которых каждой команде может соответствовать 100 и более машинных команд (например, Пролог). Кроме того, в исходных языках достаточно часто используется строгая типизация данных, осуществляемая через их предварительное описание. Программирование может опираться не на кодирование алгоритма, а на тщательное обдумывание структур данных или классов. Процесс трансляции с таких языков обычно называется компиляцией, а исходные языки обычно относятся к языкам программирования высокого уровня (или высокоуровневым языкам). Абстрагирование языка программирования от системы команд компьютера привело к независимому созданию самых разнообразных языков, ориентированных на решение конкретных задач. Появились языки для научных расчетов, экономических расчетов, доступа к базам данных и другие.

    Интерпретатор — программа или устройство, осуществляющее пооператорную трансляцию и выполнение исходной программы . В отличие от компилятора, интерпретатор не порождает на выходе программу на машинном языке. Распознав команду исходного языка, он тут же выполняет ее. Как в компиляторах, так и в интерпретаторах используются одинаковые методы анализа исходного текста программы. Но интерпретатор позволяет начать обработку данных после написания даже одной команды. Это делает процесс разработки и отладки программ более гибким. Кроме того, отсутствие выходного машинного кода позволяет не «захламлять» внешние устройства дополнительными файлами, а сам интерпретатор можно достаточно легко адаптировать к любым машинным архитектурам, разработав его только один раз на широко распространенном языке программирования. Поэтому, интерпретируемые языки, типа Java Script, VB Script, получили широкое распространение. Недостатком интерпретаторов является низкая скорость выполнения программ. Обычно интерпретируемые программы выполняются в 50-100 раз медленнее программ, написанных в машинных кодах.

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

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

    Очень часто эмулятор используется для выполнения старых программ на новых вычислительных машинах. Обычно новые компьютеры обладают более высоким быстродействием и имеют более качественное периферийное оборудование. Это позволяет эмулировать старые программы более эффективно по сравнению с их выполнением на старых компьютерах. Примером такого подхода является разработка эмуляторов домашнего компьютера ZX Spectrum с микропроцессором Z80. До сих пор находятся любители поиграть на эмуляторе в устаревшие, но все еще не утратившие былой привлекательности, игровые программы. Эмулятор может также использоваться как более дешевый аналог современных компьютерных систем, обеспечивая при этом приемлемую производительность, эквивалентную младшим моделям некоторого семейства архитектур. В качестве примера можно привести эмуляторы IBM PC совместимых компьютеров, реализованные на более мощных компьютерах фирмы Apple. Ряд эмуляторов, написанных для IBM PC, с успехом заменяют различные игровые приставки.

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

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

    Макропроцессор — программа, обеспечивающая замену одной последовательности символов другой [Браун]. Это разновидность компилятора. Он осуществляет генерацию выходного текста путем обработки специальных вставок, располагаемых в исходном тексте. Эти вставки оформляются специальным образом и принадлежат конструкциям языка, называемого макроязыком. Макропроцессоры часто используются как надстройки над языками программирования, увеличивая функциональные возможности систем программирования. Практически любой ассемблер содержит макропроцессор, что повышает эффективность разработки машинных программ. Такие системы программирования обычно называются макроассемблерами.

    Макропроцессоры используются и с языками высокого уровня. Они увеличивают функциональные возможности таких языков как PL/1, C, C++. Особенно широко макропроцессоры применяются в C и C++, позволяя упростить написание программ. Примером широкого использования макропроцессоров является библиотека классов Microsoft Foundation Classes (MFC). Через макровставки в ней реализованы карты сообщений и другие программные объекты. При этом, макропроцессоры повышают эффективность программирования без изменения синтаксиса и семантики языка.

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

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

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

    Общие особенности языков программирования и трансляторов

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

    Языки программирования являются инструментами для решения задач в разных предметных областях, что определяет специфику их организации и различия по назначению. В качестве примера можно привести такие языки как Фортран, ориентированный на научные расчеты, C, предназначенный для системного программирования, Пролог, эффективно описывающий задачи логического вывода, Лисп, используемый для рекурсивной обработки списков. Эти примеры можно продолжить. Каждая из предметных областей предъявляет свои требования к организации самого языка. Поэтому можно отметить разнообразие форм представления операторов и выражений, различие в наборе базовых операций, снижение эффективности программирования при решении задач, не связанных с предметной областью. Языковые различия отражаются и в структуре трансляторов. Лисп и Пролог чаще всего выполняются в режиме интерпретации из-за того, что используют динамическое формирование типов данных в ходе вычислений. Для трансляторов с языка Фортран характерна агрессивная оптимизация результирующего машинного кода, которая становится возможной благодаря относительно простой семантике конструкций языка — в частности, благодаря отсутствию механизмов альтернативного именования переменных через указатели или ссылки. Наличие же указателей в языке C предъявляет специфические требования к динамическому распределению памяти.

    Структура языка характеризует иерархические отношения между его понятиями, которые описываются синтаксическими правилами. Языки программирования могут сильно отличаться друг от друга по организации отдельных понятий и по отношениям между ними. Язык программирования PL/1 допускает произвольное вложение процедур и функций, тогда как в C все функции должны находиться на внешнем уровне вложенности. Язык C++ допускает описание переменных в любой точке программы перед первым ее использованием, а в Паскале переменные должны быть определены в специальной области описания. Еще дальше в этом вопросе идет PL/1, который допускает описание переменной после ее использования. Или описание можно вообще опустить и руководствоваться правилами, принятыми по умолчанию. В зависимости от принятого решения, транслятор может анализировать программу за один или несколько проходов, что влияет на скорость трансляции.

    Семантика языков программирования изменяется в очень широких пределах. Они отличаются не только по особенностям реализации отдельных операций, но и по парадигмам программирования, определяющим принципиальные различия в методах разработки программ. Специфика реализации операций может касаться как структуры обрабатываемых данных, так и правил обработки одних и тех же типов данных. Такие языки, как PL/1 и APL поддерживают выполнение матричных и векторных операций. Большинство же языков работают в основном со скалярами, предоставляя для обработки массивов процедуры и функции, написанные программистами. Но даже при выполнении операции сложения двух целых чисел такие языки, как C и Паскаль могут вести себя по-разному.

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

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

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

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

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

    Для любого языка определяется:

    Множество символов, которые можно использовать для записи правильных программ (алфавит), основные элементы.

    Множество правильных программ (синтаксис).

    «Смысл» каждой правильной программы (семантика).

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

    Формально каждая правильная программа X — это цепочка символов из некоторого алфавита A, преобразуемая в соответствующую ей цепочку Y, составленную из символов алфавита B.

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

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

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

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

    В большинстве языков программирования данное выражение определяет иерархию программных объектов, которую можно отобразить в виде дерева (рис. 1.1.):

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

    ::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

    Примечание . Знак «::=» читается как «это есть». Вертикальная черта «|» читается как «или».

    Если правила будут записаны иначе, то изменится и иерархическая структура. В качестве примера можно привести следующие способ записи правил:

    ::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

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

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

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

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

    Его синтаксическая структура описывается правилами:

    ::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

    Иерархическое дерево, определяющее синтаксическую структуру, представлено на рис. 1.3.

    Другой характерной особенностью всех языков является их семантика. Она определяет смысл операций языка, корректность операндов. Цепочки, имеющие одинаковую синтаксическую структуру в различных языках программирования, могут различаться по семантике (что, например, наблюдается в C++, Pascal, Basic для приведенного выше фрагмента арифметического выражения).

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

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

    Обобщенная структура транслятора

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

    Учитывая схожесть компилятора и интерпретатора, рассмотрим фазы, существующие в компиляторе. В нем выделяются:

    1. Фаза лексического анализа.
    2. Фаза синтаксического анализа, состоящая из:
      • распознавания синтаксической структуры;
      • семантического разбора, в процессе которого осуществляется работа с таблицами, порождение промежуточного семантического представления или объектной модели языка.

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


      2а. Фаза исследования и оптимизации промежуточного представления, состоящая из:

    2а.1. анализа корректности промежуточного представления;
    2а.2. оптимизации промежуточного представления.

      3а. Фаза оптимизации объектного кода.

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

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

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

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

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

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

    ссылки на переменные, типы данных и имена процедур, размещаемые в таблицах имен;

    связи, определяющие последовательность выполнения команд;

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

    Таким образом, синтаксический анализатор является достаточно сложным блоком транслятора. Поэтому его можно разбить на следующие составляющие:

    блок семантического анализа;

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

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

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

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

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

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

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

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

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

    На основе двух основных вариантов можно также создавать их разнообразные сочетания.

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

    Данный вариант взаимодействия блоков, на примере компилятора, представлен на рис 1.7.

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

    К достоинствам такого подхода можно отнести:

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

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

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

    К недостаткам следует отнести.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Наряду со схемами, предполагающими замену генератора кода на эмулятор, существуют трансляторы, допускающие их совместное использование. Одна из таких схем представлена на рис. 1.13.

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

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

    Контрольные вопросы и задания

    интерпретатора от компилятора;

    компилятора от ассемблера;

    перекодировщика от транслятора;

    эмулятора от интерпретатора;

    синтаксиса от семантики.

    Расскажите об известных Вам последних разработках языков программирования. Приведите основные характеристики названных языков.

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

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

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

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

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

    Основные достоинства и недостатки интерпретаторов.

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

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

    Назовите основные фазы процесса трансляции и их назначение.

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

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

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

    Основные блоки в блок-схемах.

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

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

    Основные блоки в блок-схемах:

    (5)Цикл(ромб с кругом); 6)Подпрограмма(прямоугольник, по бокам отступы))


    • Основные компоненты системы программирования: язык программирования, транслятор, компилятор. Характеристика языков высокого и низкого уровней. Примеры.

    Язык программи́рования — формальный язык, предназначенный для записи компьютерных программ.

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

    Транслятор — это программа-переводчик. Она преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд. Трансляторы делятся на две группы по их работе – компиляторы и интерпретаторы.

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

    Базовая единица действия в любом ЯП- оператор

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

    ЯП делятся на: языки высокого и низкого уровня.

    ЯНУ являются машинно зависимыми языками, потому что содержат в том или ином виде операторы определенные для конкретного ЦП или для определенной архитектуры.

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

    Языки низкого уровня — это машинный язык, язык Ассемблера.

    Машинный язык состоит из двух символов — 0 и 1 (программа строится в двоичной системе счисления).

    А вот языки высокого уровня ориентированы на человека (на пользователя ПК). Это такие языки программирования: Бейсик, Паскаль, Турбо Паскаль, С++ и другие.


    • Оператор. Операнд. Общая характеристика и классификация данных. Элемент данных. Константы и переменные. Примеры. Идентификатор. Правило именования идентификатора. Примеры.

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

    Операнд — это аргумент операции,это значение, переменная или выражение, которое расположено слева или справа от оператора(Для понимания 1 + 2 Здесь 1 и 2 — это операнды, а знак ПЛЮС (+) — это оператор. )

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

    Классификация типов данных

    Знаковые/беззнаковые( целые или вещественные)

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

    Константа- это элемент данных, сохраняющий значение заданное программистом при её описании неизменным до конца выполнения программы, в которой она определена) [const m = -50;]

    Переменная- это элемент данных, значение которого может быть изменено в процессе программы( причём, пока программа не начала работать, переменная не определена)[int a, b, c;]

    Идентификатор- это имя какого-либо элемента программы( а не только элемента данных!), заданное программистом при его описании, в соответствии с правилом определения имён для данного языка программирования.

    Правило определения идентификатора:

    1) Первый символ- символ латинского алфавита

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

    3) Длинна не может превышать 30 символов


    • Понятие типа данных. Именные и типизированные константы. Примеры. Базовые структуры: массивы, записи (структуры). Преимущества использования массивов. Использование констант при описании массивов.

    Тип данных — множество значений, которые может принимать эта переменная.

    Именные константы — это константа, тип которой определяется по значению( У=23, Е=х), типизированные константы- это константы, которые программист задает сам(float, int).

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

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

    Преимущества использования массивов:

    Удобный способ хранения нескольких элементов под одним именем,Быстрота изменения элементов,Легкость в использовании .

    Имя массива является константным указателем. Именно поэтому и невозможно копирование массивов с помощью простого оператора присвоения. Константный указатель «охраняет» область памяти, выделенную для размещения данного массива. При этом значения элементов массива можно изменять в ходе выполнения программы. Защитить их от изменения можно с помощью дополнительного спецификатора типа const. При этом массив должен быть проинициализирован непосредственно в момент определения:


    • Понятие типа данных. Основные типы данных языка С: описание, размер, примеры использования.

    Тип данных — множество значений, которые может принимать эта переменная.

    Логический тип- состоит всего из двух значений : False (ложно) и True (истинно). Эти слова определены в языке и являются, по сути, логическими константами. Минимальный размер для bool- 8 бит

    char- символьный тип(1 байт)(0. 255)

    int — целый тип(4 байта)(зависит от системы, обычно около -32к. 32к)(int a=10)

    float- вещественный тип одинарной точности(4 байта)(float b=1.5)

    double, real- обозначают множества вущественных чисел в различных диапазонах(8 байт)(double b = 0.00105)
    • Массивы. Принципы организации массивов. Одномерные и двумерные массивы. Физическая организация массивов в памяти ЭВМ. Примеры описания и использования на языке С.

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

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

    Двумерный массив-это своеобразная матрица, состоящая из Н-ого количества строк и М-ого количества столбцов.

    Принципы организации массивов(основные характеристики при определении массива)?:

    2. тип элемента (массива)

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

    4. количество элементов или длинна массива

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

    Одномерный массив (пример описания и пример использования):

    Объявление массива- int array1 [10];

    Пример использования- for (int i=0; i >

    вывод printf cout y) && (x>z))

    Дизьюнкция или or в Си.

    Пример применения: if ((x>y) || (x>z))

    Исключающее ИЛИ или xor в Си.

    Пример применения: if ((x>y) ^(x>z))


    • Оператор выбора. Синтаксис, принцип и особенности функционирования, примеры использования. Эквивалентное представление оператора выбора с помощью ветвления.

    Оператор выбора языка Си –switch

    В круглых скобках после оператора выбора языка Си switch находится переменная типа int или char (не строковая), следом расположен блок, заключенный в фигурные скобки; в блоке содержатся ветви условий case. Каждая ветвь case выполняет конкретные инструкции, если значение переменной совпадает с указанным. Если это значение является символом, то символ заключается в одинарные кавычки.

    Эквивалентное представление оператора выбора с помощью ветвления.


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

    Циклы— многократно повторяемые участки вычислений, при соблюдении заданных условий; а сами повторяемые участки- тело цикла.

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


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

    В языке Си следующие виды циклов:

    while — цикл с предусловием;

    do. while — цикл с постусловием;

    Цикл с предусловием while:

    Общая форма записи:

    Если Условие выполняется (выражение, проверяющее Условие, не равно нулю), то выполняется Блок Операций, заключенный в фигурные скобки, затем Условие проверяется снова.

    Последовательность действий, состоящая из проверки Условия и выполнения Блока Операций, повторяется до тех пор, пока выражение, проверяющее Условие, не станет ложным (равным нулю). При этом происходит выход из цикла, и производится выполнение операции, стоящей после оператора цикла.

    (Посчитать сумму чисел от 1 до введенного k)

    #define _CRT_SECURE_NO_WARNINGS // для возможности использования scanf

    int k; // объявляем целую переменную key

    int sum = 0; // начальное значение суммы равно 0

    scanf(«%d», &k); // вводим знчение переменной k

    #include // для использования функции system()

    int num; // объявляем целую переменную для числа

    system(«chcp 1251»); // переходим на русский язык в консоли

    system(«cls»); // очищаем экран

    printf(«Введите число от 0 до 10: «); // приглашение пользователю

    scanf(«%d», &num); // ввод числа

    > while ((num 10)); // повторяем цикл пока num 10

    printf(«Вы ввели число %d», num); // выводим введенное значение num — от 0 до 10


    • Цикл со счетчиком. Реализация цикла со счетчиком с использованием операторов цикла с пред и постусловием.

    В большинстве процедурных языков программирования реализуется оператором for, в котором указывается счётчик (так называемая «переменная цикла»), требуемое количество проходов (или граничное значение счётчика) и, возможно, шаг, с которым изменяется счётчик. Например, в языке Оберон-2 такой цикл имеет вид:

    FOR v := b TO e BY s DO

    здесь v — счётчик, b — начальное значение счётчика, e — граничное значение счётчика, s — шаг).

    Цикл с предусловием

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

    Цикл с постусловием

    Цикл с постусловием — цикл, в котором условие проверяется после выполнения тела цикла. Отсюда следует, что тело всегда выполняется хотя бы один раз. В языке Паскаль этот цикл реализует оператор repeat..until; в Си — do…while.

    На языке Pascal цикл с постусловием имеет следующий вид::


    • Простые и вложенные циклы: особенность организации, примеры на языке С. Досрочное завершение цикла.

    Если мы знаем точное количество действий (итераций) цикла, то можем использовать цикл for. Синтаксис его выглядит примерно так:

    for (действие до начала цикла;

    условие продолжения цикла;

    действия в конце каждой итерации цикла) <

    инструкция цикла 2;

    инструкция цикла N;

    Итерацией цикла называется один проход этого цикла

    Существует частный случай этой записи, который мы сегодня и разберем:

    for (счетчик = значение; счетчик

    using namespace std;

    int i; // счетчик цикла

    int sum = 0; // сумма чисел от 1 до 1000.

    using namespace std;

    int i = 0; // инициализируем счетчик цикла.

    int sum = 0; // инициализируем счетчик суммы.

    using namespace std;

    int i = 0; // инициализируем счетчик цикла.

    int sum = 0; // инициализируем счетчик суммы.

    do <// выполняем цикл.

    > while (i 2 then x:=10; <При y>2 цикл нужно завершить>

    Однако, во избежание трудноуловимых ошибок, управляющую переменную не принято менять иначе, чем для выполнения шага цикла. Например, после оператора if y>2 then x:=10; в нашем листинге выполнение текущего шага продолжится, что чревато лишними или неправильными вычислениями. Кроме того, текст такой программы воспринимается нелегко.

    Поэтому для досрочного выхода из цикла существует оператор break (от англ. «to break» — прервать), немедленно прекращающий его выполнение:

    while x 2 then break; <При y>2 цикл нужно завершить>

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

    Для немедленного продолжения цикла со следующего шага используется оператор continue (от англ. «to continue» – продолжить):

    writeln (‘Введите положительное число:’);

    if n 100) printf («greater»);

    for (ch=getchar(); isdigit(ch); ) . ;

    Тем не менее функция не может стоять с левой стороны оператора присваивания. Оператор типа

    swap (х, у) = 100; /* некорректный оператор */

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

    Если функция объявляется как void, она не может использоваться в выражениях. Например, предположим, что f() объявлена как void. Следующие операторы не будут компилироваться:

    t = f(); /* нет значения для присваивания t */

    f() + f(); /* нет значений для сложения */

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


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

    Передача параметров по значению

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

    procedure Test(s: string);

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

    procedure ChangeMe(var x: longint);

    x := 2; // Параметр х изменен вызванной процедурой

    Вместо создания копии переменной x, ключевое слово var требует передачи адреса самой переменной x, что позволяет процедуре непосредственно изменять ее значение.


    • Массивы как параметры процедур (функций). Примеры организации передачи параметров в виде массива на языке С.

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

    тип_функции имя_функции ( тип_массива имя_массива [ n ] )

    n – количество элементов в массиве

    Вызов функции: имя_функции (имя_массива);

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

    Пример: Написать функцию нахождения минимума в одномерном массиве.

    Основной блок компилятора

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

    Некоторые компиляторы (например, низкоуровневом языке. Такой язык — байт-код — также можно считать языком машинных команд, поскольку он подлежит интерпретации виртуальной машиной. Например, для языка Java это JVM (язык виртуальной машины Java), или так называемый байт-код Java (вслед за ним все промежуточные низкоуровневые языки стали называть байт-кодами). Для языков программирования на платформе .NET Framework (C#, Managed C++, Visual Basic .NET и другие) — это MSIL (Microsoft Intermediate Language).

    Программа на байт-коде подлежит интерпретации виртуальной машиной, либо ещё одной компиляции уже в машинный код непосредственно перед исполнением. Последнее называется «Just-In-Time компиляция» (MSIL-код компилируется в код целевой машины также JIT-компилятором, а библиотеки .NET Framework компилируются заранее).

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

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

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

    Структура компилятора

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

    1. Лексический анализ. На этом этапе последовательность символов исходного файла преобразуется в последовательность лексем.
    2. Синтаксический (грамматический) анализ. Последовательность лексем преобразуется в дерево разбора.
    3. Семантический анализ. Дерево разбора обрабатывается с целью установления его семантики (смысла) — например, привязка идентификаторов к их декларациям, типам, проверка совместимости, определение типов выражений и т. д. Результат обычно называется «промежуточным представлением/кодом», и может быть дополненным деревом разбора, новым деревом, абстрактным набором команд или чем-то ещё, удобным для дальнейшей обработки.
    4. Оптимизация. Выполняется удаление излишних конструкций и упрощение кода с сохранением его смысла. Оптимизация может быть на разных уровнях и этапах — например, над промежуточным кодом или над конечным машинным кодом.
    5. Генерация кода. Из промежуточного представления порождается код на целевом языке.

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

    Трансляция и компоновка

    Важной исторической особенностью компилятора, отражённой в его названии (англ. compile — собирать вместе, составлять), являлось то, что он мог производить и компоновку (то есть содержал две части — транслятор и компоновщик). Это связано с тем, что раздельная компиляция и компоновка как отдельная стадия сборки выделились значительно позже появления компиляторов, и многие популярные компиляторы (например, GCC) до сих пор физически объединены со своими компоновщиками. В связи с этим, вместо термина «компилятор» иногда используют термин «транслятор» как его синоним: либо в старой литературе, либо когда хотят подчеркнуть его способность переводить программу в машинный код (и наоборот, используют термин «компилятор» для подчёркивания способности собирать из многих файлов один).

    Интересные факты

    • На заре развития компьютеров первые компиляторы (трансляторы) называли «программирующими программами» [6] (так как в тот момент программой считался только машинный код, а «программирующая программа» была способна из человеческого текста сделать машинный код, то есть запрограммировать ЭВМ).

    Примечания

    1. ГОСТ 19781-83 // Вычислительная техника. Терминология: Справочное пособие. Выпуск 1 / Рецензент канд. техн. наук Ю. П. Селиванов. — М.: Издательство стандартов, 1989. — 168 с. — 55 000 экз. — ISBN 5-7050-0155-X
    2. 1234567Першиков В. И., Савинков В. М. Толковый словарь по информатике / Рецензенты: канд. физ.-мат. наук А. С. Марков и д-р физ.-мат. наук И. В. Поттосин. — М.: Финансы и статистика, 1991. — 543 с. — 50 000 экз. — ISBN 5-279-00367-0
    3. 123 СТ ИСО 2382/7-77 // Вычислительная техника. Терминология. Указ. соч.
    4. Борковский А. Б. Англо-русский словарь по программированию и информатике (с толкованиями). — М.: Русский язык, 1990. — 335 с. — 50 050 (доп.) экз. — ISBN 5-200-01169-3
    5. Толковый словарь по вычислительным системам = Dictionary of Computing / Под ред. В. Иллингуорта и др.: Пер. с англ. А. К. Белоцкого и др.; Под ред. Е. К. Масловского. — М.: Машиностроение, 1990. — 560 с. — 70 000 (доп.) экз. — ISBN 5-217-00617-X (СССР), ISBN 0-19-853913-4 (Великобритания)
    6. Н. А. Криницкий, Г. А. Миронов, Г. Д. Фролов. Программирование / Под ред. М. Р. Шура-Бура. — М.: Государственное издательство физико-математической литературы, 1963.

    См. также

    • Компилятор компиляторов
    • «Книга дракона» — классический учебник о построении компиляторов.
    • Синтаксический анализ
    • Интерпретатор

    Реализации компиляторов

    • GCC
    • Free Pascal Compiler
    • Sun Studio — компиляторы C, C++ и Fortran от Sun Microsystems Inc.
    • Open Watcom — свободное продолжение компиляторов Watcom C/C++/Fortran.
    • Intel C++/Fortran compiler
    • ICC AVR

    Литература

    • Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4
    • Робин Хантер. Основные концепции компиляторов = The Essence of Compilers. — М.: Вильямс, 2002. — С. 256. — ISBN 0-13-727835-7
    • Хантер Р. Проектирование и конструирование компиляторов / Пер. с англ. С. М. Круговой. — М.: Финансы и статистика, 1984. — 232 с.
    • Д. Креншоу.Давайте создадим компилятор!.

    Wikimedia Foundation . 2010 .

    Смотреть что такое «Компиляция (программирование)» в других словарях:

    Компиляция — Компиляция: В Викисловаре есть статья «компиляция» Компиляция (литература) (лат. … Википедия

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

    Объектно-ориентированное программирование — Эта статья во многом или полностью опирается на неавторитетные источники. Информация из таких источников не соответствует требованию проверяемости представленной информации, и такие ссылки не показывают значимость темы статьи. Статью можно… … Википедия

    JIT-компиляция — Just in time compilation (JIT, компиляция «на лету»), dynamic translation (динамическая компиляция) технология увеличения производительности программных систем, использующих байт код, путём компиляции байт кода в машинный код… … Википедия

    Сравнение языков программирования — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Условные обозначения … Википедия

    Пайтон — Python Класс языка: функциональный, объектно ориентированный, императивный, аспектно ориентированный Тип исполнения: интерпретация байт кода, компиляция в MSIL, компиляция в байт код Java Появился в: 1990 г … Википедия

    ГОСТ 19781-90: Обеспечение систем обработки информации программное. Термины и определения — Терминология ГОСТ 19781 90: Обеспечение систем обработки информации программное. Термины и определения оригинал документа: 9. Абсолютная программа Non relocatable program Программа на машинном языке, выполнение которой зависит от ее… … Словарь-справочник терминов нормативно-технической документации

    Паскаль (язык) — Pascal Семантика: процедурный Тип исполнения: компилятор Появился в: 1970 г. Автор(ы): Никлаус Вирт Паскаль (англ. Pascal) высокоуровневый язык программирования общего назначения. Один из наиболее известных языков программирования, широко… … Википедия

    Паскаль (язык программирования) — Эта статья или раздел нуждается в переработке. В Паскале нет модулей, ООП и прочих новомодных веяний. Описание расширений должно присутствовать только в статьях о соответ … Википедия

    D (язык программирования) — У этого термина существуют и другие значения, см. D. D Семантика: мультипарадигменный: императивное, объектно ориентированное, обобщённое программирование Тип исполнения: компилятор Появился в: 1999 Автор(ы) … Википедия

    Илон Маск рекомендует:  Обзор интеллектуальных платформ для email и смс-рассылок
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL