S-表达式

所谓“S-表达式/运算式”（S-expression）或“sexp”（其中“S”代表“符号的”），是指一种以人类可读的文本形式表达半结构化数据的约定。S-表达式可能以其在Lisp家族的编程语言中的使用而为人所知。其他应用则见于由Lisp衍生的语言，如DSSSL，以及如IMAP之类通信协议中作为标记出现和约翰·麦卡锡的CBCL。语法细节和所支持的数据类型虽因语言而异，但这些语言间最通用的特性则是使用S-表达式作为括号化的前缀表示法（有时亦作剑桥波兰表示法）。

Tree data structure representing the s-expression for (* 2 (+ 3 4))

数据类型和语法

S-表达式格式有许多变体，支持不同数据类型的各种不同语法。最广泛支持的是：

• 列表和点对: (1 () (2 . 3) (4))
• 符号: with-hyphen ?@!$ a\ symbol\ with\ spaces
• 字串: "Hello, world!"
• 整数: -9876543210
• 浮点数: -0.0 6.28318 6.023e23

在 LISP 编程中使用

S-表达式在Lisp中既用作代码，也用作数据（见McCarthy Recursive Functions of Symbolic Expressions）。S-表达式原本被用于将被M-表达式处理的数据，但Lisp的首个实现是一个 S-表达式的解释器，以 S-表达式编码 M-表达式，而Lisp程序员很快习惯于对代码和数据都使用 S-表达式。

S-表达式可以是如数字这样的单个对象，包括特殊原子nil和t在内的LISP 原子，或写作 (x . y)的cons pair。更长的列表则由嵌套的cons pair组成，例如(1 . (2 . (3 . nil)))（，亦可写作更易理解的(1 2 3)）。

使用前缀表示法，程序代码可写作 S-表达式。书写Lisp程序中额外的语法糖则是，一般的表达式(quote x)可以省略为'x。

数据表达式的示例

嵌套列表可以写为 S-表达式：((milk juice) (honey marmalade))是一个双元素S-表达式，其元素也是双元素 S-表达式。Lisp（和本文）中使用的以空格分隔的符号是典型的。换行符（换行符）通常有资格作为分隔符。 这是一个简单的上下文无关语法的一小部分英语写成 S-表达式（Gazdar / Melish，Lisp 中的自然语言处理）：

(((S) (NP VP))
 ((VP) (V))
 ((VP) (V NP))
 ((V) died)
 ((V) employed)
 ((NP) nurses)
 ((NP) patients)
 ((NP) Medicenter)
 ((NP) "Dr Chan"))

S 表达式的源码示例

Common Lisp范例：

(defun factorial (x)
    (if (zerop x) 1
        (* x (factorial (- x 1)))))

Scheme范例：

(define (factorial x)
    (if (zero? x) 1
        (* x (factorial (- x 1)))))

解析

S-表达式经常与 XML 进行比较，一个关键的区别是 S-表达式在语法上要简单得多，因此更容易解析。例如，可以在几十行 Python 代码中实现一个简单的 S-表达式解析器。

def parse_sexp(string):
    """
    >>> parse_sexp("(+ 5 (+ 3 5))")
    [['+', '5', ['+', '3', '5']]]
    
    """
    sexp = [[]]
    word = ''
    in_str = False
    for char in string:
        if char == '(' and not in_str:
            sexp.append([])
        elif char == ')' and not in_str:
            if word:
                sexp[-1].append(word)
                word = ''
            temp = sexp.pop()
            sexp[-1].append(temp)
        elif char in (' ', '\n', '\t') and not in_str:
            if word:
                sexp[-1].append(word)
                word = ''
        elif char == '\"':
            in_str = not in_str
        else:
            word += char
    return sexp[0]

标准化

1997年5月，罗纳德·李维斯特 提交了一份 Internet-Draft ，拟作为RFC出版。该草案定义了基于Lisp S-表达式的语法，但旨在用于一般目的的数据存储及交换（类似XML）而非仅限于编程。尽管未被批准为RFC，但此草案已被其他RFC（如RFC 2693）和数种出版物引用。最原始的用途则是在SPKI中。

Rivest的格式定义了 S-表达式为一个八位元组-串（一系列字节）或其他S-表达式的有限列表。此定义描述了三种表达这种结构的互换格式。一种为“advanced transport”——以格式而言具有很大弹性，且语法上近似于Lisp-风格表达式，但并不等同。例如，advanced transport允许八位元组-串逐字表示（串的长度后跟随一分号及整个原始的串），引号形式允许转义字符，十六进制，Base64，或者在满足一定条件时直接作为“token”。（Rivest的token与Lisp token不同之处在于前者仅仅为了方便与审美，像其他字符串一样对待，而后者有特别的语法意义。）为了更为紧密，更便于语法分析，独立于任何抽象的 S-表达式，另一种交换格式“canonical presentation”仅允许逐字表示的字符串，格式上禁止字符串以外的空白。

相关条目

• M-表达式
• CAR and CDR
• 列表构造函数
• Canonical S-expressions

外部链接

自由软件：

• sfsexp（页面存档备份，存于互联网档案馆） 小且快速的“s表达式”库（C/C++）
• minilisp（页面存档备份，存于互联网档案馆）, by Léon Bottou.
• libcurie（页面存档备份，存于互联网档案馆）一个小的libc替换,依赖“s表达式”。