Ershov-Zahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ershov-Zahlen werden im Bereich der Informatik bei der Zuweisung von Registern benötigt. Sie geben die Anzahl der Register an, die zur Auswertung eines Ausdrucks benötigt werden.

Der Algorithmus[Bearbeiten]

Das Verfahren, mit dem Register für die Auswertung arithmetischer Ausdrücke zugeordnet werden können, berechnet zunächst für einen arithmetischen Ausdruck a die Anzahl ershov(a) der Register, die benötigt werden, um den Ausdruck auszuwerten. Es ist nach dem russischen Informatiker A.P. Ershov benannt, der die Idee des Verfahrens publiziert hat. Das Verfahren spezifiziert eine Funktion der Form: ershov: Expr → ℕ, die einem gegebenen arithmetischen Ausdruck a die Anzahl der zur Auswertung benötigten Register angibt. Hierfür ist eine Fallunterscheidung notwendig:

Konstante[Bearbeiten]

Um eine Konstante auszuwerten, wird genau ein Register benötigt. Demnach gilt:
ershov(c) = 1

Variable[Bearbeiten]

Um eine Variable Auszuwerten wird ebenfalls nur ein Register benötigt:
ershov(v) = 1

Unärer Ausdruck[Bearbeiten]

Zur Auswertung eines unären Operators auf einen Ausdruck a, wird lediglich die Anzahl der Register benötigt, die a braucht, denn das Ergebnisregister von a kann einfach überschrieben werden.
ershov(OP a) = ershov(a)

Binärer Ausdruck[Bearbeiten]

Bei der Auswertung eines binären Ausdruck der Form a1 OP a2 sind weiterhin drei Fälle zu unterscheiden:

Fall I: ershov(a1) < ershov(a2)[Bearbeiten]

In diesem Fall wird a2 evaluiert, wobei ershov(a2) Register benötigt werden. Das Ergebnis ist nun beispielsweise in Rx gespeichert. Die restlichen Register werden nun nicht mehr für a2 benötigt, wodurch sie für die Berechnung von a1 zur Verfügung stehen. Demnach gilt:

ershov(a1) < ershov(a2) → ershov(a1 OP a2) = ershov(a2)

Fall II: ershov(a1) = ershov(a2)[Bearbeiten]

In diesem Fall wird für die Berechnung von a1 ershov(a1) Register benötigt. Angenommen hierfür wurden n Register benötigt, dann steht in Register Rn das Ergebnis von a1. Für die Berechnung von a2 stehen nun n-1 nicht mehr benötigte Register zur Verfügung. Da aber entsprechend diesen Falles für die Berechnung von a2 ebenfalls n Register benötigt werden gilt:

ershov(a1) = ershov(a2) → ershov (a1 OP a2) = ershov(a1) + 1

Fall III: ershov(a1) > ershov(a2)[Bearbeiten]

Die Argumentation ist analog zu Fall I:
ershov(a1) > ershov(a2) → ershov(a1 OP a2) = ershov(a1)

Funktionsaufruf[Bearbeiten]

Da die Ergebnisse eines Funktionsaufrufes: f(a1 , ... , an) ohnehin auf den Stack geschrieben werden, ist es nicht notwendig das Ergebnis auch noch in einem Register abzuspeichern. Aus derselben Argumentation wie in Fall I für Binären Ausdrücke folgt:
ershov( f(a1 , ... , an ) ) = max( ershov(a1) , ... , ershov(an) )