Формализованные языки программирования. Формальные языки: примеры

О железнодорожном языке "Платформу Красные Зори поезд проследует без остановки". Обратим внимание, что машинист употребил существительное "остановка", а не глагол "останавливаться". Остановка - очень важное для железнодорожников понятие. Поезд может "остановиться", но не "иметь остановки". Турчин [Тур-чин 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

Естественные языки программирования (ЕЯП) определяют следующий шаг развития языков программирования, отличаясь отязыков запросов тем, что пользователь любого уровня освобождается от необходимости освоения каких-либо специальных словарей, грамматики и синтаксиса –предложения ЕЯП весьма похожи на предложения обычной человеческой речи. ЕЯП еще дальше отдаляют пользователя от ВС и ее СПО, существенно повышая интеллектуальный уровень интерфейсапервого с вычислительными ресурсами. В настоящее время на ПК успешно используются ЕЯП с ограниченными возможностями, такие, как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 и др.) поставляются также на уровне иллюстративных и/или обучающих версий, которые функционально ограничены относительно основного пакета, но позволяют проводить иллюстрацию пакета в действии, а также обучать основам работы в его среде, что в целом ряде случаев позволяет сделать более осознанный выбор данного средства для последующего коммерческого использования.

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

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

Наряду с разговорными (естественными) человечество создало множество искусственных языков. Каждый из них предназначен для решения конкретных задач.

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

Определения

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

Основа большинства как искусственных, так и естественных языков — алфавит.

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

Язык характеризуется:

• набором используемых знаков;
• правилами составления из них «слов», «фраз» и «текстов»;
• набором правил (синтаксических, прагматических и семантических) использования составленных конструкций.

Характеристики естественных языков

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

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

• неоднозначность большинства слов;
• существование синонимов и омонимов;
• наличие нескольких названий у одного и того же предмета;
• существование исключений из практически всех правил.

Все эти характеристики являются главными отличиями естественных знаковых систем от формальных языков. Примеры неоднозначностей слов и высказываний известны всем. Так слово «эфир» в зависимости от контекста может означать, как вещество, так и радио- или телевещание.

При этом основными функциями разговорных языков являются:

• общение;
• познавательная деятельность;
• выражение эмоций;
• воздействие на собеседника (корреспондента, если речь идет о переписке).

Характеристики искусственных языков

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

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

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

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

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

• выбирается алфавит (совокупность исходных символов);
• задаются правила построения выражений (синтаксис) языка.

Сфера применения

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

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

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

Язык формальной логики

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

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

Формальная логика борется с “недостатками” естественных языков, связанных с неоднозначностью некоторых высказываний и пр. Для этой цели операции с мыслями заменяют действиями со знаками формального языка. Это исключает какую-либо неопределенность и позволяет точно установить истинность высказывания.

Особенности языков программирования

Как уже было сказано, их с некоторыми оговорками можно отнести к классу формальных.

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

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

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

Грамматики

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

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

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

На данный момент их, вместе с “диалектами” насчитывается несколько тысяч. Их классифицируют, как процедурные и декларативные. В языках первого типа преобразование данных задают посредством описания последовательности действий, производимых над ними, второго — отношений. Существуют и другие классификации. Например, языки программирования разделяют на функциональные, процедурные, объектно-ориентированные и логические. Если подходить к вопросу строго, то никакая классификация не может быть объективной. Ведь значительная часть языков программирования обладает возможностями формальных систем сразу нескольких типов. Со временем грани, скорее всего, будут стираться еще больше.

Теперь вы сможете ответить на вопрос: “Какие формальные языки вам известны?”. Ученые продолжают совершенствовать их, с целью сделать возможными решение различных практических и теоретических задач, которые на данный момент считаются неразрешимыми.

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

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

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

Чтобы лучше разобраться в том, как именно изучаются формальные языки, необходимо сначала понять, в чем заключаются особенности математических методов изучения. Согласно Колмогорову и др. (Александров А.Д., Колмогоров А.Н., Лаврентьев М.А. Математика. Ее содержание, методы и значение. Том 1. М.: Издательство Академии Наук СССР, 1956.), математический метод, к чему бы он ни применялся, всегда следует двум основным принципам:

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

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

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

Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита - начальные строчные буквы латинского алфавита. Например, выражение V = {a,b} обозначает алфавит из двух символов a и b.

Цепочка представляет собой конечную последовательность символов. Например, abc - цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1...an - цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.

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

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

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

Назначение грамматики - задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число. В примере выше в качестве такого принципа выступает следующий: «каждая цепочка языка начинается с символов a, за которыми идет столько же символов b». Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.

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

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

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

• Распознающие грамматики. Такие грамматики представляют собой устройства (алгоритмы), которым на вход подается цепочка языка, а на выходе устройство печатает «Да», если цепочка принадлежит языку, и «Нет» - в противном случае.
• Порождающие грамматики. Этот вид устройств используется для порождения цепочек языков по требованию. Образно говоря, при нажатии кнопки будет сгенерирована некоторая цепочка языка.
• Перечисляющие грамматики. Такие грамматики печатают одну за другой все цепочки языка. Очевидно, что если язык состоит из бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.

Окрестностные грамматики

В качестве примера рассмотрим язык A = {a+a, a+a+a, a+a+a+a,...} . Этот язык представляет собой простейшую модель языка арифметических выражений, где роль чисел играет символ «a», а роль операций - символ "+". Составим для этого языка окрестностную грамматику. Зададим окрестности для символа «a». Символ «a» может встречаться в цепочках языка A в трех синтаксических контекстах: вначале, между двумя символами "+" и в конце. Для обозначения начала и конца цепочки введем псевдосимвол "#". Тогда окрестности символа «a» будут следующими: #a+, +a+, +a# . Обычно для выделения центра окрестности этот символ в цепочке подчеркивается (ведь в цепочке могут быть и другие такие символы, которые не являются центром!), здесь этого делать не будем за неимением простой технической возможности. Символ "+" встречается только между двух символов «a», поэтому для него задается одна окрестность, цепочка a+a .

Рассмотрим цепочку a+a+a и проверим, принадлежит ли она языку. Первый символ «a» цепочки входит в нее вместе с окрестностью #a+ . Второй символ "+" входит в цепочку вместе с окрестностью a+a . Подобное вхождение можно проверить и для остальных символов цепочки, т.е. данная цепочка принадлежит языку, как и следовало ожидать. Но, например, цепочка a+aa языку A не принадлежит, поскольку последний и предпоследний символы «a» не имеют окрестностей, с которыми они входят в эту цепочку.

Не всякий язык может быть описан окрестностной грамматикой. Рассмотрим, например, язык B, цепочки которого начинаются либо с символа «0», либо с символа «1». В последнем случае далее в цепочке могут идти символы «a» и «b». Если же цепочка начинается с нуля, то далее могут идти только символы «a». Нетрудно доказать, что для этого языка нельзя придумать никакой окрестностной грамматики. Легитимность вхождения символа «b» в цепочку обусловлена ее первым символом. Для любой окрестностной грамматики, в которой задается связь между символами «b» и «1» можно будет подобрать достаточно длинную цепочку, чтобы всякая окрестность символа «b» не доставала до начала цепочки. Тогда в начало можно будет подставить символ «0» и цепочка будет принадлежать языку A, что не отвечает нашим интуитивным представлениям о синтаксическом строении цепочек этого языка.

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

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

За последние 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 и др.