21.1. Синтаксис и семантика языков программирования
У каждого языка программирования, как и у любого естественного языка, есть свои синтаксис и семантика.
Синтаксис — совокупность правил некоторого языка, определяющих формирование его элементов. Иначе говоря, это совокупность правил образования семантически значимых последовательностей символов в данном языке. Синтаксис задается с помощью правил, которые описывают понятия некоторого языка. Примерами понятий являются: переменная, выражение, оператор, процедура. Последовательность понятий и их допустимое использование в правилах определяет синтаксически правильные структуры, образующие программы. Именно иерархия объектов, а не то, как они взаимодействуют между собой, определяются через синтаксис. Например, оператор может встречаться только в процедуре, а выражение в операторе, переменная может состоять из имени и необязательных индексов и т.д. Синтаксис не связан с такими явлениями в программе, как «несоответствие типов» или «переменная с данным именем не определена». Этим занимается семантика.
Семантика — правила и условия, определяющие соотношения между элементами языка и их смысловыми значениями, а также интерпретацию содержательного значения синтаксических конструкций языка. Объекты языка программирования не только размещаются в тексте в соответствии с некоторой иерархией, но и дополнительно связаны между собой посредством других понятий, образующих разнообразные ассоциации. Например, переменная, для которой синтаксис определяет допустимое местоположение только в описаниях и некоторых операторах, обладает определенным типом, может использоваться с ограниченным множеством операций, имеет адрес, размер и должна быть описана до того, как будет использоваться в программе.
Текст исходной программы на языке высокого уровня представляет собой обычный тестовый файл. Для его «чтения» и превращения в последовательность машинных команд, прежде всего, выполняется синтаксический анализ текста программы.
Синтаксический анализатор — компонента компилятора, осуществляющая проверку исходных операторов на соответствие синтаксическим правилам и семантике данного языка программирования. Несмотря на название, анализатор занимается проверкой и синтаксиса, и семантики. Он состоит из нескольких блоков, каждый из которых решает свои задачи.
21.2. Структура языков программирования
Языки программирования достаточно сильно отличаются друг от друга по назначению, структуре, семантической сложности, методам реализации. Это накладывает свои специфические особенности на разработку конкретных трансляторов. Структура языка характеризует иерархические отношения между его понятиями, которые описываются синтаксическими правилами. Языки программирования могут сильно отличаться друг от друга по организации отдельных понятий и по отношениям между ними. Например, язык C++ допускает описание переменных в любой точке программы перед первым ее использованием, а в Паскале переменные должны быть определены в специальной области описания. В зависимости от принятого решения, транслятор может анализировать программу за один или несколько проходов, что влияет на скорость трансляции.
Семантика языков программирования изменяется в очень широких пределах. Они отличаются не только по особенностям реализации отдельных операций, но и по парадигмам программирования, определяющим принципиальные различия в методах разработки программ. Специфика реализации операций может касаться как структуры обрабатываемых данных, так и правил обработки одних и тех же типов данных. Даже при выполнении операции сложения двух целых чисел такие языки, как C и Паскаль, могут вести себя по-разному.
Один и тот же язык может быть реализован нескольким способами. Это связано с тем, что теория формальных грамматик допускает различные методы разбора одних и тех же предложений. В соответствии с этим трансляторы разными способами могут получать один и тот же результат (объектную программу) по первоначальному исходному тексту. Существует несколько компиляторов языка Паскаль: Turbo Pascal, MS Pascal, Pascal with Objects, Delphi, Builder. Вместе с тем, все языки программирования обладают рядом общих характеристик и параметров. Эта общность определяет и схожие для всех языков принципы организации трансляторов.
Для любого языка его создателями определяются:
- множество символов, которые можно использовать для записи правильных программ (алфавит);
- множество правильных программ (синтаксис);
- «смысл» каждой правильной программы (семантика).
Рассмотрим пример синтаксического разбора. Пусть в исходном тексте программы встретилась формула a + (b + c) * d. В большинстве языков программирования такая формула определяет иерархию программных объектов, которую можно отобразить в виде дерева (Рис. 21 .79). В кружках представлены символы, используемые в качестве элементарных конструкций, а в прямоугольниках задаются составные понятия, имеющие иерархическую и, возможно, рекурсивную структуру.
Синтаксическая структура, правильная для одного языка, может быть ошибочной для другого. Например, в языке Лисп приведенное выражение не будет распознано. Однако для этого языка корректным будет являться выражение ( * ( + a b c ) d ).
Рис. 21.79. Дерево синтаксического разбора.
Другой характерной особенностью всех языков является их семантика. Она определяет смысл операций языка, корректность операндов. Цепочки, имеющие одинаковую синтаксическую структуру в различных языках программирования, могут различаться по семантике (что, например, наблюдается в C++, Pascal, Basic для приведенного выше фрагмента арифметического выражения). Знание семантики языка позволяет отделить ее от его синтаксиса и использовать для преобразования в другой язык (осуществить генерацию кода). Описание семантики и распознавание ее корректности обычно является самой трудоемкой и объемной частью транслятора, так как необходимо осуществить перебор и анализ множества вариантов допустимых комбинаций операций и операндов.
Семантика языков программирования
Аннотация: В лекции излагаются основополагающие принципы, история развития, существующие подходы и выразительные возможности семантического представления формальных теорий и языков программирования.
Представим построение денотационной семантики важнейших функций языка программирования SML .
Напомним, что история развития теории и практики семантического анализа языков программирования была рассмотрена во вступительной лекции.
Прежде всего, рассмотрим неформальную семантику языков программирования.
Для построения адекватной и удобной в использовании семантики необходимо, прежде всего, определить критерии, характеризующие «хороший» язык программирования .
Попытаемся сформулировать обобщенные требования, предъявляемые к описанию языков программирования.
Во-первых, необходимо потребовать от языка программирования соблюдения принципа полноты , т.е. оснастить его таким набором конструкций, который позволяет описать синтаксис (и семантику ) всех допустимых конструкций языка без пропусков существенных аспектов.
Во-вторых, язык программирования должен удовлетворять интуитивному требованию ясности , а именно, объективно обеспечивать удобочитаемость программ, а также легкость и результативность поиска ответов на вопросы, возникающие в процессе разработки программных проектов.
Немаловажной характеристикой языка программирования является естественность , под которой мы будем понимать интуитивную близость языка терминологии разработчика, а также использование унифицированных, стандартных, привычных обозначений.
Наконец, необходимо учитывать и такой важный параметр , как реализм , который понимается как учет естественных ограничений на среду реализации языка программирования, а именно, объем оперативной памяти , время реакции и целый ряд других существенных факторов.
После обсуждения концептуально важных требований к языкам программирования в целом перейдем к неформальному обсуждению семантического подхода, способного обеспечить реализацию этих требований.
Прежде всего, расширим представление о семантике языка программирования (или формальной теории) хотя и предварительным, но более конкретным определением этого понятия.
Семантикой будем называть интерпретацию (или, иначе, смысловое значение) абстрактного синтаксиса (а точнее, множества допустимых видов конструкций языка), представленное в терминах той или иной математически строгой формальной модели .
Оказывается, все многообразие возможных подходов к семантике можно в основном представить всего двумя типами семантик , а именно, семантиками, ориентированными на компиляцию , и семантиками, ориентированными на интерпретацию .
В дальнейшем под подходами к семантике, ориентированными на компиляцию , будем понимать такие подходы, в которых семантика представляет собой множество преобразований над синтаксической моделью в той или иной форме.
В отличие от предыдущего подхода, под подходами к семантике, ориентированными на интерпретацию , будем понимать такие подходы, в которых семантика представляет собой множество описанных на специально построенном метаязыке преобразований синтаксически правильных конструкций языка программирования.
Сразу отметим, что целям нашего курса в большей степени соответствует второй подход, как более универсальный в силу того обстоятельства, что в нем используется метатеория , т.е. формализация, моделирующая преобразования текста программ.
Выделим основные направления, существующие в рамках подхода к семантике, ориентированного на интерпретацию , и свяжем их с рассмотренными нами в ходе лекции направлениями исследований.
Оказывается, существует три основных вида семантик, ориентированных на интерпретацию .
Во-первых, необходимо упомянуть об операционных семантиках . Значение конструкций языка в таких семантиках выражается в терминах переходов той или иной абстрактной машины из одного состояния в другое. В качестве показательных примеров абстрактных машин можно привести, в частности, так называемую SECD-машину П. Лендина , а также категориальную абстрактную машину . Обе формализации будут рассмотрены подробнее в ходе дальнейших лекций.
Другим типом семантик, ориентированных на интерпретацию , являются так называемые пропозиционные семантики . В отличие от операционных семантик , значение конструкций языка в таких семантиках выражается в терминах множества формул, описывающих состояния объектов программы. В качестве примеров можно привести, в частности, аксиоматический метод Хоара и метод индуктивных утверждений Флойда.
Наконец, наиболее значимым для нас типом семантик, ориентированных на интерпретацию , являются денотационные семантики , в которых смысл конструкций языка представляется в терминах абстракции функций, оперирующих состояниями программы. В частности, данный подход иллюстрирует теория вычислений Д. Скотта , основанная на семантических доменах , которую мы и предлагаем вниманию читателя.
Напомним, что теория вычислений Д. Скотта была создана до появления большинства современных языков программирования, а именно в конце 60-х годов.
Существенно, что именно эта теория (в отличие от, скажем, классической логики и ряда других формальных систем) позволяет произвести адекватную (а именно, полную и непротиворечивую) формализацию семантики языков программирования.
Теория вычислений Д. Скотта основана на фундаментальном понятии домена , который будем пока неформально понимать как некоторый аналог множества , впрочем, в отличие от традиционных множеств , адекватно формализующий рекурсивно (т.е. на основе самоприменения) определенные функции и множества .
Сформулируем последовательность изложения теории вычислений Д. Скотта .
Для построения теории вычислений необходимо, во-первых, перечислить так называемые стандартные, или, точнее, наиболее часто используемые в рамках данной формализации, домены .
После перечисления стандартных доменов необходимо определить так называемые конечные домены , или, точнее, домены , элементы которых можно перечислить явным образом.
Наконец, после перечисления доменов перейдем к определению конструкторов доменов , под которыми понимаются операции построения новых доменов на основе имеющихся. Иначе говоря, определим способы комбинирования доменов .