1

使用recursive，我可以生成简单的 AST，例如

from hypothesis import *
from hypothesis.strategies import *

def trees():
    base = integers(min_value=1, max_value=10).map(lambda n: 'x' + str(n))

    @composite
    def extend(draw, children):
        op = draw(sampled_from(['+', '-', '*', '/']))
        return (op, draw(children), draw(children))

    return recursive(base, draw)

现在我想改变它，这样我就可以生成除算术运算之外的布尔运算。我最初的想法是添加一个参数trees：

def trees(tpe):
    base = integers(min_value=1, max_value=10).map(lambda n: 'x' + str(n) + ': ' + tpe)

    @composite
    def extend(draw, children):
        if tpe == 'bool':
            op = draw(sampled_from(['&&', '||']))
            return (op, draw(children), draw(children))
        elif tpe == 'num':
            op = draw(sampled_from(['+', '-', '*', '/']))
            return (op, draw(children), draw(children))

    return recursive(base, draw)

到目前为止还好。但是我该如何混合它们呢？也就是说，我还想要比较运算符和三元运算符，也就是说，这需要“children使用不同的参数调用”。

树需要很好的类型：如果操作是'||'or '&&'，两个参数都需要是布尔值，参数'+'或'<'需要是数字等。如果我只有两种类型，我可以使用filter（给定一个type_of函数）：

if op in ('&&', '||'):
    bool_trees = children.filter(lambda x: type_of(x) == 'bool')
    return (op, draw(bool_trees), draw(bool_trees))

但在实际情况下，这是不能接受的。

recursive支持这个吗？还是有其他方法？显然，我可以直接trees递归定义，但这会遇到标准问题。

4

2 回答 2

2

您可以简单地描述从任一操作集进行比较的树 - 在这种情况下，通过从['&&', '||', '+', '-', '*', '/'].

def trees():
    return recursive(
        integers(min_value=1, max_value=10).map('x{}'.format),
        lambda node: tuples(sampled_from('&& || + - * /'.split()), node, node)
    )

但当然，这不会是很好的类型（除了可能是罕见的巧合）。我认为类型良好的 AST 的最佳选择是：

  1. 对于每种类型，为评估为该类型的树定义一个策略。基本情况只是（一种策略）该类型的值。
  2. 扩展是预先计算类型和操作的可能组合，这些可能会生成这种类型的值，使用相互递归通过st.deferred. 那看起来像......
bool_strat = deferred(
    lambda: one_of(
        booleans(),
        tuples(sampled_from(["and", "or"], bool_strat, bool_strat), 
        tuples(sampled_from(["==", "!=", "<", ...]), integer_strat, integer_strat),
    )
)
integer_strat = deferred(
    lambda: one_of(
        integers(),
        tuples(sampled_from("= - * /".split()), integer_strat, integer_strat),
    )
)
any_type_ast = bool_strat | integer_strat

它会像魔术一样工作：D

（另一方面，这有点复杂——如果你的解决方法对你有用，不要觉得有义务这样做！）

如果您看到大小有问题的爆炸——这应该是非常罕见的，因为自从那篇文章写完后引擎已经做了很多工作——老实说，这没什么可做的。将深度限制贯穿整个事物并在每个步骤中递减它确实可以作为最后的手段，但使用起来并不好。

于 2019-04-10T05:01:52.963 回答
2

我现在使用的解决方案是调整生成的树，例如，如果num在操作需要 a 时生成了树bool，我还绘制了一个比较运算符op和一个常量const并返回(op, tree, const)：

def make_bool(tree, draw):
    if type_of(tree) == 'bool':
        return tree
    else type_of(tree) == 'num':
        op = draw(sampled_from(comparison_ops))
        const = draw(integers())
        side = draw(booleans())
        return (op, tree, const) if side else (op, const, tree)

// in def extend:
if tpe == 'bool':
    op = draw(sampled_from(bool_ops + comparison_ops))
    if op in bool_ops:
        return (op, make_bool(draw(children), draw), make_bool(draw(children), draw))
    else:
        return (op, make_num(draw(children), draw), make_num(draw(children), draw))

不幸的是，它特定于 AST，意味着更频繁地生成特定种类的树。所以我仍然很高兴看到更好的选择。

于 2019-04-10T06:51:22.683 回答