Программно-математическое обеспечение. Формализованные (формальные) языки Характеристики искусственных языков
За последние 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 и др.
Естественные языки программирования (ЕЯП) определяют следующий шаг развития языков программирования, отличаясь отязыков запросов тем, что пользователь любого уровня освобождается от необходимости освоения каких-либо специальных словарей, грамматики и синтаксиса –предложения ЕЯП весьма похожи на предложения обычной человеческой речи. ЕЯП еще дальше отдаляют пользователя от ВС и ее СПО, существенно повышая интеллектуальный уровень интерфейсапервого с вычислительными ресурсами. В настоящее время на ПК успешно используются ЕЯП с ограниченными возможностями, такие, какClout, Q&A, Savvy Retriever, HAL и др. Основные разработки ЕЯП связываются с задачами ИИ и интеллектуализацией интерфейса в СУБЗ. В этом направлении непосредственную прикладную значимость (особенно в связи с массовым применением ПК) получили различного рода ЕЯП-интерфейсы с ЭВМ. Из ЕЯП такого типа можно отметитьрегламентированные языки (меню, анкетные, инструкций и др.), играющие большую роль в интеллектуализации интерфейса с ЭВМ при использовании различного рода ППО; большую роль они играют в различных системахинтервьюирования ,обучающих, экспертных и др., однако их использование жестко регламентировано определенными рамками, а в случае переноса систем срегламентированными ЕЯП на другие типы ЭВМ зачастую требуются существенные их переделки. Поэтому для более гибкого и естественного общения пользователя с ЭВМ более адекватен именноестественный язык.
Проблема использования естественного языка для организации интерфейса синтеллектуальной ВС на содержательном уровне с интересными иллюстративными примерами хорошо изложена в специальной литературе. Однако по данному вопросу следует сделать одно существенное замечание. Зачастую принимается на веру, чтоестественный язык является наилучшим способом организации интерфейса пользователя с ЭВМ. Данное предположение даже положено в основу проекта ЭВМ 5-го поколения. Однако оно не представляется нам столь ужочевидным.
В целом ряде случаев естественный язык выразителен менееграфического, тщательно отработанныйформальный язык предметной области бывает выразительнееестественного языка (также имеющегонемало недостатков). Более того, многие предметные области (математика, физика, химия, биология и др.) имеют свойязыковый сленг, в ряде случаев существенно отличающийся от обычного естественного языка. Поэтому, развитыйязыковый интерфейс может являтьсясимбиозом естественного иформальных языков либо представлять собойиерархию языков:естественный язык -формальный {структурированный) язык ЭВМ. В любом случае, данная проблема пока еще весьма далека от своего полного решения.
Лекция № 34 прикладное программное обеспечение
План лекции.
1. Прикладное программное обеспечение ЭВМ.
2. Классы пакетов прикладных программ.
3. Основные прикладные средства.
4. Качественные характеристики программного обеспечения.
34.1. Прикладное программное обеспечение эвм
В предыдущем разделе на самом общем уровне обсуждалась структура ППО, основу которого составляют ППП различных типов, назначения и организации. В связи с интенсивным вторжением в человеческую деятельность ПК и массовым характером пользования быстро растет удельный вес ППП в ПО ЭВМ. Учитывая важность данной компоненты, обеспечивающей интерфейс высокого уровня непрофессионального пользователя с вычислительными ресурсами ЭВМ, рассмотрим ее несколько детальнее, основываясь на трех уровнях:
(1) принцип организации ППП;
(2) требования к профессиональной подготовке пользователя;
(3) основные современные группы ППП.
Одной из характерных черт современных ППП является использование принципа синтеза рабочих программ из подпрограмм на основе содержательногоописания задачи на проблемно-ориентированном языке, близком к понятиям и терминам проблемной области пользователя. При таком подходе пользователь посредством специальногоязыка формирования пакета (ЯФП) содержательноописывает отдельную задачу или класс задач(требующих решения), формируяпрограмму генерации конкретного ППП из набора средствфиксированной илирасширяемой программнойсреды (рис. ЗЗа). На основе данной программы генерируется ППП для конкретного приложения со своимвходным языком (ВЯ) общения с пользователем. После создания ППП пользователь работает с ним в процессе решения своих задач. Как правило, описанный принцип организации используется дляпроблемно-ориентированных ППП, когда решаемый ими круг задач достаточно четко определен и задачи связаны какими-либо общими характеристиками, например численными методами, статистическим анализом, моделированием в конкретной предметной области и т.д. Спектр ППП подобной организации весьма широк - отбиблиотечной организации подпрограмм определенной направленности (например, статанализа) досложной программной среды (рис. ЗЗа), требующей специального ЯФП для формального описания предметной области, на которую должен быть ориентирован(сгенерирован) ППП. При создании конкретного пакета используются как средства собственно егопрограммной среды, так и вновь программируемые.
Создание ППП - достаточно длительный и трудоемкий процесс, требующий использования специальных инструментальных средств. Однако в общем случае такие системы оказываются весьма сложными, а создаваемые ими пакеты достаточно далекими от требуемой эффективности. Поэтому одним из способов устранения указанных недостатков является создание специализированных инструментальных систем, ориентированных насемейства проблемно-ориентированных ППП соднородными входными языками иодинаковыми принципами функционирования. Из отечественных средств данного типа можно отметитьмета системы САТУРН иPACKAGE . Так, вPACKAGE подобно другим аналогичным системам выделяются две вышеуказанных фазы:описание искомого ППП на специальном ЯФП (подсистемаКонструктор) игенерация ППП с его входным языком (подсистемаПрепроцессор); при этом обеспечивается технологичность программирования на основных этапахгенерации пакета: (1) описание класса решаемых пакетом задач и методов их решения; (2) создание входного языка ППП; (3) программирование и отладка необходимых программных модулей.
При указанной технологии разработка конкретного ППП начинается с описания на ЯФП подлежащих решению задач в терминах предметной области, т.е. производится программирование функциональных свойств искомого объекта - ППП посредством специальногометаязыка, включаявходной язык, на котором пользователь в последующем должен будет общаться с искомым пакетом. Результатом выполнения оттранслированной ЯФП-программы является искомый ППП с заданным емувходным языком. Таким образом, данная технология в общем случае предполагает наличие двух уровней пользователей- системного, генерирующего ППП с заданной предметной областью, ипроблемного, использующего созданный ППП посредством еговходного языка, близкого к понятиям предметной области или кестественному языку. Естественно, в случае достаточно простой программной среды, узко ориентированного класса решаемых задач и простого ЯФП функциисистемного ипроблемного пользователя может совмещать одно и то же лицо.
В настоящее время компьютерное экспериментирование (КЭ) становится одним из основных средств исследования крупных научно-инженерных, технических и общественных проблем: в космонавтике, ядерной физике и энергетике, прогнозировании и др.,сложность которых не позволяет, с одной стороны, достаточно строго исследовать иханалитически, а с другой - исследовать весьма дорогостоящими экспериментальными методами. Метод КЭ предполагает использование проблемными пользователями наборов различного назначения ППП, которые в силу экспериментального характера работы в значительной степени подвержены различного рода изменениям. Рассмотренный принцип организации ППП обладает достаточно гибкимиадаптационными возможностями для автоматизации подобного типа работ, хорошо отвечая как задачам модификации, так и расширению исходной программной среды пакета. Для повышения интеллектуального уровня интерфейса с пакетом, особенно эксплуатирующимся на ПК массовым пользователем, важную роль играет егографическая составляющая, которая также определяется в развитыхметасистемах проектирования игенерации ППП. Наряду с этим для повышениялогического уровня интерфейса уже существующих популярных ППП создаютсяграфические метасистемы, существенно расширяющиеграфический интерфейс пакетов, делая его более дружелюбным.
В отличие от рассмотренной организации ППП, обеспечивающей их гибкость и адаптируемость к предметной области и выдвигающей ряд требований к профессиональному уровню пользователя, для массового пользователя используется, как правило, жесткая организация, не позволяющая ему модифицировать пакет. Такая организация имеет два основных исполнения: (1) высокийлогический уровеньвходного языка пакета (ВЯП), ориентированного на пользователя и предметную область, ивнутреннего языка пакета, позволяющего создавать в его среде модули, обеспечивающие функции расширения пакета, а также создание документов для конкретных приложений пакета; (2) интерфейс с пакетом обеспечивается только на уровне проблемно-ориентированного ВЯП. Вобоих случаях практика создания ВЯП для пакета использует два основных подхода: (1) создание языка на основе уже существующего ЯВУ (который, как правило, является иязыком реализации пакета) и (2) разработкаоригинального входного языка. Припервом подходе существенно упрощается реализациявходного языка, тогда как для непрофессионального пользователя возникают дополнительные сложности по освоению пакета.Второй подход требует в ряде случаев значительно больших затрат на разработкувходного языка, однако позволяет сделать его легким в освоении и использовании (язык меню, элементы естественного профессионального языка, язык запросов, язык диалоговой графики и др.).
При этом спектр пользовательской ориентированности ВЯП лежит в весьма широком диапазоне - от начинающего пользователя до профессионала в некоторой предметной области. Например,игровые пакеты имеют высокопонятийныйграфический интерфейс и не требуют особого освоения; пакетытекстовых редакторов также имеют развитый языксистемы меню, достаточно высокого понятийного уровня (например пакетMs Word); проблемно-ориентированные пакеты (например,MathCAD, Reduce. Mathematica обеспеченывходным языком, ориентированным на знакомого с математическим языком пользователя. Наконец,внутренний язык пакета ориентирован, главным образом, на программирование функций, непосредственно не поддерживаемых пакетом, либо программированиедокументов для конкретных его приложений. Часто в качествевнутреннего языка используется языкреализации пакета или его модификации (например пакетыReduce. Mathematica и др.); однако в ряде случаеввнутренний язык имеет ориентацию напредметную область пакета имеетвходной язык на основе простой и дружелюбной системы меню ивнутренний С-подобный SALT-язык, позволяющий легко и быстро создавать и выполнять в среде пакета SLT-документы (программы, модули для конкретных приложений пакета)].Сложность внутренних языков ППП различна, требует определенного программистского навыка для их освоения; однако они позволяют создавать развитые библиотеки документов, выполнение которых в среде пакета позволяетсущественно расширять его функции и область приложений.
Наконец, жесткая организация в сочетании с предметно-ориентированным ВЯП ориентирована на относительно небольшие по объему пакеты либо пакеты специальной направленности, но массового применения. В качестве ВЯП, как правило, выступают языки типа меню, диалоговой графики, запросные и др., ориентированные на непрофессионального пользователя. Примером такойорганизации могут служить простые пакеты текстовых редакторов, специальные пакеты и т.д. Вместе с тем более развитые из них располагают макросредствами, позволяющими оформлять на уровнемакросов наиболее часто используемыепоследовательности операций с пакетом (напримерChiWriter , Ms Word , Word Perfect vs . др.).
Согласно своей организации пакеты допускают различных уровней и типов расширения со стороны пользователя: от возможностиполной генерации пакета на конкретные условия применения (с учетом возможности расширения его программной среды) до отсутствия какой-либо возможности расширения пакета. Однако в большинстве случаев современные ППП допускаютрасширения, из которых для проблемного пользователя наиболееестественным способом является созданиебиблиотек (документов, программ, модулей, макросов) навнутреннем языке пакета, решающихзадачи в некоторой предметной области и выполняющихся в среде самого пакета. Целый ряд пакетов допускаютрасширение своих возможностей путем создания каквнешних (относительно основных модулей пакета), так ивстроенных функций. Однако в целяхсовместимости пакетов наиболее целесообразным является расширение пакета за счет еговнешних функций и средств, не дающее возможности пользователю модифицировать (с определенными оговорками)базовую часть пакета, поставляемую и поддерживаемую фирмой-разработчиком.
Большинство современных ППП перед началом использования требуют проведения операции инсталляции, состоящей в настройке пакета на конкретные условияэксплуатации (конфигурация аппаратных средств, режим решения задач и др.). Как правило, инсталляция проводится один раз и выполняется либовнутренними средствами пакета(Ms Word, Quattro и др.), либо посредствомспециальных утилит(Sprint, Mathematica и др.). Для простых пакетовинициализация, как правило, производится каждый раз автоматически при их загрузке средствами операционной системы(Framework , AutoSketch и др.).
Документация, поставляемая с пакетом, должна включать рекомендации по его инсталляции на конкретные условия применения. Рассмотревтри основных принципа организации ППП, кратко обсудимфункциональное наполнение пакетов, которое нафайловом уровне в общем случае можно представить, как: (1)модули обеспечения основных функций пакета; (2) конфигурационные файлы; (3) утилиты общего назначения и расширяющие функции пакета; (4) специализированная БД; (5) библиотека документов для выполнения их в среде пакета; (6) файлы, содержащие справочную, лицензионную информацию по пакету, а также документацию. Как правило, во всех современных ППП прослеживается отмеченнаяструктуризация ихфайловой системы.
Ряд известных пакетов (Expert Choice , Mathematica , MathCAD , Ms Excel и др.) поставляются также на уровне иллюстративных и/или обучающих версий, которые функционально ограничены относительно основного пакета, но позволяют проводить иллюстрацию пакета в действии, а также обучать основам работы в его среде, что в целом ряде случаев позволяет сделать более осознанный выбор данного средства для последующего коммерческого использования.
Первое, что отличает один язык программирования от другого -- это их синтаксис. Основное назначение синтаксиса -- предоставить систему обозначений для обмена информацией между программистом и транслятором. Однако, при разработке деталей синтаксиса чаще исходят из второстепенных критериев, назначение которых: сделать программу удобной для чтения, написания и трансляции, а также сделать ее однозначной. Если удобство чтения и записи программ необходимы для пользователя языка программирования, то простота трансляции и отсутствие разночтений в языке имеют отношение к нуждам транслятора. Эти цели, в общем случае, противоречивы, и нахождение приемлемого компромисса при их решении является одной из центральных задач при разработке языка программирования.
Разработка нового языка программирования начинается с определения его синтаксиса. Для описания синтаксиса языка программирования, в свою очередь, нужен также некоторый класс. Язык, предназначенный для описания другого языка, называют метаязыком. Язык, используемый для описания синтаксиса языка, называют метасинтаксическим языком. В метасинтаксических языках используется специальная совокупность условных знаков, которая образует нотацию этого языка.
Исторически первым метасинтаксическим языком, который использовался на практике для описания синтаксиса языков программирования (в частности, Алгола-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) синтез объектной программы.
Язык программирования - искусственный (формальный) язык, предназначенный для записи программ для исполнителя (например, компьютера или станка с числовым управлением). Язык программирования задается своим описанием. Описание языка программирования - это документ, специфицирующий возможности алгоритмического языка. Обычно описание содержит:
· алфавит допустимых символов и служебных (ключевых) слов;
· синтаксические правила построения из алфавита допустимых конструкций языка;
· семантику, объясняющую смысл и назначение конструкций языка.
Языки программирования служат для представления решения задач в такой форме, чтобы они могли быть выполнены на ЭВМ.
Машинный язык, который состоит из команд процессора ЭВМ, также является языком программирования. Но алгоритмы, записанные на машинном языке, трудны для чтения даже программисту-разработчику, кроме того, работа с таким языком требует знания архитектуры конкретного компьютера, поэтому в программировании, как правило, используют языки более высокого уровня, чем машинные языки. Язык высокого уровня - это язык программирования, понятия и структура которого удобны для восприятия человеком и не зависят от конкретного компьютера, на котором будет выполняться программа.
Для того чтобы программу, записанную на языке программирования высокого уровня, можно было выполнить на компьютере, ее надо перевести на машинный язык. Программное средство, выполняющее эту функцию, называется транслятором.
Транслятор - это программа, которая считывает текст программы, написанной на одном языке, и транслирует (переводит) его в эквивалентный текст на другом языке (обычно на машинном языке). Трансляторы бывают двух основных видов: компиляторы и интерпретаторы .
Компилятор преобразует текст исходной программы в набор инструкций для данного типа процессора (машинный код) и далее записывает его в исполняемый файл (exe-файл), который может быть запущен на выполнение как отдельная программа. Другими словами, компилятор переводит программу с языка высокого уровня на низкоуровневый язык.
Интерпретатор в результате трансляции выполняет операции, указанные в исходной программе. При этом программа остается на исходном языке и не может быть запущена на выполнение без интерпретатора.
Разделение на компилируемые и интерпретируемые языки является несколько условным. Так, для любого традиционно компилируемого языка, как, например, Pascal, можно написать интерпретатор, а для любого интерпретируемого языка можно создать компилятор, - например, язык Бейсик, изначально интерпретируемый, может компилироваться без каких бы то ни было ограничений.
Некоторые языки, например Java и C#, находятся между компилируемыми и интерпретируемыми. А именно, программа компилируется не в машинный язык, а в машинно-независимый код низкого уровня, байт-код. Далее байт-код выполняется виртуальной машиной. Для выполнения байт-кода обычно используется интерпретация. Подобный подход в некотором смысле позволяет использовать плюсы как интерпретаторов, так и компиляторов.
Со времени создания первых программируемых машин человечество придумало уже более двух с половиной тысяч языков программирования. Количество языков программирования постоянно растет, хотя этот процесс явно замедлился. Некоторыми языками пользуется только небольшое число программистов, другие становятся известны миллионам людей. Часть из них узкоспециализированны (предназначены для решения определенного класса задач), а часть - универсальны. Профессиональные программисты иногда применяют в своей работе более десятка разных языков программирования.
Классификацию языков программирования можно вести по нескольким критериям: машинно-ориентированные (ассемблеры) и машинно-независимые, специализированные и универсальные.
К специализированным языкам можно отнести язык АРТ (A utomatically P rogrammed T ools ) - первый специализированный язык программирования для станков с числовым управлением. Язык был разработан группой американских специалистов в 1956–1959 гг. под руководством математика Дугласа Т. Росса. Язык СOBOL (Co mmon B usiness–O riented L anguage ), созданный в США под руководством Грейс Мюррей Хоппер в 1959 г., ориентирован на обработку экономической информации. Математик Грейс Мюррей Хоппер возглавила проект по разработке СOBOL в чине капитана второго ранга, впоследствии она стана контр-адмиралом. Г.М. Хоппер называют “мамой и бабушкой” СOBOLа.
(Grace Murray Hopper)
К специализированным языкам можно отнести и современные языки web-программирования Perl и PHP. Языки Рапира, Е-язык (Россия), SMR (Великобритания), LOGO (США) можно отнести к языкам, предназначенным для обучения программированию.
Самыми распространенными универсальными языками программирования сегодня являются C++, Delphi, Java, Pascal, Visual Basic, Python.
Но, рассматривая языки программирования как самостоятельный объект исследования, можно провести их классификацию по концепции построения языка.
Классификация языков программирования
Языки программирования можно разделить на два класса: процедурные и непроцедурные. Процедурные (императивные ) языки - это языки операторного типа. Описание алгоритма на этом языке имеет вид последовательности операторов. Характерным для процедурного языка является наличие оператора присваивания (Basic, Pascal, С). Программа, написанная на императивном языке, очень похожа на приказы, выражаемые повелительным наклонением в естественных языках, то есть это последовательность команд, которые должен выполнить компьютер. Программируя в императивном стиле, программист должен объяснить компьютеру, как нужно решать задачу.
Непроцедурные (декларативные ) языки - это языки, при использовании которых в программе в явном виде указывается, какими свойствами должен обладать результат, но не говорится, каким способом он должен быть получен. Непроцедурные языки делятся на две группы: функциональные и логические.
Декларативные языки программирования - это языки программирования высокого уровня, в которых операторы представляют собой объявления или высказывания в символьной логике. Типичным примером таких языков являются языки логического программирования (языки, основанные на системе правил и фактов). Характерной особенностью декларативных языков является их декларативная семантика. Основная концепция декларативной семантики заключается в том, что смысл каждого оператора не зависит от того, как этот оператор используется в программе. Декларативная семантика намного проще семантики императивных языков, что может рассматриваться как преимущество декларативных языков над императивными.
Логические языки
В программах на языках логического программирования соответствующие действия выполняются только при наличии необходимого разрешающего условия на вывод новых фактов из данных фактов согласно заданным логическим правилам. Логическое программирование основано на математической логике (см. “Логические операции. Кванторы ”, “Логические выражения ”).
Первым языком логического программирования был язык Planner, он был разработан Карлом Хьюитом в Лаборатории искусственного интеллекта Массачусетсского технологического института в 1969 г. В этом языке была заложена возможность автоматического вывода (получения) результата из данных и заданных правил путем перебора вариантов (совокупность которых называлась планом). Но самым известным языком логического программирования является ПРОЛОГ (Prolog), который был создан во Франции в Марсельском университете в 1971 г. Аленом Кольмеро (Colmerauer).
Ален Кольмеро
(Alain Colmerauer)
Программа на языке ПРОЛОГ содержит две составные части: факты и правила. Факты представляют собой данные, с которыми оперирует программа, а совокупность фактов составляет базу данных ПРОЛОГа, которая, по сути, является реляционной базой данных. Основная операция, выполняемая над данными, - это операция сопоставления, называемая также операцией унификации или согласования. Правила состоят из заголовка и подцелей. Выполнение программы, написанной на ПРОЛОГе, начинается с запроса и состоит в доказательстве истинности некоторого логического утверждения в рамках заданной совокупности фактов и правил. Алгоритм этого доказательства (алгоритм логического вывода) и определяет принципы исполнения программы, написанной на ПРОЛОГе.
В отличие от программ, составленных на языках процедурного типа, предписывающих последовательность шагов, которые должен выполнять компьютер для решения задачи, на ПРОЛОГе программист описывает факты, правила, отношения между ними, а также запросы по проблеме. Например, пусть у нас есть следующие факты относительно того, кто является чьей мамой:
мама("Даша","Маша").
мама("Наташа","Даша").
Кроме этого, имеется правило, вводящее отношение бабушка:
бабушка(X,Y):-
Теперь мы можем делать запросы на предмет того, кто бабушка того или иного человека, или кто является внучкой (внуком) определенной женщины:
бабушка("Наташа",X).
Ответ на этот запрос система ПРОЛОГ выдаст так:
Возможности применения языка ПРОЛОГ весьма обширны. Среди наиболее известных - применение в символической математике, планировании, автоматизированном проектировании, построении компиляторов, базах данных, обработке текстов на естественных языках. Но, наверное, самое характерное применение ПРОЛОГа - это экспертные системы.
На сегодняшний день существует целый класс логических языков; так, от языка Planner также произошли логические языки программирования QA-4, Popler, Conniver и QLISP. Языки программирования Mercury, Visual Prolog, Oz и Fril произошли уже от языка Prolog.
Функциональные языки
Первым языком функционального типа является язык ЛИСП, созданный в Массачусетсском технологическом институте в 1956–1959 гг. Джоном Маккарти, который в 1956 г. на Дармутской конференции (США) впервые предложил термин “искусственный интеллект”.
Джон Маккарти (John McCarthy)
И хотя до сих пор не утихают споры вокруг этого термина и развившегося научного направления в его рамках, исследователи единодушны в использовании функциональных и логических языков для данной области. Значительное число работ по искусственному интеллекту реализовано на ЛИСПе.
После своего появления ЛИСПу присваивали много эпитетов, отражающих его черты: язык функций, символьный язык, язык обработки списков, рекурсивный язык. С позиций сегодняшней классификации ЛИСП определяется как язык программирования функционального типа, в основу которого положен метод -исчисления (метод -исчисления разработан в 30-е годы прошлого столетия А.Черчем в качестве строгой математической модели для вычислимых функций, см. “Теория алгоритмов” ).
Программа, написанная на функциональном языке, состоит из неупорядоченного набора уравнений, определяющих функции и значения, которые задаются как функции от других значений. Программы и данные ЛИСПа существуют в форме символьных выражений, которые хранятся в виде списковых структур. ЛИСП имеет дело с двумя видами объектов: атомами и списками . Атомы - это символы, используемые для идентификации объектов, которые могут быть числовыми и символьными (понятия, материалы, люди и т.д.). Список - это последовательность из нуля или более элементов, заключенных в круглые скобки, каждый из которых является либо атомом, либо списком. Над списками выполняются три примитивные операции: извлечение первого элемента списка; получение оставшейся части списка после удаления первого элемента; объединение первого элемента списка L и оставшейся части списка Q.
Тексты программ на функциональных языках программирования только описывают способ решения задачи, но не предписывают последовательность действий для решения.
В качестве основных свойств функциональных языков программирования обычно рассматриваются следующие: краткость и простота; строгая типизация; модульность; функции - объекты вычисления; чистота (отсутствие побочных эффектов); отложенные (ленивые) вычисления.
Кроме ЛИСПа, к функциональным языкам относят РЕФАЛ (разработан в середине 60-х годов В.Ф. Турчиным в МГУ им. М.В. Ломоносова), Haskell, Clean, ML, OCaml, F#.
Приведем пример описания известного алгоритма быстрой сортировки списка на языке Haskell:
qsort (x:xs) = qsort elts_lt_x ++ [x]
Qsort elts_greq_x where
elts_lt_x =
elts_greq_x =
Здесь записано, что пустой список уже отсортирован. А сортировка непустого списка состоит в том, чтобы разбить список на три: список элементов, меньших головы исходного списка, голова исходного списка ([x]) и список элементов хвоста исходного списка, больше или равных x.
Объектно-ориентированные языки
Объектно-ориентированные языки - это языки, в которых понятия процедуры и данных, используемых в обычных системах программирования, заменены понятием “объект” (см. статью “Объектно-ориентированное программирование ”). Языком объектно-ориентированного программирования в чистом виде считается SmallTalk, возможности объектно-ориентированного программирования заложены также в Java, C++, Delphi.
Дальнейшее развитие современного программирования связано с так называемым “параллельным программированием”. Для реализации этой технологии разрабатываются специализированные объектно-ориентированные языки. К языкам такого типа относят, например, MC# (mcsharp ) - высокоуровневый объектно-ориентированный язык программирования для платформы.NET, поддерживающий создание программ, работающих в распределенной среде с асинхронными вызовами.
Структура языка программирования
Между существующими языками программирования есть принципиальные расхождения в концепции построения языков, особенно это справедливо для более ранних языков, но все эти языки потому и называются языками программирования, что они с точки зрения внутренней системы построения имеют одинаковое формальное строение.
Любой язык программирования состоит из предложений (операторов). Предложения (как и слова) определены над неким алфавитом С. Синтаксис языка описывает множество предложений над алфавитом С, которые внешне представляют правильно сформированные программы.
Синтаксис языка - это правила получения слов и предложений этого языка. Синтаксис схематически описывается с помощью определенных грамматических правил.
Знание формального языка (алфавита + синтаксиса) хотя и достаточно для установления синтаксической корректности программы, однако недостаточно для понимания ее назначения и способа действий. Значение и способ действия программы на языке программирования уточняются путем задания семантики.
Семантика языка - это правила интерпретации слов формального языка, т.е. установления значения отдельных языковых элементов.
Для определения формальных языков, в том числе для языков программирования, используют БНФ (формы Бэкуса - Наура) и синтаксические диаграммы. Это два взаимозаменяемых способа описания.
При описании языка программирования через БНФ используются следующие обозначения:
1) <..>- определяемое слово;
2) R - правило из синтаксиса для формирования слова;
3)
Каждое R состоит из терминальных слов или лексем языка и, возможно, следующих символов:
· [..] - данный элемент присутствует в БНФ;
· {..} - данное вхождение может быть использовано в БНФ;
· {..}* - данное вхождение может быть использовано в БНФ конечное число раз.
Пример 1. Приведем пример БНФ-правила, определяющего целое число.
Читается это правило так: “Целое число - это символ 0 или последовательность символов, которая может начинаться символом “–”, а далее следует отличная от нуля цифра, вслед за которой может следовать любая конечная последовательность цифр”.
Специальную, схожую с БНФ, форму описания формальных языков представляют синтаксические диаграммы. В синтаксических диаграммах используются три типа элементов: овал/круг, прямоугольник, стрелки. В овалах помещаются терминальные слова или лексемы, в прямоугольниках - определяемые слова. Графическое представление языка через синтаксические диаграммы делает описание языка наглядным.
Пример 2 . Описание целого числа с помощью синтаксической диаграммы.
Согласно Примерной программе, необходимо, чтобы школьники представляли современную классификацию языков программирования, а также ориентировались в областях применения каждого из них. Проще всего изложение данной темы проводить после того, как уже произошло подробное знакомство с одним из языков программирования.
Следует рассказать, почему возникают новые языки и совершенствуются старые: в первую очередь это происходит при поиске средства для быстрого написания сложных программ, которые к тому же не содержали ошибок. Известен пример, когда создание языка АДА (назван так в честь первой женщины-программиста Ады Лавлейс, дочери Байрона) было инициировано в 1974 году в Министерстве обороны США. Американские военные осознали, что они теряют много времени, усилий и денег на разработку и сопровождение встроенных компьютерных систем (например, систем наведения ракет), а трудноуловимые ошибки языков программирования приводят к настоящим катастрофам.
Декларативные языки были очень популярны в конце 80-х - начале 90-х годов прошлого столетия, они были названы языками программирования искусственного интеллекта для компьютеров пятого поколения. Однако надежды на их широкое распространение пока не оправдались. Возможно, потому, что существующие системы функционального и логического программирования не позволяют создавать быстро работающие программы для содержательных задач. Не исключено, что их время просто еще не наступило.
Выбирая стратегию преподавания темы “Алгоритмизация и программирование”, необходимо учитывать, что задача общеобразовательного курса - это в большой степени выработка определенного стиля мышления, формирование наиболее общих навыков, умений и представлений, нежели освоение тех или иных конкретных языков и технических средств программирования. В то же время, такой курс должен служить базой для последующего профессионального изучения программирования в высшей школе или старших классах средней школы (в рамках профессионального обучения).
В настоящее время существуют два наиболее распространенных подхода к преподаванию программирования:
1) преподавание на основе специально разработанного языка учебного языка, ориентированного на обучение основным навыкам программирования;
2) изучение одного или нескольких языков программирования, широко используемых на практике при решении научных и хозяйственных задач (такие языки можно назвать стандартными).
Первый подход часто используется при преподавании основ программирования в младших классах средней школы с использованием специальных языков, например, Рапиры, Е-языка, LOGO. Эти языки учитывают возможности школьников младших классов. Такой подход хорош при углубленном изучении информатики в 5–6-х классах.
Относительно второго подхода можно сказать, что большинство современных реализаций стандартных языков загружено большим количеством технических деталей и сложны в изучении. Тем не менее наиболее приемлемым для общеобразовательной школы, где курс информатики преподается в 8–11-х классах, является обучение теоретическим основам программирования на базе стандартного языка. При этом не обязательно вдаваться в глубины языка. Учащиеся, которых он заинтересует, могут сделать это и сами. Наибольшее внимание следует уделить переходу от алгоритмических структур к их программной реализации на языке программирования.
Здесь стоит отметить, что Pascal первоначально создавался как учебный язык, но со временем получил широкое распространение в качестве стандартного языка и развитие в виде объектно-ориентированного языка с визуальной технологией программирования Delphi. За основу курса в 8–9-х классах можно взять Pascal или Basic, а в качестве расширенного (факультативного) курса в 10–11-х классах ознакомить учащихся с их объектно-ориентированными расширениями (Delphi и Visual Basic). У каждого языка есть свои сторонники и противники, и конечный выбор остается за учителем.
Существует два основных подхода к изучению языка программирования: формальный и “программирование по образцу”. Первый основан на формальном (строгом) описании конструкций языка программирования (синтаксиса языка и его семантики ) тем или иным способом (с помощью синтаксических диаграмм, мета-языка или формального словесного описания, в частности, семантики) и использовании при решении задач только изученных, а следовательно понятных, элементов языка. При втором подходе школьникам сначала выдаются готовые программы, рассказывается, что именно они делают, и предлагается написать похожую программу или изменить имеющуюся, не объясняя до конца ряд “технических” или несущественных, с точки зрения учителя, для решения задачи деталей. При этом говорится, что точный смысл соответствующих конструкций вы узнаете позднее, а пока поступайте аналогичным образом. Второй подход дает возможность так называемого “быстрого старта”, но создает опасность получить полуграмотных пользователей среды программирования, т.е. людей, которые используют в своей практике достаточно сложные конструкции, но не могут четко объяснить, почему в том или ином случае нужно применять именно их, и как они работают. В результате рано или поздно такие “программисты” сталкиваются с ошибками, исправить которые они просто не в состоянии - им не хватает знаний.
Одна из задач школьной информатики - научить именно формальному подходу, в частности, при применении различных определений. И формальное изучение языка программирования этому немало способствует. Но и без хороших примеров (образцов) при обучении программированию школьников не обойтись. И чем младше ученики, тем больше примеров необходимо приводить при описании языка (иногда даже заменяя ими строгое определение). Другое дело, что следует добиваться того, чтобы в результате обсуждения примера все его детали оказались понятны школьникам (обязательно нужно объяснить, как и почему это работает, в том числе опираясь на уже изученный формальный материал). В этом случае сильные ученики получат возможность понять все досконально и смогут использовать полученные знания в дальнейшем, а остальные приобретут конкретные навыки и оставят для себя возможность вернуться при необходимости к формальным определениям позже.
О железнодорожном языке "Платформу Красные Зори поезд проследует без остановки". Обратим внимание, что машинист употребил существительное "остановка", а не глагол "останавливаться". Остановка - очень важное для железнодорожников понятие. Поезд может "остановиться", но не "иметь остановки". Турчин [Тур-чин 2000], приводя подобный пример, указывает на формализацию языка, употребляемого в узких профессиональных целях.
Формализованный язык можно определить следующим образом [Турчин 2000]. Рассмотрим двухэтажную языковую модель действительности (рис. 4. 4). Ситуация si кодируется языковым объектом Li. Объект L1 есть имя для si. Некоторое время спустя ситуация S1 сменяется ситуацией S2. Осуществляя некоторую языковую деятельность, преобразуем L1 в другой объект - L2. Если наша модель правильна, то L2 есть имя S2. В результате, не зная реальной ситуации S2, мы можем получить представление о ней путем декодирования языкового объекта L2. Выполнение преобразования L1->L2 определяет, будет ли язык формализованным.
Для формализованного языка преобразование L1->L2 определяется исключительно языковыми объектами Li, которые участвуют в нем и не зависят от языковых представлений si, соответствующих им по семантике языка.
Для неформализованного языка результат преобразования языкового объекта Li зависит не только от вида самого представления Li, но и от представления si, которое он порождает в голове человека, от ассоциаций, в которые он входит.
Человек способен воспринимать самые неформализованные языки. А компьютер не понимает, точнее, не может исполнить программу на неформальном языке. Именно поэтому важное место в изучении программирования всегда занимают формальные алгоритмические языки программирования,
О формализации неформализованного Формализация неформализованного - процесс неформализуемый. Хотя с этим пытаются бороться логики и военные.
О формуле любви Формула любви не поддается формализации. В лучшем случае она может быть представлена только в виде весьма грубой модели
Языки моделирования
Язык моделирования - набор правил, определяющих построение моделей (упрощенного представления реальности), включающий их визуализацию и определение структуры и поведения. Язык моделирования включает:
элементы модели - фундаментальные концепции моделирования и их семантику;
нотацию - визуальное представление элементов моделирования;
руководство по использованию - правила применения элементов в рамках построения моделей предметной области.
Языки программирования и интегрированные среды
По словам создателя первой интегрированной среды FRAMEWORK, интегрированная среда -это такая прикладная программа, что пользователь, запустив ее в начале рабочего дня, находит в ней все необходимые для работы ресурсы и поэтому не выходит из интегрированной среды до самого конца рабочего дня. Конечно, это определение не очень корректно и несколько идеализирует ситуацию, но его общий смысл достаточно ясен. Основная особенность интегрированных сред -высокая степень интерактивности. Она достигается за счет интеграции в единое целое различных программных ресурсов, отсюда и происходит название. Так, интегрированная среда какого-либо компилятора языка программирования (программы, которая из текста данного языка программирования создает исполняемую программу) обычно содержит текстовый редактор и собственно компилятор с системой диагностики ошибок компиляции. Кроме того, в ней обычно имеется также отладчик -интерпретатор данного языка, выполняющий программу строчка за строчкой и имеющий ряд других специальных возможностей. Одно из активно развивающихся направлений, визуальное проектирование -полностью основано на использовании возможностей интегрированной среды. Пользователь в интерактивном режиме выбирает необходимые для его программы объекты языка программирования и устанавливает между ними связи. Популярность таких языков как Visual BASIC (Microsoft), а также Object PASCAL (среды Delphi и Kylix, Borland), не случайна. Даже неопытный программист, не знающий кроме BASIC других языков программирования и никогда не программировавший под Windows, может за два-три дня с помощью Visual BASIC создать прикладную программу, работающую под Windows. А вот программисту высокого класса, не программировавшему до того под Windows, с помощью C++ зачастую приходится для создания такой же программы затратить недели, а то и месяцы. Правда, Visual BASIC обладает рядом существенных ограничений. С помощью сред визуального проектирования можно создавать весьма сложные программы, не набрав с клавиатуры ни строчки кода. Однако у всех программ, созданных на основе традиционных языков программирования процедурного типа, имеется один и тот же недостаток. Для них исполняемый код -это одно, а обрабатываемые программой данные -совсем другое. Действительно, код программы содержится в файле с расширением EXE, а данные -либо в специальных файлах данных (как правило, в текстовом либо двоичном виде во внутреннем представлении компьютера), либо вводятся с клавиатуры или с какого либо другого внешнего устройства. А теперь зададим вопрос: как быть, если пользователь должен дать исполняемой программе информацию, которую можно рассматривать как “добавку” к тексту программы? Например, мы хотим, чтобы на экране был построен график функции, и в подобной программе обеспечиваем все необходимые сервисные возможности. Однако формулу для функции должен задать сам пользователь, и заранее неизвестно, какая она будет. Совершенно очевидно, что подобного рода задачи можно решать только с помощью системы-интерпретатора. Но “за все приходится платить”. Компилятор переводит текст программы в исполняемый код, который может работать и без программы-компилятора. Программы же, созданные на основе языков интерпретирующего типа, могут исполняться только под управлением программы-интерпретатора. Кроме того, они работают медленнее скомпилированных, так как интерпретация занимает дополнительное время. Однако во многих случаях это несущественно.
Дата создания: 1963 Повлиял на: ПРОФТ Типизация: бестиповая Диалекты:
Applesoft BASIC
Commodore BASIC
Microsoft BASIC
Реализации и версии:
Applesoft BASIC Interpreter in Javascript
Atari Microsoft BASIC I/II
Commodore BASIC
Galaksija BASIC
Microsoft Visual Basic
Visual Basic for Applications
Бе́йсик (BASIC - сокращение от англ. Beginner’s All-purpose Symbolic Instruction Code - универсальный код символических инструкций для начинающих; англ. basic - основной, базовый) - семейство высокоуровневых языков программирования.
Бейсик был придуман в 1963 году преподавателями Дартмутского Колледжа Джоном Кемени и Томасом Куртцом, и под их руководством был реализован командой студентов колледжа. Со временем, когда стали появляться другие диалекты, этот «изначальный» диалект стали называть Dartmouth BASIC.
Бейсик был спроектирован так, чтобы студенты могли писать программы, используя терминалы с разделением времени. Он создавался как решение для проблем, связанных со сложностью более старых языков, предназначался для более «простых» пользователей, не столько заинтересованных в скорости программ, сколько просто в возможности использовать компьютер для решения своих задач.
При проектировании языка использовались следующие восемь принципов:
быть простым в использовании для начинающих;
быть языком программирования общего назначения;
предоставлять возможность расширения функциональности, доступную опытным программистам;
быть интерактивным;
предоставлять ясные сообщения об ошибках;
быстро работать на небольших программах;
не требовать понимания работы аппаратного обеспечения;
быть посредником меду пользователем и операционной системой.
Язык был основан частично на Фортран II и частично на Алгол-60, с добавлениями, делающими его удобным для работы в режиме разделения времени, обработки текста и матричной арифметики. Первоначально Бейсик был реализован на GE-265 с поддержкой множества терминалов. Вопреки распространённому убеждению, в момент своего появления это был компилируемый язык. Всеобщую же популярность язык получил с его появления на микрокомпьютере Altair 8800. Многие языки программирования были слишком громоздкими, чтобы умещаться в небольшой памяти. Для машин с таким медленным носителем как бумажная лента, аудиокассета и без подходящего текстового редактора такой небольшой язык как Бейсик был отличной находкой. В 1975 году Майкрософт (тогда это были лишь двое - Билл Гейтс и Пол Аллен, при участии Монте Давидова) выпустила Altair BASIC. Для операционной системы CP/M был создан диалект BASIC-80, надолго определивший развитие языка. В этот период было создано несколько новых версий Бейсика. Майкрософт продавала несколько версий BASIC для MS-DOS/PC-DOS, включая BASICA, GWBASIC и Quick BASIC (QBASIC).Компания Borland в 1985 выпустила Turbo BASIC 1.0 (его наследники впоследствии продавались другой компанией под именем PowerBASIC). На домашних компьютерах появились различные расширения Бейсика, обычно включающие средства для работы с графикой, звуком, выполнением DOS-команд, а также средства структурного программирования. Некоторые другие языки использовали хорошо известный синтаксис Бейсика в качестве основы, на которой строилась совершенно иная система (см. например, GRASS). Однако, начиная с конца 80-х, новые компьютеры стали намного более сложными и предоставляли возможности (такие как графический интерфейс пользователя), которые делали Бейсик уже не столь удобным для программирования. Бейсик начал сдавать свои позиции, несмотря на то, что огромное количество его версий ещё использовалось и продавалось. Вторую жизнь Бейсик получил с появлением Visual Basic от Microsoft. Он стал одним из наиболее часто используемых языков на платформе Microsoft Windows. Позже был создан вариант под названием WordBasic, используемый в MS Word до появления Word 97. Вариант Visual Basic for Applications (VBA) был встроен в Excel 5.0 в 1993 году, затем в Access 95 в 1995-ом, а после и во все остальные инструменты, входящие в пакет Office - в 1997-ом. Internet Explorer 3.0 и выше, а также Microsoft Outlook включали интерпретатор языка VBScript. В полный вариант пакета OpenOffice.org также включён интерпретатор Бейсика.
Hello, World!: Пример для версий QBasic 1.1, QuickBasic 4.50
PRINT " Hello , World !"
Факториал: Пример для версий QBasic 1.1, QuickBasic 4.50
Используется итеративное определение факториала. При вычислении 13! возникает арифметическое переполнение, и здесь поведение разных реализаций отличается: QBasic сообщает о переполнении, а QuickBasic просто выводит отрицательные значения. Кроме того, команда PRINT по умолчанию выводит по одному пробелу перед числом и после него.
DIM f AS LONG f = 1 PRINT " 0 ! ="; f FOR i = 1 TO 16:
f = f * i:
PRINT i; "! ="; f
