Формализованный язык программирования это

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

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

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

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

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

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

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

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

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

Источник

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

Конец

Начало

Повторять

Начало

Псевдокоды

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

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

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

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

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

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

то стоп все;

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

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

конец;

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

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

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

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

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

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

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

Универсальные языки высокого уровня обеспечивают создание различных программ (задач), например Алгол, Си, ПЛ/1 и т.д..

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

Фирма Microsoft использует Visual Basic для расширения функций своих программных продуктов. Уже в пакете Microsoft Office для Windows 3-х пользователям и программистам предлагались диалекты Word Basic и Access Basic, а ныне в Microsoft Office предусмотрен универсальный язык Visual Basic for Applications (VBA — Visual Basic для приложений). Ранее этот язык использовался только в Excel 5.0. С помощью VBA можно создавать собственные программные модули, собственные интерфейсы для офисных приложений Word, Excel, Access.

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

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

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

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

Ø применение объектно-ориентированных языков;

Ø визуальное программирование (т. е. сборка экранной формы с помощью мыши из готовых «полуфабрикатов »-объектов);

Ø быстрая разработка приложений (RAD — Rapid Applications Development);

Ø программирование с использованием функций API Windows (Applications Programming Interface — интерфейс прикладного программирования);

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

Подробно языки программирования не будут рассмотрены в данном курсе.

Источник

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

Мотивация

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

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

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

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

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

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

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

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

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

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

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

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

Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L = (здесь n — натуральное число) задает язык L, состоящий из цепочек вида ab, aabb, aaabbb и т.д. Язык L представляет собой бесконечное множество цепочек, но тем не менее, его грамматика (описание) состоит всего из 10 символов, т.е. конечна.

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

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

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

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

В середине 60-х годов советский математик Юлий Анатольевич Шрейдер предложил простой способ описания синтаксиса языков на основе т.н. окрестностных грамматик. Для каждого символа языка задается конечное число его «окрестностей» — цепочек, содержащих данный символ (центр окрестности) где-то внутри. Набор таких окрестностей для каждого символа алфавита языка называется окрестностной грамматикой. Цепочка считается принадлежащей языку, задаваемому окрестностной грамматикой, если каждый символ этой цепочки входит в нее вместе с некоторой своей окрестностью.

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

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

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

Источник