S-表達式

所謂「S-表達式/運算式」（S-expression）或「sexp」（其中「S」代表「符號的」），是指一種以人類可讀的文本形式表達半結構化數據的約定。S-表達式可能以其在Lisp家族的編程語言中的使用而為人所知。其他應用則見於由Lisp衍生的語言，如DSSSL（英語：Document Style Semantics and Specification Language），以及如IMAP之類通信協議中作為標記出現和約翰·麥卡錫的CBCL（英語：Common Business Communication Language）。語法細節和所支持的數據類型雖因語言而異，但這些語言間最通用的特性則是使用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^[1]）。S-表達式原本被用於將被M-表達式（英語：M-expression）處理的數據，但Lisp的首個實現是一個 S-表達式的解釋器，以 S-表達式編碼 M-表達式，而Lisp程序員很快習慣於對代碼和數據都使用 S-表達式。

S-表達式可以是如數字這樣的單個對象，包括特殊原子nil和t在內的LISP 原子（英語：LIST atom），或寫作 (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（英語：Internet-草案） ，擬作為RFC出版。該草案定義了基於Lisp S-表達式的語法，但旨在用於一般目的的數據存儲及交換（類似XML）而非僅限於編程。儘管未被批准為RFC，但此草案已被其他RFC（如RFC 2693）和數種出版物^[2]引用。最原始的用途則是在SPKI（英語：Simple public key infrastructure）中。

Rivest的格式定義了 S-表達式為一個八位元組-串（一系列字節）或其他S-表達式的有限列表。此定義描述了三種表達這種結構的互換格式。一種為「advanced transport」——以格式而言具有很大彈性，且語法上近似於Lisp-風格表達式，但並不等同。例如，advanced transport允許八位元組-串逐字表示（串的長度後跟隨一分號及整個原始的串），引號形式允許轉義字符，十六進制，Base64，或者在滿足一定條件時直接作為「token」。（Rivest的token與Lisp token不同之處在於前者僅僅為了方便與審美，像其他字符串一樣對待，而後者有特別的語法意義。）為了更為緊密，更便於語法分析，獨立於任何抽象的 S-表達式，另一種交換格式「canonical presentation」僅允許逐字表示的字符串，格式上禁止字符串以外的空白。

相關條目

• M-表達式
• CAR and CDR（英語：CAR_and_CDR）
• 列表構造函數
• Canonical S-expressions（英語：Canonical S-expressions）

引用

1. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I
2. [1]（頁面存檔備份，存於網際網路檔案館）

外部連結

自由軟件：

• sfsexp（頁面存檔備份，存於網際網路檔案館） 小且快速的「s表達式」庫（C/C++）
• minilisp（頁面存檔備份，存於網際網路檔案館）, by Léon Bottou.
• libcurie（頁面存檔備份，存於網際網路檔案館）一個小的libc替換,依賴「s表達式」。