Lernpfad Know-How-Computer/Know-How-Assembler - Grammatik einer formalen Sprache

zurück

Startseite

weiter

Die Grammatik einer formalen Sprache am Beispiel Know-How-Assembler

Für natürliche Sprachen wie Deutsch oder Englisch gibt es Grammatikregeln, die festlegen, wie die einzelnen Wörter zu Sätzen zusammengesetzt werden können. Für Programmiersprachen, die auch als "formale" Sprachen bezeichnet werden, gibt es solche Regeln auch. Nur wenn ein Programmcode im Sinne dieser - auch als Syntax bezeichneten - Grammatik korrekt ist, kann er in die von einem Computer ausführbare Maschinensprache übersetzt werden.

Ein Hilfsmittel zur systematischen und kompakten Darstellung solcher Syntaxregeln ist die so genannte Erweiterte Backus-Naur-Form EBNF. Wie man damit die syntaktische Korrektheit eines Programmcodes überprüfen kann, das soll jetzt am Beispiel der Know-How-Assemblersprache erklärt werden, die du ja schon im Kapitel Know-How-Assembler kennengelernt hast.

Grammatik der Know-How-Assemblersprache in EBNF

Die Grammatik oder auch "Syntax" der Know-How-Assemblersprache kann mit Hilfe der EBNF folgendermaßen definiert werden.

KHA-Programm = Anweisung { Anweisung }

Ein KHA-Programm besteht aus mindestens einer Anweisung. Beliebig viele weitere Anweisungen können folgen, müssen dies aber nicht. Diese Wiederholsungsmöglichkeit wird in der EBNF durch geschweifte Klammern ausgedrückt.

Anweisung = ( Labelanweisung | Befehl ) ;

Eine Anweisung ist entweder eine Labelanweisung oder ein Befehl. In jedem Fall muss danach noch ein Semikolon ; folgen. Die Entweder-oder-Alternative wird in der EBNF durch den senkrechten Strich ausgedrückt. Die runden Klammern werden genutzt, um Elemente zu gruppieren.

Labelanweisung = Bezeichner : ( Befehl | Zahl )

Eine Labelanweisung beginnt mit einem Bezeichner, dem ein Doppelpunkt : folgen muss. Danach folgt entweder ein Befehl oder eine Zahl.

Befehl = Adressbefehl | stp

Ein Befehl ist entweder ein Adressbefehl oder der Stoppbefehl stp.

Adressbefehl = ( inc | dec | jmp | isz ) Bezeichner

Ein Adressbefehl beginnt mit genau einem der vier Befehle inc, dec, jmp, isz und endet in jedem Fall mit einem Bezeichner.

Zahl = Ziffer { Ziffer }

Eine Zahl besteht aus mindestens einer Ziffer, der beliebig weitere Ziffern folgen können, aber nicht müssen. Nach dieser speziellen Definition kann eine Zahl führende Nullen besitzen, aber kein Vorzeichen oder Dezimalkomma.

Bezeichner = Buchstabe { ( Buchstabe | Ziffer ) }

Ein Bezeichner beginnt auf jeden Fall mit einem Buchstabe. Danach können beliebig viele weitere Buchstaben und Ziffern in beliebiger Reihenfolge folgen.

Buchstabe = a | b | ... | z | A | B | ... | Z

Ein Buchstabe ist entweder ein Kleinbuchstaben aus dem Bereich von a bis z oder ein Großbuchstaben aus dem Bereich von A bis Z. Deutsche Umlaute gelten nach dieser Definition also z.B. nicht als Buchstaben.

Ziffer = 0 | 1 | ... | 9

Eine Ziffer ist entweder das Zeichen 0 oder 1 oder ... oder 9.

EBNF-Fachbegriffe

In der EBNF-Darstellung werden diejenigen Elemente, die in einer der Definitionszeilen links vom Gleichheitszeichen vorkommen, als Nicht-Terminale bezeichnet. Sie stehen noch nicht auf der untersten, "terminalen" Ebene der Definitionshierarchie, sondern werden durch elementarere Nicht-Terminale oder durch Terminale definiert. Terminale sind Elemente, die selbst nicht mehr weiter erklärt werden, sondern auf der untersten Stufe, also am Ende der Erklärungskette stehen. Das oberste Element in der Hierarchie ist das so genannte Startsymbol - in diesem Fall lautet es KHA-Programm.
Nicht-Terminale sind hier z.B. die Ausdrücke Labelanweisung, Befehl oder Bezeichner. Terminale sind z.B. der Buchstabe a, das Semikolon ; oder die Ziffer 7. Aber auch die Maschinenbefehle inc, jmp oder stp werden in dieser Grammatik als terminale Symbole betrachtet. In der obigen EBNF-Darstellung der KHA-Syntax werden die Nicht-Terminale in kursiver Schrift dargestellt - in Abgrenzung zu den Terminalen.
Die Ersetzungsregeln, mit denen Nicht-Terminale durch elementarere Nicht-Terminale oder Termiale definiert werden, werden auch als Produktionen bezeichnet.

Ableitung eines Programms "bottom up"

Mit Hilfe der EBNF-Regeln kann nun ein KHA-Programm auf seine formale, d.h. syntaktische Korrektheit überprüft werden. Dafür gibt es grundsätzlich zwei Vorgehensweisen: die bottom up- und die top down-Methode.

Beispielhaft wird im Folgenden der Anfang des KHA-Programms "Von x auf 0" nach der bottom up-Methode abgeleitet. Hier zunächst noch einmal der gesamte Programmcode, wobei die einzelnen Anweisungen jetzt aus Gründen der Übersichtlichkeit nicht mehr durch Zeilenumbrüche, sondern durch Semikolons abgeschlossen werden:

start: isz x; jmp xminus1; stp; xminus1: dec x; jmp start; x: 3;

Das Programm beginnt mit einer Folge von (terminalen) Buchstaben, nämlich s t a r und t, die durch das Nicht-Terminal Bezeichner ersetzt werden kann. Danach folgt das terminale Symbol :, das erst mal nicht ersetzt wird. Es folgt - bis zum nächsten Leerzeichen - die Buchstabenfolge i s z. Diese kann als "reservierter" Bezeichner durch das Terminal isz ersetzt werden. Der anschließende Buchstabe x ist wieder ein Bezeichner und das dann folgende Semikolon ; ist ein Terminal.
Der Anfang des Programms kann also nach ersten Ersetzungen auf "unterer Ebene" der EBNF-Hierarchie in die folgende Sequenz überführt werden:

start : isz x ; ...
➥ Bezeichner : isz Bezeichner ; ...

Die Zweierkombination isz Bezeichner kann nun durch das - in der EBNF-Darstellung schon etwas höher stehende - Nicht-Terminal Adressbefehl und dieses wiederum durch das Nicht-Terminal Befehl ersetzt werden. Der Programmanfang erhält dadurch die Form:

➥ Bezeichner : Adressbefehl ; ...
➥ Bezeichner : Befehl ; ...

Die Dreierkombination Bezeichner : Befehl kann nun durch das Nicht-Terminal Labelanweisung ersetzt werden, das zusammen mit dem anschließenden Semikolon ; durch das Nicht-Terminal Anweisung ersetzbar ist:

➥ Labelanweisung ; ...
➥ Anweisung ...

Ganz entsprechend können auch die restlichen Teile des Programms durch schrittweise Ersetzungen in die Nicht-Terminale Anweisung überführt werden, so dass insgesamt eine Folge von sechs Anweisungen entsteht. Diese kann schließlich mit Hilfe der obersten Ersetzungsregel zum Startsymbol KHA-Programm zusammengefasst werden.

➥ Anweisung Anweisung ... Anweisung
➥ KHA-Programm

Damit ist das Ziel erreicht: Das Programm "Von x auf 0" hat die Prüfung auf syntaktische Korrektheit bestanden.

Zusammenfassung

Bei der bottom-up-Methode werden Teilfolgen von Terminalen und solchen Nicht-Terminalen, die in der Grammatik weiter unten stehen, durch darüber stehende Nicht-Terminale zusammengefasst und ersetzt, bis am Ende das oberste Nicht-Terminal, das Startsymbol übrig bleibt.
Bei der so genannten top-down-Methode wird dagegen umgekehrt von dem Startsymbol ausgegangen und es wird versucht, dieses nach den Ersetzungsregeln derart in weiter unten stehende Nicht-Terminale und Terminale zu zerlegen, bis schließlich der aus lauter Terminalen bestehende Programmcode entsteht.

Aufgabe

Oben wurde beispielhaft der Anfang des KHA-Programms "Von x auf 0" start: isz x; mit Hilfe der bottom-up-Methode bis zum Nicht-Terminal Anweisung abgeleitet. Führe auch für den Rest des Programms jmp xminus1; stp; xminus1: dec x; jmp start; x: 3; entsprechende bottom-up-Ableitungen durch, um zu zeigen, dass auch dieser Programmteil syntaktisch korrekt ist.

zurück

Startseite

weiter