Сист. прогр. Ч2 (Методические указания к выполнению лабораторных работ по СПО), страница 13

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

УСЛОВИЯ

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

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

СИГНАЛЫ

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

МУЛЬТИЗАДАЧНЫЙ РЕЖИМ

В С предусмотрены мультизадачные средства, облегчаю­щие программирование в мультипроцессорных системах.

РАСШИРЯЕМОСТЬ И МАКРОКОМАНДЫ ВРЕМЕНИ КОМПИЛЯЦИИ.

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

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

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

РАЗНОЕ

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

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

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

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

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

Возможность инициализации переменных на этапе трансляции( в частности таблиц).

Параллелизм.

Как и многие другие современные языки, С имеет сред­ства, предназначенные для специальных применений. Например, в Англии до перехода к десятичной системе в 1971 году в ком­мерческих применениях широко использовался описатель «стерлинг». Описатели «с плавающей точкой» и «комплексные переменные» удобны для инженерных применений.

РЕЗЮМЕ

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

16. ФОРМАЛЬНЫЕ СИСТЕМЫ И ЯЗЫКИ ПРОГРАММИРОВАНИЯ. ВВЕДЕНИЕ

Цели данной главы следующие:

1. Дать неформальное введение в формальные системы и грамматики.

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

3. Представить формальные системы и общеупотребитель­ную для данной области терминологию.

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

5. Разобрать два способа описания языков программирования: форма Бэкуса - Наура и канонические системы.

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

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

ИСПОЛЬЗОВАНИЕ ФОРМАЛЬНЫХ СИСТЕМ В ЯЗЫКАХ ПРОГРАММИРОВАНИЯ

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

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

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

ОПИСАНИЕ ЯЗЫКА

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

СИНТАКСИЧЕСКИ-ОРИЕНТИРОВАННЫЕ КОМПИЛЯТОРЫ

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

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

ИЗУЧЕНИЕ СЛОЖНОСТИ СТРУКТУРЫ

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

Можно провести аналогию с шенноновской теорией информации. Шеннон определил меру информации и применил ее для кодирования. Теория давала границы эффективности при кодировании и передаче информации. Исследователи фирмы Bell Telephone Laboratories, создающие технику для кодирования и передачи информации, получили возможность сравнивать производительность разрабатываемых схем с шенноновской границей, используя ее как критерий оценки. Шенноновская теория не определяет схему кодирования. Она просто обеспечивает средство измерения ее эффективности. Аналогично при определении сложности создатель компилятора должен говорить не о том, какой конкретно метод следует использовать, а о том может ли существовать какой-либо другой, лучший метод.

АНАЛИЗ СТРУКТУРЫ.

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

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

1. Что является базовыми элементами языка?

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

3. Какие классы задач могут быть запрограммированы на данном языке?

4. Какова стоимость и трудность написания программы?

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

ФОРМАЛЬНОЕ ОПИСАНИЕ ЯЗЫКА

ВВЕДЕНИЕ В ФОРМАЛИЗАЦИЮ

Прежде чем углубиться в рассмотрение формализма, полезно проанализировать некоторые проблемы формального описания языков и рассмотреть интуитивную форму такого описания. Язык можно представить как некоторое множество предложений или формул - строк символов - с корректно определенной структурой и, обычно, со значением. Правила, определяющие допустимые конструкции языка, составляют его синтаксис: синтаксис языка описывает его форму. Например, когда мы говорим, что х + 2 является выражением, а х2+ таковым не является, мы оперируем синтаксисом алгебры. Присваивание значений (интерпретация) символам и формулам есть семантика языка. Когда мы говорим, например, что x+2 есть сумма значения х и 2 или что 2∙х =x+x есть истина, мы апеллируем к обычной семантике алгебры.

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

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

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

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

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

Определение 1. Алфавит Т есть конечное множество символов (терминальных символов). Формула (называемая также строкой или предложением) есть конкатенация символов.