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の場合'&&'、両方の引数がブール値である必要があり、'+'orの引数'<'が数値である必要があるなどです。型が 2 つしかない場合は、次のように使用できます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 に答える