Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 54

Termauswertung

Wir werden später erneut auf Algorithmen zur Auswertung von Termen kommen. Hier wird nur kurz skizziert, wie ein derartiger Algorithmus prinzipiell abläuft. Die Auswertung eines Terms geschieht von innen nach außen (der Klammerstruktur folgend). Es werden also jeweils Teilterme gesucht, die direkt auswertbar sind (da die Parameterwerte direkt Werte darstellen), und diese werden durch Ausführung der betreffenden Operation ausgewertet und durch das Ergebnis der Auswertung ersetzt. Wie bereits erwähnt, wird bei bedingten Termen zuerst die Bedingung ausgewertet und danach die Auswertung bei der ausgewählten Alternative fortgeführt – hier wird im Gegensatz zu anderen Operatoren also von außen nach innen vorgegangen.

Die Auswertung eines Terms verdeutlicht folgendes Beispiel:

	1+ if true ∨ ¬false then 7 · 9 + 7 − 6 else abs(3 − 8) fi
	1+ if true ∨ ¬ true then 7 · 9 + 7− 6 else abs(3 − 8) fi
	1+ if true then 7 · 9 + 7− 6 else abs(3 − 8) fi
	1 + 7 · 9 + 7− 6
	1 + 63 + 7− 6
	64 + 7− 6
	71− 6
	65

Eigenschaften der Termauswertung

Der Algorithmus zur Termauswertung ist in dieser Form nichtdeterministisch, determiniert und terminierend. Als Beispiel für den Nichtdeterminismus kann man folgende Auswertung betrachten: (7 + 9) · (4 + 10) kann über 16 · (4 + 10) oder über (7 + 9) · 14 zu 16 · 14 ausgewertet werden. Man kann den Algorithmus deterministisch machen, indem z.B. bei mehreren Möglichkeiten jeweils immer der am weitesten links stehende auswertbare Teilterm ausgewertet wird.