Лекция 2. Концепция императивного языка программирования

2 План 1. Основная задача программирования. 2. Языки программирования как формальные языки описания алгоритмов. 3. Краткая история языков программирования (ЯП). 4. Структура языка программирования. 5. О синтаксисе и семантике описаний алгоритмов. 6. Формальные средства описания синтаксиса ЯП. 7. Функциональная и операционная семантика ЯП.

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

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

5 Языки программирования как формальные языки описания алгоритмов 2. Все средства языка должны быть формализованы в такой степени, чтобы их можно было реализовать как машинные программы; (например, предложение Найти документ X в базе Y должно породить программу в машинном языке, осуществляющую требуемый поиск). 3. Язык программирования не только поддерживает предметно-ориентированную деятельность, но и стимулирует ее развитие (понятие базы данных, вычислительной сети привело к революции в деловой деятельности).

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

7 Языки программирования как формальные языки описания алгоритмов Изучая новый язык программирования, лучше всего к нему относиться, как к любому другому иностранному языку: средства языка принимать как данные от Бога, даже, если они нам кажутся непонятными, плохими или ненужными

8 Краткая история языков программирования Вопрос для самостоятельного изучения Результат работы: презентация

9 Краткая история языков программирования Современный этап в развитии программирования характеризуется следующими чертами: 1. Развитие языков программирования для мультипроцессорных и мультимашинных систем; 2. Развитие декларативных языков программирования, ориентированных на задачи искусственного интеллекта; 3. Развитие объектно-ориентированных языков, в которых иерархия абстракций позволяет наращивать средства языка, одновременно меняя архитектуру применительно к рассматриваемому классу проблем.

10 Структура языка программирования Любой язык программирования обладает сходством с естественными языками. Он имеет свой алфавит, словарь, знаки препинания (разделители) Словарь языка программирования состоит из чисел, слов и некоторых других символов. Элементы этого словаря называют лексемами. Примеры лексем: 394, -5678, , 67.5 е 8 - числа; int, cos, maxint - имена; (, ) - скобки.

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

12 О синтаксисе и семантике описаний алгоритмов Правила образования более сложных конструкций языка называются синтаксическими. Совокупность синтаксических правил образует синтаксис языка программирования. Синтаксические конструкции языка интерпретируются как действия или описания. Например, оператор присваивания x:=x+2 имеет смысл: сложить значение переменной x с числом 2 и результат интерпретировать как (новое) значение этой же переменной. Совокупность интерпретаций синтаксических правил называется семантикой языка.

13 О синтаксисе и семантике описаний алгоритмов Изучение языка программирования заключается в изучении его синтаксиса и семантики

14 Формальные средства описания синтаксиса ЯП В отличие от естественных языков, ЯП, как и другие формальные языки, должны быть определены самым точным и недвусмысленным образом. Для формального определения языковых конструкций используют т.н. метаязыки (формальные языки описания формальных языков). Описание языка программирования на метаязыке – составная часть т.н. спецификаций транслятора ЯП. Нужный уровень строгости, достигаемый формализмом метаязыка, необходим для его изучения.

15 Язык формул Бэкуса-Наура Каждый язык, в том числе и формальный, имеет свой понятийный аппарат (Слово, знак препинания, предложение, … - понятия (языковые конструкции), используемые для описания естественных языков). Вместе с тем каждый язык использует и некоторый алфавит (буквы, знаки препинания, и т.д.) так, что текст в этом языке представляет собой последовательность элементов алфавита (лексем). В соответствии с этим мы будем пользоваться терминами Понятие языка и лексема. Заметим, что сами эти термины представляют новый (третий) уровень абстракции в описании языка. Определим теперь язык Бэкуса-Наура.

16 Язык формул Бэкуса-Наура Понятие языка - это (метаязыковое) имя определяемой языковой конструкции. Имя конструкции в определении языка играет роль символа, который называется метасимволом (нетерминальным символом). Определяемый язык представлен в виде конечного набора метасимволов (метасловаря) языка. Метасловарь представляет понятийный аппарат языка программирования. С формальной точки зрения метасловарь удобно считать алфавитом нетерминальных символов (метаалфавитом)

17 Язык формул Бэкуса-Наура Вместе с метаалфавитом ЯП определяется и лексический словарь ЯП – конечный набор лексем. С формальной точки зрения лексический словарь также удобно считать алфавитом терминальных символов. Лексема - это атомарный объект языка.

18 Язык формул Бэкуса-Наура Описание ЯП на языке формул Бэкуса – Наура (БНФ) – это набор где –N – алфавит нетерминальных символов –T – алфавит терминальных символов –R – конечный набор грамматических правил – – символ программа {начальный нетерминальный символ} Каждое грамматическое правило имеет вид p, где - элемент алфавита Т, p – слово в объединенном алфавите N T.

19 Язык формул Бэкуса-Наура Таким образом, R = { 1 ::= p1, 2 ::= p2,..., k ::= pk } Символ ::=, отделяющий левую часть правила (определяемый символ) от правой части (определения) означает «есть по определению». Одно из правил в левой части должно содержать символ. Обычно это правило в списке указывается первым: R = { p1, 2 p2,..., k pk }

20 Язык формул Бэкуса-Наура Пример правила ::= ;. Грамматическое правило описывается формулой ;. где - символ понятия программа, - символ понятия заголовок, - символ понятия блок, а ; и. – лексемы.

21 Язык формул Бэкуса-Наура Правила используются в процессе синтаксического анализа программ на ЯП. Блок синтаксического анализа компилятора представляет собой набор процедур анализа отдельных понятий, рекурсивно вызывающих друг друга. Например, оператор While описывается правилом ::= While do

22 Язык формул Бэкуса-Наура В язык БНФ добавляют дополнительные средства в виде двуместных операций *, |, и одноместных операций [ ], { }. Их можно описать как сокращения исходных формул: – ::= p и ::= q ::= p * q – ::= p1 и ::= p2 ::= p1 | p2 – ::= p и ::= pq ::= p[q] – ::= p и ::= ::= {p} Здесь - символ, означающий «пустое слово». Алгебра, которую мы фактически определили, называется алгеброй регулярных языков.

23 Синтаксические диаграммы Синтаксические диаграммы – наглядный способ изображения формул Бэкуса-Наура. имя Program (), Заголовок программы

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

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

26 Пример: Определение блока на языке Бэкуса-Наура ::= [ ] [ ; ]

27 Пример: Определение блока на языке синтаксических диаграмм Раздел меток Раздел типов Раздел переменных Раздел процедур и функций Раздел констант Раздел операторов ; ; ; ; ; Блок

28 Спасибо за внимание!