Ausdruck Bäume für dummies?

Die beste Erklärung, die über das expression-Bäume, die ich je gelesen ist dieser Artikel von Charlie Calvert.

Um es zusammenzufassen;

Einen Ausdruck-Baum repräsentiert was Sie tun wollen, nicht wie Sie wollen, es zu tun.

Betrachten die folgende sehr einfache lambda-Ausdruck:

Func<int, int, int> function = (a, b) => a + b;

Diese Erklärung besteht aus drei Abschnitten:

• Eine Erklärung: Func<int, int, int> function
• Ein ist-gleich-operator: =
• Ein lambda-Ausdruck: (a, b) => a + b;

Die variable function Punkte bei raw-ausführbaren code, der weiß, wie man zwei zahlen zu addieren.

Dies ist der wichtigste Unterschied zwischen Delegierten und Ausdrücke. Rufen Sie function (a Func<int, int, int>), ohne jemals zu wissen, was Sie tun werden, mit der zwei Ganzzahlen übergeben. Es dauert zwei und gibt ein,, dass die meisten Ihren code wissen kann.

Im vorherigen Abschnitt haben Sie gesehen, wie eine variable zu deklarieren, die Punkte bei raw ausführbaren code. Ausdruck Bäume nicht in ausführbaren code, Sie sind eine form der Daten-Struktur.

Nun, im Gegensatz zu den Delegierten, Ihren code kann wissen, was ein Ausdruck Baum gemeint ist, zu tun.

LINQ bietet eine einfache syntax für die übersetzung von code in eine Daten-Struktur namens ein Ausdruck Baum. Der erste Schritt ist, fügen Sie eine using-Anweisung vorstellen, die Linq.Expressions namespace:

using System.Linq.Expressions;

Nun legen wir noch einen expression tree:

Expression<Func<int, int, int>> expression = (a, b) => a + b;

Den identischen lambda-Ausdruck in dem vorherigen Beispiel angezeigt wird umgewandelt in einen expression tree deklariert werden, der Typ Expression<T>. Der Bezeichner expression ist nicht ausführbaren code; es ist eine Daten-Struktur namens ein Ausdruck Baum.

Das bedeutet, dass Sie nicht nur berufen, ein Ausdruck, der Baum, wie man einen Delegaten aufrufen, aber Sie können es zu analysieren. Also, was können Sie Ihren code verstehen, durch die Analyse der variable expression?

//`expression.NodeType` returns NodeType.Lambda.
//`expression.Type` returns Func<int, int, int>.
//`expression.ReturnType` returns Int32.

var body = expression.Body;
//`body.NodeType` returns ExpressionType.Add.
//`body.Type` returns System.Int32.

var parameters = expression.Parameters;
//`parameters.Count` returns 2.

var firstParam = parameters[0];
//`firstParam.Name` returns "a".
//`firstParam.Type` returns System.Int32.

var secondParam = parameters[1].
//`secondParam.Name` returns "b".
//`secondParam.Type` returns System.Int32.

Hier sehen wir, dass es eine große Menge von Informationen, die wir bekommen können, die von einem Ausdruck.

Aber warum müssten wir das?

Haben Sie erfahren, dass Sie einen Ausdruck-Baum ist eine Datenstruktur, die für ausführbaren code. Aber wir haben bisher nicht beantwortet die zentrale Frage, warum man möchte, um eine solche Umwandlung. Dies ist die Frage, die wir anfangs gestellt haben, von diesem post, und jetzt ist es Zeit, Sie zu beantworten.

Einer LINQ to SQL-Abfrage wird nicht ausgeführt, in Ihrem C# - Programm. Statt, es wird übersetzt in SQL, gesendet über einen Draht, und ausgeführt auf einem Datenbank-server. In anderen Worten, der folgende code ist nie tatsächlich ausgeführt wird, in Ihrem Programm:

var query = from c in db.Customers where c.City == "Nantes" select new { c.City, c.CompanyName };

Ist es zunächst übersetzt werden in die folgende SQL-Anweisung und dann die Ausführung auf einem server:

SELECT [t0].[City], [t0].[CompanyName] FROM [dbo].[Customers] AS [t0] WHERE [t0].[City] = @p0

Den code, der sich in einem Abfrage-Ausdruck übersetzt werden muss in eine SQL-Abfrage, die gesendet werden können, um einen anderen Prozess als ein string. In diesem Fall, dass der Prozess geschieht auf eine SQL server-Datenbank. Es ist offensichtlich viel leichter zu übersetzen, eine Daten-Struktur, wie Sie einen Ausdruck-Baum in SQL, als es zu übersetzen raw-IL oder ausführbaren code in SQL. Übertreiben die Schwierigkeit, das problem etwas, nur vorstellen, die versuchen zu übersetzen, eine Serie von Nullen und Einsen in SQL!

Wenn es Zeit ist, übersetzen Sie Ihre query-Ausdruck in SQL, der Ausdruck, der Baum, der Ihre Abfrage wird auseinander genommen und analysiert, ebenso nahmen wir neben unseren einfachen lambda-Ausdruck Baum im vorherigen Abschnitt. Zugegeben, der Algorithmus für die Analyse der LINQ to SQL-Ausdruck, der Baum ist viel anspruchsvoller als die, die wir verwendet, aber das Prinzip ist das gleiche. Nachdem es analysiert hat, die Teile des expression tree, dann LINQ prüft Sie und entscheidet über die beste Weg, um eine SQL-Anweisung schreiben, die zurückkehren wird, die angeforderten Daten.

Ausdruck Bäume wurden erstellt, um die Aufgabe der Umwandlung von Codes, wie eines Abfrage-Ausdrucks in einen string, der übergeben werden kann, um einen anderen Prozess und dort ausgeführt. Es ist so einfach. Es ist kein großes Geheimnis hier, keinen Zauberstab, der muss geschwenkt werden. Man nimmt einfach code, wandelt es in Daten, und dann analysiert die Daten zu finden die konstituierenden Teile, die übersetzt wird in eine Zeichenfolge, die übergeben werden können, um einen anderen Prozess.

Da die Abfrage kommt, die für den compiler gilt, die in solche eine abstrakte Datenstruktur, der compiler ist frei zu interpretieren, es in fast irgendeiner Weise Sie es will. Es ist nicht gezwungen, der zum ausführen der Abfrage in einer bestimmten Reihenfolge oder in einer bestimmten Art und Weise. Stattdessen kann die Analyse der expression tree, entdecken Sie, was Sie getan haben wollen, und dann entscheiden, wie es zu tun. Zumindest in der Theorie, es hat die Freiheit, das zu betrachten eine beliebige Anzahl von Faktoren, wie den aktuellen Netzwerk-traffic, die Last auf die Datenbank, der aktuellen Ergebnisse stellt es zur Verfügung hat, etc. In der Praxis LINQ to SQL nicht all diese Faktoren berücksichtigen, aber es ist kostenlos in der Theorie ganz schön viel zu tun, was er will. Darüber hinaus könnte man pass dieser Ausdruck Baum, um einen benutzerdefinierten code, den Sie schreiben, mit der hand, die könnten es analysieren und übersetzen Sie es in etwas, das sehr Verschieden von dem, was produziert wird, die von LINQ to SQL.

Wieder einmal sehen wir, dass der Ausdruck Bäume erlauben uns, Sie zu vertreten (express?) was wir machen wollen. Und wir verwenden die übersetzer, die sich dafür entscheiden wie unsere Ausdrücke sind gewöhnungsbedürftig.

Ausdruck Bäume sind eine in-memory-Repräsentation eines Ausdrucks, z.B. ein arithmetischer oder boolescher Ausdruck.
Betrachten Sie beispielsweise den arithmetischen Ausdruck

a + b*2

Da * eine höhere Rangfolge hat als +, der Ausdruck, der Baum ist gebaut wie die:

    [+]
  /    \
 a     [*]
      /   \
     b     2

Unter diesem Baum, es kann ausgewertet werden, die für alle Werte von a und b.
Darüber hinaus können Sie wandeln Sie in andere Ausdruck Bäume, zum Beispiel zur Ableitung des Ausdrucks.

Beim implementieren Sie einen Ausdruck-Baum, würde ich vorschlagen, erstellen Sie eine base-Klasse
Ausdruck. Abgeleitet von der Klasse BinaryExpression würde verwendet werden für alle binäre Ausdrücke, wie z.B. + und * . Dann könnte man die Einführung einer VariableReferenceExpression auf Referenz-Variablen (z.B. a und b), und eine andere Klasse ConstantExpression (für die 2 aus dem Beispiel).

Den expression tree ist in vielen Fällen aufgebaut wie das Ergebnis der Analyse einer Eingabe (vom Benutzer direkt oder aus einer Datei).
Für die Bewertung der Ausdruck, der Baum, würde ich vorschlagen, verwenden Sie die Besucher-Muster.

IIUC, ein Ausdruck, der Baum ist ähnlich zu einem Abstrakten Syntax Baum, sondern ein Ausdruck der Regel yiels ein einzelner Wert, in der Erwägung, dass ein AST darstellen kann, ein ganzes Programm (mit Klassen, Pakete, Funktion, Aussagen, etc.)

Sowieso, für die einen der Ausdruck (2 + 3) * 5, der Baum:

    *
   / \ 
  +   5
 / \
2   3

Bewerten jeden Knoten rekursiv (bottom-up), um den Wert an der Wurzel-Knoten, d.h. der Wert des Ausdrucks.

Können Sie natürlich unäre - (negation) oder trinary (wenn-dann-sonst) - Operatoren zu, und die Funktionen (n-ary, dh eine beliebige Anzahl von ops), wenn Sie Ihre expression-language erlaubt es.

Bewertung der Arten und zu tun geben-die Steuerung erfolgt über ähnliche Bäume.

Ist der Ausdruck der Struktur, in die Sie sich beziehen, ist Ausdruck Auswertung Baum?

Wenn ja, dann ist es Baum konstruiert durch den parser. Parser verwendet, der Lexer/Tokenizer zu identifizieren, die Spielmarken von dem Programm. Parser konstruiert der Binäre Baum aus der tokens.

Hier ist die ausführliche Erklärung