Z perspektywy kodu źródłowego lub nawet kodu trzech adresów (TAC) możesz bardzo łatwo zwizualizować problem na tej stronie ...
http://cgm.cs.mcgill.ca/~hagha/topic30/topic30.html#Exptree
Jeśli przejdziesz do sekcji drzewa wyrażeń, a następnie przewiniesz nieco w dół, zobaczysz „sortowanie topologiczne” drzewa i algorytm oceny wyrażenia.
W takim przypadku możesz użyć DAG do oceny wyrażeń, co jest przydatne, ponieważ ocena jest normalnie interpretowana, a użycie takiego ewaluatora DAG przyspieszy w zasadzie prostą interpretację, ponieważ nie jest to wypychanie i wyskakiwanie na stos, a także dlatego, że eliminuje wspólne wyrażenia podrzędne.
Podstawowy algorytm obliczania DAG w języku innym niż starożytny egipski (tj. Angielski) jest następujący:
1) Zrób swój obiekt DAG w ten sposób
Potrzebujesz listy na żywo, a ta lista zawiera wszystkie bieżące węzły DAG na żywo i wyrażenia podrzędne DAG. Wyrażenie podrzędne DAG jest węzłem DAG lub można je również nazwać węzłem wewnętrznym. Przez węzeł DAG na żywo mam na myśli to, że jeśli przypiszesz do zmiennej X, stanie się ona aktywna. Typowe wyrażenie podrzędne, które następnie używa X, używa tego wystąpienia. Jeśli X zostanie ponownie przypisany do, wówczas tworzony jest NOWY WĘZEŁ DAG i dodawany do aktualnej listy, a stary X jest usuwany, więc następne wyrażenie podrzędne, które używa X, będzie odnosić się do nowej instancji i nie będzie kolidować z wyrażeniami podrzędnymi, które wystarczy użyć tej samej nazwy zmiennej.
Po przypisaniu do zmiennej X, przypadkowo wszystkie węzły wyrażenia podrzędnego DAG, które są aktywne w momencie przypisania, stają się nieaktywne, ponieważ nowe przypisanie unieważnia znaczenie wyrażeń podrzędnych używających starej wartości.
class Dag {
TList LiveList;
DagNode Root;
}
// In your DagNode you need a way to refer to the original things that
// the DAG is computed from. In this case I just assume an integer index
// into the list of variables and also an integer index for the opertor for
// Nodes that refer to operators. Obviously you can create sub-classes for
// different kinds of Dag Nodes.
class DagNode {
int Variable;
int Operator;// You can also use a class
DagNode Left;
DagNode Right;
DagNodeList Parents;
}
Więc to, co robisz, to przechodzenie przez drzewo we własnym kodzie, takim jak na przykład drzewo wyrażeń w kodzie źródłowym. Na przykład wywołaj istniejące węzły XNodes.
Więc dla każdego XNode musisz zdecydować, jak dodać go do DAG i istnieje możliwość, że jest już w DAG.
To bardzo prosty pseudokod. Nie jest przeznaczony do kompilacji.
DagNode XNode::GetDagNode(Dag dag) {
if (XNode.IsAssignment) {
// The assignment is a special case. A common sub expression is not
// formed by the assignment since it creates a new value.
// Evaluate the right hand side like normal
XNode.RightXNode.GetDagNode();
// And now take the variable being assigned to out of the current live list
dag.RemoveDagNodeForVariable(XNode.VariableBeingAssigned);
// Also remove all DAG sub expressions using the variable - since the new value
// makes them redundant
dag.RemoveDagExpressionsUsingVariable(XNode.VariableBeingAssigned);
// Then make a new variable in the live list in the dag, so that references to
// the variable later on will see the new dag node instead.
dag.AddDagNodeForVariable(XNode.VariableBeingAssigned);
}
else if (XNode.IsVariable) {
// A variable node has no child nodes, so you can just proces it directly
DagNode n = dag.GetDagNodeForVariable(XNode.Variable));
if (n) XNode.DagNode = n;
else {
XNode.DagNode = dag.CreateDagNodeForVariable(XNode.Variable);
}
return XNode.DagNode;
}
else if (XNode.IsOperator) {
DagNode leftDagNode = XNode.LeftXNode.GetDagNode(dag);
DagNode rightDagNode = XNode.RightXNode.GetDagNode(dag);
// Here you can observe how supplying the operator id and both operands that it
// looks in the Dags live list to check if this expression is already there. If
// it is then it returns it and that is how a common sub-expression is formed.
// This is called an internal node.
XNode.DagNode =
dag.GetOrCreateDagNodeForOperator(XNode.Operator,leftDagNode,RightDagNode) );
return XNode.DagNode;
}
}
Więc to jest jeden sposób patrzenia na to. Podstawowy spacer po drzewie i po prostu dodawanie i odwoływanie się do węzłów Dag na bieżąco. Korzeń dag jest tym, co DagNode zwraca korzeń drzewa, na przykład.
Oczywiście przykładowa procedura może być podzielona na mniejsze części lub utworzona jako podklasy z funkcjami wirtualnymi.
Jeśli chodzi o sortowanie Dag, przechodzisz przez każdy DagNode od lewej do prawej. Innymi słowy, podążaj za lewą krawędzią DagNodes, a następnie za prawą krawędzią boczną. Numery są przypisywane odwrotnie. Innymi słowy, kiedy osiągniesz DagNode bez dzieci, przypisz temu węzłowi bieżący numer sortowania i zwiększ numer sortowania, aby rekurencja rozwinęła liczby przypisane w kolejności rosnącej.
Ten przykład obsługuje tylko drzewa z węzłami, które mają zero lub dwoje dzieci. Oczywiście niektóre drzewa mają węzły z więcej niż dwojgiem dzieci, więc logika jest nadal taka sama. Zamiast obliczać od lewej do prawej, obliczaj od lewej do prawej itd.
// Most basic DAG topological ordering example.
void DagNode::OrderDAG(int* counter) {
if (this->AlreadyCounted) return;
// Count from left to right
for x = 0 to this->Children.Count-1
this->Children[x].OrderDag(counter)
// And finally number the DAG Node here after all
// the children have been numbered
this->DAGOrder = *counter;
// Increment the counter so the caller gets a higher number
*counter = *counter + 1;
// Mark as processed so will count again
this->AlreadyCounted = TRUE;
}