Zephyr ASDL（抽象语法描述语言）

12 投票

3 回答

2824 浏览

数据工程师

提问于 2025-04-17 10:18

问题：

什么是Zephyr ASDL，它和其他编译器技术，比如词法分析器和语法分析器生成器，有什么关系？

如果你能详细一点就太好了，但当内容变得比较技术性时，请指向其他在线参考资料，因为我对编译器的了解大多来自于玩yacc和flex，写一个简单的C语言最大匹配词法分析器，以及在网上查资料和阅读相关内容。

问题背景：

我最近在阅读http://docs.python.org/devguide/compiler.html，看到了一句：

AST节点的规范是使用Zephyr抽象语法定义语言（ASDL）来指定的。

我根据底部的引用找到了这个链接：http://www.cs.princeton.edu/research/techreps/TR-554-97。

我第一次读这篇文章的时候感觉有点混乱，所以我希望能先更好地理解ASDL的目的是什么（在编译过程中的作用），再尝试第二遍。

代码生成词法分析编译原理语法分析抽象语法树编译器设计 ASDL AST节点

3 个回答

你的问题是关于具体语法和抽象语法之间的区别。

具体语法就是你在使用编程语言时需要遵循的规则。这种具体语法会被解析器检查，确保你遵循了语言的语法规则。解析器还有一个不为程序员所知的作用，就是在内存中构建一个专门的数据结构，代表你输入的内容。很多算法会在这个数据结构上进行操作。这个数据结构被称为“抽象语法树”（Abstract Syntax Tree，简称AST）。
抽象语法：这是一个类的集合（在面向对象的编程中）或类型（在函数式编程中），用于构建AST。例如，你可能会有一个名为“程序”（Program）的类，它捕捉了程序的本质。你还可以有一个“如果”（If）类，表示“if”语句的结构（包括一个条件、一个常规的主体，可能还有一个用于“else”部分的第二个主体）。

像Zephyr这样的ASDL是用来描述这个抽象语法的类集合，而不是语法本身。

一旦这个类的集合被完全描述（或者生成），它就可以在解析器中使用，解析器会基于这些类来构建AST。

回答于 2025-04-17 由 Python大师

分享举报

ASDL是一种工具，当你需要在一个模块中生成一棵树，并在其他模块中输入同样的树（或者几乎相同的树，经过某种优化）时，就会用到它。

为了做到这一点，你需要有一些构建树的函数（最好能检查类型），还有打印树的函数，这样你在可视化时可以确保你生成的树是正确的。

ASDL的输入是一种树，它的写法和代数数据类型的语法（比如Haskell或ML）几乎一样，或者是BNF语法，但要简单得多。ASDL会根据你简单描述的树自动生成所有的构造函数和打印函数。

举个例子，如果你有一个词法分析器，它需要生成带有类型的词素。你还需要查看词素的输出流（这是线性的，所以是一棵非常简单的树）。你不需要为打印和构建词素写函数，而是可以像这样定义它们：

   lexeme=
       ID(STRING)
     | INT(num_integer)
     | FLOAT(num_float)
     attributes(int coord_x, int coord_y)
   num_integer:
     ....
   num_float:
     ....

然后你可以在词法分析器中调用构造函数，比如ID、INT、FLOAT等。ASDL会把这个简单的语法转换成你需要的所有函数，无论是构建抽象语法树的节点，还是打印，或者其他你需要的功能。ASDL对生成的代码没有限制。

如果你给一个类型添加了attributes，比如一个标记的坐标，这些属性会被附加到该类型每个构造函数的参数中。

由解析器创建的更复杂的树可能看起来像这样：

expr:  SUM(expr, expr)
      |PRODUCT(expr, expr)
      |number
number: num_integer

在这种情况下，ASDL会检查解析器调用的SUM(_ _)是否会传递给用expr的构造函数之一创建的sum节点。num_integer是外部定义的，可能是通过词法分析器的ASDL树定义的。

需要注意的是，你不能定义包含正则表达式的构造函数，比如number: [0-9]+。ASDL比EBNF更简单。

这些构造函数的定义方式是为了构建你需要的内容，并且它们会进行类型检查，以确保你的词法分析器、解析器或代码生成器输出的树符合ASDL定义的语言。

要很好地理解ASDL，你需要写3到4个解析器，看看它们生成的代码中有什么共同点。这个共同的部分实际上就是ASDL，所以它是解析器输出的一种抽象。

回答于 2025-04-17 由 Python大师

分享举报

词法分析器和解析器生成器可以接受对词素和语法的描述，然后生成实现这些描述的代码。词法分析器需要用正则表达式来描述标记，而解析器生成器则使用各种扩展的BNF表示法。

你提到的那篇论文我觉得写得很清楚：ASDL是一种小语言，用来抽象地描述一组树节点（它们的类型和签名）。通过这种语言，人们可以编写工具（论文的作者们就是这样做的），将这些描述转换成实现树所需的记录类型，以便与解析器一起使用。所以，ASDL有点像正则表达式和BNF，它的目的是提供给代码生成器，用来生成编译器的一部分。

从更广泛的角度来看，编译器是一种相对成熟的技术，理论上应该能够根据不同部分的描述来生成它们。正则表达式、BNF和ASDL是解析阶段的关键。

理想情况下，你希望有描述目标指令集、流程分析、从抽象树到目标指令集的转换（你提到的最大匹配）以及描述优化的方法。然后，配合每个部分的工具，你就可以从“规范”中构建整个编译器。实际上，这方面已经有很多研究；人们已经分别和一起做了这些工作。不出所料，其中一些工作来自普林斯顿的“Zephyr”项目（看起来那里的Zephyr网站现在已经关闭），它的目标就是做这种事情。

总之，可以在Google Scholar上搜索“编译器生成器”。

回答于 2025-04-17 由 Python大师

分享举报

Zephyr ASDL（抽象语法描述语言）

3 个回答

撰写回答