4793

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

Лекция

Информатика, кибернетика и программирование

Концепция императивного язык программирования. Основная задача программирования. Краткая история языков программирования. Языки программирования (ЯП) как формальные языки описания алгоритмов. Структура языка программирования. О синтаксисе и семантик...

Русский

2012-11-27

83 KB

19 чел.

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

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

  1.  Основная задача программирования

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

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

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

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

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

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

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

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

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

Идея языка программирования появилась так же давно, как и универсальные вычислительные машины - на рубеже 40-50 годов. Уже на первых шагах их эксплуатации выяснились недостатки использования машинного кода, определились методы устранения или уменьшения этих недостатков: использование библиотек стандартных подпрограмм, имен вместо адресов, предварительного распределения памяти и т.д.

Большое влияние на последующие разработки оказал язык Fortran, созданный в IBM под руководством Дж. Бэкуса (1954-57гг.) В то же время М.Г.Хоппер (Ramington-Rand Univac) и ее группа разработали язык обработки коммерческой информации Flow-Matic. М.Г.Хоппер принадлежит термин “компилятор”. Так называлась ее первая транслирующая программа.

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

Вот некоторые даты:

1957 г. Fortran США, IBM, Дж. Бэкус: по существу, первый широко применяемый язык, ориентированный на научно-инженерные и численные задачи.

1960 г. Cobol США, Объединенный комитет производителей и пользователей ЭВМ: язык для коммерческих задач.

1960 г. Algol-60 Улучшенный вариант языка Algol-58, Европа, США, международная рабочая группа: универсальный язык, прародитель Pascal-я и многих других языков европейского стиля.

1965 г. BASIC Дж. Кемени, Т.Куртц, США, Дартмутский колледж: язык для начинающих.

1969 г. Logo С.Пейперт, США, Массачусетский технологический институт: язык для детей.

1966 г. PL-1 группа IBM,США: Многоцелевой язык для систем коллективного пользования.

1968 г. Algol-68 Европа, международная рабочая группа: европейский ответ на PL-1.

1970 г. Pascal Н.Вирт, Швейцария, федеральный институт технологии, Цюрих: язык для обучения специалистов в области информатики.

1959 г. Lisp Дж.Маккарти, США, Массачусетский технологический институт: язык функционального программирования.

1972 г. Prolog А.Колмероэ и его коллеги из лаборатории Искусственного интеллекта, Марсельский университет, Франция: язык логического программирования, завоевавший широкую известность как язык для задач обработки баз знаний.

1972-75гг. С и его развитие С++. Д. Керниган, Д. Ричи, Б. Страустрап, AT & T Bell Lab.,: языки системного программирования, получившие широкое распространение благодаря своей эффективности и поддержке ведущих программистских компаний.

1975 г. Modula-2 Н.Вирт, Развитие языков Pascal и Modula для системного программирования.

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

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

Перенесение акцентов с ЭВМ на программы еще более ярко выразилось в появлении принципиально новых стилей программирования - функционального программирования (Lisp), логического программирования (Prolog), алгебраического программирования (Reduce, APS).

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

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

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

Языки программирования (ЯП) как формальные языки описания алгоритмов

Понятие о лексике, прагматике, синтаксисе и семантике языка

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

394, -5678, 12.456, 67.5е8 - числа; Integer, Cos, MaxInt - имена; (, ) - скобки.

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

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

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

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

Средства определения языка

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

Язык формул Бэкуса-Наура

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

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

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

Описание ЯП на языке формул Бэкуса – Наура (БНФ) – это набор

< N, T, R, >

где

Nалфавит нетерминальных символов

Tалфавит терминальных символов

Rконечный набор грамматических правил

символ “программа” {начальный нетерминальный символ}

Каждое грамматическое правило имеет вид   p, где - элемент алфавита Т, p – слово в объединенном алфавите N T. Таким образом,

R = { 1 ::= p1 , 2 ::= p2 , . . . , k ::= pk }

Символ ::=, отделяющий левую часть правила (определяемый символ) от правой части (определения) означает «есть по определению».

Одно из правил в левой части должно содержать символ . Обычно это правило в списке указывается первым:

R = {   p1 , 2  p2 , . . . , k  pk }

Грамматическое правило, приведенное выше, описывается формулой    ; . где - символ понятия “программа”, - символ понятия “заголовок”, - символ понятия “блок”, а “ ; ” и “ . ” – лексемы. Для достижения семантической ясности формулы БНФ записывают в терминах метасловарей, заключая понятия языка в (остроугольные) скобки:

<программа> ::= <заголовок> ; <блок> .

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

<Оператор> ::= While <Логическое выражение> do <Оператор>

Для того, чтобы использовать нерекурсивные способы описания синтаксических конструкций, в язык БНФ добавляют дополнительные средства в виде двуместных операций “*”, “|”, и одноместных операций “[ ]”, “{ }”. Их можно описать как сокращения исходных формул:

::= p и  ::= q    ::= p * p 

::= p1 и  ::= p2   ::= p1 | p2 

::= p  и  ::= pq   ::= p[q]

::= p и  ::=    ::= {p}

Здесь - символ, означающий «пустое слово». Заметим, что операция конкатенации «*» по существу использовалась ранее «по умолчанию». Алгебра, которую мы фактически определили, называется алгеброй регулярных языков.

 

Синтаксические диаграммы

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

 

              

 

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

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

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

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

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

<Блок> ::= [<Раздел меток>] [ ; <Раздел меток>] [ ; <Раздел типов>] [ ; <Раздел переменных>] [ ; <Раздел процедур и функций>] <Раздел операторов>


 

                              

                              

                   

                       

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

Язык программирования Паскаль

Язык программирования Паскаль разработан известным швейцарским ученым и педагогом в области программирования Н.Виртом. Предварительное сообщение появилось в 1968 г. В 1971 году заработал первый компилятор пересмотренной версии, которая приобрела статус стандарта.

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

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

Алфавит языка

В языке используются:

1.Латинские буквы (большие и маленькие), знак подчеркивания ’_’

2.Цифры 0,...,9

3.Математические символы +, -, *, /, <, >, =

4.Разделители: ; , “ ‘ . : ^

5.Скобки ( ) [ ] { }

6.Другие символы (используемые для печати): буквы национальных алфавитов, !, ?, \, |, ...

В различных версиях могут использоваться различные наборы символов. Сейчас широко используется набор символов кода ASCII (American Standard Code for Information Interchange). Этот код предусматривает расширения для национальных алфавитов, символов псевдографики, которые могут меняться от версии к версии.

Данные

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

В языке Паскаль представляются числа и строки.

Целые числа записываются в десятичной системе счисления: 137, -56, +26 .

Вещественные числа используют также десятичную нотацию, причем целая часть отделяется от дробной не запятой, а точкой. Для обозначения порядка числа в качестве разделителя используется буква Е. Например, -5.1Е14 означает -5.1, умноженное на 10 в степени 14 (-5,1*1014). Степени чисел могут быть и отрицательными: 6.74Е-8, -56.89Е-10.

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

‘ строка из символов ‘, ‘ апостроф ‘’ в слове ‘

Имена

Именем в языке называется последовательность (латинских) букв, знака подчеркивания ‘_’ и цифр, начинающаяся с буквы либо со знака подчеркивания. Хотя имена могут быть сколь угодно длинными, в реализации количество значащих символов в имени может быть ограничено. В стандарте языка имена различаются по первым восьми символам. Это означает, что имена VeryLongNumber, VeryLongCardinal в стандарте языка обозначают (именуют) один и тот же объект. Кроме того, язык не различает больших и маленьких букв. Поэтому имена Sin, SIN, sin неразличимы.

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

Pi, Сonstant - имена констант; x, y1, y2, Counter - имена переменных;

Integral, MaxMin - имена процедур; Man, Color, WeekDay - имена типов;

Некоторые имена предопределены заранее. Например:

Sin - имя для обозначения функции синус; Read - имя для обозначения процедуры чтения;

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

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

Структура программы

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

Рис.1

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


Имя                          

имя

Program

(

)

 ,

Заголовок

программы

Раздел меток            

Раздел типов

Раздел переменных

Раздел процедур и функций

Раздел констант

Раздел операторов

;

;

;

;

;

Блок

Заголовок

Блок

  ;

 .

Программа