笙亿网络策划

JavaScript 怎么解析 S-Expressions？

约 5 分钟读完 2 阅
文章导读
Previous Quiz Next Lisp 编程语言家族是以 S-expressions 为基础构建的。在本文中，您将学习制作一个简单的 S-expression 解析器的步骤。这可以作为 Lisp 解析器的基础。
📋 目录
  1. 壹 什么是 S-expressions？
  2. 贰 S-expressions 的用途是什么？
  3. 叁 JavaScript 中的逐步 S-expression 解析器
  4. 肆 示例
A A

JavaScript - 解析 S-expressions

Previous
Quiz
Next

Lisp 编程语言家族是以 S-expressions 为基础构建的。在本文中，您将学习制作一个简单的 S-expression 解析器的步骤。这可以作为 Lisp 解析器的基础。

Lisp 是最容易实现的语言，而创建解析器是第一步。我们可以使用 parser generator 来实现，但自己编写解析器更简单。我们将使用 JavaScript。

什么是 S-expressions？

为了定义嵌套的列表数据结构，我们使用 s-expressions，它们通常在 Lisp 和其他函数式编程语言中使用。一个 s-expression 可以是一个 atom，或者一系列 s-expressions。

如果您不了解 Lisp 语言，S-expressions 看起来像这样 −

(+ (second (list "xxx" 10)) 20)

这是一种数据格式，其中一切都由 atom 或用括号包围的列表组成（来自其他列表的 atom 由空格分隔）。

像 JSON 一样，S-expressions 可以有多种数据类型。数字、字符串和符号（不带引号）可以在多种语言中表示变量名。

此外，您可以使用特定的点运算符来形成像下面的 pair。

(1 . b)

列表可以表示为 doted pairs（这意味着它是一个 linked list 数据结构）。

这是一个列表 −

(1 2 3 4)

它可以写成 −

(1 . (2 . (3 . (4 . Nil))))

特殊符号 "nil" 表示空列表的结尾。这种格式允许您生成任何 binary tree。不过，为了避免复杂化，我们的解析器将不使用这种 doted notation。

S-expressions 的用途是什么？

S-expressions 用于创建 Lisp 代码，也可以用于通信数据。

它们也存在于 WebAssembly 的文本版本中。可能是因为解析器简单，而且您不必创建自己的格式。与其使用 JSON，不如用它们在服务器和浏览器之间通信。

JavaScript 中的逐步 S-expression 解析器

以下是 s-expression 解析器需要遵循的步骤 −

  • 标记化输入：首先，将输入字符串分成 tokens，这些 tokens 可以是括号 (,) 或 symbols。

  • 递归解析：递归处理 tokens 以创建结构。当找到开括号时，生成一个新列表。闭括号表示当前列表的结束。

  • 基本情况：Symbols（如整数或单词）作为值返回，但列表使用括号内的表达式创建。

示例

以下代码将输入字符串转换为可读的 token（符号、整数和括号）。parse() 方法持续循环遍历每个 token。当检测到 ( 时，它创建一个新列表。当找到 ) 时，它完成该列表。数字被解析为 JavaScript 数字；其他一切都被解释为符号（字符串）。

// 将输入字符串分词为 S-expression token 的函数
function tokenize(input) {
   return input
      // 在 '(' 周围添加空格    
      .replace(/\(/g, ' ( ')  
      
      // 在 ')' 周围添加空格
      .replace(/\)/g, ' ) ')  
      .trim()
      
      // 按空白字符分割
      .split(/\s+/);          
}

// 递归函数，将 token 解析为 S-expression
function parse(tokens) {
   if (tokens.length === 0) {
      throw new Error("意外的输入结束");
   }
   
   // 获取下一个 token
   let token = tokens.shift();  
   
   // 开始一个新列表
   if (token === '(') {        
      let list = [];
      // 处理直到遇到闭合括号
      while (tokens[0] !== ')') {   
        // 递归解析内部表达式  
        list.push(parse(tokens)); 
      }
      tokens.shift();  // 移除闭合的 ')'
      return list;
   } else if (token === ')') {
      throw new Error("意外的 ')'");
   } else {
      // 返回一个 atom（符号或数字） 
      return atom(token);  
   }
}

// 判断 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);    

// 将 token 解析为 AST（抽象语法树）
let ast = parse(tokens);         

console.log(ast);

输出

如果使用上述输入运行以上代码，输出将为 − 

["+", 1, ["*", 2, 3]]