Естественный язык программирования пример. Формализованные (формальные) языки

ФОРМАЛИЗОВАННЫЙ ЯЗЫК – искусственная знаковая система, предназначенная для представления некоторой теории. Формализованный язык отличается от естественных (национальных) языков человеческого общения и мышления, от искусственных языков типа Эсперанто, от «технических» языков науки, сочетающих средства определенной части естественного языка с соответствующей научной символикой (язык химии, язык обычной математики и др.), от алгоритмического языка типа обобщенного программирования и т.п. прежде всего тем, что его задача – служить средством фиксации (формализации) определенного логического содержания, позволяющего вводить отношение логического следования и понятие доказуемости (либо их аналоги). Исторически первым формализованным языком была силлогистика Аристотеля, реализованная с помощью стандартизованного фрагмента естественного (греческого) языка. Общую идею формализованного языка сформулировал Лейбниц (characteristica universalis), предусматривавший его расширение до «исчисления умозаключений» – calculus ratiocinator. В Новое время различные варианты формализованных языков разрабатывались на основе аналогии между логикой и алгеброй. Вехой здесь явились труды Моргана , Буля и их последователей, в особенности Шрёдера и Порецкого . Современные формализованные языки – в их наиболее распространенных формах – восходят к труду Фреге «Begriffsschrift» – «Запись в понятиях» (1879), от которого идет главная линия развития языка логики высказываний и (объемлющей ее) логики (многоместных) предикатов, а также применение этих логических языковых средств к задачам обоснования математики.

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

Формализованные языки различаются по своей логической силе, начиная с «классических» языков (в которых в полной мере действуют аристотелевские законы тождества, противоречия и исключенного третьего, а также принцип логической двузначности) и кончая многочисленными языками неклассических логик, позволяющих ослаблять те или иные принципы, вводить многозначность оценок формул либо их модальности. Разработаны языки, в которых логические средства в том или ином смысле минимизируются. Таковы языки минимальной и положительной логик или язык логики высказываний, использующий единственную логическую операцию, напр. штрих Шеффера (см. Логические связки ).

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

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

Непременной чертой формализованного языка является «возможностное» истолкование правил вывода; напр., на определенном шаге мы вольны использовать либо не использовать, скажем, правило modus ponens. Этой черты лишены алгоритмические языки, носящие «предписывающий» характер. Но по мере развития компьютерной логики и разработки программ «описывающего» типа это различие начинает сглаживаться. В этом же направлении действует и разработка формализованных языков, ориентированных на решения задач эвристики.

Литература:

1. Черч А. Введение в математическую логику, т. 1. М., 1960;

2. Клини С.К. Введение в метаматематику. М., 1957;

3. Карри Х. Основания математической логики. М., 1969;

4. Фрейденталь Х. Язык логики. М., 1969;

5. Смирнова Е.Д. Формализованные языки и проблемы логической семантики. М., 1982.

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

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

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

Исторически первым метасинтаксическим языком, который использовался на практике для описания синтаксиса языков программирования (в частности, Алгола-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) синтез объектной программы.

ФОРМАЛИЗОВАННЫЕ (ФОРМАЛЬНЫЕ) ЯЗЫКИ

ПОНЯТЬ

Формализованный (формальный) язык - искусственный язык, характеризующийся точными правилами построения выражений и их понимания.

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

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

Формальные языки часто конструируются на базе языка математики.

На протяжении всей истории развития математики в ней широко использовались символические обозначения для различных объектов и понятий. Однако, наряду с символическими обозначениями ученые-математики свободно пользовались и естественным языком. Но на каком-то этапе развития науки (XVII век) возникла необходимость строгого логического анализа математических суждений, а также уточнения важного для математики понятия “доказательство”. Оказалось, что решить эти задачи невозможно без строгой формализации математических теорий. Появилась потребность в изложении этих теорий на формальном языке. Веком бурного развития различных формальных языков можно считать XX век.

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

Все формальные языки - это кем-то созданные конструкции. Большинство из них строятся по следующей схеме.

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

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

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

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

ПРИМЕР 1

Одним из важных с точки зрения информатики является алфавит, состоящий из двух букв “0”, “1”. Всякой конечная последовательность нулей и единиц - есть слово в этом алфавите.

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

Термы - это аналог имен объектов, их основное назначение - обозначать некоторый объект.

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

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

ПРИМЕР 2

В логике такими функциями являются инверсия (), конъюнкция (), дизъюнкция (), импликация () и др.

Примеры термов в алгебре логики:

А; АВ А; (АС).

В языках программирования в образовании термов участвуют арифметические операции, операции отношения (,

Примеры термов в языке программирования Pascal:

А; prog_1; ((A1+25)3*B) and (B0)); 2+sqrt(z*sin(b)).

Формулы

ПРИМЕР 3

Примеры логических формул:

(АС)  АС = 1; x((x)(x))

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

Примеры “формул” языка программирования Pascal:

A:= 2+sqrt(Z*sin(B)); if F3 then write(R) else R:=sqr(F);

Осмысленные выражения получаются в формальном языке, только если соблюдены определенные в языке правила образования, преобразования и “понимания” термов и формул. К таким правилам относятся:

правила построения термов и формул;

правила интерпретации термов и формул (семантический аспект языка);

правила вывода

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

ПРИМЕР 4

Оператор языка Pascal

if F3 then write(R) else R:=sqr(F);

интерпретируется в соответствии со следующим правилами:

переменная F может быть только целого или вещественного типа, а переменная R - только вещественного типа. Если это не так, то считается, что оператор синтаксически неверен, и выполняться он не будет (будет выдано сообщение о синтаксической ошибке);

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

если значение выражения (сложного терма “F3”), стоящего вслед за ключевым (зарезервированным) словом if, есть “истина” (true), то выполняется оператор, расположенный за ключевым словом then (на экран выводится значение переменной F); если же его значение “ложь” (false), то выполняется оператор, расположенный за ключевым словом else (вычисляется квадрат значения переменной F и результат помещается в ячейку с именем R).

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

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

ЗНАТЬ

Формализованный (формальный) язык - искусственный язык, характеризующийся точными правилами построения выражений и их интерпретации (понимания).

При построения формального языка выбирается алфавит , и описывается синтаксис языка.

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

Выражениями формального языка являются термы и формулы.

Основное назначение терма - обозначать некоторый объект.

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

Сложные термы строятся по определенным правилам путем применения к простым термам допустимых в языке функций.

Формулы образуются из термов, к которым применены допустимые в языке операторы.

Синтаксис языка - совокупность правил построения осмысленных выражений - включает в себя:

правила построения термов и формул;

правила интерпретации термов и формул;

правила вывода одних формул и термов из других формул и термов.

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

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

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

УМЕТЬ

ЗАДАНИЕ 1

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

Если в этом языке программирования зарезервированные слова? Если да, то приведите примеры зарезервированных и не зарезервированных слов.

Что в языках программирования можно рассматривать как термы и формулы?

ОТВЕТ. В алфавит языка программирования входят все символы, которые можно использовать при написании программ.

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

Формулами языка программирования являются допустимые в нем операторы: ввода, вывода, присваивания, условный, цикла и т.п.

ЗАДАНИЕ 2

Если вы изучали основы формальной логики, то:

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

проинтерпретируйте формулу: x ((x)  (x)) или  (А  А) = 1

ОТВЕТ. 2) - это закон непротиворечия, суть которого: никакое высказывание не может быть истинным и ложным одновременно.

ЗАДАНИЕ 3

Что является алфавитом десятичной системы счисления?

Каково основное правило образования (записи) чисел в этой позиционной системе счисления?

ОТВЕТ. Алфавит: десятичные цифры, десятичная точка (или запятая) и знаки плюс и минус. Правило: вес цифры в числе зависит от ее позиции в записи числа.

ЗАДАНИЕ 4

Каким образом может быть проинтерпретировано слово двоичного алфавита “0100 1001 0100 0110” в известной вам системе программирования (пробелы вставлены для удобства восприятия)?

ОТВЕТ. В языке Pascal эти два байта могут быть интерпретированы как строка символов “IF”, как два числа типа byte - 73 и 70, как одно число типа integer - 20758 (18758 ???).

ЗАДАНИЕ 5

Графический интерфейс системы Windows содержит такие элементы как пиктограммы или иконки. Можно ли считать, что они входят в алфавит языка пользовательского интерфейса этой системы? Ответ обоснуйте.

РАСШИРЬ СВОЙ КРУГОЗОР

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

Причина возникновения знаков достаточно очевидна: большинство объектов познания и деятельности не доступны непосредственному восприятию в процессе познания и предъявлению в процессе коммуникации.

Знак (гр.  - знак, лат.транскрипция - semeion) - это материальный объект, выступающий в качестве представителя некоторого другого объекта, свойства или отношения и используемый для приобретения, хранения, переработки и передачи сообщений (информации, знаний).

ПРИМЕЧАНИЕ 1. Вместо слова “знак” в схожем смысле употребляются другие понятия: “имя”, “термин”, “обозначение”.

По определению одного из создателей теории знаков (семиотики) Ч.П.Пирса, знак - это такой элемент x, который заменяет субъекту некоторый элемент y (денотат) по некоторому признаку.

Соответственно, денотат - это то, что данный знак обозначает в конкретной ситуации.

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

ПРИМЕЧАНИЕ 2. Вместо слова “денотат” в логике употребляют другие (тождественные, синонимические) названия: чаще всего “значение”, “обозначаемое”.

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

ПРИМЕЧАНИЕ 3. Термин “концепт” имеет синонимы: “смысл”, “смысл знака”.

НАПРИМЕР, в слове “животное” мы обнаруживаем древнее значение слова “живот” - жизнь. Животные отличаются не наличием живота, а тем, что они живые, им присущ живот-жизнь. Таким образом, концепт знака “животное” - понятие живого существа, детонат - любое конкретное живое существо, которое имеется в виду в данной знаковой ситуации.

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

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

Иконическое отношение между означающим и означаемым - это, по Ч.Пирсу, “простая общность по некоторому свойству”. Знаки-копии (iconic signs) - воспроизведения, репродукции, которые сходны с обозначаемым (например, фотографии, отпечатки пальцев).

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

Для построения формальных языков важен именно этот тип знаков (см. параграф первой главы об основном тезисе формализации).

ПРИМЕЧАНИЕ 4. Символические знаки иногда называют символами . По мысли выдающегося русского философа П.А.Флоренского символ есть “бытие, которое больше самого себя. Символ - это нечто, являющее собою то, что не есть он сам, большее его, и однако существенно чрез него объявляющееся”. Например, мифическое существо грифон, сочетающее в себе льва и орла, является одним из символов Иисуса Христа.

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

НАПРИМЕР, буква  в финикийской азбуке называлась “алеф” - бык (она напоминает голову быка). Тогда она была иконическим знаком. В греческом же языке эта буква не связана с быком и становится знаком-символом.

По мере развития математической символики также происходит замена иконических знаков символами. Например, римская цифра V напоминала раскрытую руку (пять пальцев), а современная цифра 5 является символом.

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

Денотатами далеко не всегда являются реально существующие предметы и совокупности таких предметов. Множество примеров денотатов, не являющихся объектами реальности, содержится в известной сказке Л. Кэрола “Алиса в стране чудес”. В ней же образно сформулирован принцип возникновения таких денотатов:

“Жить-то он жил (Мартовский заяц- прим авт.), а быть-то он не был”. В этой связи и русская присказка “жил да был” вовсе не кажется тавтологией.

Структура знака описывается так называемым “треугольником Фреге” (по имени выдающегося немецкого логика, много сделавшего для развития теории формальных языков). В другой терминологии он называется “семантическим треугольником” или треугольником Огдена и Ричардса. Он устанавливает связь между знаком, денотатом знака и концептом знака.

Рис. 4.3.1. Треугольник Фреге

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

1) Синонимия - ситуация, заключающаяся в полном или частичном совпадении значений различных знаков:

Рис. 4.3.2. Схема синонимии

2) знаки могут иметь один и тот же денотат, но обладать разным смыслом (денотативное тождество). Например, знаки “sin 30°” и “1/2” имеют один и тот же денотат, то есть именуют одно и то же действительное число, но смысл этих знаков различен:

Рис. 4.3.3. Схема денотативного тождества

3) Полисемия (многозначность)- наличие у знака более одного значения:

Рис. 4.3.4. Схема полисемии

ИНТЕРЕСНЫЙ ФАКТ

Историческая справка

Первые шаги к созданию формального языка логики были сделаны еще в период античности. Аристотель (384-322 д н.э.) ввел в употребление буквенные переменные для субъектов и предикатов простых категорических высказываний, а глава школы стоиков Хрисипп (ок. 281-208 до н.э.) и его ученики - переменные для высказываний в целом. В XVI веке Р.Декарт (1596-1659) создал основу современного формального языка математики - буквенную алгебру, а Г.В.Лейбниц (1646-1716) перенес Декартову символику в логику. Основным языком логики в то время был естественный язык. Осознавая существенные синтаксические и семантические недостатки естественного языка (громоздкость, многозначность и неточность выражений, нечеткость синтаксических правил и т.п.), Лейбниц сформулировал тезис о том, что без создания специального искусственного языка - “универсального исчисления” - дальнейшее развитие логики невозможно. Но лишь в конце XIX века идея Лейбница получила развитие в исследованиях Дж.Буля (1815-1864), С.Джевонса (1835-1882), Э.Шредера (1841-1902) и других - появилась алгебра логики.

Дальнейшее развитие языка логики связано с именами Дж.Пеано (1858-1932) и Г.Фреге (1848-1925). Пеано ввел ряд принятых в современной математике символов, в частности “”, “”, “”, для обозначения соответственно отношений принадлежности, объединения и пересечения множеств. Фреге построил аксиоматическое исчисление высказываний и предикатов, в котором содержались все основные элементы современных логических исчислений.

Опираясь на результаты, полученные Фреге, и используя модифицированную символику Пеано, Б.Рассел (1872-1970) и А.Н.Уайтхед (1861-1947) в совместном труде “Принципы математики” (1913) сформулировали основные положения формального языка логики.

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

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

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

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

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

Особое место среди языков программирования занимают языки, обеспечивающие работу систем управления базами данных (СУБД). Часто в них выделяют две подсистемы: язык описания данных и язык манипулирования данными (другое название - язык запросов).

Основные понятия

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

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

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

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

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

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

Системой операций называется совокупность всех машинных операций, предусмотренных в ЭВМ.

Команда представляет собой элементарное предписание, предусматривающее выполнение некоторой группы операций.

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

Программирование

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

При решении на ЭВМ некоторой задачи (класса задач) работа распадается на следующие этапы:

математическую формулировку задачи;

разработку методики ее решения;

разработку алгоритма ее решения и запись ее на некотором языке программирования;

программирование;

отладку программы на машине;

подготовку исходных данных, решение задачи на ЭВМ.

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

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

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

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

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

Применяя ЭВМ для решения задачи, необходимо учитывать следующие ее особенности:

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

Программирование. Программирование заключается в записи разработанного алгоритма на языке программирования (например, на так называемом языке АССЕМБЛЕРА или на АЛГОЛе, ФОРТРАНе, КОБОЛе, ПЛ/I), выполняемой вручную, и последующей трансляции на машинный алгоритмический язык.

Трансляцией называется процесс равносильного преобразования алгоритма, заданного на языке программирования, в алгоритм на машинном языке. Этот процесс выполняется с помощью специальной программы, называемой транслятором.

Отладка программы на машине. Отладка программы на машине преследует цель устранить в программе неправильности и включает: контроль программы; поиск и определение содержания (диагностику) ошибок; исправление обнаруженных ошибок.

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

Как правило, для ввода информации в вычислительную машину используются либо 80-колонные ПК, либо бумажная ПЛ. На больших машинах имеется и то и другое. Перфокарта содержит 12 строк, и, следовательно, в каждой колонке возможно 12 пробивок; в поперечном направлении перфоленты допускаются 5, 6, 7 и 8 позиции пробивки. Таким образом, теоретически возможно использование алфавита от 2 5 =32 до 2 12 =4096 символов, но на практике в колонке перфокарты редко встречается более 3 пробивок, так что, как правило, используемый алфавит содержит от 40 до 80 символов. Среди оборудования вычислительной машины имеется самостоятельное устройство воспроизведения на бумаге информации, содержащейся на перфокартах и перфоленте в виде, удобном для чтения ее человеком. В результате мы получаем то, что обычно называется листингом, или распечаткой.

После ввода в ЭВМ программ и исходных данных решение задачи производится автоматически.

Математическое обеспечение ЭВМ

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

В систему МО вычислительных машин могут входить следующие группы программ:

операционная система программ;

система средств программирования;

приложения к программам;

система программ поддержания математического обеспечения;

система испытательных программ, предназначенных для контроля исправности ЭВМ.

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

диспетчер - программа, обеспечивающая определенный режим работы ЭВМ;

супервизор, или монитор,- программа, обеспечивающая работу, задаваемую машине человеком-оператором в рамках установленного для нее режима;

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

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

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

Супервизор планирует по требованию человека-оператора порядок выполнения программ и распределяет между ними наличное оборудование ЭВМ, организует их очередь и поддерживает в этой очереди порядок. Основные задачи, стоящие перед супервизором,- это: управление ходом работы ЭВМ; поддерживание связи с человеком-оператором.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В библиотеку собирают обычно специально составленные и специально оформленные программы.

Перечисленные средства программирования целесообразно применять для решения различных задач (проблем). При этом считается, что программы отдельных задач (проблем) могут быть и не очень «хорошие», зато суммарным расход средств на программирование и решение задачи на ЭВМ бывает обычно меньше, чем при составлении более «хороших» программ.

Математическое обеспечение АСУ

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

Основными положениями, которыми необходимо руководствоваться при создании МО АСУ, являются следующие:

• совместимость и базирование разрабатываемого МО АСУ на имеющемся МО ЭВМ;
• ориентированность выбираемых средств МО на задачи АСУ;
• достаточное разнообразие средств автоматизации программирования;
• возможность эффективного внесения изменений в рабочие программы;
• возможность однозначного и исчерпывающего описания алгоритмов;
• возможность оптимизации работы программ частного применения;
• модульность построения программ.

МО АСУ служит для представления пользователю широкого спектра услуг по технологии программирования. Его можно разделить на две части: составление управляющих программ и составление обрабатывающих программ.

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

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

Функции системы автоматизации программирования следующие: запись программ на входных языках программирования; трансляции программ на внутренний язык ЭВМ; объединение (сборка) нужных конфигураций (сегментов) из стандартных подпрограмм; отладка программ на уровне входных языков; корректировка программ на уровне входных языков.

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

Основными компонентами МО АСУ являются системная диспетчерская программа и библиотека стандартных подпрограмм и типовых программ, предназначенных для обработки производственно-экономической информации.

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

Библиотека стандартных подпрограмм, имеющаяся в МО ЭВМ, является переходной ступенью к разработке системной библиотеки, ориентированной на процессы обработки информации в АСУ. Системная библиотека должна содержать:

программы ввода и преобразования в машинную форму документов и других письменных источников исходных данных;

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

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

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

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

1. формальные алгоритмические языки;
2. формальные неалгоритмические языки программирования;
3. не вполне формализованные знаковые системы, применяемые при программировании.

Формальные языки программирования. К этой группе языков относятся: алгоритмические языки машин и операционных систем; машинно-ориентированные алгоритмические языки; проблемно-ориентированные алгоритмические языки; универсальные машинно-независимые алгоритмические языки.

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

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

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

Проблемно-ориентированные алгоритмические языки это такие языки, которые специально разработаны для описания процессов решения задач некоторого узкого класса, например задач линейной алгебры, статистики, задач обработки данных и т. п. В частности, к проблемно-ориентированным языкам относится КОБОЛ.

Универсальные машинно-независимые алгоритмические языки пригодны для создания алгоритмов решения задач весьма широких классов. К числу этих языков относятся уже упомянутые АЛГОЛ, ФОРТРАН, ПЛ/1.

Из числа универсальных машинно-независимых алгоритмических языков исключение составляет ЯЛС. Назначение этого языка не сводится к тому, чтобы быть языком программирования. ЯЛС используется как первый этап описания алгоритмов при программировании на машинном языке или на языке АССЕМБЛЕРА (операторный метод программирования; записанный на ЯЛС алгоритм вручную переводится на язык машины или язык АССЕМБЛЕРА).

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

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

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

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

язык нулевого или низшего уровня - машинный код;

язык первого уровня - мнемокод, или язык символического кодирования;

язык второго уровня - автокод (макрокод);

языки третьего уровня (высшего)-проблемно-ориентированные языки.

В качестве входных языков в зависимости от вида задач АСУП целесообразно применять проблемно-ориентированные языки различного типа

Сравнительные данные формальных алгоритмических языков программирования

(например, для анализа - АЛГОЛ, ФОРТРАН и др., для экономических задач- АЛГЭК и др., для информационных задач -КОБОЛ, СИНТОЛ и др.).

Рассмотрим некоторые из алгоритмических языков программирования.

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

АЛГОЛ-60 не только универсальный язык программирования, но и международный язык описания алгоритмов.

Основой записи алгоритмов на языке АЛГОЛ-60 является последовательность операторов, разделенных символом «;». К этой последовательности операторов, являющихся единичными действиями в языке, присоединяется последовательность описаний, дающих транслятору информацию о необходимых свойствах, используемых в операторах. Описания, например, дают информацию о классах чисел, используемых в качестве значений переменных, о размерности массивов чисел и т. д. Такое объединение описаний и операторов в этом языке называется блоком.

Программой в языке АЛГОЛ-60 называется блок, или составной оператор, который не содержит внутри другого оператора и не использует другой оператор, не содержащийся в нем.

Вычислительные центры, в которых ведется программирование на АЛГОЛе, должны накапливать опыт не в виде полных АЛГОЛ-программ, а в виде описаний процедур. Это связано с тем, что готовые АЛГОЛ-программы включить в новые программы практически невозможно, тогда как описания процедур для этого специально предназначены.

В СССР АЛГОЛ-60 получил распространение в виде некоторых его вариантов.

ФОРТРАН. Слово ФОРТРАН образовано из двух английских слов (Formula Translator). Одной из важнейших особенностей языка ФОРТРАН является то, что он относительно свободен от специфики конкретной вычислительной машины. ФОРТРАН является машиннонезависимым языком программирования.

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

Повсеместное внедрение ФОРТРАНа в практику программирования происходит благодаря его качествам, из которых следует отметить, во-первых, его простоту по сравнению с другими алгоритмическими языками (например, АЛГОЛом); во-вторых, благодаря отсутствию слишком сложных конструкций оттранслированные программы получаются более эффективными по сравнению с программами, составленными на других языках; в то же время ФОРТРАН пригоден для программирования большинства вычислительных алгоритмов;

в-третьих, в ФОРТРАНе имеются очень мощные средства для связи человека с машиной: выдаваемая ЭВМ информация представляется в виде, привычном для ученых и инженеров. И наконец, в-четвертых, ФОРТРАН хорошо приспособлен для эффективного использования внешних устройств ЭВМ.

Алгоритм решения задачи, записанный с помощью ФОРТРАНа, состоит из последовательности операторов. Эти операторы могут принадлежать к нескольким различным типам. Вместе взятые операторы, определяющие алгоритм решения задачи, составляют исходную программу. После того как исходная программа написана и отперфорирована на перфокартах, она преобразуется с помощью транслятора ФОРТРАНа в рабочую программу.

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

При составлении программ на ФОРТРАНе рекомендуется придерживаться следующего порядка следования операторов: 1) оператор-заголовок основной программы (подпрограммы); 2) оператор описания файлов; 3) неявный оператор задания типа; 4) явный оператор задания типа, оператор задания размеров, оператор задания общих областей; 5) оператор задания эквивалентности; 6) оператор-функция, оператор-процедура; 7) оператор задания формата, выполняемые операторы (безусловные, условные, ввода, вывода); 8) оператор конца.

КОБОЛ. Название языка происходит от английских слов Common Business Orientated Language. КОБОЛ - проблемно-ориентированный алгоритмический язык, предназначенный для описания процессов решения задач и обработки данных. В настоящее время КОБОЛ является единственным широко распространенным языком высокого уровня для программирования экономических задач. Его широкая популярность объясняется тем, что КОБОЛ достаточно близок к естественному языку, на котором обычно формулируются и решаются экономические задачи.

Отличительные особенности языка КОБОЛ состоят в следующем:

язык в известном смысле является подмножеством английского языка; написанный на КОБОЛе текст можно понимать без предварительной подготовки;

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

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

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

В КОБОЛе значительно облегчено внесение в программу мелких изменений, необходимых при обработке коммерческой информации.

В КОБОЛе основной единицей ввода-вывода является файл данных. Каждый файл состоит из записей. Один и тот же файл часто используется в различных программах в зависимости от характера решаемых задач. Описание файлов является очень строгим и не допускает изменений.

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

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

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

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

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

Рассмотрим некоторые специализированные алгоритмические языки моделирования.

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

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

Внимание специалистов, связанных с решением проблем моделирования, привлекают специализированные языки, разработанные для этих целей на базе АЛГОЛа. Среди таких языков автоматического программирования наиболее совершенными являютсяSIMULA и SOL (СОЛ).

Примером одного из наиболее удачных специализированных алгоритмических языков, предназначенных для моделирования дискретно изменяющихся систем, является язык СОЛ - Simulation Orientated Language.

Язык СОЛ построен на базе универсального языка программирования АЛГОЛ, имеет такую же структуру и использует основные его элементы. Для описания широкого класса процессов с дискретными событиями СОЛ представляет универсальную систему понятий, и потому он во многих отношениях очень похож на проблемно-ориентированные языки автоматического программирования, такие, как АЛГОЛ или ФОРТРАН. Однако языку СОЛ присущи основные черты, отличающие его от этих языков: СОЛ обеспечивает механизм моделирования асинхронных параллельных процессов, удобные обозначения для случайных элементов внутри арифметических выражении, автоматические средства сбора статистических данных о компонентах моделируемой системы. С другой стороны, многие черты проблемно-ориентированных универсальных языков не используются в СОЛе не потому, что они несовместимы с ним, а скорее потому, что они вносят большие усложнения в его схему, не расширяя его возможности. Принципы, положенные в основу построения языка и написания моделирующих программ на нем, позволяют строить модели сложных систем в удобной для чтения форме.

ПЛ/ I . Название языка происходит от английских слов Programming Language/One.

Язык ПЛ/I появился после создания целого ряда весьма совершенных языков, и, конечно, эти языки-предшественники оказали существенное влияние на его структуру. Так, в нем сохранены от АЛГОЛа блочная структура программы, возможность динамического распределения памяти, имеется аппарат вызова процедур, способ задания форматов, используемый в ФОРТРАНе, и т. д. Но много и новых черт. Язык удобен для моделирования, решения логических задач, исследования логических схем, решения задач в реальном масштабе времени, разработки систем математического обеспечения. Возможно использование разного типа данных (двоичных, десятичных, символьных, комплексных чисел, матриц и т. д.), однако весьма сложно организовывать эти данные в массивы, таблицы, тексты, анкеты, картотеки и т. и. Имеется большой набор стандартных функций и процедур. В языке ПЛ/I разработана удачная система операции, управляющих всеми процессами ввода, вывода и обмена информацией между основными и запоминающими устройствами. Все эти особенности производят впечатление сильной перегруженности языка. Следует иметь в виду и недостатки: описание языка неудовлетворительно, оно не формализовано.

ПЛ/I - многоцелевой язык программирования, предназначенный не только для экономического и научно-технического программирования, но также для программирования работ в реальном масштабе времени и для создания систем программирования.

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

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

Программы на языке ПЛ/I пишутся в свободной форме; программист может сам разработать нужные ему формы записи программ. При этом обеспечен доступ ко всем средствам системы ЭВМ.

Операторы программы, записанной на языке ПЛ/I, объединяются в «блоки». Блоки выполняют важные функции: они определяют область действия переменных и других имен, так что одно и то же имя в разных блоках может использоваться для различных целей; они позволяют отводить ячейки памяти под переменные только на время выполнения данного блока и освобождать их для использования в других целях по прекращении работы блока.

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

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

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

На основании этой информации транслятор РПГ формирует рабочую программу, и затем созданная программа обрабатывает входные файлы и печатает требуемый отчет.

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

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

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

После написания программы на соответствующих бланках текст программы перфорируется на картах.

Для получения рабочей программы сначала нужно выполнить трансляцию исходной программы. Для этого к картам исходной программы добавляются некоторые управляющие карты, такие, как управляющая карта транслятора РГ1Г и карты управляющих операторов - УПРАВЛЕНИЯ ЗАДАНИЯМИ, необходимые для работы транслятора РПГ. После трансляции полученный модуль может быть отредактирован с помощью РЕДАКТОРА. В результате редактирования получается готовая для выполнения программа (загрузочный модуль), которая называется рабочей программой. Компиляция и редактирование необходимы для получения желаемого отчета.

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

АЛГАМС. Алгоритмический язык АЛГАМС ориентирован на машины средней мощности; основой его стало подмножество языка АЛГОЛ-60.

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

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

При вводе текста последовательным элементам массива начиная с указанного объекта ввода присваиваются целые значения, соответствующие последовательным символам вводимой строки в смысле процедуры=ТЕХТ. Процедура = ТЕХТ определяется следующим образом: <оператор текст> ::=ТЕХТ (<строка>, <переменная с индексами>).

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

БЭЙСИ К. Название языка происходит от английских слов Beginners all Purpose Symbolic Instructioncode. Он получил широкую популярность благодаря своей простоте, легкости в изучении и большим возможностям для решения самых различных задач. Во многих мини-ЭВМ этот язык принят в качестве основного разговорного языка. Язык БЭЙСИК представляет собой язык программирования. Он удобен для решения научно-технических задач небольшого объема как по количеству выполняемых операций, так и по количеству исходных и результирующих данных. Важнейшей особенностью языка является то, что он приспособлен для шаговой реализации. Это означает, что после каждого изменения исходного текста программы на языке БЭЙСИК можно перетранслировать не всю-программу, а только те ее операторы, которые были изменены. Возможность шаговой реализации языка БЭЙСИК позволяет сократить затраты машинного времени на перетрансляцию. Это в свою очередь позволяет ускорить цикл отладки настолько, что становится целесообразной отладка БЭЙСИК-программ в режиме диалога.

Помимо возможности накапливать большие программы, состоящие из перенумерованных операторов языка БЭЙСИК, предусмотрены так называемые прямые команды, т. е. такие, которые исполняются тотчас же после ввода их с пульта программиста (с телетайпа). В режиме прямых команд могут использоваться не только административные директивы типа RUN-запуск исполнения, LIST - распечатка текста, SAVE - сохранить текст программы в библиотеке, BYE - конец сеанса работы; любой оператор языка БЭЙСИК, введенный без порядкового номера, исполняется в режиме прямой команды. Это позволяет, в частности, распечатывать и изменять значения переменных в любой момент выполнения программы.

Служебное слово Выполняемое действие

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

INPUT Ввести числа с пульта программиста и заслать их в указанные переменные

LET Присвоить переменной значение выражения

GO ТО Перейти к выполнению оператора с заданным номером

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

DATA Данные; этот оператор не выполняется. Он описывает блок отладочных данных (чисел). Совокупность блоков отладочных данных образует массив отладочных данных

END Конец программы

Таким образом, шаговая схема компиляции в сочетании с режимом прямых команд позволяет эффективно отлаживать БЭЙСИК-программы в режиме диалога.

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

При решении многих задач необходимо представление данных в виде таблиц. Используя возможности некоторых операторов языка БЭЙСИК, можно формировать таблицы различных форматов.

Главная » База знаний » Естественный язык программирования пример. Формализованные (формальные) языки