AST-Transformationen - wie modellieren?



  • Hallo,

    ich schreibe eine kleine Programmiersprache und möchte den AST optimieren. Die Hierarchie sieht grob so aus: Expression ist eine Klasse in der AST-Hierarchie, von der dann wiederum u.A. Constant und Application abgeleitet sind. Kleines UML-Diagramm:

    +-------------+
                                          +- |   Constant  |
    +-----------+       +------------+ <--+  +-------------+
    |    ...    | <---- | Expression | 
    +-----------+       +------------+ <--+  +-------------+
                                          +- | Application |
                                             +-------------+
    

    Nun möchte ich Application zu Constant falten wenn möglich, also z.B. f(2, 3) durch 6 ersetzen. Aber wie modelliere ich das? Ich muss an einer Stelle des ASTs die Application rauslöschen und durch eine Constant ersetzen. Mit einer virtuellen Methode, die das Objekt entsprechend verändert, ist das nicht möglich, denn hier ist fundamental ein Typwechsel involviert und virtuelle Methoden können den Typ von *this natürlich nicht ändern.

    Eine Möglichkeit wäre es, den AST von außen mit einer Menge dynamic_cast s zu traversieren, was aber wahrscheinlich extrem langsam wäre. Zusätzlich ist das meiner Meinung nach auch sehr hacky.

    Also wie würdet ihr dieses Matching modellieren und den Typ durch einen anderen austauschen?



  • Hier ist noch ein minimales Beispiel zum oben erwähnten Ansatz mit dynamic_cast :

    #include <memory>
    #include <vector>
    #include <utility>
    #include <algorithm>
    #include <numeric>
    #include <iostream>
    
    struct Expression {
    	virtual ~Expression() = default;
    
    	virtual std::ostream& Print( std::ostream& Stream ) const = 0;
    };
    
    struct Constant : Expression {
    	int Value;
    
    	explicit Constant( int Value = 0 )
    		: Value{ Value } {
    	}
    
    	virtual std::ostream& Print( std::ostream& Stream ) const override {
    		return Stream << Value;
    	}
    };
    
    struct Application : Expression {
    	std::vector< std::unique_ptr< Expression > > Arguments;
    
    	template< typename... ArgsT >
    	explicit Application( ArgsT&&... Args ) {
    		using T = const int[];
    		T{ ( Arguments.emplace_back( std::forward< ArgsT >( Args ) ), 0 )... };
    	}
    
    	virtual std::ostream& Print( std::ostream& Stream ) const override {
    		Stream << '(';
    		if( !Arguments.empty() ) {
    			Stream << ' ';
    			for( auto i = Arguments.begin();; ) {
    				( **i ).Print( Stream );
    				if( ++i == Arguments.end() )
    					break;
    				Stream << ", ";
    			}
    			Stream << ' ';
    		}
    		Stream << ')';
    		return Stream;
    	}
    };
    
    void Fold( std::unique_ptr< Expression >& Expr ) {
    	if( Application* App = dynamic_cast< decltype( App ) >( &*Expr ) ) {
    		for( auto& i : App->Arguments )
    			Fold( i );
    		if( std::all_of( begin( App->Arguments ), end( App->Arguments ),
    				[]( auto const& Ptr ) -> bool { return dynamic_cast< Constant const* >( &*Ptr ); }
    			) )
    			Expr = std::make_unique< Constant >( std::accumulate( begin( App->Arguments ), end( App->Arguments ), 1,
    				[]( int Product, auto const& Ptr ) { return Product * dynamic_cast< Constant const* >( &*Ptr )->Value; } ) );
    	}
    }
    
    int main() {
    	std::unique_ptr< Expression > Foo =
    		std::make_unique< Application >(
    			std::make_unique< Application >(
    				std::make_unique< Constant >( 2 ),
    				std::make_unique< Constant >( 3 )
    			),
    			std::make_unique< Constant >( 7 )
    		);
    	Foo->Print( std::cout ) << '\n';
    	Fold( Foo );
    	Foo->Print( std::cout ) << '\n';
    }
    

    Live



  • Evtl. mit einem Visitor, der die Kinder der jeweiligen Expression als Parameter reinbekommt und eine Expression zurückgibt.



  • Danke für den Ratschlag. Ich dachte anfangs auch an das Visitor-Pattern, wusste aber nicht, wie ich damit einen Typ durch einen anderen ersetzen kann. Ich mache das nun so wie du sagtest, indem ich einen unique_ptr< Expression > zurückgebe. Funktioniert wunderbar.

    LG


Log in to reply