 |
Пункт 1. Определение языков посредством множеств.
|
|
|
|
Глава 1. Общие сведения о системах программирования.
Параграф 1. Типовая система программирования.
Пункт 1. Определение СП. Виды.
Система программирования представляет собой совокупность программных средств автоматизации разработки программ, их отладки и подготовки к выполнению: трансляторы с их языками программирования, редактор связей, загрузчик, средства отладки, библиотеки трансляторов и вспомогательные программы (утилиты).
СП выполняется под управлением ОС и может иметь с ней общие компоненты, например, загрузчик, библиотеки, утилиты. СП можно разделить на самостоятельные и встроенные по отношению к другим программным комплексам.
Самостоятельные СП являются системами общего назначения. Встроенные СП являются составной частью другого программного комплекса. Такие СП применяются в СУБД и наиболее развитых пакетах прикладных программ.
Пункт 2. Варианты основных компонентов СП.
Трансляторы. Это программы, выполняющие преобразование программы, представленной на одном языке, в эквивалентную ей программу на другом языке.
Варианты трансляторов в зависимости от назначения:
1. Компилятор. Переводит программу с одного языка на язык более низкого уровня (машинно-ориентированный или, чаще всего, машинный). При переводе на машинно-ориентированный язык он строит программу, подобную программе на языке ассемблера.
2. Ассемблер. Это компилятор на языке ассемблера.
3. Интерпретатор. Выполняет программу в машинно-независимой форме посредством подпрограмм, входящих в его состав. Обычно он предварительно переводит программу на некоторый более удобный промежуточный язык. Промежуточная программа не сохраняется.
|
|
|
4. Инкрементный транслятор. Предназначен специально для повторной трансляции фрагментов программы и дополнений к ней без повторной трансляции всей программы.
5. Компилятор переднего плана. Переводит программу на промежуточный машинно-независимый язык. Позволяет сохранять промежуточную программу.
6. Препроцессор. Переводит программу с макрорасширения входного языка транслятора на этот входной язык. Обычно реализуется как префиксная часть некоторых трансляторов.
7. Макрогенератор. Это препроцессор для ассемблера. Переводит программу с макроязыка на язык ассемблера.
8. Кросс-компилятор. Транслируя программу на одной машине (платформе), формирует объектный код для другой машины (платформы).
9. Компилятор компиляторов. Переводит формальное описание языка программирования в транслятор для этого языка.
10. Детранслятор. Восстанавливает программу на ЯП по ее эквиваленту на языке машины.
11. Дисассемблер. Это детранслятор для языка ассемблера.
Компоновщики. Это общее название системных программ, выполняющих подготовку объектных и загрузочных модулей к их выполнению.
Типовые функции компоновщиков, которые их различают:
1. перемещение – настройка сегментов на размещение их в новом адресном пространстве.
2. связывание – объединение двух или более модулей в единую программу.
3. перекрытие – настройка модулей программы на выполнение с перекрытиями групп сегментов в основной памяти.
4. загрузка – размещение программы в основной памяти для выполнения.
Параграф 2. Классификация языков программирования.
Основные характеристики ЯП: мощность, уровень и целостность.
1. Мощность. Характеризуется разнообразием задач, алгоритмы которых можно записать, используя этот язык. Очевидно, самым мощным ЯП является язык процессора, так как любую задачу, сформулированную на каком-либо языке программирования, можно записать и на языке компьютера.
|
|
|
2. Уровень языка. Определяется сложностью решения задач с использованием этого языка. Чем проще записывается решение задач, чем меньше объем полученных исходных программ, тем выше уровень языка.
3. Целостность. Обусловливается свойствами совокупности понятий, служащих для описания этого языка, и включает 3 взаимосвязанных аспекта:
А) экономия понятий предполагает достижение максимальной мощности языка с помощью минимального числа понятий.
Б) независимость понятий означает, что между ними не должно быть взаимного влияния: если какое-либо понятие используется в разных контекстах, то правила его использования должны быть одни и те же.
В) единообразие понятий требует согласованного единого подхода к описанию и использованию всех понятий.
Глава 2. Основные понятия и определения формальных языков.
Параграф 1. Формальные грамматики и языки.
Пункт 1. Определение языков посредством множеств.
В основе каждого языка лежит алфавит. Алфавит определяется множеством символов, применяемых для построения строк (цепочек, предложений) языка.
Пример 1. Алфавит 
16-ричных цифр и алфавит 
двоичных цифр:
; 
.
Строка – это любая последовательность символов алфавита, расположенных один за другим.
Пустой называется строка, содержащая нуль символов. Такую строку будем обозначать через 
.
Строку из 
символов 
будем обозначать через 
, например 
и 
.
Строки символов можно именовать, например 
и др. Длину некоторой строки 
будем обозначать 
.
Запись 
используют для изображения множества всех строк, включая пустую, составленных из символов, входящих в алфавит 
. Очевидно, 
.
Любую строку 
можно представить в виде сцепления (конкатенации) 
строк, где 
и 
. Строку 
в такой записи называют префиксом (головой - head), а строку 
- суффиксом (хвостом - tail) строки . Если для строки нужно обозначить ее голову, содержащую символов, то пишут 
. Также для обозначения хвоста длины пишут 
.
Строку в строке 
, где 
, называют подстрокой строки .
Формальным языком 
в алфавите называют произвольное подмножество множества .
Поскольку формальные языки представляют собой множества, над языками можно выполнять операции объединения, сцепления и др. Особыми конкатенациями являются 
и 
|
|
|
Итерация языка или замыкание Клини - сцепление произвольного числа строк некоторого формального языка : 
.
.
обозначает нуль или более сцеплений языка .
Позитивное замыкание 
содержит одно или более сцеплений языка: 
.
Задать формальный язык в алфавите - значит либо перечислить все строки языкового подмножества множества 
, либо указать правила их образования.
Например, в алфавите 
запись 
определяет язык как пустую строку и любое количество строк, каждая из которых состоит из строки нулей и последующей строки единиц такой же длины. Перебирая значения 
, получаем 
, что при любом ограниченном является подмножеством множества .
|
|
|
