S-表達式
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Corrected_S-expression_tree_2.svg/220px-Corrected_S-expression_tree_2.svg.png)
(* 2 (+ 3 4))
所謂「S-表達式/運算式」(S-expression)或「sexp」(其中「S」代表「符號的」),是指一種以人類可讀的文本形式表達半結構化數據的約定。S-表達式可能以其在Lisp家族的編程語言中的使用而為人所知。其他應用則見於由Lisp衍生的語言,如DSSSL,以及如IMAP之類通信協議中作為標記出現和約翰·麥卡錫的CBCL。語法細節和所支持的數據類型雖因語言而異,但這些語言間最通用的特性則是使用S-表達式作為括號化的前綴表示法(有時亦作劍橋波蘭表示法)。
數據類型和語法
[編輯]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-表達式處理的數據,但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)和數種出版物[2]引用。最原始的用途則是在SPKI中。
Rivest的格式定義了 S-表達式為一個八位元組-串(一系列字節)或其他S-表達式的有限列表。此定義描述了三種表達這種結構的互換格式。一種為「advanced transport」——以格式而言具有很大彈性,且語法上近似於Lisp-風格表達式,但並不等同。例如,advanced transport允許八位元組-串逐字表示(串的長度後跟隨一分號及整個原始的串),引號形式允許轉義字符,十六進制,Base64,或者在滿足一定條件時直接作為「token」。(Rivest的token與Lisp token不同之處在於前者僅僅為了方便與審美,像其他字符串一樣對待,而後者有特別的語法意義。)為了更為緊密,更便於語法分析,獨立於任何抽象的 S-表達式,另一種交換格式「canonical presentation」僅允許逐字表示的字符串,格式上禁止字符串以外的空白。
相關條目
[編輯]引用
[編輯]外部連結
[編輯]自由軟件: