Синтаксис языков программирования

Разбить на страницы

Показывать лекцию целиком

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

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

Определим понятие синтаксиса более строго.

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

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

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

Мы будем рассматривать параллельно БНФ -формализации синтаксиса ламбда-исчисления и языка программирования SML. В последнем случае мы ограничимся базовым набором конструкций языка, подчеркнув такие существенные возможности, как кортежи (tuples) и let-выражения.

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

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

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

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

Рассмотрим синтаксис языка программирования SML в сравнении с синтаксисом ламбда-исчисления.

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

Прежде всего, необходимо договориться об обозначениях.

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

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

Определяющий символ "::=" отделяет определяемую конструкцию от составляющих ее ранее определенных базовых конструкций.

Определяемая конструкция записывается слева от "::=" в угловых скобках "<" и ">".

Альтернативы (возможные варианты) конструкций перечисляются по вертикали.

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

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

$$<выражение> ::= <константа> | <переменная> | \\ ( <выражение> <выражение> ) |\\ \lambda <переменная> . <выражение>$$

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

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

константы ;

переменной ;

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

символа $$\lambda$$, за которым следует переменная, точка и выражение, т.е. знакомой нам операции абстракции.

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

Для иллюстрации перечисленных выше тезисов рассмотрим важнейшие синтаксические категории языка программирования SML.

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

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

Под термином " зарезервированное " (или, иначе, служебное) слово будем иметь в виду конструкцию языка, однозначно интерпретируемую в качестве инструкции языка программирования (например, "if", "then", "let" ). Напомним, что в данной нотации цитирование производится без кавычек или других символов-ограничителей.

Комментарием назовем произвольный поясняющий текст к программе, который, согласно синтаксису языка SML, положено заключать в ограничители вида "(*" и "*)".

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

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

Приведем соответствующую формализацию в терминах БНФ.

<выражение> ::= <идентификатор> | <литерал> |
    <выражение> <выражение> |
    <выражение> <идентификатор> <выражение>

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

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

литерал ( литералы будут рассмотрены далее в ходе лекции) или

последовательность из двух выражений или

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

Продолжим обсуждение выражений.

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

if <выражение> then <выражение> 
    else <выражение> |
    ( <выражение> ... <выражение> ) | 	
    let <описание> in <выражение> end |
    ( <выражение> )

два выражения, соединенные зарезервированными словами if ("если"), then ("тогда") и else ("в противном случае"), называемые условным выражением и фактически представляющие собой предикатную функцию, которая реализует выполнение второго выражения в случае истинности первого и выполнение третьего в противном случае;

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

описание и выражение, соединенные зарезервированными словами let ("положим"), in ("в") и end ("конец"), которые определяют операцию подстановки описания в выражение с учетом всевозможных вхождений в него указанного фрагмента описания;

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

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

Перейдем к рассмотрению структуры синтаксически допустимых видов описаний объектов языка.

Приведем соответствующую формализацию в терминах БНФ.

<описание> ::=
    val < идентификатор > = < выражение > | 
    fun < идентификатор > < идентификатор > =
	    < выражение > | 
    local < описание > in <описание> end

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

идентификатор и выражение, соединенные зарезервированными словами val и "=", которые обозначают связывание идентификатора ( переменной, константы или другого синтаксически допустимого объекта языка программирования) с тем или иным выражением ;

три идентификатора и выражение, соединенные зарезервированными словами fun и "=", которые обозначают связывание функции (обозначенной первым идентификатором ) с параметром (обозначенным вторым идентификатором ) с выражением, определяющим порядок вычисления значения;

два описания, соединенные зарезервированными словами local, in и end, которые обозначают локальное определение первого описания в контексте второго.

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

Перейдем к рассмотрению структуры синтаксически допустимых описаний типов объектов языка.

Приведем соответствующую формализацию в терминах БНФ.

<тип> ::= int | bool | 
<тип> * ... * <тип> |
<тип> -> <тип>

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

целочисленные величины, обозначаемые зарезервированным словом int ;

логические значения, обозначаемые зарезервированным словом bool ;

кортежи - упорядоченные n -ки элементов определенных типов ;

функции - упорядоченные n -ки элементов определенных типов, соединенных зарезервированными символами "->".

Рассмотрим следующий пример, иллюстрирующий приписывание типов в языке SML. Константа типа кортеж вида (0,false,1,true) имеет тип (int*bool*int*bool).

Заметим, что варианты типов (1) и (2) являются элементарными, тогда как (3) и (4) представляют собой производные типы с явно указанной (или выводимой) структурой, откуда и происходит название " структурированный тип ".

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

Рассмотрим подробнее синтаксические особенности основных видов литералов.

Приведем соответствующую формализацию в терминах БНФ.

<литерал> ::= <литерал целого типа> |
    <литерал строкового типа> | 
    <литерал вещественного типа>

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

целочисленные литералы, имеющие тип int и лежащие в диапазоне от -2³⁰ до +2³⁰ (последнее обстоятельство связано с особенностями машинного представления данных);

строковые литералы, имеющие тип string и представляющие собой алфавитно-цифровые последовательности символов в коде формата ASCII;

вещественные литералы, имеющие базовый тип real, обобщенную форму вида M x 10^E, где 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;

Как можно заметить, первое выражение представляет собой ни что иное, как подстановку, которую можно формализовать ламбда-термом вида $$(\lambda 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-выражения и др.).

Для более подробного самостоятельного ознакомления с тематикой лекции рекомендуется следующий список источников: [24, 58].

Страницы:

Определим понятие синтаксиса более строго.

Рассмотрим синтаксис языка программирования SML в сравнении с синтаксисом ламбда-исчисления.

Прежде всего, необходимо договориться об обозначениях.

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

Определяемая конструкция записывается слева от "::=" в угловых скобках "<" и ">".

Альтернативы (возможные варианты) конструкций перечисляются по вертикали.

$$<выражение> ::= <константа> | <переменная> | \\ ( <выражение> <выражение> ) |\\ \lambda <переменная> . <выражение>$$

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

константы ;

переменной ;

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

символа $$\lambda$$, за которым следует переменная, точка и выражение, т.е. знакомой нам операции абстракции.

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

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

Приведем соответствующую формализацию в терминах БНФ.

<выражение> ::= <идентификатор> | <литерал> |
    <выражение> <выражение> |
    <выражение> <идентификатор> <выражение>

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

литерал ( литералы будут рассмотрены далее в ходе лекции) или

последовательность из двух выражений или

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

Продолжим обсуждение выражений.

if <выражение> then <выражение> 
    else <выражение> |
    ( <выражение> ... <выражение> ) | 	
    let <описание> in <выражение> end |
    ( <выражение> )

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

Перейдем к рассмотрению структуры синтаксически допустимых видов описаний объектов языка.

Приведем соответствующую формализацию в терминах БНФ.

<описание> ::=
    val < идентификатор > = < выражение > | 
    fun < идентификатор > < идентификатор > =
	    < выражение > | 
    local < описание > in <описание> end

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

Перейдем к рассмотрению структуры синтаксически допустимых описаний типов объектов языка.

Приведем соответствующую формализацию в терминах БНФ.

<тип> ::= int | bool | 
<тип> * ... * <тип> |
<тип> -> <тип>

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

целочисленные величины, обозначаемые зарезервированным словом int ;

логические значения, обозначаемые зарезервированным словом bool ;

кортежи - упорядоченные n -ки элементов определенных типов ;

функции - упорядоченные n -ки элементов определенных типов, соединенных зарезервированными символами "->".

Рассмотрим подробнее синтаксические особенности основных видов литералов.

Приведем соответствующую формализацию в терминах БНФ.

<литерал> ::= <литерал целого типа> |
    <литерал строкового типа> | 
    <литерал вещественного типа>

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

Приведем соответствующую формализацию в терминах БНФ:

<выражение> <выражение>

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

Рассмотрим функцию succ, которая задается определением

fun succ n = n+1;

и осуществляет прибавление единицы к (целочисленному) аргументу.

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

Приведем соответствующую формализацию в терминах БНФ:

if <выражение> then <выражение> else <выражение>;

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

if n>=10 then 1 else 0;

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

Рассмотрим структуру синтаксически допустимых конструкций, известных под названием let-выражений.

Приведем соответствующую формализацию в терминах БНФ:

let <описание> in <выражение> end;

Проиллюстрируем синтаксис let-выражений примерами из языка программирования SML.

Рассмотрим следующие let-выражения:

let val n=2 in n+1 end;
let k=9876*8765 in (k-1, k, k+1) end;

В ходе лекции неоднократно упоминалось понятие кортежа.

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

(<выражение>, ..., <выражение>)

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

Пример 1: (1, 2*1, 2*2*1) 
Пример 2: (1, true, 0, false)

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

<описание> ::= 
    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;

БНФ являются актуальной и адекватной формализацией синтаксиса языка;

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Синтаксис языков программирования

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!