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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Грамматики

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

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

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

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

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

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

ПОНЯТЬ

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

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

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

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

На протяжении всей истории развития математики в ней широко использовались символические обозначения для различных объектов и понятий. Однако, наряду с символическими обозначениями ученые-математики свободно пользовались и естественным языком. Но на каком-то этапе развития науки (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-х годов, а программа, переводящая предложения этого языка на машинный язык, стала называться транслятором .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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