Erklärung der Syntax

Jedes GOTO-Programm ${\displaystyle P}$ besteht aus einer Anzahl von Anweisungen ${\displaystyle A}$, getrennt mit jeweils einem Semikolon. Vor jeder Anweisung befindet sich eine (eindeutige) Marke ${\displaystyle M_{1},\ M_{2},\ \dots }$, gefolgt von einem Doppelpunkt.

GOTO-Programme haben eine endliche Anzahl von Variablen ${\displaystyle x_{1},\ x_{2},\ \dots }$ und Konstanten ${\displaystyle c}$. Es sind nur fünf verschiedene Anweisungen erlaubt:

• Zuweisung einer Variablen durch eine weitere (dieselbe oder eine andere) Variable, vermehrt um eine Konstante, etwa

${\displaystyle x_{1}:=x_{2}+3}$

• oder vermindert um eine Konstante, etwa

${\displaystyle x_{3}:=x_{3}-1}$.

• eine Sprunganweisung

${\displaystyle \mathrm {GOTO} \quad M_{4}}$

• eine bedingte Sprunganweisung, wobei eine Variable auf Gleichheit mit einer Konstanten abgefragt wird, etwa

${\displaystyle {\rm {IF}}\quad x_{4}=45\quad {\rm {THEN}}\quad {\rm {GOTO}}\quad M_{5}}$

• und die STOP-Anweisung

${\displaystyle {\rm {STOP}}}$.

Addition zweier Variablen

Das folgende GOTO-Programm berechnet die Summe ${\displaystyle x_{1}+x_{2}}$ von zwei nicht-negativen Zahlen ${\displaystyle x_{1},x_{2}}$ und speichert diese in die Variable ${\displaystyle x_{3}}$.

 ${\displaystyle M_{1}:}$ ${\displaystyle x_{3}:=x_{1}}$;
 ${\displaystyle M_{2}:}$ ${\displaystyle x_{4}:=x_{2}}$;
 ${\displaystyle M_{3}:}$ ${\displaystyle {\rm {IF}}\ x_{4}=0\ {\rm {THEN}}\ {\rm {GOTO}}\ M_{7}}$;
 ${\displaystyle M_{4}:}$ ${\displaystyle x_{3}:=x_{3}+1}$;
 ${\displaystyle M_{5}:}$ ${\displaystyle x_{4}:=x_{4}-1}$;
 ${\displaystyle M_{6}:}$ ${\displaystyle \mathrm {GOTO} \quad M_{3}}$;
 ${\displaystyle M_{7}:}$ ${\displaystyle STOP}$

Multiplikation zweier Variablen

Das folgende Programm berechnet das Produkt ${\displaystyle x_{1}\cdot x_{2}}$ von zwei nicht-negativen Zahlen ${\displaystyle x_{1},x_{2}}$ und speichert dieses in die Variable ${\displaystyle x_{3}}$. Da wir schon ein Programm zur Implementierung der Addition zweier Variablen haben, verwenden wir diese, um eine Implementierung der Multiplikation zu entwickeln.

 ${\displaystyle M_{1}:}$ ${\displaystyle x_{3}:=0}$;
 ${\displaystyle M_{2}:}$ ${\displaystyle x_{4}:=x_{2}}$;
 ${\displaystyle M_{3}:}$ ${\displaystyle {\rm {IF}}\quad x_{4}=0\quad {\rm {THEN}}\quad {\rm {GOTO}}\quad M_{7}}$;
 ${\displaystyle M_{4}:}$ ${\displaystyle x_{4}:=x_{4}-1}$;
 ${\displaystyle M_{5}:}$ ${\displaystyle x_{3}:=x_{3}+x_{1}}$;
 ${\displaystyle M_{6}:}$ ${\displaystyle \mathrm {GOTO} \quad M_{3}}$;
 ${\displaystyle M_{7}:}$ ${\displaystyle STOP}$;

Hier ist zu beachten, dass ${\displaystyle M_{5}:}$ ${\displaystyle x_{3}:=x_{3}+x_{1}}$ formal kein gültiges GOTO-Programm ist, sondern durch ein entsprechendes GOTO-Programm für die Addition ersetzt werden muss. Führt man diese Ersetzung durch, erhält man folgendes GOTO-Programm für die Multiplikation von zwei nicht-negativen Zahlen ${\displaystyle x_{1},x_{2}}$.

 ${\displaystyle M_{1}:}$ ${\displaystyle x_{3}:=0}$;
 ${\displaystyle M_{2}:}$ ${\displaystyle x_{4}:=x_{2}}$;
 ${\displaystyle M_{3}:}$ ${\displaystyle {\rm {IF}}\quad x_{4}=0\quad {\rm {THEN}}\quad {\rm {GOTO}}\quad M_{10}}$;
 ${\displaystyle M_{4}:}$ ${\displaystyle x_{4}:=x_{4}-1}$;
 ${\displaystyle M_{5}:}$ ${\displaystyle x_{5}:=x_{1}}$;
 ${\displaystyle M_{6}:}$ ${\displaystyle {\rm {IF}}\quad x_{5}=0\quad {\rm {THEN}}\quad {\rm {GOTO}}\quad M_{3}}$;
 ${\displaystyle M_{7}:}$ ${\displaystyle x_{3}:=x_{3}+1}$;
 ${\displaystyle M_{8}:}$ ${\displaystyle x_{5}:=x_{5}-1}$;
 ${\displaystyle M_{9}:}$ ${\displaystyle \mathrm {GOTO} \quad M_{6}}$;
 ${\displaystyle M_{10}:}$ ${\displaystyle STOP}$;