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
undApplication
abgeleitet sind. Kleines UML-Diagramm:+-------------+ +- | Constant | +-----------+ +------------+ <--+ +-------------+ | ... | <---- | Expression | +-----------+ +------------+ <--+ +-------------+ +- | Application | +-------------+
Nun möchte ich
Application
zuConstant
falten wenn möglich, also z.B.f(2, 3)
durch6
ersetzen. Aber wie modelliere ich das? Ich muss an einer Stelle des ASTs dieApplication
rauslöschen und durch eineConstant
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'; }
-
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