Основными элементами любого языка программирования являются его алфавит, синтаксис и семантика.
Алфавит – совокупность символов, отображаемых на устройствах печати и экранах и/или вводимых с клавиатуры терминала. Обычно это набор символов Latin-1 с исключением управляющих символов. Иногда в это множество включаются неотображаемые символы с указанием правил их записи (комбинирование в лексемы).
Лексика – совокупность правил образования цепочек символов (лексем), образующих идентификаторы (переменные и метки), операторы, операции и другие лексические компоненты языка. Сюда же включаются зарезервированные (запрещенные, ключевые) слова языка программирования, предназначенные для обозначения операторов, встроенных функций и пр. Иногда эквивалентные лексемы, в зависимости от языка программирования, могут обозначаться как одним символом алфавита, так и несколькими. Например, операция присваивания значения в языке Си обозначается как «=», а в языке Паскаль – «:=». Операторные скобки в языке Си задаются символами «{» и «}», а в языке Паскаль – begin и end. Граница между лексикой и алфавитом, таким образом, является весьма условной, тем более что компилятор обычно на фазе лексического анализа заменяет распознанные ключевые слова внутренним кодом (например, begin – 512, end – 513) и в дальнейшем рассматривает их как отдельные символы.
Синтаксис – совокупность правил образования языковых конструкций, или предложений языка программирования – блоков, процедур, составных операторов, условных операторов, операторов цикла и пр. Особенностью синтаксиса является принцип вложенности (рекурсивность) правил построения конструкций. Это значит, что элемент синтаксиса языка в своем определении прямо или косвенно в одной из его частей содержит сам себя. Например, в определении оператора цикла телом цикла является оператор, частным случаем которого является все тот же оператор цикла.
Необходимо строгое соблюдение правил правописания (синтаксиса) программы. В частности, в Паскале однозначно определено назначение знаков пунктуации. Точка с запятой (;) ставится в конце заголовка программы, в конце раздела описания переменных, после каждого оператора. Перед словом End точку с запятой можно не ставить. Запятая (,) является разделителем элементов во всевозможных списках: списке переменных в разделе описания, списке вводимых и выводимых величин.
Строгий синтаксис в языке программирования необходим прежде всего для транслятора. Транслятор – это программа, которая исполняется формально. Если, допустим, разделителем в списке переменных должна быть запятая, то любой другой знак будет восприниматься как ошибка. Если точка с запятой является разделителем операторов, то транслятор в качестве оператора воспринимает всю часть текста программы от одной точки с запятой до другой. Если вы забыли поставить этот знак между какими-то двумя операторами, то транслятор будет принимать их за один, что неизбежно приведет к ошибке.
Основное назначение синтаксических правил – придать однозначный смысл языковым конструкциям. Если какая-то конструкция может трактоваться двусмысленно, значит, в ней обязательно содержится ошибка. Лучше не полагаться на интуицию, а выучить правила языка.
Для описания синтаксиса языка программирования тоже нужен какой-то язык. В этом случае речь идет о метаязыке («надъязыке»), предназначенном для описания других языков. Наиболее распространенными метаязыками в литературе по программированию являются металингвистические формулы Бекуса – Наура (язык БНФ) и синтаксические диаграммы. Язык синтаксических диаграмм более нагляден, легче воспринимается.
В БНФ всякое синтаксическое понятие описывается в виде формулы, состоящей из правой и левой части, соединенных знаком::=, смысл которого эквивалентен словам «по определению есть». Слева от знака::= записывается имя определяемого понятия (метапеременная), которое заключается в угловые скобки < >, а в правой части записывается формула или диаграмма, определяющая все множество значений, которые может принимать метапеременная.
Синтаксис языка описывается путем последовательного усложнения понятий: сначала определяются простейшие (базовые), затем все более сложные, включающие в себя предыдущие понятия в качестве составляющих.
В такой последовательности, очевидно, конечным определяемым понятием должно быть понятие программы.
В записях метаформул приняты определенные соглашения. Например, формула БНФ, определяющая понятие «двоичная цифра», выглядит следующим образом:
<двоичная цифра>::=0|1
Значок «|» эквивалентен слову «или».
В диаграммах стрелки указывают на последовательность расположения элементов синтаксической конструкции; кружками обводятся символы, присутствующие в конструкции.
Понятие «двоичный код» как непустую последовательность двоичных цифр БНФ описывает так:
<двоичный код>::=<двоичная цифра>|<двоичный
код><двоичная цифра>
Определение, в котором некоторое понятие определяется само через себя, называется рекурсивным. Рекурсивные определения характерны для БНФ.
Возвратная стрелка обозначает возможность многократного повторения. Очевидно, что диаграмма более наглядна, чем БНФ.
Синтаксические диаграммы были введены Н. Виртом и использованы для описания созданного им языка Паскаль.
Семантика – смысловое содержание конструкций, предложений языка, семантический анализ – это проверка смысловой правильности конструкции. Например, если мы в выражении используем переменную, то она должна быть определена ранее по тексту программы, а из этого определения может быть получен ее тип. Исходя из типа переменной, можно говорить о допустимости операции с данной переменной. Семантические ошибки возникают при недопустимом использовании операций, массивов, функций, операторов и пр.
Способы задания языков
Понятие языка. Формальное определение языка
В общем случае язык - это заданный набор символов и правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных текстов. Основой любого естественного или искусственного языка является алфавит, определяющий набор допустимых символов языка.
Алфавит -это счетное множество допустимых символов языка. Это множество символовобозначают 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. Определением метода распознавания цепочек языка.
Первый из методов является чисто формальным и на практике не применяется, так как большинство языков содержат бесконечное число допустимых цепочек и перечислить их просто невозможно.
Второй способ предусматривает некоторое описание правил, с помощью которых строятся цепочки языка. Тогда любая цепочка, построенная с помощью этих правил из символов и алфавита языка, будет принадлежать заданному языку.
Третий способ предусматривает построение некоторого логического устройства (распознавателя) – автомата, который на входе получает цепочку символов, а на выходе выдает ответ: принадлежит или нет эта цепочка заданному языку .
Говоря о любом языке, можно выделить синтаксис и семантику. Кроме того, трансляторы имеют дело также с лексическими конструкциями (лексемами), которые задаются лексикой языка.
Синтаксис языка – это набор правил, определяющий допустимые конструкции языка. Синтаксис определяет «форму языка» - задает набор цепочек символов, которые принадлежат языку. Чаще всего синтаксис языка можно задать в виде строгого набора правил, но полностью это утверждение справедливо только для чисто формальных языков.
Семантика языка – это раздел языка, определяющий значения предложений языка. Семантика определяет «содержание языка» - задает значения для всех допустимых цепочек языка. Семантика для большинства языков определяется неформальными методами.
Лексика – это совокупность слов (словарный запас) языка. Слово или лексическая единица языка – это конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций. Иначе говоря, лексическая единица может содержать только элементарные символы и не может содержать других лексических единиц.
Лексическими единицами русского языка являются слова русского языка, а знаки препинания и пробелы представляют собой разделители, не образующие лексем. Лексическими единицами алгебры являются числа, знаки математических операций, обозначения функций и неизвестных величин. В языках программирования лексическими единицами являются ключевые слова, идентификаторы, константы, метки, знаки операций; в них также существуют и разделители (запятые, скобки, точки с запятой и т. д.)
Конспект урока
Два аспекта языков
- У языка программирования есть два аспекта:
- Синтаксис (правила написания кода, правописание, порядок слов)
- Некоторые языки программирования имеют похожий синтаксис
- Некоторые языки имеют экзотический, необычный синтаксис
- Семантику сложно увидеть, она неявная
Синтаксис и семантика
- В современных языках хороший код означает легко понятную семантику
- Если понять то, что делает код сложно, то код не слишком хороший
- Синтаксис легко изучать
- Синтаксис необходимо знать, но этого недостаточно
Выбор языка
- Не так важно с какого языка начинать
- Вы будете переключаться на разные языки и использовать несколько языков и технологий одновременно. Такова реальность современного программирования.
- Мы выбрали JavaScript, потому что он простой, очень популярный и работает почти везде.
- JavaScript обычно используется для написания веб-сайтов, мобильных приложений, программного обеспечения для серверов и многого другого.
- Этот сайт в эту самую секунду использует JavaScript.
- Программы, написанные на JavaScript, запущены сейчас на ваших компьютерах.
Дополнительно
Вы будете писать программы на современном языке программирования, и большую часть времени не будете сталкиваться с двоичной системой - теми нулями и единицами или битами . Но вы должны понимать идею , которая лежит в основе двоичных чисел. Вот короткое и простое иллюстрированное объяснение:
Транскрипт урока
Мы назвали систему нажимания кнопок "языком". Рычаг, видимо, это отдельная штука, он как команда "ЗАПУСТИТЬ". Мы вводим код кнопками и ЗАПУСКАЕМ его рычагом.
Знаете, как лингвисты обсуждают грамматику, структуру слов и подобные вещи? Их не особо интересуют романы, песни или рассказы, они больше заинтересованы в языке, который используется для этих романов, песен и рассказов. Их интересует код. Большинство людей, напротив, заинтересовано в историях и смысле. Не только в книгах и фильмах, но и в жизни. Когда я прошу свою девушку купить мне новый альбом, потому что я делаю нелепые рисунки для этих уроков, меня интересует результат, цель, а не этимология и структура слова "альбом".
Можно считать, что у языка есть два... компонента или две особенности: грамматика и назначение. Языки программирования похожи в этом смысле, но поскольку они намного проще, чем человеческие, грамматика у них не на первом месте, но синтаксис - порядок слов и словообразование - важен. А для назначения, для понятия "смысл" программисты используют модное слово "семантика".
Попробуем сравнить язык магического ящика Тоты с каким-нибудь современным языком программирования.
У этого ящика очень сложный синтаксис, с символами Х и О сложно работать. А вот этот современный код выглядит... хмм, как английский язык! Этот синтаксис намного легче освоить, как минимум можно догадаться, что значит каждое слово.
Набор правил, который описывает как символы и слова могут использоваться - это синтаксис.
Вы увидите, что некоторые языки программирования имеют похожий синтаксис, а некоторые - экзотический, необычный.
Семантику или смысл увидеть сложнее, потому что он неявный. Какое назначение у этого кода? Это огненная вспышка, как мы уже поняли. Какое назначение у этого кода? Возможно, вы догадались: он выводит на печать фразу задом наперед. Смысл, конечный результат запущенного кода - это семантика.
В современных языках программирования связь между кодом и его видимым назначением можно использовать, чтобы судить о качестве кода. Если вы смотрите на код и быстро улавливаете его назначение, то это хороший код. Если при взгляде на код у вас возникает мысль "что это, чёрт возьми, такое?!", вероятно, он не слишком хороший. Это подводит нас к важной идее: код пишется для людей. Компьютерам всё равно, легко ли читается код: для них любой код легкочитаемый.
Вы можете подумать - ну, я хочу писать приложения и создавать веб-сайты, поэтому естественно мне важно назначение - семантика, так же как для писателя - сюжет, а не лингвистика. Так зачем беспокоиться о синтаксических конструкциях? Язык программирования - это инструмент, с помощью которого вы рассказываете свою историю, чем бы она ни была: сайтом, приложением или ботом. И чем лучше вы знаете свой инструмент, тем меньше вы о нём думаете и тем больше можете сделать. Так же как писатель должен уметь выражать идеи нужными словами и использовать синтаксические конструкции, которые будут понятны людям.
К счастью, у языков программирования очень простой синтаксис по сравнению с языками, на которых говорят люди. Так что не беспокойтесь, не смотря на то, что нам придётся изучать синтаксис, эта задача будет достаточно простой.
Получается... программировать легко? Если компьютеры тупые и выполняют только то, что мы им говорим, а синтаксис языка программирования - простая штука, всё вместе должно быть достаточно лёгкой задачей, так?
Эмм... нет. Если честно, то программирование - не настолько лёгкая задача. Ну, да, написать школьное сочинение легко по сравнению с "Войной и миром". А докторская диссертация по квантовой физике - это вообще другой уровень. Так что не стоит обобщать. Любая деятельность из перечисленных - варианты письменного изложения, но сравнивать их и судить о "письменном изложении" не целесообразно. Программирование может быть простым, а может быть сложным, в зависимости от того, кто и что делает.
Вы быстро поймёте, что синтаксис легко изучить, но сам по себе он вам не поможет. Это необходимая вещь, но не самодостаточная.
На протяжении следующих уроков мы сфокусируемся на семантике, назначении и рассмотрим несколько крутых идей, которые позволили появиться компьютерам, интернету, роботам и мобильным телефонам. Параллельно мы изучим синтаксис.
Последний момент, который мы затронем перед погружением - это, мм, какой язык выбрать? Их так много и это может казаться критическим моментом. Момент, конечно, критический, но не потому что "нужно принять окончательное решение, которое повлияет на всю оставшуюся жизнь", а потому что мы должны понимать, что выбор языка программирования - это как выбор инструмента для ввода текста, а не человеческого языка.
Вы можете писать что-то ручкой на бумаге, использовать печатную машинку, компьютер или доску. У каждого инструмента свои возможности и ограничения. И если вы хотите стать писателем, не так важно чем вы пользуетесь для ввода текста - ручкой или кнопками клавиатуры. Мы хотим изучать программирование, а не только язык программирования.
Язык нужно выбрать достаточно хороший, достаточно простой, известный и с хорошими возможностями. В процессе профессионального роста вы БУДЕТЕ переключаться между языками, использовать сразу несколько языков и технологий одновременно и это не будет для вас проблемой, так же как переход с печатной машинки на Microsoft Word - это не проблема.
Мы выбираем JavaScript в качестве первого языка программирования и в качестве инструмента для изучения программирования. Программы, написанные на JavaScript почти всё время запущены в вашем компьютере, поскольку большая часть веб-сайтов, включая тот, на котором вы смотрите это видео, используют JavaScript. Он невероятно популярный и становится всё более популярным с каждым годом.
Ну что, давайте начнем программировать!
программный синтаксис комбинаторный логика
В лекции рассматриваются вопросы, относящиеся к понятийному аппарату, истории развития и выразительным возможностям синтаксического представления формальных теорий и языков программирования .
Формализуем основные конструкции языка программирования SML посредством форм Бэкуса-Наура или БНФ (история их создания изложена во вступительной лекции).
Неформально определим синтаксис (языка программирования или математической теории) как форму конструкций (программы или теории) и способов их комбинирования. Более точное определение синтаксиса будет сформулировано далее в ходе лекции.
Определим понятие синтаксиса более строго.
Под синтаксисом понимают раздел описания формального математического языка или языка программирования, исследующий вид, форму и структуру конструкций (без учета их значения или практической применимости).
Забегая вперед, заметим, что значение конструкций языка программирования описывается и исследуется семантикой (о ней речь пойдет в следующей лекции), а вопросы и ценность практической применимости - прагматикой.
Основной задачей синтаксиса является определение формы и вида допустимых языковых конструкций. Эту задачу можно решить путем перечисления описаний всех языковых конструкций. Одним из механизмов такого описания является уже упомянутая нами нотация БНФ
Мы будем рассматривать параллельно БНФ-формализации синтаксиса ламбда-исчисления и языка программирования SML. В последнем случае мы ограничимся базовым набором конструкций языка, подчеркнув такие существенные возможности, как кортежи (tuples) и let-выражения.
Для формирования правильного понимания роли и места синтаксиса в исследовании языков программирования рассмотрим обобщенную схему трансляции исходного текста программы (написанной, например, на языке программирования SML) в машинный код.
В ходе трансляции программы, прежде всего, выполняется так называемая процедура лексического анализа, которая включает в себя выделение в тексте программы элементарных конструкций языка, или, иначе, лексем (в частности, имен переменных или идентификаторов, специальных или ключевых слов, значений констант, переменных и др.).
По завершении лексического анализа выполняется так называемая процедура синтаксического разбора текста программы, которая представляет собой проверку корректности синтаксиса текста, написанного на языке программирования. Эта процедура, возможно, включает выполнение проверки корректности типизации в той или иной форме.
Наконец, в случае, если все конструкции языка, присутствующие в тексте программы, являются синтаксически корректными, а также не выявлено несоответствий типов, запрещенных с точки зрения анализатора корректности типизации, производится преобразование текста программы в промежуточный код (ассемблер, код той или иной абстрактной машины) или собственно машинный код.
Рассмотрим синтаксис языка программирования SML в сравнении с синтаксисом ламбда-исчисления.
Для большей наглядности и сопоставимости формализаций синтаксиса обоих языков (языка формальной математической теории и языка программирования) будем использовать единую нотацию, а именно, БНФ.
Прежде всего, необходимо договориться об обозначениях.
Рассмотрим традиционные обозначения БНФ и поясним смысл каждого из них.
Фактически БНФ представляют собой определения одних понятий через другие. При этом понятия заключаются в угловые скобки, и используется ряд специализированных символов и соглашений, суть которых поясняется далее.
Определяющий символ "::=" отделяет определяемую конструкцию от составляющих ее ранее определенных базовых конструкций.
Определяемая конструкция записывается слева от "::=" в угловых скобках "<" и ">".
Альтернативы (возможные варианты) конструкций перечисляются по вертикали.
Цитирование (подобно тому, как мы цитировали специальные символы, заключая их в двойные кавычки) не имеет обозначения.
Проиллюстрируем формализацию синтаксиса посредством нотации БНФ, рассмотрев в качестве примера формальной системы хорошо знакомое нам по предыдущим лекциям ламбда-исчисление.
<выражение> ::= <константа> | <переменная> |
(<выражение> <выражение>) |
л <переменная> . <выражение>
Поясним смысл приведенных обозначений.
В данном примере определяется понятие выражения, синтаксическое представление которого может быть выражено в виде одной из следующих альтернатив:
- 1. константы;
- 2. переменной;
- 3. двух выражений, заключенных в круглые скобки, т.е. знакомой нам операции аппликации ламбда-выражений;
- 4. символа л, за которым следует переменная, точка и выражение, т.е. знакомой нам операции абстракции.
Оказывается, что синтаксис языка программирования SML имеет ряд очевидных аналогий с синтаксисом ламбда-исчисления. Эти аналогии являются неизбежными как в силу функциональной природы рассматриваемого языка программирования, так и на том основании, что язык SML разрабатывался как средство доказательства теорем, а, значит, его синтаксис (а, забегая вперед, заметим, что и семантика) должен быть прозрачен математически.
Для иллюстрации перечисленных выше тезисов рассмотрим важнейшие синтаксические категории языка программирования SML.
Описанием будем в дальнейшем называть запись, связывающую выражение языка программирования с именем, обозначающим его в программе (идентификатором).
Под термином "зарезервированное" (или, иначе, служебное)слово будем иметь в виду конструкцию языка, однозначно интерпретируемую в качестве инструкции языка программирования (например, "if", "then", "let"). Напомним, что в данной нотации цитирование производится без кавычек или других символов-ограничителей.
Комментарием назовем произвольный поясняющий текст к программе, который, согласно синтаксису языка SML, положено заключать в ограничители вида "(*" и "*)".
В частности, рассмотрим структуру основных синтаксически допустимых типов выражений языка.
<выражение> ::= <идентификатор> | <литерал> |
<выражение> <выражение> |
<выражение> <идентификатор> <выражение>
Как видно из БНФ-формализации, синтаксически корректным выражением в языке программирования SML считается:
- 1. идентификатор (т.е. имя переменной, константы, функции или типа, обычно представляемой в виде алфавитно-цифровой последовательности ограниченной длины и начинающейся с буквенного символа) или
- 2. литерал (литералы будут рассмотрены далее в ходе лекции) или
- 3. последовательность из двух выражений или
- 4. последовательность из двух выражений, соединенных идентификатором.
Продолжим обсуждение выражений.
В дополнение к перечисленным альтернативам, синтаксически допустимыми выражениями языка программирования SML, также являются:
if <выражение> then <выражение>
else <выражение> |
(<выражение> ... <выражение>) |
let <описание> in <выражение> end |
- 1. три выражения, соединенные зарезервированными словами if ("если"), then ("тогда") и else ("в противном случае"), называемые условным выражением и фактически представляющие собой предикатную функцию, которая реализует выполнение второго выражения в случае истинности первого и выполнение третьего в противном случае;
- 2. конечную последовательность выражений, заключенную в круглые скобки (или так называемый кортеж) и применяемую для структуризации данных;
- 3. описание и выражение, соединенные зарезервированными словами let ("положим"), in ("в") и end ("конец"), которые определяют операцию подстановки описания в выражение с учетом всевозможных вхождений в него указанного фрагмента описания;
- 4. выражение, заключенное в круглые скобки (как мы уже знаем, в ламбда-исчислении и комбинаторной логике эту операцию можно производить без ограничений) и используемое для явного указания приоритета операции.
Продолжим обсуждение синтаксических категорий языка программирования SML.
Перейдем к рассмотрению структуры синтаксически допустимых видов описаний объектов языка.
Приведем соответствующую формализацию в терминах БНФ.
<описание> ::=
val < идентификатор > = < выражение > |
fun < идентификатор > < идентификатор > =
< выражение > |
local < описание > in <описание> end
Синтаксически допустимыми описаниями языка программирования SML, как следует из представленной БНФ, являются:
- 1. идентификатор и выражение, соединенные зарезервированными словами val и "=", которые обозначают связывание идентификатора (переменной, константы или другого синтаксически допустимого объекта языка программирования) с тем или иным выражением;
- 2. три идентификатора и выражение, соединенные зарезервированными словами fun и "=", которые обозначают связывание функции (обозначенной первым идентификатором) с параметром (обозначенным вторым идентификатором) с выражением, определяющим порядок вычисления значения;
- 3. два описания, соединенные зарезервированными словами local, in и end, которые обозначают локальное определение первого описания в контексте второго.
Продолжим обсуждение синтаксических категорий языка программирования SML.
Перейдем к рассмотрению структуры синтаксически допустимых описаний типов объектов языка.
Приведем соответствующую формализацию в терминах БНФ.
<тип> ::= int | bool |
<тип> * ... * <тип> |
<тип> -> <тип>
Как следует из представленной БНФ, синтаксически допустимыми типами языка программирования SML являются:
- 1. целочисленные величины, обозначаемые зарезервированным словом int;
- 2. логические значения, обозначаемые зарезервированным словом bool;
- 3. кортежи - упорядоченные n-ки элементов определенных типов;
- 4. функции - упорядоченные n-ки элементов определенных типов, соединенных зарезервированными символами "->".
Рассмотрим следующий пример, иллюстрирующий приписывание типов в языке SML. Константа типа кортеж вида (0,false,1,true) имеет тип (int*bool*int*bool).
Заметим, что варианты типов (1) и (2) являются элементарными, тогда как (3) и (4) представляют собой производные типы с явно указанной (или выводимой) структурой, откуда и происходит название "структурированный тип".
В ходе лекции нами уже упоминалось о такой синтаксической категории как литералы, или о базовых типах SML, состоящих из определенных последовательностей символов.
Рассмотрим подробнее синтаксические особенности основных видов литералов.
Приведем соответствующую формализацию в терминах БНФ.
<литерал> ::= <литерал целого типа> |
<литерал строкового типа> |
<литерал вещественного типа>
Как следует из представленной БНФ, синтаксически допустимыми типами литералов в языке программирования SML являются следующие:
- 1. целочисленные литералы, имеющие тип int и лежащие в диапазоне от -230 до +230 (последнее обстоятельство связано с особенностями машинного представления данных);
- 2. строковые литералы, имеющие тип string и представляющие собой алфавитно-цифровые последовательности символов в коде формата ASCII;
- 3. вещественные литералы, имеющие базовый тип real, обобщенную форму вида M x 10E, где M - мантисса в диапазоне от -1 до +1, а E - порядок в соответствующем диапазоне.
Заметим, что значение (т.е. семантика) литералов в полной мере определяется их лексическим (а, значит, и синтаксическим) представлением.
Продолжим обсуждение синтаксических категорий языка программирования SML.
Перейдем к рассмотрению фундаментальной с точки зрения формализации языков функционального программирования - ламбда-исчисления - операции аппликации функций.
<выражение> <выражение>
Как следует из представленной БНФ, синтаксически допустимая конструкция языка программирования SML, описывающая операцию аппликации, весьма точно соответствует описанию операции аппликации в ламбда-исчислении.
Проиллюстрируем аппликацию функции к аргументу в языке программирования SML следующим примером.
Рассмотрим функцию succ, которая задается определением
fun succ n = n+1;
и осуществляет прибавление единицы к (целочисленному) аргументу.
Для рассматриваемой функции succ синтаксически корректная аппликация может иметь вид succ 2 и вычисляться в ходе выполнения программы в значение 3.
Продолжим обсуждение синтаксических категорий языка программирования SML.
Перейдем к рассмотрению синтаксически допустимых конструкций языка программирования SML, называемых условными выражениями.
Приведем соответствующую формализацию в терминах БНФ:
if <выражение> then <выражение> else <выражение>;
Как видно из БНФ-формализации, синтаксически корректное условное выражение состоит из трех подвыражений, соединенных зарезервированными словами if, then и else, уже упоминавшихся нами в ходе лекции.
Добавим к сказанному ряд необходимых замечаний. Во-первых, результатом вычисления первого выражения должно быть логическое значение. Во-вторых, типы второго и третьего выражений должны совпадать. Наконец, часть условного выражения, начинающаяся с else, не является обязательной.
Заметим также, что функции сравнения встроены в язык SML и имеют вид: "=" (равно), "<" (меньше), ">" (больше), "<=" (меньше или равно), ">=" (больше или равно), "<>" (не равно). Результатом вычисления любой из этих функций является логическое значение.
Проиллюстрируем синтаксис условного выражения следующим примером на языке SML:
if n>=10 then 1 else 0;
Заметим, что приведенное выражение может использоваться для анализа параметра функции, вычисляющей, например, количество разрядов десятичного числа.
Продолжим обсуждение основных синтаксических категорий языка программирования SML.
Рассмотрим структуру синтаксически допустимых конструкций, известных под названием let-выражений.
Приведем соответствующую формализацию в терминах БНФ:
let <описание> in <выражение> end;
Как видно из БНФ-формализации, синтаксически корректное let-выражение состоит из описания и выражения, соединенных зарезервированными словами let, in и end.
Как можно заключить из синтаксиса, let-выражение представляет собой ни что иное, как подстановку значения в ламбда-абстракцию. Let-выражения используются в языке программирования SML для связывания значений и оптимизации вычислений, в частности, для обеспечения многократного вычисления повторяющихся фрагментов программы.
Проиллюстрируем синтаксис let-выражений примерами из языка программирования SML.
Рассмотрим следующие let-выражения:
let val n=2 in n+1 end;
let k=9876*8765 in (k-1, k, k+1) end;
Как можно заметить, первое выражение представляет собой ни что иное, как подстановку, которую можно формализовать ламбда-термом вида (лx.x + 1) 2. Второе выражение позволяет свести многократное вычисление громоздкой операции (умножения) к однократному.
В ходе лекции неоднократно упоминалось понятие кортежа.
Рассмотрим подробнее этот весьма важный (в особенности при реализации функций) вид синтаксических конструкций языка программирования SML.
Приведем формализацию синтаксически допустимого представления кортежа в терминах БНФ:
(<выражение>, ..., <выражение>)
Исходя из вида БНФ-формализации, уточним понятие кортежа. Кортежем называется группа, состоящая, по меньшей мере, из двух выражений (возможно, имеющих разные типы), объединенная в обособленную совокупность.
Заметим, что кортежи используются в SML для реализации многоместных (имеющих более одного аргумента) функций, а более широко в теории и практике программирования - в реляционных базах данных (в которых данные представляются в виде таблиц), поскольку кортеж представляет собой, по сути, строку такой таблицы.
Проиллюстрируем синтаксис конструкции кортежа примерами из языка программирования SML:
Пример 1: (1, 2*1, 2*2*1)
Пример 2: (1, true, 0, false)
Заметим, что в случае единственного выражения кортеж вырождается в выражение в скобках. Естественно, что любое SML-выражение можно заключить в скобки, например для явного указания приоритета аппликаций, арифметических и логических операций.
Полученный в ходе лекции опыт рассмотрения основных видов синтаксических конструкций языка программирования SML позволяет перейти к формальному синтаксису таких фундаментальных языковых конструкций как описания переменных и функций.
Рассмотрим формализации синтаксически корректных описаний переменных и функций в терминах БНФ:
<описание> ::=
val <идентификатор> = <выражение>
<описание> ::=
fun <идентификатор> <идентификатор> =
<выражение>
Первое определение представляет собой описание переменной, второе - функции. При этом оба определения имеют сходную структуру.
Проиллюстрируем формальные описания переменных и функций следующими примерами:
Пример 1. val x=2;
Пример 2. fun fact n =
if n<2 then 1
else n * fact (n - 1);
Пример 3. fun f (x,y) = x*x + y*y;
Первый из приведенных примеров представляет собой описание (целочисленной) переменной x, второй - рекурсивной (самоприменимой) функции fact вычисления факториала (произведения натуральных чисел от 1 до n), а третий - двухместной функции f, вычисляющей сумму квадратов аргументов.
Заметим в заключение, что именно при реализации последней функции используются кортежи (поскольку синтаксис SML в "чистом" виде, как следует из БНФ, допускает применение только одноместных функций).
Итак, в данной лекции были рассмотрены основные виды синтаксических конструкций языка программирования SML. По итогам обсуждения можно сделать следующие выводы:
- · синтаксис языков функционального программирования достаточно близок к синтаксису формальных теорий, на которых они основаны (в частности, это справедливо для ламбда-исчисления и языка SML);
- · БНФ являются актуальной и адекватной формализацией синтаксиса языка;
- · язык программирования SML, в отличие от ранних языков функционального программирования, имеет ряд расширенных конструкций (кортежи, let-выражения и др.).
Синтаксис проверяется на ранних стадиях трансляции . В интерпретируемых языках программирования проверка синтаксиса производится или в процессе интерпретации (выполнения), или в процессе предварительной компиляции в промежуточный код. Кроме того, синтаксис может проверяться непосредственно при редактировании исходных текстов программ при использовании IDE .
Синтаксис записи функции
Синтаксис записи функции - формальные правила, которым должна удовлетворять запись определения или вызова функции ; форма записи функции. Если синтаксис функции будет неверен, компилятор вернет ошибку, и программа не будет собрана, пока ошибка не будет исправлена.
К синтаксическим ошибкам записи функции, например, относятся:
- написание названия функции при её вызове, не соответствующее грамматике языка (неверный регистр символов для регистрострогих языков);
- использование при вызове или определении функции литералов, не соответствующих грамматике языка (другие виды скобок, разделитель аргументов);
- отсутствие возвращаемого функцией типа данных (для тех языков, для которых это определено грамматикой).