S-表达式

维基百科,自由的百科全书
跳转至: 导航搜索
File:Corrected S-expression tree 2.png
Tree data structure representing the s-expression for (* 2 (+ 3 4))

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

數據類型和語法[编辑]

S 表達式格式有許多變體,支持不同數據類型的各種不同語法。最廣泛支持的是:

  • Lists and pairs: (1 () (2 . 3) (4))
  • Symbols: with-hyphen ?@!$ a\ symbol\ with\ spaces
  • Strings: "Hello, world!"
  • Integers: -9876543210
  • Floating-point numbers: -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-表达式可以是如数字这样的单个对象,包括特殊原子nilt在内的LISP 原子英语LIST atom,或写作 (x . y)cons pair英语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”仅允许逐字表示的字符串,格式上禁止字符串以外的空白。

相关条目[编辑]

外部链接[编辑]

自由软件

  • sfsexp 小且快速的“s表达式”库(C/C++)
  • minilisp, by Léon Bottou.
  • libcurie一个小的libc替换,依赖“s表达式”。