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

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

Алфавит - фиксированный для данного языка набор основных сим-волов, допустимых для составления текста программы на этом языке. Синтаксис - система правил, определяющих допустимые конструк-ции языка программирования из букв алфавита. Семантика - система правил однозначного толкования отдельных языковых конструкций, позволяющих воспроизвести процесс обработки данных. При описании языка и его применении используют понятия языка. Понятие подразумевает некоторую синтаксическую конструкцию и оп-ределяемые ею свойства программных объектов или процесса обработ-ки данных. Взаимодействие синтаксических и семантических правил определяют те или иные понятия языка, например, операторы, идентификаторы, переменные, функции «процедуры, модули и т.д. В отличие от естественных языков правила грамматики и семантики для языков программиро-вания, как и для всех формальных языков, должны быть явно, одно-значно и четко сформулированы. Языки программирования, имитирующие естественные языки, обла-дающие укрупненными командами, ориентированными на решение прикладных содержательных задач, называют языками «высокого уров-ня». В настоящее время насчитывается несколько сотен таких языков, а если считать и их диалекты, то это число возросло до нескольких тысяч. Языки программирования высокого уровня существенно отличаются от машинно-ориентированных (низкого уровня) языков. Во-первых, ма-шинная программа, в конечном счете, записывается с помощью лишь двух символов О и I. Во-вторых, каждая ЭВМ имеет ограниченный на-бор машинных операций, ориентированных на структуру процессора. Как правило, этот набор состоит из уравнительно небольшого числа простейших операций, типа: переслать число в ячейку; считать число из ячейки; увеличить содержимое ячейки на +1 и т.п. Команда на машин-ном языке содержит очень ограниченный объем информации, поэтому она обычно определяет простейший обмен содержимого ячеек памяти, элементарные арифметические и логические операции. Команда содер-жит код и адреса ячеек, с содержимым которой выполняется закодиро-ванное действие.

Языки программирования высокого уровня имеют следующие дос-тоинства:

Алфавит языка значительно шире машинного, что делает его гораздо боли выразительным и существенно повышает наглядность и понят-ность текста;

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

Конструкции команд (операторов) отражают содержательные виды обработки данных и задаются в удобном для человека виде;

Используется аппарат переменных и действия с ними;

Поддерживается широкий набор типов данных. Таким образом, языки программирования высокого уровня являются машинно-независимыми и требуют использования соответствующих программ-переводчиков (трансляторов) для представления программы на языке машины, на которой она будет исполняться. Алгоритмическое программирование. На заре вычислительной техники компьютеры имели весьма небольшой по современным меркам объем оперативной памяти, который достигал десятков ки-лобайт. Обычный размер программ тех лет составлял несколько де-сятков строк кода. Такие программы разрабатывали методом алго-ритмического программирования: сначала готовили алгоритм в ви-де наглядной блок-схемы, а потом записывали его операторами того или иного языка программирования. Программа, составленная методом алгоритмического програм-мирования, начинается в одной точке, затем последовательно ис-полняет все инструкции и завершается в другой точке. Конечно, та-кие программы могут иметь и циклы, и ветвления, но общая логика работы программы все-таки последовательная: от начала к концу. Языки программирования 50-70 гг. XX в. были рассчитаны на алгоритмическое программирование. Основными языками тех лет были ФОРТРАН и АЛ ГОЛ-60. Язык ФОРТРАН имел упрощенный синтаксис, и его предпочитали инженеры, а язык АЛГОЛ-60 отли-чался строгими требованиями, и его предпочитали ученые, в основ-ном математики и физики. Несколько позже, в середине 60-х гг. был разработан язык алгоритмического программирования Бейсик, который и сегодня используют для начального знакомства с алгорит-мами и алгоритмическим программированием. Если цель обучения программированию состоит только в освоении приемов создания простейших алгоритмов, то язык Бейсик для этого вполне достато-чен. Процедурное программирование. Понятие подпрограммы было введено еще в ранних языках программирования. В алгоритмиче-ском программировании их использовали для того, чтобы выделить в отдельные блоки некоторые часто повторяющиеся операции. Обычно программа, записанная на алгоритмическом языке, содер-жит до десятка подпрограмм, которые делают ее более понятной. При желании без них можно обойтись, просто текст программы становится несколько более запутанным. В 70-х гг. XX в. размеры оперативной памяти компьютеров дос-тигли сотен килобайт. Появились дисковые накопители, с которыми программы могли обмениваться данными без участия человека. Это позволило увеличить размеры программ до тысяч операторов, и то-гда недостатки языков алгоритмического программирования стали сдерживать работу программистов. Если написать на алгоритмическом языке очень длинную про-грамму, то с ней трудно разобраться. Переходы из одних мест в другие кажутся запутанными, а большое количество переменных не укладывается в голове. Легко забыть, что хранится в той или иной переменной, и перепутать их имена. Выход из тупика был найден в более широком использовании подпрограмм. Программа, записанная на языке процедурного про-граммирования, выглядит как множество циклов, вложенных друг в друга. Она непрерывно «крутится» в этих циклах и время от време-ни вызывает исполнение функций и процедур. Даже если в про-грамме тысячи строк, разобраться с ней становится гораздо проще. Программист всегда может легко определить, внутри какого цикла в данный момент работает программа, и если там происходит какой-то сбой, то быстро выясняются имена подпрограмм, которые могут его вызвать. Алгоритмы для процедурного программирования тоже можно изображать графически, только называются они не блок-схемами, а структурными диаграммами. Вход в программу обычно один, но выходов из нее (в отличие от алгоритмического программирования) может быть много, и они не всегда размещаются в конце листинга. Для выхода из программы достаточно просто из любого места вы-звать завершающую процедуру. Первым языком процедурного программирования стал язык Пас-каль (Pascal). Это не значит, что на нем нельзя писать программы методом алгоритмического программирования, просто для проце-дурного программирования он подходил лучше, чем любой другой язык своего времени. Вскоре появился другой популярный язык процедурного программирования - СИ (С). Все первые языки, предназначенные для создания баз данных (Clipper, dBASE II, Fox-Pro, Paradox и мн. др.), тоже были рассчитаны на процедурное про-граммирование. Средствами процедурного программирования была создана ос-новная масса программ 70-80 гг. XX в. Большинство программ для MS-DOS (текстовых редакторов, бухгалтерских систем, баз данных и т. п.), используемых и по сей день, тоже были созданы этим прие-мом. Так же создавалось и большинство компьютерных игр для MS-DOS вплоть до начала 90-х гг. Усложнение подпрограмм. С развитием процедурного програм-мирования программисты поняли, какую огромную роль имеют подпрограммы. Неожиданно выяснилось, что программы самых разных классов - от служебных до игровых, могут быть очень по-хожи по структуре, а различаются лишь содержанием подпрограмм. Тогда программисты стали пытаться сделать подпрограммы такими, чтобы их можно было использовать многократно в разных проек-тах. Отдельные процедуры и функции стали приобретать такую мощь, что одним вызовом процедуры можно было выполнить сложнейшие действия, для которых раньше требовались недели программирования. Типизация подпрограмм. Чем мощнее становились процедуры и функции, тем выше был соблазн стандартизовать их так, чтобы без изменений использовать в разных программах. И тогда выяснилось, что одни подпрограммы подходят для этого хорошо, а другие - не очень. Нетрудно присоединить к любой программе процедуру или функцию, которая не обменивается с программой параметрами (ти-па RND), а просто выполняет какое-то действие, но чем больше па-раметров участвует в работе процедуры, тем труднее ее встроить в другую программу без специальной настройки. В итоге к середине 80-х гг. XX в. большинство компаний, вы-пускающих программы, занялись стандартизацией используемых процедур. Объектный подход. Чтобы подпрограммы стали стандартными и могли использоваться без переделок (но с поднастройками) повсе-местно, потребовалось изобрести для них классификацию и разра-ботать принципы их создания, документирования и применения. Эти принципы назвали объектно-ориентированным подходом. Достаточно сложные и мощные подпрограммы, поставлявшиеся вместе с языками программирования, стали считаться стандарт-ными объектами. Их можно было использовать в своих программах после несложной настройки параметров. Возьмем, к примеру, под-программу, выполняющую поиск слов в тексте. Ее можно исполь-зовать в разных программах, причем по-разному. При вызове с од-ними параметрами она способна искать заданные слова по содер-жащимся в них символам, при вызове с другими параметрами - по использованному шрифту, а при вызове с третьим набором пара-метров она не только найдет слова с ошибками, но и исправит их. Объекты стали считаться новыми, особыми типами данных, в которых сочетаются программный код и сами данные. Свойства объектов. С понятием объекта неразрывно связано по-нятие его свойств. Все объекты имеют свойства и различимы по своим свойствам. В итоге использование в программах готовых объектов стало очень простым: вызвали объект, настроили его свойства - получили готовый программный код. Использование готовых объектов с настраиваемыми свойствами позволило созда-вать программы без программирования. Если раньше для рисования правильного треугольника на экране программист должен был писать одну процедуру, а для рисования квадрата - другую, то при объектно-ориентированном подходе он может вызвать стандартный объект Shape (Фигура) и настроить его свойство, отвечающее за количество вершин. Более того, он может еще настроить такие свойства, как толщина, цвет и вид линии (сплошная, пунктирная и т. п.). Настройка свойств объектов выпол-няется простой операцией присвоения значений. То есть для про-граммиста свойства объектов - это обычные, хорошо знакомые пе-ременные, которым можно присваивать значения. Итак, объекты в программировании - это аналог подпрограмм. Свойства объектов - это аналог переменных, используемых в подпрограммах, а аналогом рабочего кода стали методы объектов. Методы объектов - это стандартные процедуры, которые свя-заны со своими объектами. Разным типам объектов соответствуют разные свойства и разные методы. Например, объекты, относящиеся к типу «окно», можно открывать и закрывать - это два типичных метода для окон. Объекты, относящиеся к типу «фигура», можно закрашивать разными цветами -за это отвечает метод, называе-мый заливкой. А с объектом «целое число» связаны знакомые нам методы сложения, умножения, деления и вычитания. Классификация объектов. Если бы объект был просто совокупно-стью методов и свойств, то ничего нового он программистам бы не дал - это была бы самая обычная стандартная подпрограмма с па-раметрами. Раньше каждая компания накапливала библиотеки про-цедур для себя, теперь появилась возможность всемирной стандар-тизации. Теперь, когда компания Borland или Microsoft включает в свою систему программирования класс объектов Frame, то любой программист в мире знает, что при его вызове на экране получится окно. Он также знает, как вызвать метод его закрытия или откры-тия, и каким свойствам надо присвоить значения, чтобы окно полу-чилось нужного размера. То же относится к другим объектам: Shape (Фигура), Table (Таблица) и др. Если сравнить программирование со строительством дома, то во времена процедурного программирования каждая фирма сама лепи-ла и обжигала для себя кирпичи (подпрограммы) и сохраняла в тай-не приемы работы с ними. С введением объектно-ориентированного подхода все программисты получили одинаковые заготовки (объек-ты) для кирпичей, труб, плит и панелей. Для их использования надо знать методы и свойства, связанные с каждым типом.

Наследование свойств и методов. Возможность классификации и стандартизации - не единственное достоинство объектно-ориентированного программирования. Важную роль сыграла также возможность наследования свойств и методов. Если бы все про-граммисты составляли свои программы только из заранее заготов-ленных объектов (стандартных классов), то все программы были бы удивительно похожи. С одной стороны, это хорошо, а с другой - плохо. Для служебных программ, например приложений Windows, это хорошо, потому что упрощается их изучение и освоение. Но для развлекательных программ это плохо: им требуется разнообразие. Но программист не обязан пользоваться только готовыми клас-сами объектов. Он может создавать свои объекты - для этого ему достаточно запрограммировать связанные с ними методы и подго-товить свойства. Более того, программист не должен делать это «с нуля». Он может взять какой-то готовый класс объектов и на его основе создать свой. Большинство методов и свойств ему не при-дется создавать - они наследуются автоматически. Конструирование вместо программирования. Создать программу, рисующую на экране красивое окно, весьма непросто, а использо-вать готовый объект Frame и настроить его свойства, чтобы окно было таким, каким надо, может каждый начинающий программист. После настройки свойств объекта он получает готовый программ-ный код длиной в десятки килобайт, хотя на самом деле присвоил всего лишь несколько значений переменным, выражающим свойст-ва объекта. Так благодаря объектно-ориентированному подходу программи-рование стало превращаться в конструирование программ из гото-вых блоков. Единственное, что остается для ручного программиро-вания, - запись строк, в которых свойства объектов получают нужные значения. Иногда программисты сталкиваются с тем, что для своих задач не находят готовых объектов. В этом случае им приходится дейст-вительно серьезно заниматься программированием, чтобы создать методы и описать свойства нестандартных объектов. Впрочем, и эта задача значительно упрощается, если программист не изобретает новый объект «с нуля», а использует для его создания другой, ранее созданный объект. Таким образом, объектно-ориентированный подход позволил создавать новые программы путем перенастройки старых. Это позволило значительно поднять производительность труда про-граммистов и перейти во второй половине 90-х гг. к созданию про-грамм размером в миллионы строк кода. Наглядный пример - опе-рационная система Windows. Над первой версией (Windows 95) компания Microsoft работала много лет. Сегодня новые версии Win-dows выходят каждый год: 1998 Windows 98 1999 Windows 98 SE 2000 Windows 2000, Windows Me 2001 Windows XP (версии Ноте и Professional) 2002 Windows XP (Server и Advanced Server). Объектно-ориентированные языки программирования. Переход к объектно-ориентированному программированию в середине 80-х годов XX в. состоялся не сразу, а только после создания языков программирования нового поколения. Вместе с новой концепцией программирования были разработаны и новые компиляторы, и биб-лиотеки объектов. Одним из первых объектно-ориентированных языков стал язык СИ++ (C++). Язык Паскаль (Pascal) развился в язык Object Pascal. Появились и другие объектно-ориентированные языки программирования, например язык Java, разработанный кор-порацией Sun Microsystems, - ныне он широко используется при создании приложений, работающих в Интернете. Визуальное программирование В операционной системе Win-dows немало стандартных элементов управления, таких как окна, меню, списки, переключатели, флажки и пр. Стандартны приемы работы с мышью: наведение, щелчок, двойной щелчок и прочие. Эти элементы и приемы управления стали настолько стандартными, что их унаследовало и большинство программ, написанных для ра-боты с Windows. Стандартизация графических элементов управле-ния и приемов работы с ними с помощью мыши позволила вновь изменить стиль программирования и перейти к так называемому визуальному программированию.

Системы визуального программирования. Переход к визуальному программированию наметился еще во времена операционной среды Windows 3.1 (1992-1994), но подлинное развитие новый метод по-лучил только после 1995 г., когда стали появляться специальные программные комплексы, получившие название систем визуального программирования. По-английски они также называются RAD-системами (RAD - Rapid Application Development - среда быст-рой разработки приложений). Языку Object Pascal соответствует система Delphi, языку Бейсик (Basic) - система Visual Basic, языку СИ ++ (C++) - система C++ Builder, языку Java - система Java Builder. Принципы визуального программирования. До визуального про-граммирования программист использовал в работе печатные спра-вочники или программные справочные системы, в которых были описаны правила создания объектов из стандартных классов, при-ведены основные методы и свойства объектов и правила их исполь-зования и настройки. Визуальное программирование позволило во многих случаях отказаться от справочников и создавать объекты с помощью мыши, что и удобно, и наглядно. Общий принцип визу-ального программирования такой. 1. Стандартные классы объектов, например такие, как окна, кнопки, списки, поля, переключатели, флажки и мн. др., представлены в системе визуального программирования в ви-де значков на инструментальной панели. Эти значки называ-ются компонентами. То есть компоненты - это инструменты для создания объектов. 2. Для вставки объекта в свою программу программист выбира-ет нужный компонент, после чего с помощью мыши помеща-ет в заготовку окна (она называется формой) заготовку буду-щего элемента управления. 3. Поместив объект на форму, программист щелчком мыши вы-зывает окно свойств этого объекта и настраивает их. После настройки объект приобретает размеры, местоположение, имя, надпись и т. п. Свойства могут иметь внутренние свой-ства, например, надпись на кнопке может иметь заданный цвет, шрифт, размер и т. п.

4. Точно так же с помощью мыши программист может вызвать окно кода, связанного с объектом, и выполнить настройку ме-тодов объекта. Например, он может сделать так, чтобы при открытии окна раздавался звук, а перед его закрытием возникало предупреждающее сообщение. 5. После размещения всех необходимых элементов управления на форме, настройки их свойств и подключения необходимых методов программа готова. С помощью мыши выдается команда на ее трансляцию. Системы Delphi и C++ Builder выполняют компи-ляцию, а система Visual Basic - интерпретацию. Событийное программирование Существует три стиля управле-ния: командный, диалоговый и пакетный. Это относится не только к программированию, а вообще к любому управлению. Подобие диалоговой работы впервые возникло во второй половине 60-х гг., ко-гда в больших ЭВМ появились многозадачные операционные сис-темы, работавшие в режиме разделения времени. Компьютер одно-временно работал с десятками пользователей, мгновенно пере-ключаясь между ними и их задачами. Каждый пользователь пола-гал, что компьютер работает только с ним. Тогда впервые программисты стали общаться с ЭВМ напрямую. Их рабочие места осна-стили терминалами (монитор + клавиатура). Но диалог происходил не внутри программы, а на уровне операционной системы, то есть либо перед исполнением программы, либо после него. Получив ре-зультат расчета, программист мог повторить расчет с другими дан-ными или внести изменения в программу и вновь запустить ее ис-полнение. До середины 70-х гг. в языках программирования не бы-ло средств для организации диалога. Такие языки появились только после создания персональных компьютеров. Все диалоговые возможности компьютера основаны на том, что программа работает в некоем бесконечном цикле, в ходе которого бесконечно опрашивает внешние устройства управления (клавиату-ру, мышь, модем и др.), а после получения отклика входит в другой цикл и опять что-то опрашивает. Вплоть до конца 80-х гг. програм-мисты отводили сотни строк своих программ реализации этих цик-лов. В итоге прием стал настолько стандартным, что его передали операционной системе, и начиная с Windows 3.0 программист мог не опрашивать устройства управления, а ждать сигнала от Windows. Для операционной системы Windows нажатие клавиш на клавиату-ре, перемещение мыши и нажатие ее кнопок, открытие и закрытие окон, поступление сигналов от внутренних часов, модема, принтера и прочих периферийных устройств, называются событиями. С раз-ными объектами Windows связаны разные события. Например, для окна событиями являются его открытие и закрытие; для текстового поля - его изменение, а для командной кнопки - щелчок мышью, совершенный над ней. При получении от операционной системы сигнала о том, что произошло некое событие, связанное с объектом, автоматически запускается подпрограмма-метод, являющаяся обработчиком данного события. В ней программист может записать ал-горитм действий, которые он хочет выполнить при наступлении со-бытия. Выше мы говорили о том, что с объектами связаны две характеристики: свойства и методы. Теперь мы можем добавить третью - события, связанные с объектами. В качестве реакции на событие объект автоматически запускает подпрограмму-метод, пред-варительно подготовленную программистом, а она, в свою очередь, может вызвать изменение свойств данного объекта или иных объек-тов, а также вызвать другие события, связанные с другими объектами и т. д. Последовательность исполнения программы при ис-пользовании событийного механизма зависит от порядка, в котором наступают те или иные события, и от реакции программных объектов на эти события. Практически все прикладные программы Win-dows основаны на событийном механизме. Действие инструментов рисования в программе Paint зависит от того, на каком из них произошел щелчок (какой инструмент избрал пользователь) и как он управляет мышью в ходе рисования. Действие процедур формати-рования в программе WordPad также зависит от того, какие экран-ные элементы управления зафиксировали событие. Событийный механизм не является свойством тех или иных языков программи-рования - это свойство (и особенность) операционной системы компьютера. При объединении событийного механизма, предостав-ляемого операционной системой, и объектно-ориентированного подхода, предоставляемого языком программирования, образуется отличная возможность для простой реализации диалога с компьютером. Это сочетание и называют событийным программировани-ем.

Конец

Начало

Повторять

Начало

Псевдокоды

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

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

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

алгоритм алгоритм Евклида;

пока первое число не равно второму

если числа равны

то стоп все;

иначе определить большее из двух чисел;

з аменить большее число на разность большего и меньшего чисел

конец;

взять первое число в качестве ответа

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

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

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

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

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

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

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

Первый машинный язык был придуман в 1941 году Конрадом Цузе, который является изобретателем аналитической машины. Чуть позже, в 1943 г., Говард Эйкен создал машину "Марк-1", способную считывать инструкцию на уровне машинного кода.

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

Классификация языков программирования

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

• Аспектно-ориентированные (основная идея - разделение функциональности для увеличения эффективности программных модулей).
• Структурные (в основе лежит идея создания иерархической структуры отдельных блоков программы).
• Логические (в основе лежит теория аппарата математической логики и правил резолюции).
• Объектно-ориентированные (в таком программировании используются уже не алгоритмы, а объекты, которые принадлежат определенному классу).
• Мультипарадигмальные (сочетают в себе несколько парадигм, и программист сам решает, каким языком воспользоваться в том или ином случае).
• Функциональные (в качестве основных элементов выступают функции, которые меняют значение в зависимости от результатов вычислений исходных данных).

Программирование для начинающих

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

• Basic придуман в 1964 году, относится к семейству высокоуровневых языков и используется для написания прикладных программ.
• Python ("Питон") довольно легко выучить благодаря простому читаемому синтаксису, преимущество же в том, что на нем можно создавать как обычные десктопные программы, так и веб-приложения.
• Pascal ("Паскаль") - один из древнейших языков (1969 г.), созданных для обучения студентов. Его современная модификация имеет строгую типизацию и структурированность, однако "Паскаль" - вполне логичный язык, который понятен на интуитивном уровне.

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

Новички имеют возможность ускорить изучение программирования и его основ благодаря специальным инструментам. Основной помощник - это интегрированная среда разработки программ и приложений Visual Basic («Визуал Бейсик» одновременно является и языком программирования, который унаследовал стиль языка Basic 1970-х годов).

Уровни языков программирования

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

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

Языки программирования высокого уровня: список

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

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

Самые используемые языки программирования

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

• языки ООП: Java, C++, Python, PHP, VisualBasic и JavaScript;
• группа структурных языков: Basic, Fortran и Pascal;
• мультипарадигмальные: C#, Delphi, Curry и Scala.

Область применения программ и приложений

Выбор языка, на котором написана та или иная программа, во многом зависит от области ее применения. Так, например, для работы с самим "железом" компьютера (написания драйверов и поддерживающих программ) лучшим вариантом станет C ("Си") или С++, которые входят в основные языки программирования (список смотрите выше). А для разработки мобильных приложений, в том числе игр, следует выбрать Java или С# ("Си-шарп").

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

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

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

Другое направление разработки языков программирования связано с созданием специализированных (проблемно-ориентированных) программных систем и сред для пользователей-непрограммистов (технологов, конструкторов, экономистов и др.). Примерами таких систем и сред являются САПР различного назначения, автоматизированные обучающие системы, системы дистанционного обучения, экспертные и моделирующие системы в экономике и т.д. Назначение соответствующих проблемно-ориентированных языков, используемых в подобных системах, часто отражено в их названиях, например: «Язык описания схем технологического оборудования», «Язык описания сценария обучения», «Язык моделирования ситуаций» и т.п.

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

формальными языками. Что же такое формальный язык? В самом общем виде на этот вопрос можно ответить так: язык - это множество предложений, а формальный язык - это язык, предложения которого построены по определенным правилам.

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

И естественные языки, и языки программирования - бесконечные множества. На языке программирования можно написать неограниченное число программ.

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

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

Существуют различные способы описания синтаксиса формальных языков (способам описания посвящена вторая глава учебного пособия). Наиболее используемыми в языках программирования являются форма Бэкуса - Наура (БНФ) и синтаксические диаграммы.

БНФ была разработана Бэкусом и впервые применена для строгого описания языка АЛГОЛ-60 в 1963 г. Эта форма используется как для описания структуры языка в целом, так и для описания отдельных языковых конструкций (подмножеств языка) и его элементов - операторов, идентификаторов, выражений, чисел и др.

Ниже приведены примеры БНФ, определяющие синтаксис десятичных целых чисел и синтаксис арифметических выражений, содержащих операции «+» и «*».

БНФ десятичных целых чисел:

= 0|1|...|9

БНФ арифметических выражений:

:= () а

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

В левой части БНФ в угловых скобках записываются названия определяемых синтаксических категорий (понятий, единиц), символ «:= » означает «есть», «это», «определяется как», символ «|» означает «или».

Правая часть БНФ определяет возможные варианты конструирования конкретных значений этих категорий, в данном случае - значений десятичных чисел и конкретных арифметических выражений. БНФ содержит также и алфавит символов, из которых составляются эти значения. Для десятичных целых чисел алфавит - это множество {+,-, 0, 1,..., 9}, а для выражений - это множество {а, *, +, (,)}.

Процесс конструирования значений синтаксической категории состоит в выводе этих значений путем последовательных подстановок правых частей правил БНФ в левые. Ниже приведены выводы числа « - 320» и выражения «а+а*а» с использованием соответствующих БНФ:

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

Именно появление БНФ стимулировало быстрое развитие теории формальных языков и ее применение к прикладным задачам разработки языков программирования и проектирования трансляторов.

Если в рассмотренных БНФ каждую синтаксическую категорию из левой части правил обозначить через А, В и С соответственно, а вместо символа:= использовать -то будут получены следующие формы:

Для десятичных целых чисел:

А->В+В-В В^>СВС С-> 0 | 11... | 9

Для арифметических выражений:

А^А+ВВ

В->В*СС

С^>(А)а

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

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

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

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

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

то можно построить множество предложений с различными смыслами. Например, предложения «автомобиль едет» и «автомобиль думает» правильны с точки зрения синтаксиса. Однако первое предложение имеет корректный смысл, о втором можно сказать, что оно бессмысленно. Таким образом, семантика определяет множество смыслов и допустимых соответствий между предложениями (текстами) и смыслами.

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

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

будет семантически некорректным, если а имеет значение 10,5 (а = 10.5), а b - значение ложь (b = false).

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

Многие аспекты семантики языка программирования можно описать в виде перечня семантических соглашений, которые носят общий, неформальный характер. Например, программистам известны такие соглашения, как «каждый идентификатор в блоке описывается один раз», «переменная должна быть определена до ее использования» и т.д.

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

Что касается прогнозов на перспективы дальнейшего развития языков программирования, то здесь существует достаточно широкий спектр мнений, вплоть до диаметрально противоположных. Некоторые авторы считают, что каждый из языков имеет свои семантические особенности, которые делают его удобным и привлекательным для той или иной области программирования (например, Пролог и Лисп - ориентированы на решение задач искусственного интеллекта; Фортран - наиболее эффективен при решении вычислительных задач; Кобол - используется для экономических расчетов и т.д.). Поэтому следует создавать все новые языки, обладающие специфическими возможностями или периодически обновлять уже имеющиеся версии, а не пытаться создать универсальный язык. В подтверждение этой точки зрения приводится аргумент, что все амбициозные проекты по созданию универсального языка потерпели неудачу (достаточно вспомнить несбывшиеся надежды, связанные с разработкой языков АДАиПЛ-1).

Другая часть авторов считает, что со времени опубликования стандартов первых языков программирования - Фортран, Алгол и др. - в 60-х гг. XX в., произошла «стабилизация» языков в том смысле, что сходные по назначению языковые конструкции в разных языках имеют практически одну и ту же семантическую основу, несмотря на различия в лексике и синтаксисе. Поэтому, как только удастся формально определить эту общую семантическую базу, можно будет приступить к созданию универсального языка, который уже будет не языком программирования в традиционном понимании, а заготовками семантических конструкций. Программа будет представляться набором этих конструкций, а текстовый редактор уступит место структурному редактору. В качестве примера частичной реализации этого подхода приводятся визуальные среды программирования, подобные Delphi, C++ Builder и др.

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

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

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

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

Формальные языки и грамматики

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

знаковой системы, т.е. множества допустимых последовательностей знаков;

множества смыслов этой системы;

соответствия между последовательностями знаков и смыслами, делающего «осмысленными» допустимые последовательности знаков.

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

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

Множество А* называют итерацией алфавита А.

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

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

Альтернативным набором терминов для буквы, алфавита или цепочки (слова) является набор: слово, словарь и предложение соответственно. Совокупность цепочек (или предложений) называется языком. Формально язык L над алфавитом А.

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

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

Систематическое использование математических методов для описания языков программирования начинается с 1960-х годов. Тогда было обнаружено, что формы Бэкуса, которые использовались для описания синтаксиса языка АЛГОЛ-60, имеют строгое формальное обоснование с помощью средств математической лингвистики. С этого времени и началась история развития и применения формального математического аппарата -- теории формальных языков и грамматик -- для проектирования и конструирования трансляторов.

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

Формальное определение грамматики

Форма Бэкуса-Наура

Грамматика определяется следующим образом:

VT - множество терминальных символов (множество символов алфавита);

VN - множество нетерминальных символов (символов, определяющих понятия языка

P - множество правил;

S - целевой символ грамматики, аксиома.

Рассмотрим формальное описание грамматики по Бэкусу для целых десятичных чисел.

G({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -}, {<число>, <цифра>}, P, <число>)

P - правило генерации лексем языка:

<число> -> [(+,-)]<цифра>[<цифра>]

<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.

Необязательный элемент внутри правила заключается в квадратные скобки [...].

Альтернативные элементы обозначаются вертикальным списком вариантов, заключенным в фигурные скобки {...}.

Необязательные альтернативные варианты обозначаются вертикальным списком вариантов, заключенным в квадратные скобки [...].

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

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

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

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

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

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

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

Теория формальных грамматик занимается описанием, распознаванием и переработкой языков. Она позволяет ответить на ряд прикладных вопросов. Например, могут ли языки из некоторого класса Z распознаваться быстро и просто; принадлежит ли данный язык классу Z; существуют ли алгоритмы, которые давали бы ответ на вопросы типа: «Принадлежит или нет к языку L цепочка а?» и т.д.

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

с помощью порождающей процедуры;

с помощью распознающей процедуры.

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

Вторая -- с помощью некоторого абстрактного распознающего устройства (автомата).

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

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

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

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

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

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

Класс 2. Контекстно-свободные грамматики. Замена нетерминала происходит без учета контекста. КС-грамматики играют главную роль при формальном изучении синтаксиса языков программирования и построении блока синтаксического анализа транслятора.

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

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

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

В соответствии с типами грамматик, языки делятся на 4 типа:

<тип 0> - языки с фразовой структурой. К этому типу относятся все естественные языки.

<тип 1> - контекстно-зависимые языки. Языки и грамматики применяются в анализе и переводе текстов на естественных языках. На основе таких грамматик может выполняться автоматизированный перевод с одного естественного языка на другой.

<тип 2> - контекстно-свободные языки. Контекстно-свободные языки лежат в основе синтаксических конструкций современных языков программирования.

<тип 3> - регулярные языки. Являются самыми распространенными и широко используемыми в области проектирования вычислительных систем. Для работы с ними используют регулярные множества, регулярные выражения и конечные автоматы.

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

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

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

где V={} - входной алфавит;

Q={} - алфавит состояний;

Функция переходов;

Начальное состояние автомата;

F - конечное состояние автомата;

Конечный автомат условно можно представить следующей схемой (рисунок 2.1).

Рисунок 2.1 - Упрощенная схема конечного автомата

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

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

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

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

Распознаватели можно классифицировать в зависимости от вида составляющих их компонентов:

Считывающего устройства;

Устройства управления памяти.

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

По виду устройств управления, распознаватели бывают:

Детерминированные;

Недетерминированные.

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

По видам памяти, распознаватели бывают:

1) без памяти;

2) с ограниченной памятью;

3) с неограниченной памятью.

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

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

Магазинная память организована по принципу "первым пришел, последним вышел".

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

1) лексический анализ;

2) синтаксический анализ;

3) семантический анализ;

4) синтез объектной программы.