Лексика синтаксис и семантика языка программирования. Синтаксис и семантика паскаль. Нормальные формы Бекуса

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

Алфавит. Синтаксис и семантика:

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

Строчные и прописные латинские буквы:

Символ подчеркивания: «_» Пробел: « » Арабские цифры от 0 до 9:

Перечень знаков операций:

Последовательность ограничителей:

Спецификаторы:

Служебные слова:

Элементарные конструкции языка Паскаль: имена, числа, строки . Именами (или идентификаторами) называются элементы языка - метки, константы, переменные, типы, процедуры, модули, функции, объекты. Имя (идентификатор) в среде Турбо Паскаль включает в себя цифры, буквы латинского алфавита, символ подчеркивания. Отсутствует различие между прописными и строчными буквами (PROGRAM, Program и program - означает одно и то же).

На первом месте в идентификаторе не может стоять цифра (т.е. 1program - не правильно, program3 иprogram2file - такие идентификаторы допускаются). Символ «_» может находиться в любой позиции (т.е. _program,program_, program_file - допустимые идентификаторы). Идентификатор может иметь неопределенную длину, однако только первые 63 символа в нем значимые. Служебные (зарезервированные) слова не могут выступать в качестве имен.

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

В исходном коде программы комментарии заключают или в фигурные скобки»{ … }», или в скобки вида «(* … *)». Комментарии могут занимать неопределенное число строк. В языке Паскаль числа чаще представляются в десятичной системе счисления (целые и действительные). Положительный знак числа не учитывается, поэтому может быть опущен. Целые числа представляются в форме без десятичной точки:

395 -67 7808 +126

А действительные представляются в форме с десятичной точкой:

597.2 1.79 -5.526 8.0004

При случае допускается возможность записи числа с использованием десятичного порядка (обозначается E):

3E09 = 3*10^9 -5.34E6 = -5.34*10^6 29.3E-29 = 29.3*10^(-29)

Способы задания языков

Понятие языка. Формальное определение языка

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

Алфавит -это счетное множество допустимых символов языка. Это множество символовобозначают V. Согласно формальному определению, алфавит не обязательно должен быть конечным (перечислимым) множеством, но реально все существующие языки строятся на основе конечных алфавитов.

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

Если V – некоторый алфавит, то:

● V⁺ –множество всех цепочек над алфавитом V без l;

● V* - множество всех цепочек над алфавитом V , включая l.

Справедливо равенство:V* =V + È{λ}

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

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

Два языка L(V) и L"(V) совпадают (эквивалентны): L’(V)=L(V), если L’(V)⊆L(V) и L(V)⊆L’(V).

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

Два языка L(V) и L’(V) почти эквивалентны, если L’(V)È{l}= L(V)È{l}. Множества допустимых цепочек символов почти эквивалентных языков могут различаться только на пустую цепочку символов.

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

Язык задать можно тремя способами:

1. Перечислением всех допустимых цепочек языка.

2. Указанием способа порождения цепочек языка (заданием грамматики языка)

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

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

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

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

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

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

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

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

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

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

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

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

Языки программирования относятся к группе формальных языков, для которых в отличие от естественных языков однозначно определены синтаксис и семантика. Описание синтаксиса языка включает определение алфавита и правил построения различных конструкций языка из символов алфавита и более простых конструкций. Для этого обычно используют форму Бэкуса-Наура (БНФ) или синтаксические диаграммы . Описание конструкции в БНФ состоит из символов алфавита языка, названий более простых конструкций и двух специальных знаков:

· «::=» - читается как «может быть заменено на»,

· «|» - читается как «или».

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

Пример БНФ

Правила построения конструкции <Целое>, записанные в

БНФ, могут выглядеть следующим образом:

<Целое> ::= <3нак> <Целое без знака> | <Целое без знака>

<Целое без знака> ::= <Целое без знака> <Цифра> | <Цифра>

<Цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<3нак> ::= + | -

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

Синтаксические диаграммы отображают правила построения конструкций в более наглядной форме. На такой диаграмме символы алфавита изображают блоками в овальных рамках, названия конструкций – в прямоугольных, а правила построения конструкций - в виде линий со стрелками на концах. При этом, если линия входит в блок, то в описываемую конструкцию должен входить соответствующий символ. Разветвление линии означает, что при построении конструкции возможны варианты. На рис. 2.1 представлена синтаксическая диаграмма, иллюстрирующая первые два правила описания конструкции <Целое>. Из диаграммы видно, что целое число может быть записано со знаком или без и включать произвольное количество цифр.

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

Алфавит языка программирования Borland Pascal 7.0 включает:

1. строчные, прописные буквы латинского алфавита (a..z, A..Z) и знак подчеркивания (_), который также во многих случаях считается буквой (строчные и прописные буквы не различаются);

2. цифры (0...9);

3. специальные знаки, состоящие из одного и двух символов:

. ,+ - * / = : < > { } () ^ @ $ #<> <= >= := (* *)

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

Из символов алфавита в соответствии с правилами синтаксиса строят различные конструкции. Простейшей из них является конструкция <Идентификатор>.

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

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

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

Структура программы

Программа на Borland Pascal состоит из трех частей: заголовка, раздела описаний и раздела операторов.

• Заголовок программы не является обязательным, он состоит из служебного слова program и идентификатора - имени программы.
• Раздел описаний содержит описания всех используемых программой ресурсов (полей данных, подпрограмм и т.д.).
• Раздел операторов заключается в, так называемые, операторные скобки begin ...end и заканчивается точкой. Между операторными скобками записывают управляющие операторы программы, которые разделяют специальным знаком – точкой с запятой «;». Если точка с запятой стоит перед end , то считается, что после точки с запятой стоит «пустой» оператор.
• В тексте программы возможны комментарии, которые помещают в фигурные скобки.

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

Program example; {заголовок программы}

{раздел описаний}

Uses crt;

Var a,b:integer; {объявление переменных}

{раздел операторов}

Write ("Введите два натуральных числа:"); {запрашиваем ввод данных}

Readln(a,b); {вводим значения}

while a<>b do {цикл-пока а<>b}

if a>b then a:=a-b {если a>b, тогда a:=a-b}

else b:=b-a; {иначе b:=b-a}

Writeln(‘Hauбoльшuй общий делитель равен ’,a); {выводим результат}

End. {конец программы}

Программа названа «example». Раздел описаний в данном случае включает только описание переменных (см. параграф 2.3). Раздел операторов содержит операторы ввода исходных данных, вычислений и вывода результатов. Начнем рассмотрение особенностей программирования на языке Borland Pascal с проблемы описания данных.

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

Алфавит – совокупность символов, отображаемых на устройствах печати и экранах и/или вводимых с клавиатуры терминала. Обычно это набор символов Latin-1 с исключением управляющих символов. Иногда в это множество включаются неотображаемые символы с указанием правил их записи (комбинирование в лексемы).

Лексика – совокупность правил образования цепочек символов (лексем), образующих иден­тификаторы (переменные и метки), операторы, операции и другие лексические компоненты языка. Сюда же включаются зарезервированные (запрещенные, ключевые) слова языка программирования, предназначенные для обозначения операторов, встроенных функций и пр. Иногда эквивалентные лексемы, в зависимости от языка программирования, могут обозначаться как одним символом алфавита, так и несколькими. Например, операция присваивания значения в языке Си обозначается как «=», а в языке Паскаль – «:=». Операторные скобки в языке Си задаются символами «{» и «}», а в языке Паскаль – begin и end. Граница между лексикой и алфавитом, таким образом, является весьма условной, тем более что компилятор обычно на фазе лексического анализа заменяет распознанные ключевые слова внутренним кодом (например, begin – 512, end – 513) и в дальнейшем рассматривает их как отдельные символы.

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

Необходимо строгое соблюдение правил правописания (синтаксиса) программы. В частности, в Паскале однозначно определено назначение знаков пунктуации. Точка с запятой (;) ставится в конце заголовка программы, в конце раздела описания переменных, после каждого оператора. Перед словом End точку с запятой можно не ставить. Запятая (,) является разделителем элементов во всевозможных списках: списке переменных в разделе описания, списке вводимых и выводимых величин.

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

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

Для описания синтаксиса языка программирования тоже нужен какой-то язык. В этом случае речь идет о метаязыке («надъязыке»), предназначенном для описания других языков. Наиболее распространенными метаязыками в литературе по программированию являются металингвистические формулы Бекуса – Наура (язык БНФ) и синтаксические диаграммы. Язык синтаксических диаграмм более нагляден, легче воспринимается.

В БНФ всякое синтаксическое понятие описывается в виде формулы, состоящей из правой и левой части, соединенных знаком::=, смысл которого эквивалентен словам «по определению есть». Слева от знака::= записывается имя определяемого понятия (метапеременная), которое заключается в угловые скобки < >, а в правой части записывается формула или диаграмма, определяющая все множество значений, которые может принимать метапеременная.

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

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

В записях метаформул приняты определенные соглашения. Например, формула БНФ, опре­деляющая понятие «двоичная цифра», выглядит следующим образом:

<двоичная цифра>::=0|1

Значок «|» эквивалентен слову «или».

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

Понятие «двоичный код» как непустую последовательность двоичных цифр БНФ описывает так:

<двоичный код>::=<двоичная цифра>|<двоичный

код><двоичная цифра>

Определение, в котором некоторое понятие определяется само через себя, называется рекурсивным. Рекурсивные определения характерны для БНФ.

Возвратная стрелка обозначает возможность многократного повторения. Очевидно, что диа­грамма более наглядна, чем БНФ.

Синтаксические диаграммы были введены Н. Виртом и использованы для описания созданного им языка Паскаль.

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

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

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

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

В 1960-х гг. X. Барендрегтом (Hendrik Barendregt) был детально описан синтаксис лямбда-исчисления - математической формализации, поддерживающей языки функционального программирования. Примерно в то же время Дж. Бэкусом (John Backus) были созданы основы формализации синтаксиса языков программирования посредством специального математического языка. Позднее П. Науром (Peter Naur) этот язык (а с точки зрения целевого языка программирования - метаязык) был доработан, в результате чего возникла математическая нотация, известная и сегодня под названием «форм Бэкуса - Наура» (БНФ).

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

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

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

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

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

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

Прежде всего, необходимо договориться об обозначениях. Рассмотрим традиционные обозначения БНФ и поясним смысл каждого из них.

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

Проиллюстрируем формализацию синтаксиса формальной системы посредством нотации БНФ, рассмотрев в качестве примера знакомое нам по предыдущим главам лямбда-исчисление:

() | к .

Поясним смысл приведенных обозначений.

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

• 1) константы;
• 2) переменной;
• 3) двух выражений, заключенных в круглые скобки, г.е. операции аппликации лямбда-выражений;
• 4) символа к, за которым следует переменная, точка и выражение, т.е. операции абстракции лямбда-выражений.

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

Для иллюстрации перечисленных выше тезисов рассмотрим важнейшие синтаксические категории языка программирования F#. Под выражением будем понимать обозначение конструкции языка, которой может быть присвоено значение (константы, переменной, функции и т.д.). Описанием будем в дальнейшем называть запись, связывающую выражение языка программирования с именем, обозначающим его в программе (идентификатором). Под термином «зарезервированное» (или, иначе, «служебное») слово будем иметь в виду конструкцию языка, однозначно интерпретируемую в качестве инструкции языка программирования (например, «if», «then», «let»). Напомним, что в данной нотации цитирование производится без кавычек или других символов-ограничителей. Комментарием назовем произвольный поясняющий текст к программе, который, согласно синтаксису языка F# положено заключать в ограничители вида «(*» и «*)», а «//» - комментарий до конца строки.

Продолжим обсуждение синтаксических категорий языка программирования F#. В частности, рассмотрим структуру основных синтаксически допустимых типов выражений языка. Приведем соответствующую формализацию в терминах БНФ:

Как видно из БНФ-формализации, синтаксически корректным выражением в языке программирования F# считается:

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

В дополнение к перечисленным на предыдущем слайде альтернативам синтаксически допустимыми выражениями языка программирования F#, как следует из БНФ

if then else | (...) |

также являются:

• 1) три выражения, соединенные зарезервированными словами if («если»), then («тогда») и else («в противном случае»), называемые условным выражением и фактически представляющие собой предикатную функцию, которая реализует выполнение второго выражения в случае истинности первого и выполнение третьего в противном случае;
• 2) конечную последовательность выражений, заключенную в круглые скобки (или так называемый кортеж) и применяемую для структуризации данных;
• 3) описание и выражение, соединенные зарезервированным словом in («в»), которые определяют операцию подстановки описания в выражение с учетом всевозможных вхождений в него указанного фрагмента описания;
• 4) выражение, заключенное в круглые скобки (как мы уже знаем, в лямбда-исчислении и комбинаторной логике эту операцию можно производить без ограничений) и используемое для явного указания приоритета операции.

Перейдем к рассмотрению структуры синтаксически допустимых видов описаний объектов языка. Приведем соответствующую формализацию в терминах БПФ:

let = | let «^последовательность неременных> =

Синтаксически допустимыми описаниями языка программирования F#, как следует из представленной БНФ, являются:

• 1) идентификатор и выражение, соединенные зарезервированными словами let и =, которые обозначают связывание идентификатора (переменной, константы или другого синтаксически допустимого объекта языка программирования) с тем или иным выражением;
• 2) идентификатор, последовательность переменных и выражение, соединенные зарезервированными словами let и =, которые обозначают связывание функции (обозначенной первым идентификатором) с выражением, которое определяет порядок вычисления значения.

Перейдем к рассмотрению структуры синтаксически допустимых видов описаний типов объектов языка. Приведем соответствующую формализацию в терминах БНФ:

Sbytel intl6 | uint 16| uint32| int64| uint64|

Как следует из представленной БНФ, синтаксически допустимыми типами языка программирования F# являются:

• 1) целочисленные величины;
• 2) числа с «плавающей» запятой;
• 3) логические значения;
• 4) отсутствие значения;
• 5) кортежи - упорядоченные п -ки элементов определенных типов;
• 6) функции - упорядоченные и-ки элементов определенных типов, соединенных зарезервированными символами -к

Рассмотрим следующий пример, иллюстрирующий приписывание типов в языке F#. Константа типа кортеж вида (0, false, 1, true) имеет тип (int*bool*int*bool). Заметим, что варианты типов (1)-(4) являются элементарными, тогда как (5) и (6) представляют собой производные типы с явно указанной (или выводимой) структурой, откуда и происходит название «структурированный тип».

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

Рассмотрим подробнее синтаксические особенности основных видов литералов. Приведем соответствующую формализацию в терминах БНФ:

Как следует из представленной БНФ, синтаксически допустимыми типами литералов в языке программирования F# являются следующие:

• 1) целочисленные литералы, имеющие типы int, sbyte, byte, inti б, uintlG, int32, uint, uint32, int64, uint64, bigint;
• 2) строковые литералы, имеющие типы Char, byte, byte, string;
• 3) вещественные литералы, имеющие типы decimal, float; double, single, float32.

Заметим, что значение (т.е. семантика) литералов в полной мере определяется их лексическим (а значит, и синтаксическим) представлением.

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

Как следует из представленной БНФ, синтаксически допустимая конструкция языка программирования F#, описывающая операцию аппликации, весьма точно соответствует описанию операции аппликации выражений в лямбда-исчислении.

Проиллюстрируем аппликацию функции к аргументу в языке программирования F# следующим примером. Рассмотрим функцию succ, которая задается определением

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

Перейдем к рассмотрению синтаксически допустимых конструкций языка программирования F#, называемых условными выражениями. Приведем соответствующую формализацию в терминах БНФ:

Как видно из БНФ-формализации, синтаксически корректное условное выражение состоит из трех подвыражений, соединенных зарезервированными словами if, then и else, уже упоминавшихся в данном параграфе.

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

Заметим также, что функции сравнения встроены в язык F# и имеют вид «=» (равно), «» (больше), «=» (больше или равно), «» (не равно). Результатом вычисления любой из этих функций является логическое значение.

Проиллюстрируем синтаксис условного выражения следующим примером на языке F#:

if п>=10 then 1 else О

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

Рассмотрим структуру синтаксически допустимых конструкций, известных под названием let-выражений. Приведем соответствующую формализацию в терминах БНФ:

Как видно из БНФ-формализации, синтаксически корректное let- выражение состоит из описания и выражения, соединенных зарезервированными словами let и in.

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

Проиллюстрируем синтаксис let-выражений примерами из языка программирования F#. Рассмотрим следующие let-выражения:

let k=9876*8765 in (k-1, k, k+1)

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

(лх. х+1) 2. Второе выражение позволяет свести многократное вычисление громоздкой операции (умножения) к однократному.

В данном параграфе неоднократно упоминалось понятие кортежа. Рассмотрим подробнее этот весьма важный (особенно при реализации функций) вид синтаксических конструкций языка программирования F#. Приведем формализацию синтаксически допустимого представления кортежа в терминах БНФ:

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

Проиллюстрируем синтаксис конструкции кортежа примерами из языка программирования F#:

• (1, 2*1, 2*2*1)
• (1, true, 0, false)

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

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

Рассмотрим формализации синтаксически корректных описаний переменных и функций в терминах БНФ:

::= fun -> ::= let =

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

Проиллюстрируем формальные описания переменных и функций следующими содержательными примерами:

let гес fact n=if n -> x*x+y*y;

Первый из приведенных примеров представляет собой описание (целочисленной) переменной х, второй - рекурсивной (самонрименимой) функции fact вычисления факториала (произведения натуральных чисел от 1 до п), а третий - двухместной функции f, вычисляющей сумму квадратов аргументов.

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

• синтаксис языков функционального программирования достаточно близок к синтаксису формальных теорий, на которых они основаны (в частности, это справедливо для лямбда-исчисления и языка F#);
• БНФ являются актуальной и адекватной формализацией синтаксиса языка;
• язык программирования F#, в отличие от ранних языков функционального программирования, имеет ряд расширенных конструкций (кортежи, let-выражения и др.).

Контрольные вопросы

Вариант 1 : в чем состоит основное назначение синтаксиса?

• а) формализация вида и формы конструкций языка (+);
• б) формализация значения конструкций языка;
• в) формализация абстрактной машины для реализации языка.

Вариант 2: какова последовательность синтаксического разбора программы?

• а) лексический, синтаксический, семантический анализ (+);
• б) синтаксический, лексический, семантический анализ;
• в) семантический, лексический, синтаксический анализ.

Вариант 3: что из перечисленного является формализацией синтаксиса?

• а) форма Бэкуса - Наура (+);
• б) лямбда-исчисление;
• в) комбинаторная логика.

Вариант 1 : какой из объектов не имеет обозначения в формах Бэкуса - Наура?

• а) определяемая конструкция;
• б) альтернативные конструкции;
• в) цитирование (+).

Вариант 2: что понимается под синтаксисом?

• а) совокупность элементов языка;
• б) описание формы языка (+);
• в) модель реализации языка.

Вариант 3: какие объекты может содержать выражение языка F#?

• а) идентификатор, литерал, выражение (+);
• б) функция, идентификатор, литерал;
• в) условие, литерал, выражение.

Вариант 1: каков наиболее полный перечень синтаксических категорий языка F#?

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

Вариант 2: какие ключевые слова используются для описания в языке F#?

• а) val, fun, let;
• б) val, if, local;
• в) let, fun (+).

Вариант 3: на какие категории подразделяются типы F#?

• а) структурированные и неструктурированные (+);
• б) литералы и функции;
• в) переменные и константы.