深さ最初にPythonでジェネレータを使用するツリーのトラバーサル

Question

現在、私はPythonのPythonの非常に小さなサブセットのコンパイラをプログラミングしています。私はすでにシンタックスツリーを構築していましたが、（コードを生成するためには不可欠な）ツリートラバーサルのコーディングに関するいくつかの問題がありました。だから私は、最初にあなたに私のデータ構造を示すと一緒に行くよ：

class AbstractSyntaxTree(object): 
    def __init__(self, startSymbol): 
     self.root = Node(startSymbol, val=None) 
     self.nodes = [self.root] 

    def addNode(self, name, val, parentId): 
     parent = self.nodes[parentId] 
     self.nodes.append(Node(name=name, val=val, parent=parent)) 
     return len(self.nodes)-1 

    def getLastId(self): 
     return len(self.nodes)-1 

    def __iter__(self): 
     for node in self.root: 
      yield node 

これは私のノード定義である：

class Node: 
    def __init__(self, name, val, parent=None): 
     self.name = name 
     self.val = val 
     self.parent = parent 
     self.children = [] 

     if parent: 
      parent.children.append(self) 

    def __iter__(self): 
     yield self 
     for child in self.children: 
      for node in child: 
       yield node 

私のパーサは全ての文法シンボルが関数呼び出しで再帰下降構文解析であり、他の文法記号。 programは私のスタートシンボルです。成功し解析した後、私はNodeとAbstractSyntaxTreeで定義された私の__iter__発電機を使用して第1の深さ、それを繰り返すことによって、構文ツリー内のすべての私のノードを印刷することができるかどう

def program(self, indentLvl=0): 
    parent = self.synTree.getLastId() 
    if self.smellAndConsume(TOK.EOF, parentId=parent): return 
    self.smellAndConsume(TOK.NEWL, parentId=parent) 
    self.synTree.addNode(name=VAR.statement, val=None, parentId=parent) 
    self.statement() 
    while self.accept and not self.isConsumable(TOK.EOF): 
     self.consume(TOK.NEWL, parentId=parent) 
     self.synTree.addNode(name=VAR.statement, val=None, parentId=parent) 
     self.statement() 
    self.consume(TOK.EOF, parentId=parent) 

は今、興味がありました。しかし、

def test_tree_traversal(): 
    for node in miniPyGrammar.synTree: 
     print(node) 

すべてのノードが印刷されません。コードをデバッグすると、私のルートノードに子ノードがありませんでしたが、私はaddNodeとルートノードidを呼び出しました。誰かがここで何が起こっているかの手がかりを持っていますか？

さらに詳しい情報やコードスニペットが必要な場合は、お気軽にお問い合わせください。

編集：（私はまだここで何が起こっている奇妙なことを見つけるが。）私は解決策を見つけたこのコードは、今期待通りに動作します。

def test_tree_traversal(code): 
    grammar = Grammar() 
    grammar.parse(code) 
    for node in grammar.synTree: 
     print(node) 

def execute_tests(): 
    for name, code in programs.items(): 
     parse_test(name, code) 
     test_tree_traversal(code) 

私はグローバル文法オブジェクトとexecute_testsが上の解析呼んでいた前に、その文法、その後、私は文法オブジェクトsynTreeにアクセスするtest_tree_traversalを実行しました。不思議なことに、呼び出しのあいだで、ガベージコレクションはASTのいくつかのノードを削除しました。なぜ私はそれがガベージコレクションだと思いますか？その行動は非決定的であったからです。

編集：これはエラーが発生しやすいコードです： 唯一の違いは、テストを実行する前に新しい文法オブジェクトをインスタンス化することです。文法には'parse 'メソッドがあります。このメソッドは、プログラムが構文的に正しい場合にtrueを返し、Grammar.synTree経由でアクセス可能なASTを作成します。

miniPyGrammar = Grammar() 

def parse_test(
    programName: str, 
    programCode: str): 
    success = miniPyGrammar.parse(programCode) 
    if success: 
     print('{} is a valid miniPyProgram :)'.format(programName)) 
    else: 
     print('{} is not a valid miniPyProgram'.format(programName)) 
    print(miniPyGrammar.synTree) 

def tree_traversal(code): 
    for node in miniPyGrammar.synTree: 
     print(node) 

def execute_tests(): 
    for name, code in programs.items(): 
     parse_test(name, code) 
     tree_traversal(code) 

if __name__ == '__main__': 
    execute_tests() 

Answer 1

あなたのツリーを繰り返し処理するのではなく、代わりにVisitor patternを使用することをお勧めします。このアプローチでは、抽象構文木のトラバーサルを簡単にモジュール化できます。

この方法を使用すると、ツリー内のノードタイプごとにspecficクラスを作成する必要があることに注意してください。たとえば、オペレータノードにはOperatorクラス、ファンクションコールノードにはFunctionCallクラスなどがあります。

ここでは、開始する必要があるASTの非常に単純な例を示します。ASTは、番号のオペレータのOperatorノード、及びNumberノードで構成：

class Node: 
    pass 


class Operator(Node): 
    def __init__(self, op, left, right): 
     self.op = op 
     self.left = left 
     self.right = right 


class Number(Node): 
    def __init__(self, value): 
     self.value = value 


class AstWalker: 
    def visit(self, node): 
     name = 'visit_' + node.__class__.__name__ 
     vistor = getattr(self, name, self.missing) 
     vistor(node) 

    def missing(self, node): 
     name = node.__class__.__name__ 
     raise Exception('No visitor method for node type: ' + name) 

    def visit_Operator(self, node): 
     print('operator:', node.op) 
     self.visit(node.left) 
     self.visit(node.right) 

    def visit_Number(self, node): 
     print('number:', node.value) 


# The ast represents the expression: 
# 
# (1 * 5) - (3/5) 
# 
ast = Operator(op='-', 
     left=Operator(op='*', 
        left=Number(1), 
        right=Number(5) 
     ), 

     right=Operator(op='/', 
        left=Number(3), 
        right=Number(5) 
     ) 
) 

walker = AstWalker() 
walker.visit(ast) 

上記のコードの出力である：

operator: - 
operator: * 
number: 1 
number: 5 
operator:/
number: 3 
number: 5 

上記コードの興味深い部分はAstWalkerクラスです。ここでパターンを実装します。ここで簡単に説明します。

visitメソッドは、上記のコードの肉です。マジックが起こる場所です。長い話を短くするために、visitは1つの引数nodeをとります。 OperatorノードまたはNumberのいずれかになります。次に、node.__class__.__name__を使用してノードのクラスの名前を取得します。ご覧のとおり、visitという名前には、ツリー内の各ノードの訪問者メソッド - visit_Operatorとvisit_Numberが訪問しているため、名前が付いています。

最後にself.visitに、getattrを使用して、クラスから正しい訪問者メソッドを取得します。ノードがNumbergetattrの場合、visit_Numberメソッドを返します。 Operatorも同様です。ビジターメソッドは、呼び出されたとnodeが渡される。

私たちが渡された何とかnodeオブジェクトはビジターメソッドを持っていないことが判明した場合、我々はself.missingを返し、それを呼び出します。 self.missing私たちが遭遇したノードオブジェクトは訪問者メソッドを持たない単純なレポートです。

上記のように、各訪問者メソッドは1つの引数nodeをとります。現在のノードが訪問していました。上の例では、単に各nodeの属性を出力します。ただし、バイトコードを生成するのは簡単に変更できます。