Что такое алфавит языка программирования
Описанию грамматики языка предшествует описание его алфавита. Алфавит любого языка состоит из фиксированного набора символов, однозначно трактуемых. Алфавит языков программирования, как правило, связан с литерами клавиатуры печатной машинки. Клавиатуры персональных компьютеров близки к ним по наличию литер.
Алфавиты большинства языков программирования близки друг другу и основываются на буквах латинского алфавита, арабских цифрах и общепринятых спецсимволах, таких как знаки препинания, математических операций, сравнений и обозначений. Большинство популярных языков программирования в своем алфавите содержат следующие элементы:
Несмотря на значительные различия между языками программирования, ряд фундаментальных понятий в большинстве из них схожи. Приведем часть этих понятии.
Все операторы языка в тексте программы отделяются друг от друга явными или неявными разделителями, например:
Операторы выполняются в порядке их следования в тексте программы. Лишь с помощью операторов перехода этот естественный порядок может быть нарушен.
Важнейшие характеристики структурированной величины таковы: упорядоченность (да или нет), однородность (да или нет), способ доступа к элементам, фиксированность числа элементов (да или нет). Так, массив является упорядоченной однородной структурой с прямым доступом к элементам и фиксированным их количеством.
Всем программным объектам в языках даются индивидуальные имена. Имя программного объекта называют идентификатором (от слова «идентифицировать»). Чаще всего идентификатором является любая конечная последовательность букв к цифр, начинающаяся с буквы:
Как правило, в большинстве языков программирования в качестве идентификатора запрещается использовать служебные слова языка.
Многим слово «идентификатор» не нравится, и в настоящее время чаще употребляют слово «имя», поскольку
Программисты выбирают имена по своему усмотрению. Принципы выбора и назначения имен программным объектам естественны. Следует избегать мало выразительных обозначений, не гоняться за краткими именами. Имена должны быть понятны, наглядны, отражать суть обозначаемого объекта. Например,
Особый интерес представляют в языках программирования описания нестандартных структур данных, таких как запись, файл, объект, список, дерево и т.п.
Приведем список наиболее употребительных обозначений типов данных, используемых в описаниях:
Семантический смысл переменной заключается в хранении некоторого значения. соответствующего ее типу (например, переменная целого типа может принимать значение произвольного целого числа), а также в выполнении с ней операций пересылки в нее и извлечения из нее этого значения.
Заголовок необходим для ссылок на модуль.
Интерфейс содержит объявления, включая процедуры и функции.
Раздел «реализация» содержит тела процедур и функций, перечисленных в интерфейсной части.
Раздел «инициализация» содержит операторы, необходимые для инициализации модуля.
Каждый модуль компилируется отдельно, и каждый элемент модуля можно использовать в программе без дополнительного объявления.
Что такое алфавит языка программирования
1. Служебные (зарезервированные) слова. Их смысл зафиксирован в языке, и поэтому служебные слова нельзя использовать в качестве имен, вводимых программистом. Полный список служебных слов приведен в Приложении 1.
2. Имена (идентификаторы). Они вводятся для обозначения в программе переменных, констант, типов, процедур и функций. Имена формируются из букв и цифр. Первым символом имени должна быть буква. Длина имени не должна превышать 63 символа. Заглавные и строчные буквы в именах не различаются. Таким образом, следующие три идентификатора обозначают одну и ту же переменную:
index
INDEX
Index
3. Числа и символьные строки.
4. Знаки операций и разделители. Они формируются из одного или нескольких специальных символов.
5. Комментарии. Они представляют собой произвольную последовательность символов (не обязательно из алфавита языка, то есть допускаются и русские буквы), заключенную в фигурные скобки < >. Комментарии не изменяют смысл программы, не влияют на ее выполнение и предназначены для пояснений.
Для отделения лексем друг от друга используются символы пробелов или же лексемы должны быть размещены на различных строках программы.
Cтруктура программ в языке программирования Pascal.
Программа на языке Pascal всегда состоит из двух основных частей: описания последовательности действий, которые необходимо выполнить, и описания данных, с которыми оперируют действия. Действия представляются операторами языка, данные вводятся посредством описаний и определений. Описание данных, которые будут использоваться в программе предшествуют описанию действий, которые будут выполнены с данными. Кроме того, программа может быть снабжена заголовком, который задаст имя программы и ее параметры.
Рассмотрим полную структуру программы на языке Паскаль. В общем случае программа состоит из:
Пример. Программа, вычисляющая сумму двух чисел.
Алфавит, синтаксис и семантика языка программирования
Основными элементами любого языка программирования являются его алфавит, синтаксис и семантика.
Алфавит – совокупность символов, отображаемых на устройствах печати и экранах и/или вводимых с клавиатуры терминала. Обычно это набор символов Latin-1 с исключением управляющих символов. Иногда в это множество включаются неотображаемые символы с указанием правил их записи (комбинирование в лексемы).
Лексика – совокупность правил образования цепочек символов (лексем), образующих идентификаторы (переменные и метки), операторы, операции и другие лексические компоненты языка. Сюда же включаются зарезервированные (запрещенные, ключевые) слова языка программирования, предназначенные для обозначения операторов, встроенных функций и пр. Иногда эквивалентные лексемы, в зависимости от языка программирования, могут обозначаться как одним символом алфавита, так и несколькими. Например, операция присваивания значения в языке Си обозначается как «=», а в языке Паскаль – «:=». Операторные скобки в языке Си задаются символами «<» и «>», а в языке Паскаль – begin и end. Граница между лексикой и алфавитом, таким образом, является весьма условной, тем более что компилятор обычно на фазе лексического анализа заменяет распознанные ключевые слова внутренним кодом (например, begin – 512, end – 513) и в дальнейшем рассматривает их как отдельные символы.
Синтаксис – совокупность правил образования языковых конструкций, или предложений языка программирования – блоков, процедур, составных операторов, условных операторов, операторов цикла и пр. Особенностью синтаксиса является принцип вложенности (рекурсивность) правил построения конструкций. Это значит, что элемент синтаксиса языка в своем определении прямо или косвенно в одной из его частей содержит сам себя. Например, в определении оператора цикла телом цикла является оператор, частным случаем которого является все тот же оператор цикла.
Необходимо строгое соблюдение правил правописания (синтаксиса) программы. В частности, в Паскале однозначно определено назначение знаков пунктуации. Точка с запятой (;) ставится в конце заголовка программы, в конце раздела описания переменных, после каждого оператора. Перед словом End точку с запятой можно не ставить. Запятая (,) является разделителем элементов во всевозможных списках: списке переменных в разделе описания, списке вводимых и выводимых величин.
Строгий синтаксис в языке программирования необходим прежде всего для транслятора. Транслятор – это программа, которая исполняется формально. Если, допустим, разделителем в списке переменных должна быть запятая, то любой другой знак будет восприниматься как ошибка. Если точка с запятой является разделителем операторов, то транслятор в качестве оператора воспринимает всю часть текста программы от одной точки с запятой до другой. Если вы забыли поставить этот знак между какими-то двумя операторами, то транслятор будет принимать их за один, что неизбежно приведет к ошибке.
Основное назначение синтаксических правил – придать однозначный смысл языковым конструкциям. Если какая-то конструкция может трактоваться двусмысленно, значит, в ней обязательно содержится ошибка. Лучше не полагаться на интуицию, а выучить правила языка.
Для описания синтаксиса языка программирования тоже нужен какой-то язык. В этом случае речь идет о метаязыке («надъязыке»), предназначенном для описания других языков. Наиболее распространенными метаязыками в литературе по программированию являются металингвистические формулы Бекуса – Наура (язык БНФ) и синтаксические диаграммы. Язык синтаксических диаграмм более нагляден, легче воспринимается.
Синтаксис языка описывается путем последовательного усложнения понятий: сначала определяются простейшие (базовые), затем все более сложные, включающие в себя предыдущие понятия в качестве составляющих.
В такой последовательности, очевидно, конечным определяемым понятием должно быть понятие программы.
В записях метаформул приняты определенные соглашения. Например, формула БНФ, определяющая понятие «двоичная цифра», выглядит следующим образом:
Значок «|» эквивалентен слову «или».
В диаграммах стрелки указывают на последовательность расположения элементов синтаксической конструкции; кружками обводятся символы, присутствующие в конструкции.
Понятие «двоичный код» как непустую последовательность двоичных цифр БНФ описывает так:
Определение, в котором некоторое понятие определяется само через себя, называется рекурсивным. Рекурсивные определения характерны для БНФ.
Возвратная стрелка обозначает возможность многократного повторения. Очевидно, что диаграмма более наглядна, чем БНФ.
Синтаксические диаграммы были введены Н. Виртом и использованы для описания созданного им языка Паскаль.
Семантика – смысловое содержание конструкций, предложений языка, семантический анализ – это проверка смысловой правильности конструкции. Например, если мы в выражении используем переменную, то она должна быть определена ранее по тексту программы, а из этого определения может быть получен ее тип. Исходя из типа переменной, можно говорить о допустимости операции с данной переменной. Семантические ошибки возникают при недопустимом использовании операций, массивов, функций, операторов и пр.
Основные понятия языка
Предисловие
Этот курс лекций построен на основе учебника автора «C/C++. Программирование на языке высокого уровня » [18], который выпускается издательством ПИТЕР с 2001 года по настоящее время. Учебнику был присвоен гриф Министерства образования Российской Федерации, он входит в списки рекомендуемой литературы во многих вузах России и ближнего зарубежья. Материалы учебника, вошедшие в этот курс, подверглись частичному обновлению и переработке. В 2010 году учебник был удостоен премии Правительства Санкт-Петербурга «За выдающиеся достижения в сфере высшего и профессионального образования» в составе учебно-методического комплекса по языкам программирования.
В этот комплекс входят также практикум по C/C++ [19] и учебники по языкам C# и Паскаль [20, построенные по единому принципу. Соответствующие учебные курсы можно найти на этом сайте. В комплекс входит более 250 индивидуальных вариантов заданий на лабораторные работы в расчете на учебную группу из 20 человек (все варианты можно найти в учебнике [18]) и более 1000 тестовых вопросов. Преподавателям будут полезны презентации лекций. На сайте интернет-школы программирования http://ips.ifmo.ru можно проверить правильность выполнения некоторых лабораторных работ с помощью системы автоматического тестирования программ.
Доброжелательную и конструктивную критику, а также предложения по улучшению курса направляйте автору по адресу pta- ipm @yandex.ru.
Состав языка
Презентацию к лекции Вы можете скачать здесь.
Алфавит языка
Все тексты на языке пишутся с помощью его алфавита. Алфавит C++ включает:
Из символов базового набора составляются лексемы языка и директивы препроцессора. Символы из набора реализации используются для написания комментариев. Компилятор комментарии игнорирует.
Лексемы
Существуют следующие виды лексем:
Объединенная единым алгоритмом совокупность описаний и операторов образует программу.
Путь от текста программы к исполняемому коду
Описание синтаксических конструкций
Для описания языка здесь используется неформальный способ, при котором необязательные части синтаксических конструкций заключаются в квадратные скобки, текст, который необходимо заменить конкретным значением, пишется по-русски, а выбор одного из нескольких элементов обозначается вертикальной чертой. Например:
Фигурные скобки используются для группировки элементов, из которых требуется выбрать только один.
Имена (идентификаторы)
Алфавит, слово, язык в программировании
Рассмотрим самое простое понятие теории языков — понятие алфавита.
Обычно задают определенную нумерацию алфавита (как, скажем, для русского алфавита: «а» — первая буква, «б» — вторая и т.д. до 33-й — «я»). Впредь договоримся, фиксируя алфавит, записывать его буквы в порядке их номеров.
Определение 7.1. Словом или цепочкой в алфавите называют произвольный кортеж из множества (k-й декартовой степени алфавита ) для различных
Такая запись слова согласуется с его интуитивным пониманием как цепочки следующих друг за другом символов. Тогда пустое слово — это слово, не имеющее символов, «пустой лист бумаги», на котором еще ничего не написано.
Докажем, что множество счетно. Для этого достаточно построить какую-либо нумерацию этого множества. Рассмотрим здесь нумерацию, называемую лексикографической.
Решим обратную задачу, найдя слово в данном трехбуквенном алфавите, имеющее номер 321. Согласно приведенному выше алгоритму, получим
Лексикографическая нумерация напоминает способ упорядочения слов в словарях: однобуквенные слова следуют в порядке номеров букв в алфавите, среди двух двухбуквенных слов меньший номер имеет слово, начинающееся буквой с меньшим номером, и т.д. Но полного совпадения нет, так как в словаре слова группируются по начальной букве, а не по длине.
Нам будет удобно в дальнейшем использовать следующую запись непустого слова в алфавите по буквам:
Кроме перечисленных теоретико-множественных операций можно рассматривать и специальные операции над языками.
Прежде чем обратиться к этим операциям, определим операцию соединения (или конкатенации) слов. Соединением слов и называют слово
Вхождения одного слова в другое
На основе понятия соединения слов определим понятие вхождения одного слова в другое.
При этом слово называют левым, а слово — правым крылом указанного вхождения. Слово называют основой вхождения.
Заметим, что каждое слово входит в себя само и пустое слово входит в любое слово.
Например, слова «цикл» и «циклоп» входят в слово «энциклопедия». Соответствующие вхождения записывают следующим образом:
Соединение конечных языков легко вычислить.
Вычисление конкатенации языков в конечном случае очень похоже на умножение (раскрытие скобок) в обычной школьной алгебре. Можно былб бы формально написать так:
В данном случае плюс — это только соединительный знак, используемый вместо запятой. Позже мы увидим, что подобным чисто формальным записям может быть придан строгий алгебраический смысл.
Итерация языка и возведение его в степень
Итерацией языка называют объединение всех его степеней:
Основное алгебраическое свойство множества всех языков
Теорема 7.1. Алгебра есть замкнутое полукольцо.
Проверка аксиом полукольца сводится к доказательству:
1) того, что по операции объединения множество всех языков образует коммутативный и идемпотентный моноид (с пустым множеством в качестве нейтрального элемента (нуль полукольца)); это тривиально ввиду известных свойств операции объединения множеств;
3) следующих тождеств:
(эти тождества определяют свойство дистрибутивности операции соединения относительно объединения).
что гарантирует выполнение непрерывности операции умножения данного полукольца, т.е. непрерывности операции соединения. Эти тождества доказываются точно так же, как тождества обычной дистрибутивности.
Рассмотрим, например, доказательство второго тождества из (7.1), используя, как и выше, метод двух включений. Если
Тождество доказывается аналогично.