Синтаксис SML

Синтаксис ламбда-исчисления

Обозначения БНФ

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

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

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

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

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

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

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

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

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

1. константы;

2. переменной;

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-07