使用语法解析器构建Python文件树

Question

我有一个为解释型语言定制的语法，现在想找一些建议，关于如何制作一个解析器，这个解析器可以生成一个树形结构，我可以对其进行查询。通过这个结构，我希望能够生成解释型语言的代码。我看到的大多数语法解析器都是用来验证已经存在的代码的。我的第二个问题是，语法是否应该抽象到一个程度，让Python代码可以在树中用实际的代码术语替换符号？理想情况下，我希望能够查询一个根符号，然后返回所有属于这个根符号的符号，一直到终端符号。

关于这个过程或相关词汇的任何建议都将非常有帮助。谢谢。

Answer 1

我会使用ANTLR。现在的版本是3，它支持生成Python代码。在解析过程中，它会自动生成一个抽象语法树（AST），你可以对这个树进行遍历。这里面一个重要的部分是要在你的语法中标注哪些符号（比如运算符）应该被当作子树来处理。

Answer 2

绝大多数的解析器库会从你生成的代码中创建一个抽象语法树（AST）。你可以使用任何库，比如pyparsing。要把AST转换成代码，你可能需要手动写一些函数来完成这个过程，但其实用递归的方法来做是相当简单的。例如：

def generate(ast):
    if ast[0] == '+':
        return generate(ast[1]) + " + " + generate(ast[2])
    elif ast[0] == 'for':
        return "for %s in %s:\n" % (ast[1], generate(ast[2])) + generate(ast[3])
    ...

假设AST的结构就是一个列表，列表的第一个元素是节点名称的标签，后面跟着任何参数的树，比如：[+, 4, [*, 'x', 5]]。当然，你应该使用你的解析器库所使用的格式，除非你自己在写解析器。

我不太明白你说的Python代码是如何将树中的符号替换为实际的代码术语的。

你可以写一个简单的函数，来遍历根节点下的所有符号：

def traverse_preorder(ast):
    yield ast[0]
    for arg in ast[1:]:
        for x in traverse_preorder(arg):
            yield x

再想想，变量名ast可能不是个好选择，因为它和ast模块有点冲突。