Mit Google fortfahren
Syntaxdiagramme lesen, prüfen und erstellen
Ein Syntaxdiagramm beschreibt mit gerichteten Wegen, welche Zeichenfolgen nach einer formalen Regel erlaubt sind. Du folgst einem vollständigen Weg vom Eingang bis zum Ausgang: Die dabei durchlaufenen Terminalsymbole ergeben ein gültiges Wort.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Vom Weg zum Wort
Ein Syntaxdiagramm besitzt einen Eingang, einen Ausgang und gerichtete Verbindungen dazwischen. Du beginnst am Eingang, folgst den Pfeilrichtungen und musst den Ausgang erreichen.
Formale Sprache
Eine formale Sprache ist eine Menge von Wörtern, die nach genau festgelegten Regeln gebildet werden. Ein Wort ist dabei eine endliche Zeichenfolge, zum Beispiel 1100 oder x+20*y.
Ein vollständiger Weg lässt sich auf zwei Arten nutzen:
- Erzeugen: Du wählst einen erlaubten Weg und schreibst die durchlaufenen Zeichen auf.
- Prüfen: Du suchst zu einem vorgegebenen Wort einen Weg, dessen Zeichen genau in derselben Reihenfolge erscheinen.
Gibt es keinen solchen vollständigen Weg, gehört das Wort nicht zu der beschriebenen Sprache.
Nicht irgendein Ausschnitt des Weges zählt. Ein Wort ist nur dann syntaktisch zulässig, wenn sein gesamter Zeichenverlauf vom Eingang bis zum Ausgang passt.
Terminale und Nichtterminale
Syntaxdiagramme trennen Zeichen, die im fertigen Wort stehen, von Bezeichnungen für Teilregeln.
Terminalsymbol
Ein Terminalsymbol ist ein Zeichen oder eine feste Zeichenfolge, die im fertigen Wort vorkommt. Es wird typischerweise in einem Kreis, Oval oder abgerundeten Kasten dargestellt. Beispiele sind 0, x, + oder if.
Nichtterminalsymbol
Ein Nichtterminalsymbol bezeichnet eine syntaktische Kategorie mit einem eigenen Diagramm. Es steht typischerweise in einem rechteckigen Kasten. Beispiele sind Ziffer, Variable oder Ausdruck.
Triffst du auf das Nichtterminal Ziffer, wechselst du in dessen Diagramm. Dort wählst du beispielsweise eines der Terminale 0 bis 9. Nach dem vollständigen Durchlauf kehrst du in das übergeordnete Diagramm zurück.
Beispiel: x+20*y ableiten
Für Rechenausdrücke können die Kategorien Ausdruck, Summand, Faktor, Variable, Zahl und Ziffer verwendet werden. Eine verkürzte Ableitung zeigt, wie Nichtterminale schrittweise verschwinden:
Ausdruck
→ Summand + Summand
→ Faktor + Faktor * Faktor
→ Variable + Zahl * Variable
→ x + Ziffer Ziffer * y
→ x + 2 0 * y
→ x+20*y
Am Ende sind nur noch Terminalsymbole vorhanden. Damit wurde das Wort aus den Regeln erzeugt.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Ein Zeichen, das im fertigen Wort stehen darf, ist ein . Eine Bezeichnung für ein eigenes Unterdiagramm ist ein . Nach dem Durchlaufen eines Unterdiagramms kehrst du in das zurück. Eine Ableitung endet, wenn nur noch übrig sind.
Grundmuster erkennen
Komplexe Syntaxdiagramme setzen sich aus wenigen Grundmustern zusammen:
- Sequenz: Teile müssen nacheinander durchlaufen werden.
- Alternative: An einer Verzweigung wird genau einer der angebotenen Wege gewählt.
- Optionaler Teil: Ein Abschnitt darf durchlaufen oder umgangen werden.
- Wiederholung: Ein Abschnitt darf mehrfach durchlaufen werden; je nach Weg kann auch kein Durchlauf erlaubt sein.
- Rekursion: Ein Diagramm verweist direkt oder über andere Kategorien wieder auf sich selbst.
Zyklen und Rekursion können unendlich viele verschiedene Wörter beschreiben. Jeder Weg für ein konkretes Wort muss trotzdem endlich sein.
Beispiel: Drei Muster verbinden
Eine Regel fordert:
- Am Anfang steht
11oder0. - Danach folgen beliebig viele Blöcke
A,BBoderCCC. - Am Ende steht
1oder00.
Das Wort 11BBACCC00 ist zulässig:
11erfüllt die erste Alternative.BB,AundCCCsind drei erlaubte Durchläufe der Wiederholung.00erfüllt die letzte Alternative.
Das Wort 11CC00 ist nicht zulässig. In der Mitte ist nur der Block CCC erlaubt, nicht CC.
Ein Wort vollständig prüfen
Beim Prüfen hilft ein festes Vorgehen:
- Markiere Eingang und Ausgang.
- Lies das nächste Zeichen des Wortes.
- Wähle nur einen Weg, dessen Terminal zu diesem Zeichen passt.
- Durchlaufe jedes angetroffene Nichtterminal vollständig.
- Prüfe am Ende: Sind alle Zeichen verbraucht und ist der Ausgang erreicht?
Beispiel: Gleich viele Einsen und Nullen
Die rekursive Regel
Bitmuster → 10 oder Bitmuster → 1 Bitmuster 0
erzeugt eine nichtleere Folge von Einsen, gefolgt von gleich vielen Nullen.
Prüfung von 1100:
Bitmuster
→ 1 Bitmuster 0
→ 1 1 0 0
→ 1100
Das innere Bitmuster wird durch 10 ersetzt. Deshalb ist 1100 zulässig.
11000 ist nicht zulässig: Zwei Einsen stehen drei Nullen gegenüber. Nach einer vollständigen Ableitung bliebe eine zusätzliche 0 übrig.
Ein Diagramm entwerfen
Beginne beim Entwerfen nicht mit Kästen und Pfeilen, sondern mit der Zeichenregel.
- Bestimme feste Zeichenfolgen.
- Markiere Alternativen.
- Bestimme optionale oder wiederholbare Teile.
- Lagere wiederkehrende Teilregeln als Nichtterminale aus.
- Verbinde alles zu mindestens einem vollständigen Weg.
- Teste passende Wörter und gezielt gewählte Gegenbeispiele.
Beispiel: Anfang 11, Ende 00
Gesucht sind Wörter, die mit 11 beginnen und mit 00 enden. Dazwischen darf eine beliebige Folge aus 0 und 1 stehen.
Eine textuelle Wegbeschreibung lautet:
Eingang → 11 → Wiederholung von 0 oder 1 → 00 → Ausgang
Die Wiederholung darf ohne Durchlauf verlassen werden. Deshalb ist 1100 zulässig. Bei 110100 bildet 01 den Mittelteil, also ist auch dieses Wort zulässig.
1000 ist nicht zulässig, weil der geforderte Anfang 11 fehlt. 1100010 ist nicht zulässig, weil das Wort nicht mit 00 endet.
Teste beim Entwerfen besonders die Grenzen: den kürzesten erlaubten Weg, keinen Durchlauf einer möglichen Wiederholung, mehrere Wiederholungen sowie Wörter mit falschem Anfang oder Ende.
Was Syntaxdiagramme nicht prüfen
Syntaxdiagramme beschreiben die formale Struktur einer Zeichenfolge. Sie können beispielsweise festlegen, wo ein Schlüsselwort, eine Klammer oder eine Ziffer stehen darf.
Nicht jede zusätzliche Bedingung lässt sich dadurch ausdrücken. Bei einem Programm kann die Zeichenfolge syntaktisch passend aufgebaut sein, obwohl etwa der Typ eines zugewiesenen Wertes nicht zum Typ der Variablen passt. Solche bedeutungs- oder typabhängigen Bedingungen werden zusätzlich geprüft.
Syntaktisch korrekt bedeutet: Die Form passt zur Regel. Es bedeutet nicht automatisch, dass ein Programm sinnvoll ist oder alle semantischen Bedingungen erfüllt.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Syntaxdiagramm
- vollständiger Weg: Eingang bis Ausgang
- Bausteine: Terminale und Nichtterminale
- Strukturen: Sequenz, Alternative, Wiederholung und Rekursion
- Anwendungen: Wörter erzeugen, prüfen und Regeln entwerfen
- Grenze: syntaktische Form statt vollständiger Semantik
Abschluss-Check
Wenn du alle drei Aufgaben begründen kannst, kannst du Syntaxdiagramme nicht nur ablesen, sondern auch systematisch prüfen und aus Regeln entwickeln.