Войти
Дерево структура данных, представляющая S-выражение (* 2 (+ 3 4))В компьютерном программировании, S-выражения (или символьные выражения, сокращенно sexprs ) являются обозначениями для вложенный список (древовидная -структурированная) данные, изобретенные и популяризированные языком программирования Lisp, который использует их для исходного кода как а также данные. В обычном синтаксисе в скобках Лиспа, S-выражение классически определяется как
( x. y)где x и y являются S-выражениями.Вторая, рекурсивная часть определения представляет упорядоченную пару, что означает, что S-выражения может представлять любое двоичное дерево, хотя S-выражения, содержащие циклы, не могут, наоборот, быть представлены как двоичные деревья.
Определение атома зависит от контекста; в первоначальном определении Джона Маккарти предполагалось, что существует «бесконечный набор различимых атомарных символов », представленных как «строки заглавных латинских букв и цифры с одиночными вставленными пробелами »(т. е. символьная строка и числовые литералы ). В большинстве современных обозначений sexpr дополнительно используется сокращенная запись для представления списков в S-выражениях, так что
(xyz)означает
(x. (Y. (Z. NIL)))где NIL- это специальный объект конца списка (альтернативно записывается (), которое является единственным представлением в Схема ).
В семействе языков программирования Lisp S-выражения используются для представления как исходного кода, так и данных. Другое использование S-выражений - в языках, производных от Лиспа, таких как DSSSL, и в качестве разметки в протоколах связи, например, IMAP и Джон Маккарти CBCL. Он также используется как текстовое представление WebAssembly. Детали синтаксиса и поддерживаемых типов данных различаются для разных языков, но наиболее распространенной особенностью этих языков является использование S-выражений и префиксной нотации.
Существует множество вариантов формата S-выражения, поддерживающих множество различных синтаксисы для разных типов данных. Наиболее широко поддерживаются:
(1 () (2. 3) (4))с дефисом? @! $\ символ \ с \ пробелами«Hello, world!»-9876543210-0.06.283186.022e23Символ #часто используется для префикса расширений синтаксиса, например # x10для шестнадцатеричных целых чисел или # \ Cдля символов.
При представлении исходного кода в Лиспе первый элемент S-выражения обычно является именем оператора или функции, а любые оставшиеся элементы рассматриваются как аргументы. Это называется «префиксной нотацией» или «польской нотацией ». Например, логическое выражение , записанное 4 == (2 + 2)в C, представлено как (= 4 (+ 2 2))в префиксной нотации Лиспа на основе s-expr.
Как отмечалось выше, точное определение «атома» варьируется в LISP-подобных языках. Строка в кавычках обычно может содержать что угодно, кроме кавычек, в то время как атом идентификатора без кавычек обычно может содержать что угодно, кроме кавычек, пробелов, круглых скобок, скобок, фигурных скобок, обратной косой черты и точки с запятой. В любом случае запрещенный символ обычно может быть включен путем экранирования его предыдущей обратной косой чертой. Поддержка Unicode различается.
Рекурсивный случай определения s-expr традиционно реализуется с использованием cons-ячеек.
S-выражения изначально предназначались только для обработки данных с помощью M-выражений, но первая реализация Лиспа была интерпретатором кодировок S-выражений для M-выражений, и программисты на Лиспе вскоре привыкли использовать S-выражения как для кода, так и для данных. Это означает, что Лисп гомиконичен ; то есть первичным представлением программ также является структура данных в примитивном типе самого языка.
Вложенные списки могут быть записаны как S-выражения: ((молочный сок) (медовый мармелад))- это двухэлементный S -выражение, элементы которого также являются двухэлементными S-выражениями. Нотация, разделенная пробелами, используемая в Лиспе (и в этой статье), является типичной. Разрывы строк (символы новой строки) обычно квалифицируются как разделители.
Это простая контекстно-свободная грамматика для небольшого подмножества английского языка, записанная как S-выражение (Gazdar / Melish, Обработка естественного языка в Лиспе), где S = предложение, NP = Существительная фраза, VP = глагольная фраза, V = глагол:
(((S) (NP VP)) ((VP) (V)) ((VP) (V NP)) ((V) умер) ( (V) нанятые) ((NP) медсестры) ((NP) пациенты) ((NP) Medicenter) ((NP) "Dr Chan"))
Программа код можно записать в S-выражениях, обычно используя префиксную нотацию.
Пример в Common Lisp :
(defun factorial (x) (if (zerop x) 1 (* x (factorial (- x 1))))
S-выражения могут быть прочитанным в Лиспе с помощью функции READ. READ читает текстовое представление S-выражения и возвращает данные Lisp. Функцию PRINT можно использовать для вывода S-выражения. Затем вывод можно прочитать с помощью функции READ, когда все объекты напечатанных данных имеют читаемое представление. В Лиспе есть удобочитаемые представления чисел, строк, символов, списков и многих других типов данных. Программный код можно отформатировать как красиво напечатанные S-выражения с помощью функции PPRINT (примечание: с двумя буквами P, сокращенно от pretty-print).
Программы на Лиспе являются допустимыми S-выражениями, но не все S-выражения являются допустимыми программами на Лиспе. (1.0 + 3.1)- допустимое S-выражение, но не действительная программа Lisp, поскольку Lisp использует префиксную нотацию, а число с плавающей запятой (здесь 1.0) недопустимо как операция (первый элемент выражение).
S-выражение, которому предшествует одинарная кавычка, как в 'x, является синтаксическим сахаром для заключенного в кавычки S-выражения, в этом случае (quote x).
S-выражения часто сравнивают с XML : ключевое отличие состоит в том, что S-выражения имеют только одну форму включения, пара точек, и их намного проще анализировать, в то время как теги XML могут содержать простые атрибуты, другие теги или CDATA, каждый из которых использует свой синтаксис.
Стандарты для некоторых языков программирования, производных от Lisp, включают спецификацию их синтаксиса S-выражений. К ним относятся Common Lisp (стандартный документ ANSI ANSI INCITS 226-1994 (R2004)), Scheme (R5RS и R6RS ) и ISLISP.
В мае 1997 года Рон Ривест представил Интернет-черновик для рассмотрения для публикации в качестве RFC. В проекте определен синтаксис, основанный на S-выражениях Lisp, но предназначенный для хранения и обмена данными общего назначения (аналогично XML ), а не специально для программирования. Он никогда не был утвержден в качестве RFC, но с тех пор он цитировался и использовался другими RFC (например, RFC 2693 ) и несколькими другими публикациями. Первоначально он был предназначен для использования в SPKI.
. Формат Ривеста определяет S-выражение как строку октетов (последовательность из байтов ) или конечный список других S-выражений. Он описывает три формата обмена для выражения этой структуры. Один из них - это «расширенный транспорт», который очень гибок с точки зрения форматирования и синтаксически похож на выражения в стиле Лиспа, но не идентичны. Расширенный транспорт, например, позволяет дословно представлять строки октетов (длина строки, за которой следует двоеточие и вся необработанная строка), форма в кавычках позволяет использовать escape-символы, шестнадцатеричное, Base64, или размещается непосредственно как «жетон», если он соответствует определенным условиям. (Токены Ривеста отличаются от токенов Лиспа тем, что первые предназначены только для удобства и эстетики и обрабатываются точно так же, как другие строки, в то время как последние имеют особое синтаксическое значение.)
Черновик Ривеста определяет каноническое представление «для целей электронной подписи». Он должен быть компактным, более простым для анализа и уникальным для любого абстрактного S-выражения. Он разрешает только дословные строки и запрещает пробелы как форматирование вне строк. Наконец, существует «базовое транспортное представление», которое является канонической формой или такой же закодированной, что и Base64, и окружено фигурными скобками, последнее предназначено для безопасной транспортировки канонически закодированного S-выражения в системе, которая может изменить интервал (например, система электронной почты, которая имеет строки шириной 80 символов и переносит все, что длиннее).
Этот формат не получил широкого распространения для использования за пределами SPKI (некоторые из пользователей: GnuPG, libgcrypt, Nettle и GNU lsh). Веб-страница S-выражений Rivest предоставляет исходный код C для синтаксического анализатора и генератора (доступен по лицензии MIT ), который можно адаптировать и встроить в другие программы. Кроме того, нет ограничений на самостоятельную реализацию формата.
