JavaScript - 解析 S 表达式
Lisp 编程语言家族基于 S 表达式构建。本文将介绍如何创建一个简单的 S 表达式解析器。这将构成 Lisp 解析器的基础。
Lisp 是最容易实现的语言，创建解析器是第一步。我们可以使用解析器生成器来实现，但自己编写解析器更简单。我们将使用 JavaScript。
什么是 S 表达式?
为了定义嵌套列表数据结构，我们使用 Lisp 和其他函数式编程语言中常用的 S 表达式。一个 S 表达式可以是一个原子，也可以是一系列 S 表达式。
如果您不懂 Lisp 语言，S 表达式如下所示:-
(+ (second (list "xxx" 10)) 20)
这是一种数据格式，其中所有内容都由括号括起来的原子或列表组成(其他列表中的原子之间用空格分隔)。
与 JSON 类似，S 表达式可以具有多种数据类型。数字、字符串和符号(不带引号)可以在多种语言中表示变量名。
此外，您还可以使用特定的点运算符来组成如下所示的对。
(1 . b)
列表可以表示为点对(这意味着它是一个链表数据结构)。
这是一个列表 -
(1 2 3 4)
它可以写成 -
(1 . (2 . (3 . (4 . Nil))))
特殊符号"nil"表示空列表的结尾。这种格式允许您生成任何二叉树。但是，为了避免复杂化，我们不会在解析器中使用这种带点符号。
S 表达式的用途是什么?
S 表达式用于创建 Lisp 代码，也可用于数据通信。
它们也存在于 WebAssembly 的文本版本中。可能是因为解析器很简单，您无需创建自己的格式。使用 JSON 而不是 JSON 在服务器和浏览器之间进行通信。
JavaScript 中 S-表达式解析器的分步说明
以下是使用 S-表达式解析器需要遵循的步骤 -
对输入进行标记:首先，将输入字符串分成标记，可以是括号 (,) 或符号。
递归解析:对标记进行递归处理以创建结构。当找到左括号时，它会生成一个新的列表。右括号表示当前列表的结束。
基本情况:符号(例如整数或单词)以值的形式返回，但列表是使用括号内的表达式创建的。
示例
以下代码将输入字符串转换为可读的标记(符号、整数和括号)。parse() 方法会不断循环遍历每个标记。当它检测到 ( 时，会创建一个新的列表。当它找到 ) 时，会完成列表。数字会被解析为 JavaScript 数字;其他所有内容都会被解释为符号(字符串)。
// 将输入字符串标记为 S 表达式标记的函数
function tokenize(input) {
return input
// 在'('周围添加空格
.replace(/\(/g, ' ( ')
// 在 ')' 周围添加空格
.replace(/\)/g, ' ) ')
.trim()
// 按空格拆分
.split(/\s+/);
}
// 递归函数将标记解析为 S 表达式
function parse(tokens) {
if (tokens.length === 0) {
throw new Error("Unexpected end of input");
}
// 获取下一个令牌
let token = tokens.shift();
// 开始新列表
if (token === '(') {
let list = [];
// 处理直到到达右括号
while (tokens[0] !== ')') {
// 递归解析内部表达式
list.push(parse(tokens));
}
tokens.shift(); // Remove the closing ')'
return list;
} else if (token === ')') {
throw new Error("Unexpected ')'");
} else {
// 返回一个原子(符号或数字)
return atom(token);
}
}
// 用于识别标记是数字还是符号的函数
function atom(token) {
let number = Number(token);
if (!isNaN(number)) {
// 如果是数字，则返回
return number;
} else {
// 否则，将其作为符号返回
return token;
}
}
// 用法
let input = "(+ 1 (* 2 3))";
// 对输入进行分词
let tokens = tokenize(input);
// 将分词解析为抽象语法树 (AST)
let ast = parse(tokens);
console.log(ast);
输出
如果使用输入运行上述代码，输出将为 -
["+", 1, ["*", 2, 3]]
