练习 34：分析器

优质

小牛编辑

135浏览

2023-12-01

你现在有了一个解析器，它应该生成一个语法产生式对象树。我会将其称为“解析树”，这意味着你可以从“解析树的顶部开始，然后“遍历”它，直到你访问每个节点来分析整个程序。当你了解BSTree和TSTree数据结构时，你已经做了这样的事情。你从顶部开始访问了每个节点，并且你访问的顺序（深度优先，广度优先，顺序遍历等）确定了节点的处理方式。你的解析树具有相同的功能，编写微型 Python 解释器的下一步是遍历树并分析它。

分析器的任务是，在你的语法中找到语义错误，并修复或添加下一阶段需要的信息。语义错误是错误，虽然语法正确，但并不适合 Python 程序。这可以是一个尚未定义的遍历，也可以是不符合逻辑的代码，它根本没有意义。一些语言语法是如此松散，分析器必须做更多的工作来修复解析树。其他语言很容易解析和处理，甚至不需要分析器的步骤。

为了编写分析器，你需要一种方法来访问解析树中的每个节点，分析错误，并修复任何缺少的信息。有三种通用方法可以用于实现它：

你创建一个分析器，它知道如何更新每个语法产生式。它将以和解析器相似的方式遍历解析树，对每种生产式类型都拥有一个函数，但他的任务是更改，更新和检查产生式。
你改变你的语法产生式，让他们知道如何分析自己的状态。那么你的分析器就仅仅是一个引擎，它遍历解析树，调用每个产生式的analyze()方法。使用这种风格，你将需要一些状态，它们会传递给每个语法产生式类，这个类应该是第三个类。
你创建一组单独的类来实现最终分析后的树，你可以将其传递给解释器。通过许多方式，你将使用一组新的类来映射语法分析器的语法产生式，这些新的类接受全局状态，语法产生式，并配置其__init__，使其为分析后的结果。

我建议你现在使用或来完成挑战练习。

访客模式

“访问者模式”是面向对象语言中非常常见的技术，其中你可以创建一些类，它们知道被“访问”时应该做什么。这可以让你将处理某个类的代码集成到这个类。这样做的优点是，你不需要大型的if语句来检查类上的类型，来了解该做什么。相反，你只需创建一个类似于这个的类：

class Foo(object):
    def visit(self, data):
        # do stuff to self for foo

一旦你拥有了这个类（visit可以叫任何东西），你可以遍历列表来调用它。

for action in list_of_actions:
    action.visit(data)

你将使用这种模式用于或风格的分析器；唯一的区别是：

如果你决定，你的语法产生式也将是分析结果，那么你的analyze()函数（也就是我们的visit()）只会将该数据存储在产生式类，或者在提供给它的状态中。
如果你决定，你的语法产生式将为解释器生成另一组类（请参阅练习 35），那么每次analyze的调用都将返回一个新对象，该对象将放入列表中以供以后使用，或将其作为子树附加到当前对象。

我将介绍第一种情况，其中你的语法产生式也是你的分析器结果。这适用于我们简单的微型 Python 脚本，你应该遵循这种风格。如果你想尝试其他的设计，那么你可以之后尝试。

简短的微型 Python 分析器

警告

如果你想自己尝试，为你的语法产生式尝试实现访客模式，那么你应该停在这里。我将给出一个相当完整但简单的例子，它充满了障碍。

访客模式背后的概念似乎是奇怪的，但它是完全有意义的。每个语法产生式都知道在不同阶段应该做什么，所以你可以把这个阶段代码放在需要的数据附近。为了演示这个，我写了一个小型的伪造的PunyPyAnalyzer，它仅仅使用访客模式打印出解析。我只完成一个语法产生式的样例，所以你可以理解这是如何完成的。我不想给你太多的线索。

我做的第一件事是，定义一个Production类，我的所有语法产生式都将继承它。

class Production(object):
    def analyze(self, world):
        """Implement your analyzer here."""

它拥有我的初始的analyze()方法，并接受我们随后使用的PunyPyWorld。第一个语法产生式的示例使FuncCall产生式：

class FuncCall(Production):

    def __init__(self, name, params):
        self.name = name
        self.params = params

    def analyze(self, world):
        print("> FuncCall: ", self.name)
        self.params.analyze(world)

函数调用有名称和params，它是一个Parameters产生式类，用于函数调用的参数。看看analyze()方法，你会看到第一个访客函数。当你访问PunyPyAnalyzer时，你将看到如何运行，但是请注意，此函数之后在每个函数的参数上调用param.analyze(world)：

class Parameters(Production):

    def __init__(self, expressions):
        self.expressions = expressions

    def analyze(self, world):
        print(">> Parameters: ")
        for expr in self.expressions:
            expr.analyze(world)

这就产生了Parameters类，它包含每个表达式，它们组成函数的参数。Parameters.analyze仅仅遍历它的表达式列表，其中我们拥有两个：

class Expr(Production): pass

class IntExpr(Expr):
    def __init__(self, integer):
        self.integer = integer

    def analyze(self, world):
        print(">>>> IntExpr: ", self.integer)

class AddExpr(Expr):
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def analyze(self, world):
        print(">>> AddExpr: ")
        self.left.analyze(world)
        self.right.analyze(world)

在这个例子中，我只添加了两个数字，但是我创建一个基本的Expr类，然后创建IntExpr和AddExpr类。每个都仅仅拥有analyze()方法，打印出其内容。

因此，我们有用于分析树的类，我们可以做一些分析。我们需要的第一件事是一个世界，它可以跟踪变量定义、函数、以及我们的Production.analyze()方法所需的其他东西。

class PunyPyWorld(object):

    def __init__(self, variables):
        self.variables = variables
        self.functions = {}

当调用任何Production.analyze()方法时，PunyPyWorld对象被传递给它，因此analyze()方法知道世界的状态。它可以更新变量，寻找函数，并在世界中执行任何所需的事情。

然后我们需要一个PunyPyAnalyzer，它可以接受解析树和世界，并使所有的语法产生式运行：

class PunyPyAnalyzer(object):
    def __init__(self, parse_tree, world):
        self.parse_tree = parse_tree
        self.world = world

    def analyze(self):
        for node in self.parse_tree:
            node.analyze(self.world)

函数的简单调用hello(10 + 20)的配置相当简单。

variables = {}
world = PunyPyWorld(variables)
# simulate hello(10 + 20)
script = [FuncCall("hello",
            Parameters(
                [AddExpr(IntExpr(10), IntExpr(20))])
            )]
analyzer = PunyPyAnalyzer(script, world)
analyzer.analyze()

要确保你理解了我构造script的方式。注意到第一个参数是一个列表了嘛？

解析器与分析器

在这个例子中，我假设PunyPyParser已将NUMBER记号转换为整数。在其他语言中，你可能只拥有记号，并让PunyPyAnalyzer进行转换。这一切都取决于，你想让错误发生在哪里，以及哪里可以做最有用的分析。如果你将工作放在解析器中，那么你可以马上给出格式化方面的早期错误。如果将其放在分析器中，那么你可以给出错误，使用整个解析文件来有所帮助。

挑战练习

所有这些analyze()方法的要点不仅仅是打印出来，而是改变每个Production子类的内部状态，以便解释器可以像脚本一样运行它。你在这个练习中的任务是，接受你的语法产生式类（可能与我的不同）并进行分析。

随意借鉴我的出发点。如果需要，可以使用我的分析器和我的世界，但是你应该尝试首先编写自己的分析器。你还应该将练习 33 中的产生式类与我的比较。你的更好吗？它们能支持这种设计吗？如果他们不能则改变它们。

你的分析器需要做一些事情才能使解释器正常工作：

跟踪变量定义。在一个实际的语言中，这将需要一些非常复杂的嵌套表，但是对于微型 Python 来说，只需假设有一个巨大的表（TSTree或dict），所有变量都在这里。这意味着hello(x, y)函数的x和y参数实际上是全局变量。
跟踪函数的位置，以便以后运行它们。我们的微型 Python 只有简单的函数，但是当Interpreter运行时，它需要“跳转”到并运行它们。最好的办法保留它们，便于之后使用。
检查你可以想到的任何错误，例如使用中缺少的变量。这是棘手的，因为 Python 这样的语言，在解释器阶段中进行更多的错误检查。你应该决定在分析过程中，可能出现哪些错误并实现它们。例如，如果我尝试使用未定义的变量，会发生什么？
如果你正确地实现了 Python INDENT语法，那么你的FuncCall产生式应该有额外的代码。解释器将需要它来运行它，所以确保有一个实现它的方式。

研究性学习

这个练习已经很难了，但是如何创建一个更好的方式，来存储变量，至少实现一个额外的作用域层级？记得“作用域”的概念是，hello(x, y)中的x, y不影响hello函数之外的你定义x和y。
在Scanner，Parser和Analyzer中实现赋值。这意味着我应该可以执行x = 10 + 14，你可以处理它。

深入学习

研究“基于表达式”和“基于语句”的编程语言之间的区别。较短版本是一些只有表达式的语言，所以任何东西都有与之相关的某种（返回）值。其他语言的表达式拥有值，语句没有，因此把它们赋给变量会失败。Python 是哪种语言？