S表达式是Lisp编程语言家族的基础。在本文中，我将逐步向您展示如何创建一个简单的S表达式解析器。这可以作为Lisp解析器的基础。
Lisp是实现最简单的语言之一，创建解析器是第一步。我们可以使用解析器生成器来完成这项任务，但自己编写解析器会更容易。我们将使用JavaScript。
（本文内容参考：java567.com）
什么是S表达式？
如果您不熟悉Lisp语言，S表达式看起来像这样：
(+ (second (list "xxx" 10)) 20)
这是一种数据格式，其中所有内容都由括号包围的原子或列表创建（其他列表的原子之间由空格分隔）。
S表达式可以具有不同的数据类型，就像JSON一样：
- 数字
- 字符串
- 符号 - 它们类似于字符串，但没有引号，可以被解释为不同语言的变量名。
此外，您还可以使用特殊的点运算符来创建一对。
(1 . b)
您可以将列表表示为点对（表示它们实际上是一个链接列表数据结构）。
这个列表：
(1 2 3 4)
可以写成：
(1 . (2 . (3 . (4 . nil))))
nil是表示空列表的列表的末尾的特殊符号。使用这种格式，您可以创建任何二叉树。但我们在解析器中不使用这种点记法，以免复杂化问题。
S表达式有什么用？
Lisp代码是由S表达式创建的，但您也可以用它来交换格式。
它们还是WebAssembly的文本表示的一部分。可能是因为解析器的简单性，以及您无需自己制定格式。您可以将它们用于服务器和浏览器之间的通信，而不是使用JSON。
如何在 JavaScript 中实现 S-表达式解析器
Tokenizer（标记器）
标记器是解析器的一部分，将文本分割为可解析的标记。
通常，解析器会配合 Lexer 或标记器生成标记。这就是一些解析器生成器的工作方式（例如 lex 和 Yacc 或 flex 和 bison。后者是 GNU 项目的一部分，是自由开源软件）。
这是最简单的标记化方式：
'(foo bar (baz))'.split(/(\(|\)|\n|\s+|\S+)/);
这是一个联合（使用管道操作符）或我们需要处理的不同情况。括号在正则表达式中是特殊字符，因此需要用斜杠进行转义。
它几乎可以工作。第一个问题是在正则表达式匹配之间存在空字符串。就像这个表达式一样：
'(('.split(/(\(|\)|\n|\s+|\S+)/);
// ==> [ '', '(', '', '(', '' ]
我们有 5 个标记而不是 2 个。我们可以用 Array::filter 解决这个问题。
'(('.split(/(\(|\)|\n|\s+|\S+)/).filter(token => token.length);
// ==> ["(", "("]
如果标记为空，则长度将返回 0 并转换为 false，这意味着它将过滤掉所有空字符串。
我们也不需要空格，因此我们也可以将其过滤掉：
'( ('.split(/(\(|\)|\n|\s+|\S+)/).filter(token => token.trim().length);
// ==> ["(", "("]
第二个更大的问题是最后一个标记 baz))，这里是一个例子：
'(foo bar (baz))'.split(/(\(|\)|\n|\s+|\S+)/).filter(token => token.trim().length);
// ==> ["(", "foo", "bar", "(", "baz))"]
问题在于表达式 \S+，它是贪婪的并匹配除空格之外的所有内容。为了解决问题，我们可以使用这个表达式：\s()+。
它将匹配除空格和括号之外的所有内容（与 \S+ 相同，但包括括号）。
'(foo bar (baz))'.split(/(\(|\)|\n|\s+|[^\s()]+)/).filter(token => token.trim().length);
// ==> ["(", "foo", "bar", "(", "baz", ")", ")"]
正如你所见，输出是正确的。让我们将这个标记器写成一个函数：
const tokens_re = /(\(|\)|\n|\s+|[^\s()]+)/;
function tokenize(string) {
string = string.trim();
if (!string.length) {
return [];
}
return string.split(tokens_re).filter(token => token.trim());
}
我们不需要在 token.trim() 后使用 length，因为空字符串也会被转换为 false 值，而过滤器会删除这些值。
但是字符串表达式（即带引号的表达式）怎么办？让我们看看会发生什么：
tokenize(`(define (square x)
"Function calculate square of a number"
(* x x))`);
// ==> ["(", "define", "(", "square", "x", ")", "\"Function", "calculate", "square",
// ==> "of", "a", "number\"", "(", "*", "x", "x", ")", ")"]
注意：这是 Lisp 方言 Scheme 中的一个函数。我们使用模板字符串，所以我们可以在 Lisp 代码中添加换行符。
从输出中可以看出，单个字符串都被空格分隔开了。让我们修复一下：
字符串的正则表达式
我们需要将字符串文字作为我们的标记器的一个例外添加进去。最好放在正则表达式的联合中的第一项。
处理字符串文字的表达式如下：
/"[^"\\]*(?:\\[\S\s][^"\\]*)*"/
它处理了字符串中的转义引号。
这是完整的正则表达式应该是这样的：
const tokens_re = /("[^"\\]*(?:\\[\S\s][^"\\]*)*"|\(|\)|\n|\s+|[^\s()]+)/;
注意：我们也可以添加 Lisp 注释，但因为这不是 Lisp 解析器而是 S-表达式，所以我们不会在这里添加。JSON 也不支持注释。如果你想创建一个 Lisp 解析器，你可以把它作为一个练习添加进去。
我们的标记器现在运行正常：
tokenize(`(define (square x)
"Function calculate square of a number"
(* x x))`);
// ==> ["(", "define", "(", "square", "x", ")",
// ==> "\"Function calculate square of a number\"",
// ==> "(", "*", "x", "x", ")", ")"]
解析器
我们将使用栈数据结构（LIFO - 后进先出）来创建我们的解析器。
要完全理解解析器的工作原理，最好了解数据结构，比如链表、二叉树和栈。
这是我们解析器的第一个版本：
function parse(string) {
const tokens = tokenize(string);
const result = []; // 作为普通数组
const stack = []; // 作为栈
tokens.forEach(token => {
if (token == '(') {
stack.push([]); // 将新列表加入栈中
} else if (token == ')') {
if (stack.length) {
// 栈顶已构建的列表
const top = stack.pop();
if (stack.length) {
// 将构建的列表添加到上一个列表中
var last = stack[stack.length - 1];
last.push(top);
} else {
result.push(top); // 完全构建的列表
}
} else {
throw new Error('语法错误 - 未匹配的右括号');
}
} else {
// 找到原子并添加到栈顶
// 顶部用作数组我们只在末尾添加
const top = stack[stack.length - 1];
top.push(token);
}
});
if (stack.length) {
throw new Error('语法错误 - 期望右括号');
}
return result;
}
该函数返回一个数组，其中包含以数组形式表示的结构。如果我们需要解析多个 S-表达式，数组中将有更多的项：
parse(`(1 2 3) (1 2 3)`)
// ==> [["1", "2", "3"], ["1", "2", "3"]]
虽然我们不需要处理点，S-表达式可以以这种形式存在：
((foo . 10) (bar . 20))
我们不需要为列表创建特殊结构即可使解析器正常工作。但最好从一开始就拥有这种结构（这样你就可以将其作为 Lisp 解释器的基础）。我们将使用一个 Pair 类，这样我们就可以创建任何二叉树。
class Pair {
constructor(head, tail) {
this.head = head;
this.tail = tail;
}
}
我们还需要表示列表结束（或空列表）的东西。在 Lisp 语言中，通常是 nil：
class Nil {}
const nil = new Nil();
我们可以创建一个将数组转换为我们结构的静态方法：
class Pair {
constructor(head, tail) {
this.head = head;
this.tail = tail;
}
static fromArray(array) {
if (!array.length) {
return nil;
}
let [head, ...rest] = array
if (head instanceof Array) {
head = Pair.fromArray(head);
}
return new Pair(head, Pair.fromArray(rest));
}
}
要将这个添加到我们的解析器中，我们只需要在最后添加它：
result.map(Pair.fromArray);
注意：如果以后想添加点运算符，你将需要在解析器内手动创建对。我们没有转换整个数组，因为这将是我们 S-表达式的容器。数组中的每个元素应该是一个列表，这就是我们使用 Array::map 的原因。
让我们看看它是如何工作的：
parse('(1 (1 2 3))')
输出将是一个像这样的结构（这是使用 JSON.stringify 输出的，nil 的值被插入其中）。
{
"head": "1",
"tail": {
"head": {
"head": "1",
"tail": {
"head": "2",
"tail": {
"head": "3",
"tail": nil
}
}
},
"tail": nil
}
}
最后一件事是将 List 字符串化，通过将一个 toString 方法添加到我们的 Pair 类中：
class Pair {
constructor(head, tail) {
this.head = head;
this.tail = tail;
}
toString() {
const arr = ['('];
if (this.head) {
const value = this.head.toString();
arr.push(value);
if (this.tail instanceof Pair) {
// 替换内部列表的 hack
// 因为结构是树
// 这里的 tail 是下一个元素
const tail = this.tail.toString().replace(/^\(|\)$/g, '');
arr.push(' ');
arr.push(tail);
}
}
arr.push(')');
return arr.join('');
}
static fromArray(array) {
// ... 与之前相同
}
}
让我们看看它是如何工作的：
parse("(1 (1 2 (3)))")[0].toString()
// ==> "(1 (1 2 (3)))"
最后的问题是输出结构中没有数字。一切都是字符串。
原子的解析
我们将使用下面的正则表达式：
const int_re = /^[-+]?[0-9]+([eE][-+]?[0-9]+)?$/;
const float_re = /^([-+]?((\.[0-9]+|[0-9]+\.[0-9]+)([eE][-+]?[0-9]+)?)|[0-9]+\.)$/;
if (atom.match(int_re) || atom.match(float_re)) {
// 在 JavaScript 中，每个数字都是浮点数，但如果速度慢，你可以使用 parseInt 来处理 int_re
return parseFloat(atom);
}
接下来，我们可以解析字符串。我们的字符串几乎与 JSON 中的字符串相同，唯一的区别是它们可以包含换行符（这通常是 Lisp 方言中处理字符串的方式）。因此，我们可以使用 JSON.parse，并将 \n 替换为 \n（转义换行符）。
if (atom.match(/^".*"$/)) {
return JSON.parse(atom.replace(/\n/g, '\\n'));
}
因此，通过这种方式，我们可以免费获得所有转义字符（即：\t 或 Unicode 字符 \u）。
S-表达式的下一个元素是符号。它们是任何不是数字或字符串的字符序列。我们可以创建一个 LSymbol 类，以区分 JavaScript 的 Symbol。
class LSymbol {
constructor(name) {
this.name = name;
}
toString() {
return this.name;
}
}
解析原子的函数可以像这样：
function parseAtom(atom) {
if (atom.match(int_re) || atom.match(float_re)) { // 数字
return parseFloat(atom);
} else if (atom.match(/^".*"$/)) {
return JSON.parse(atom.replace(/\n/g, '\\n')); // 字符串
} else {
return new LSymbol(atom); // 符号
}
}
我们的解析器函数将添加 parseAtom：
function parse(string) {
const tokens = tokenize(string);
const result = [];
const stack = [];
tokens.forEach(token => {
if (token == '(') {
stack.push([]);
} else if (token == ')') {
if (stack.length) {
const top = stack.pop();
if (stack.length) {
const last = stack[stack.length - 1];
last.push(top);
} else {
result.push(top);
}
} else {
throw new Error('语法错误 - 未匹配的右括号');
}
} else {
const top = stack[stack.length - 1];
top.push(parseAtom(token)); // 添加了这一行
}
});
if (stack.length) {
throw new Error('语法错误 - 期望右括号');
}
return result.map(Pair.fromArray);
}
我们还可以改进 Pair 的 toString 方法，使用 JSON.stringify 来处理字符串，以便与符号区分开来：
class Pair {
constructor(head, tail) {
this.head = head;
this.tail = tail;
}
toString() {
const arr = ['('];
if (this.head) {
let value;
if (typeof this.head === 'string') {
value = JSON.stringify(this.head).replace(/\\n/g, '\n');
} else {
// 任何对象，包括 Pair 和 LSymbol
value = this.head.toString();
}
arr.push(value);
if (this.tail instanceof Pair) {
// 替换内部列表的 hack，因为结构是树，这里的 tail 是下一个元素
const tail = this.tail.toString().replace(/^\(|\)$/g, '');
arr.push(' ');
arr.push(tail);
}
}
arr.push(')');
return arr.join('');
}
static fromArray(array) {
// ... 与之前相同
}
}
这就是一个完整的解析器。剩下的是 true 和 false 值（或许还有 null），但这留给读者作为练习。
（本文内容参考：java567.com）
标签：解析器,head,const,JavaScript,token,tail,解析,stack,表达式 From： https://www.cnblogs.com/web-666/p/18119442