码云账号不再使用社区账号进行二次身份验证的通知 详情
私信发送成功
检测到您已登录开源中国,是否 一键登录码云
Watch Star Fork

龙哥盟飞龙 / lmpythw-zh

克隆/下载
一键复制 编辑 原始数据 按行查看 历史
ex34.md 10.63 KB wizardforcel 提交于 2017-08-13 16:55 . ex34

练习 34:分析器

原文:Exercise 34: Analyzers

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

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

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

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

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

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

访客模式

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

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

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

for action in list_of_actions:
    action.visit(data)

你将使用这种模式用于 #2 或 #3 风格的分析器;唯一的区别是:

  • 如果你决定,你的语法产生式也将是分析结果,那么你的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类,然后创建IntExprAddExpr类。每个都仅仅拥有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 来说,只需假设有一个巨大的表(TSTreedict),所有变量都在这里。这意味着hello(x, y)函数的xy参数实际上是全局变量。
  • 跟踪函数的位置,以便以后运行它们。我们的微型 Python 只有简单的函数,但是当Interpreter运行时,它需要“跳转”到并运行它们。最好的办法保留它们,便于之后使用。
  • 检查你可以想到的任何错误,例如使用中缺少的变量。这是棘手的,因为 Python 这样的语言,在解释器阶段中进行更多的错误检查。你应该决定在分析过程中,可能出现哪些错误并实现它们。例如,如果我尝试使用未定义的变量,会发生什么?
  • 如果你正确地实现了 Python INDENT语法,那么你的FuncCall产生式应该有额外的代码。解释器将需要它来运行它,所以确保有一个实现它的方式。

研究性学习

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

深入学习

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

Float_left Icon_close