假设我想编写一个小型解释器,可以评估具有二进制操作
目前我只关心AST的解释,因此为了简单起见,我们跳过标记化和解析。
在Haskell中,有一种更或多或少规范的方法来实现:
现在,Python 3.6似乎没有代数数据类型。我的问题是有许多可能的解决方法。最明显的一个是使用
这段代码可以正常工作并打印出预期的结果
以下是几个更多的选项,但是每个选项都有一些缺点:
那么,在Python 3.6.x中是否有某种标准方法来定义AST的解释器,以避免上述缺点?还是应该坚持使用
Plus
、一元操作Negate
和整数常量的表达式。目前我只关心AST的解释,因此为了简单起见,我们跳过标记化和解析。
在Haskell中,有一种更或多或少规范的方法来实现:
data Ast = Plus Ast Ast | Negate Ast | IntConst Int
ev :: Ast -> Int
ev (Plus a b) = (ev a) + (ev b)
ev (Negate x) = - (ev x)
ev (IntConst i) = i
main = print $ show $ ev $ (Plus (IntConst 50) (Negate $ IntConst 8))
现在,Python 3.6似乎没有代数数据类型。我的问题是有许多可能的解决方法。最明显的一个是使用
isinstance
:class Plus:
def __init__(self, first, second):
self.first = first
self.second = second
class Negate:
def __init__(self, first):
self.first = first
class IntConst:
def __init__(self, value):
self.value = value
def ev(ast):
if isinstance(ast, Plus):
return ev(ast.first) + ev(ast.second)
elif isinstance(ast, Negate):
return - ev(ast.first)
elif isinstance(ast, IntConst):
return ast.value
print(ev(Plus(IntConst(50), Negate(IntConst(8)))))
这段代码可以正常工作并打印出预期的结果
42
,但是看起来有些混乱。以下是几个更多的选项,但是每个选项都有一些缺点:
- 使用猴子补丁:例如这个例子在解释器中定义了一堆
???_execute
方法,然后将它们附加到表示AST元素的类上。对我来说看起来非常可怕(如果我尝试并行执行两个不同解释器的两个单独的AST会发生什么事情,一切都会崩溃,对吧?)。 - 定义一个通用的
NodeVisitor
,为每种类型的AST节点都有一个visit_???
方法,然后进行一些分派,将字符串中的正确方法名和传递给visit
方法的实例的类的名称粘合在一起。这似乎更加健壮,但我不喜欢方法名称被持续重建:解释器应该专注于AST,而不是生成自己的源代码(方法名称)。 - 使用一些额外的宏小玩意,显然可以生成case类。我目前不想使用任何第三方工具,我想要一个尽可能独立于其他所有内容的微小脚本。
那么,在Python 3.6.x中是否有某种标准方法来定义AST的解释器,以避免上述缺点?还是应该坚持使用
isinstance
?或者实现好老式的Java风格的Visitor
(不确定它是否被认为是Pythonic)?
编辑
使用 @juanpa.arrivillaga 提出的 functools
,我得到了以下结果:
Use
collections.namedtuple
andfunctools.singledispatch
:from collections import namedtuple from functools import singledispatch Plus = namedtuple('Plus', ['left', 'right']) Negate = namedtuple('Negate', ['arg']) IntConst = namedtuple('IntConst', ['value']) @singledispatch def ev(x): raise NotImplementedError("not exhaustive: %r" % (type(x))) ev.register(Plus, lambda p: ev(p.left) + ev(p.right)) ev.register(Negate, lambda n: -ev(n.arg)) ev.register(IntConst, lambda c: c.value) print(ev(Plus(IntConst(50), Negate(IntConst(8)))))
However, it does not seem to work if
ev
is a method, because it cannot dispatch on theself
-argument (see this related question), so I can get only a functionev
, but no instance that represents the interperter.
def visit(self, node): method_name = 'visit_' + type(node).__name__ [...]
部分。如果我理解正确,它会在每次调用NodeVisitor
上的visit
方法时构建method_name
。这反过来意味着算术表达式的简单求值器将浪费比实际计算多一个数量级的时间在字符串操作上。 - Andrey Tyukin