Zum Inhalt springen

Syntaxdiagramm: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Die Seite wurde neu angelegt: „Ein Syntaxdiagramm zeigt die Regeln einer Sprache als Wegenetz. Jeder Weg vom Eingang zum Ausgang ergibt ein gültiges Wort. ==Definition== Ein '''Syntaxdiagramm''' ist die grafische Darstellung einer BNF-Regel. Für jedes Nichtterminal gibt es ein eigenes Diagramm, das nach dem Nichtterminal benannt ist. Jedes Diagramm hat einen Eingang und einen Ausgang. Ein Wort gehört zur Sprache, wenn ein Weg in Pfeilrichtung vom Eingang zum Au…“
 
Keine Bearbeitungszusammenfassung
 
Zeile 2: Zeile 2:


==Definition==
==Definition==
Ein '''Syntaxdiagramm''' ist die grafische Darstellung einer [[Backus-Naur-Form|BNF-Regel]]. Für jedes Nichtterminal gibt es ein eigenes Diagramm, das nach dem Nichtterminal benannt ist. Jedes Diagramm hat einen Eingang und einen Ausgang. Ein Wort gehört zur Sprache, wenn ein Weg in Pfeilrichtung vom Eingang zum Ausgang genau die Zeichen des Wortes liefert. Trifft der Weg auf ein Nichtterminal, wird zuerst dessen Diagramm durchlaufen. Danach geht der Weg an dieser Stelle weiter.
Ein '''Syntaxdiagramm''' ist die grafische Darstellung einer Regel der [[Backus-Naur-Form]]. Für jedes Nichtterminal gibt es ein eigenes Diagramm, das nach dem Nichtterminal benannt ist. Jedes Diagramm hat einen Eingang und einen Ausgang. Das Diagramm des Startsymbols ist das Startdiagramm, dort beginnt jede Prüfung.
 
Ein Wort gehört zur Sprache, wenn ein Weg in Pfeilrichtung vom Eingang zum Ausgang des Startdiagramms genau die Zeichen des Wortes liefert. Trifft der Weg auf ein Nichtterminal, wird zuerst dessen Diagramm durchlaufen. Danach geht der Weg an dieser Stelle weiter.


==Elemente==
==Elemente==
[[Datei:Syntaxdiagramm Elemente.png|mini|Elemente eines Syntaxdiagramms]]
[[Datei:Syntaxdiagramm Elemente.png|mini|Elemente eines Syntaxdiagramms]]
Der Weg beginnt am Eingang links und endet am Ausgang rechts. Pfeile geben die Richtung an. Ein Syntaxdiagramm besteht aus sechs Elementen:
Der Weg beginnt am Eingang links und endet am Ausgang rechts. Pfeile geben die Richtung an. Ein Syntaxdiagramm besteht aus sechs Elementen:


* '''Terminal''': ein Element mit runden Ecken. Es enthält ein Zeichen, das wörtlich im Text steht.
* '''Terminal''': ein Element mit runden Ecken. Es enthält ein Zeichen oder ein festes Wort, das wörtlich im Text steht.
* '''Nichtterminal''': ein Rechteck. Es verweist auf das Diagramm dieses Nichtterminals.
* '''Nichtterminal''': ein Rechteck. Es verweist auf das Diagramm dieses Nichtterminals. Das kann auch das eigene Diagramm sein, dann ist die Regel rekursiv.
* '''Folge''': Elemente auf demselben Weg werden nacheinander durchlaufen.
* '''Folge''': Elemente auf demselben Weg werden nacheinander durchlaufen.
* '''Alternative''': Der Weg verzweigt. Genau ein Zweig wird gewählt.
* '''Alternative''': Der Weg verzweigt. Genau ein Zweig wird gewählt.
* '''Wiederholung''': Ein Rückweg führt hinter dem Element zurück an dessen Anfang. Das Element wird mindestens einmal durchlaufen und darf beliebig oft wiederholt werden.
* '''Wiederholung''': Ein Rückweg führt hinter dem Element zurück an dessen Anfang. Das Element wird mindestens einmal durchlaufen und darf beliebig oft wiederholt werden.
* '''Option''': Ein Weg führt am Element vorbei. Das Element darf entfallen.
* '''Option''': Ein Weg führt am Element vorbei. Das Element darf entfallen.
Führt um eine Wiederholung zusätzlich ein Weg herum, darf das Element beliebig oft vorkommen, auch keinmal.


==Von der Backus-Naur-Form zum Syntaxdiagramm==
==Von der Backus-Naur-Form zum Syntaxdiagramm==
Jede Regel der BNF ergibt ein Diagramm mit dem Namen des Nichtterminals auf der linken Seite. Die rechte Seite wird Element für Element übertragen. <code>A</code> und <code>B</code> stehen dabei für beliebige Teile der rechten Seite:
Jede Regel der BNF oder der [[Backus-Naur-Form#Erweiterte Backus-Naur-Form|erweiterten BNF]] ergibt ein Diagramm mit dem Namen des Nichtterminals auf der linken Seite. Die rechte Seite wird Element für Element übertragen. <code>A</code> und <code>B</code> stehen dabei für beliebige Teile der rechten Seite:


{| class="wikitable"
{| class="wikitable"
! BNF !! Syntaxdiagramm
! Regel !! Syntaxdiagramm
|-
|-
| Folge <code>A B</code> || Kette: A und B hintereinander auf einem Weg
| Folge <code>A B</code> || Kette: A und B hintereinander auf einem Weg
|-
|-
| <code>A &#124; B</code> || Verzweigung: ein Weg durch A, ein Weg durch B
| Alternative <code>A &#124; B</code> || Verzweigung: ein Weg durch A, ein Weg durch B
|-
|-
| <code>[ A ]</code> || Option: ein Weg an A vorbei
| Option <code>[ A ]</code> (nur erweiterte BNF) || ein Weg durch A und ein Weg an A vorbei
|-
|-
| <code>{ A }</code> || Rückweg: A lässt sich wiederholen
| Wiederholung <code>{ A }</code> (nur erweiterte BNF) || A mit Rückweg und zusätzlich ein Weg an A vorbei
|-
|-
| Nichtterminal || Rechteck, das auf das Diagramm des Nichtterminals verweist
| Nichtterminal || Rechteck, das auf das Diagramm des Nichtterminals verweist
Zeile 35: Zeile 38:
|}
|}


<code>{ A }</code> erlaubt auch null Durchläufe. Ein Rückweg um ein Element bedeutet dagegen mindestens einen Durchlauf. Für <code>{ A }</code> gehört deshalb zum Rückweg zusätzlich ein Weg an <code>A</code> vorbei, wie bei der Option. Die Folge <code>A { A }</code> dagegen ist genau ein Element <code>A</code> mit Rückweg.
<code>{ A }</code> erlaubt auch null Durchläufe. Ein Rückweg um ein Element bedeutet dagegen mindestens einen Durchlauf. Für <code>{ A }</code> gehört deshalb zum Rückweg zusätzlich ein Weg an <code>A</code> vorbei, wie bei der Option. Die Folge <code>A { A }</code> dagegen ergibt ein einziges Element <code>A</code> mit Rückweg und ohne Weg daran vorbei: <code>A</code> kommt mindestens einmal vor.
 
Eine leere Alternative <code>ε</code> der BNF wird zu einem Weg ohne Element. Eine Regel der BNF, die sich selbst verwendet, um etwas zu wiederholen, wird im Diagramm zu einem Rückweg. Verwendet sich eine Regel selbst, um etwas zu verschachteln, bleibt im Diagramm das Rechteck mit dem eigenen Namen stehen.
 
==Vom Syntaxdiagramm zur Backus-Naur-Form==
Aus jedem Diagramm entsteht eine Regel:
# Der Name des Diagramms wird das Nichtterminal auf der linken Seite.
# Der Weg wird vom Eingang zum Ausgang verfolgt. Elemente hintereinander ergeben eine Folge. Terminale werden wörtlich notiert, in der erweiterten BNF in Anführungszeichen. Nichtterminale stehen in spitzen Klammern.
# Eine Verzweigung ergibt Alternativen, getrennt durch <code>|</code>.
# Ein Weg an einem Element vorbei ergibt in der erweiterten BNF eine Option <code>[ A ]</code>. In der BNF ohne Erweiterungen entstehen zwei Alternativen, eine mit und eine ohne das Element.
# Ein Rückweg um ein Element ergibt in der erweiterten BNF <code>A { A }</code>. In der BNF ohne Erweiterungen übernimmt ein neues Nichtterminal die Wiederholung mit einer Regel, die sich selbst verwendet.
# Ein Rückweg um ein Element zusammen mit einem Weg an ihm vorbei ergibt in der erweiterten BNF <code>{ A }</code>. In der BNF ohne Erweiterungen hat das neue Nichtterminal dann die Alternativen <code>ε</code> und <code>A</code> gefolgt vom neuen Nichtterminal.


==Beispiele==
==Beispiele==
Zeile 42: Zeile 56:


<syntaxhighlight lang="text">
<syntaxhighlight lang="text">
<zahl>      ::= [<vorzeichen>] <ziffer> {<ziffer>}
<zahl>      ::= [ <vorzeichen> ] <ziffer> { <ziffer> }
<vorzeichen> ::= + | -
<vorzeichen> ::= "+" | "-"
<ziffer>    ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<ziffer>    ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
</syntaxhighlight>
</syntaxhighlight>


Zeile 50: Zeile 64:


[[Datei:Syntaxdiagramm ganze Zahl.png|mini|Syntaxdiagramme für Zahl, Vorzeichen und Ziffer]]
[[Datei:Syntaxdiagramm ganze Zahl.png|mini|Syntaxdiagramme für Zahl, Vorzeichen und Ziffer]]
 
* Diagramm ''Zahl'': Die Option <code>[ &lt;vorzeichen&gt; ]</code> ergibt einen Weg, der am Rechteck Vorzeichen vorbeiführt. Danach folgt <code>&lt;ziffer&gt; { &lt;ziffer&gt; }</code>: eine Ziffer, der beliebig viele Ziffern folgen dürfen. Das ist ein Rechteck Ziffer mit Rückweg, denn die Ziffer kommt mindestens einmal vor.
* Diagramm ''Zahl'': Die Option <code>[&lt;vorzeichen&gt;]</code> ergibt einen Weg, der am Rechteck Vorzeichen vorbeiführt. Danach folgt <code>&lt;ziffer&gt; {&lt;ziffer&gt;}</code>: eine Ziffer, der beliebig viele Ziffern folgen dürfen. Das ist ein Rechteck Ziffer mit Rückweg, denn die Ziffer kommt mindestens einmal vor.
* Diagramm ''Vorzeichen'': Der Weg verzweigt in die Terminale <code>+</code> und <code>-</code>. Im Diagramm stehen sie ohne Anführungszeichen, die runden Ecken kennzeichnen sie als Terminale.
* Diagramm ''Vorzeichen'': Der Weg verzweigt in die Terminale <code>+</code> und <code>-</code>.
* Diagramm ''Ziffer'': Der Weg verzweigt in die Terminale <code>0</code> bis <code>9</code>. Das Bild kürzt mit … ab.
* Diagramm ''Ziffer'': Der Weg verzweigt in die Terminale <code>0</code> bis <code>9</code>. Das Bild kürzt mit … ab.


Zeile 61: Zeile 74:
! Wort !! Weg !! Ergebnis
! Wort !! Weg !! Ergebnis
|-
|-
| <code>-12</code> || Die Option wird genommen, das Diagramm Vorzeichen liefert <code>-</code>. Dann liefert Ziffer die <code>1</code>. Der Rückweg führt noch einmal zu Ziffer, sie liefert die <code>2</code>. Der Weg endet am Ausgang. || passt
| <code>-12</code> || Der Weg führt durch das Rechteck Vorzeichen, sein Diagramm liefert <code>-</code>. Dann liefert Ziffer die <code>1</code>. Der Rückweg führt noch einmal zu Ziffer, sie liefert die <code>2</code>. Der Weg endet am Ausgang. || passt
|-
|-
| <code>7</code> || Die Option wird übersprungen. Ziffer liefert die <code>7</code>. Der Weg endet am Ausgang. || passt
| <code>7</code> || Der Weg führt am Vorzeichen vorbei. Ziffer liefert die <code>7</code>. Der Weg endet am Ausgang. || passt
|-
|-
| <code>12-</code> || Die Ziffern <code>1</code> und <code>2</code> führen zum Ausgang. Das <code>-</code> bleibt übrig. Ein Vorzeichen steht nur am Anfang. || passt nicht
| <code>12-</code> || Die Ziffern <code>1</code> und <code>2</code> führen zum Ausgang. Das <code>-</code> bleibt übrig. Ein Vorzeichen steht nur am Anfang. || passt nicht
Zeile 69: Zeile 82:
| <code>+</code> || Das Vorzeichen <code>+</code> ist lesbar. Danach müsste mindestens eine Ziffer folgen, sie fehlt. || passt nicht
| <code>+</code> || Das Vorzeichen <code>+</code> ist lesbar. Danach müsste mindestens eine Ziffer folgen, sie fehlt. || passt nicht
|}
|}
===Wiederholung mit Trennzeichen als Syntaxdiagramm darstellen===
[[Datei:Syntaxdiagramm Menge von Ziffern.png|mini|Syntaxdiagramm einer Menge von Ziffern]]
Dargestellt wird die Regel für eine Menge von Ziffern aus dem Beispiel [[Backus-Naur-Form#Erweiterte Form in die Backus-Naur-Form überführen|Erweiterte Form in die Backus-Naur-Form überführen]]:
<syntaxhighlight lang="text">
<menge> ::= "{" <ziffer> { ";" <ziffer> } "}"
</syntaxhighlight>
* Die Terminale <code>{</code> und <code>}</code> stehen am Anfang und am Ende des Weges, jeweils als Element mit runden Ecken.
* Dazwischen folgt das Rechteck Ziffer.
* Die Wiederholung <code>{ ";" &lt;ziffer&gt; }</code> darf auch keinmal vorkommen. Sie wird deshalb zu einem Rückweg um die Folge aus <code>;</code> und Ziffer und zusätzlich zu einem Weg, der an dieser Folge vorbeiführt.
Drei Zeichenfolgen werden geprüft:
* <code>{7}</code>: Der Weg führt durch <code>{</code> und durch Ziffer, dann an der Wiederholung vorbei und durch <code>}</code>. Die Zeichenfolge passt.
* <code>{4;0;7}</code>: Nach der ersten Ziffer führt der Weg durch <code>;</code> und Ziffer, über den Rückweg noch einmal durch <code>;</code> und Ziffer und dann durch <code>}</code>. Die Zeichenfolge passt.
* <code>{4;}</code>: Nach dem Semikolon muss eine Ziffer folgen, es folgt aber <code>}</code>. Die Zeichenfolge passt nicht.
===Rekursive Regel als Syntaxdiagramm darstellen===
[[Datei:Syntaxdiagramm Klammerausdruck.png|mini|Syntaxdiagramm für korrekt geklammerte Ausdrücke]]
Die Regel für korrekt geklammerte Ausdrücke aus dem Beispiel [[Backus-Naur-Form#Grammatik in die Backus-Naur-Form übertragen|Grammatik in die Backus-Naur-Form übertragen]] verwendet sich selbst:
<syntaxhighlight lang="text">
<ausdruck> ::= ( <ausdruck> ) <ausdruck> | ε
</syntaxhighlight>
Die leere Alternative <code>ε</code> wird zu einem Weg ohne Element. Die andere Alternative wird zu einem Weg mit vier Elementen: dem Terminal <code>(</code>, dem Rechteck Ausdruck, dem Terminal <code>)</code> und noch einmal dem Rechteck Ausdruck. Beide Rechtecke verweisen auf das Diagramm selbst.
Ein Rückweg kann diese Rekursion nicht ersetzen: Zu jeder öffnenden Klammer muss später genau eine schließende folgen, und ein Rückweg zählt nicht mit, wie oft er durchlaufen wurde.
Zwei Wörter werden geprüft:
* <code>()</code>: Der Weg führt durch <code>(</code>. Für das erste Rechteck wird das Diagramm erneut durchlaufen, und zwar auf dem Weg ohne Element. Danach führt der Weg durch <code>)</code>. Auch für das zweite Rechteck wird das Diagramm auf dem Weg ohne Element durchlaufen.
* <code>(())</code>: Der Weg beginnt wieder mit <code>(</code>. Für das erste Rechteck wird das Diagramm jetzt auf dem Weg mit den Klammern durchlaufen, er liefert wie eben <code>()</code>. Danach folgen <code>)</code> und für das zweite Rechteck der Weg ohne Element.
===Syntaxdiagramm in die Backus-Naur-Form überführen===
[[Datei:Syntaxdiagramm Dezimalzahl.png|mini|Syntaxdiagramm einer Dezimalzahl]]
Das Diagramm beschreibt Dezimalzahlen wie <code>3,14</code> oder <code>42</code>. Das Rechteck Ziffer verweist auf das Diagramm Ziffer aus dem ersten Beispiel. Gesucht sind die Regeln in der erweiterten BNF und in der BNF ohne Erweiterungen.
'''Schritt 1: Weg verfolgen.''' Der Weg führt zuerst durch das Rechteck Ziffer mit Rückweg: eine oder mehrere Ziffern. Danach verzweigt er. Der obere Weg führt direkt zum Ausgang. Der untere Weg führt durch das Terminal <code>,</code> und noch einmal durch ein Rechteck Ziffer mit Rückweg. Der Teil hinter dem Komma ist also eine Option.
'''Schritt 2: Erweiterte BNF notieren.''' Der Rückweg wird zu <code>&lt;ziffer&gt; { &lt;ziffer&gt; }</code>, die Option steht in eckigen Klammern, das Komma als Terminal in Anführungszeichen:
<syntaxhighlight lang="text">
<dezimalzahl> ::= <ziffer> { <ziffer> } [ "," <ziffer> { <ziffer> } ]
</syntaxhighlight>
'''Schritt 3: BNF ohne Erweiterungen notieren.''' Das neue Nichtterminal <code>&lt;ziffern&gt;</code> übernimmt die Wiederholung. Aus der Option werden zwei Alternativen, eine ohne und eine mit Nachkommateil:
<syntaxhighlight lang="text">
<dezimalzahl> ::= <ziffern> | <ziffern> , <ziffern>
<ziffern>    ::= <ziffer> | <ziffer> <ziffern>
</syntaxhighlight>
'''Schritt 4: Prüfen.''' Für <code>42</code> führt der Weg durch Ziffer, über den Rückweg noch einmal durch Ziffer und dann auf dem oberen Weg zum Ausgang. Für <code>3,14</code> führt er einmal durch Ziffer, dann auf dem unteren Weg durch das Komma und zweimal durch Ziffer. Beide Zahlen lassen sich auch mit beiden Fassungen der Regeln bilden. <code>,5</code> passt nicht, weil vor dem Komma mindestens eine Ziffer stehen muss. <code>7,</code> passt nicht, weil hinter dem Komma mindestens eine Ziffer folgen muss.


[[Kategorie:Formale Sprachen]]
[[Kategorie:Formale Sprachen]]
[[Kategorie:AHR I Informatik LK]]
[[Kategorie:AHR I Informatik LK]]

Aktuelle Version vom 11. November 2026, 22:07 Uhr

Ein Syntaxdiagramm zeigt die Regeln einer Sprache als Wegenetz. Jeder Weg vom Eingang zum Ausgang ergibt ein gültiges Wort.

Definition

Ein Syntaxdiagramm ist die grafische Darstellung einer Regel der Backus-Naur-Form. Für jedes Nichtterminal gibt es ein eigenes Diagramm, das nach dem Nichtterminal benannt ist. Jedes Diagramm hat einen Eingang und einen Ausgang. Das Diagramm des Startsymbols ist das Startdiagramm, dort beginnt jede Prüfung.

Ein Wort gehört zur Sprache, wenn ein Weg in Pfeilrichtung vom Eingang zum Ausgang des Startdiagramms genau die Zeichen des Wortes liefert. Trifft der Weg auf ein Nichtterminal, wird zuerst dessen Diagramm durchlaufen. Danach geht der Weg an dieser Stelle weiter.

Elemente

Elemente eines Syntaxdiagramms

Der Weg beginnt am Eingang links und endet am Ausgang rechts. Pfeile geben die Richtung an. Ein Syntaxdiagramm besteht aus sechs Elementen:

  • Terminal: ein Element mit runden Ecken. Es enthält ein Zeichen oder ein festes Wort, das wörtlich im Text steht.
  • Nichtterminal: ein Rechteck. Es verweist auf das Diagramm dieses Nichtterminals. Das kann auch das eigene Diagramm sein, dann ist die Regel rekursiv.
  • Folge: Elemente auf demselben Weg werden nacheinander durchlaufen.
  • Alternative: Der Weg verzweigt. Genau ein Zweig wird gewählt.
  • Wiederholung: Ein Rückweg führt hinter dem Element zurück an dessen Anfang. Das Element wird mindestens einmal durchlaufen und darf beliebig oft wiederholt werden.
  • Option: Ein Weg führt am Element vorbei. Das Element darf entfallen.

Führt um eine Wiederholung zusätzlich ein Weg herum, darf das Element beliebig oft vorkommen, auch keinmal.

Von der Backus-Naur-Form zum Syntaxdiagramm

Jede Regel der BNF oder der erweiterten BNF ergibt ein Diagramm mit dem Namen des Nichtterminals auf der linken Seite. Die rechte Seite wird Element für Element übertragen. A und B stehen dabei für beliebige Teile der rechten Seite:

Regel Syntaxdiagramm
Folge A B Kette: A und B hintereinander auf einem Weg
Alternative A | B Verzweigung: ein Weg durch A, ein Weg durch B
Option [ A ] (nur erweiterte BNF) ein Weg durch A und ein Weg an A vorbei
Wiederholung { A } (nur erweiterte BNF) A mit Rückweg und zusätzlich ein Weg an A vorbei
Nichtterminal Rechteck, das auf das Diagramm des Nichtterminals verweist
Terminal Element mit runden Ecken

{ A } erlaubt auch null Durchläufe. Ein Rückweg um ein Element bedeutet dagegen mindestens einen Durchlauf. Für { A } gehört deshalb zum Rückweg zusätzlich ein Weg an A vorbei, wie bei der Option. Die Folge A { A } dagegen ergibt ein einziges Element A mit Rückweg und ohne Weg daran vorbei: A kommt mindestens einmal vor.

Eine leere Alternative ε der BNF wird zu einem Weg ohne Element. Eine Regel der BNF, die sich selbst verwendet, um etwas zu wiederholen, wird im Diagramm zu einem Rückweg. Verwendet sich eine Regel selbst, um etwas zu verschachteln, bleibt im Diagramm das Rechteck mit dem eigenen Namen stehen.

Vom Syntaxdiagramm zur Backus-Naur-Form

Aus jedem Diagramm entsteht eine Regel:

  1. Der Name des Diagramms wird das Nichtterminal auf der linken Seite.
  2. Der Weg wird vom Eingang zum Ausgang verfolgt. Elemente hintereinander ergeben eine Folge. Terminale werden wörtlich notiert, in der erweiterten BNF in Anführungszeichen. Nichtterminale stehen in spitzen Klammern.
  3. Eine Verzweigung ergibt Alternativen, getrennt durch |.
  4. Ein Weg an einem Element vorbei ergibt in der erweiterten BNF eine Option [ A ]. In der BNF ohne Erweiterungen entstehen zwei Alternativen, eine mit und eine ohne das Element.
  5. Ein Rückweg um ein Element ergibt in der erweiterten BNF A { A }. In der BNF ohne Erweiterungen übernimmt ein neues Nichtterminal die Wiederholung mit einer Regel, die sich selbst verwendet.
  6. Ein Rückweg um ein Element zusammen mit einem Weg an ihm vorbei ergibt in der erweiterten BNF { A }. In der BNF ohne Erweiterungen hat das neue Nichtterminal dann die Alternativen ε und A gefolgt vom neuen Nichtterminal.

Beispiele

Ganze Zahl als Syntaxdiagramm darstellen

Dargestellt wird die Regel für <zahl> aus dem Beispiel Ganze Zahl beschreiben, zusammen mit den beiden Regeln, auf die sie verweist:

<zahl>       ::= [ <vorzeichen> ] <ziffer> { <ziffer> }
<vorzeichen> ::= "+" | "-"
<ziffer>     ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Es entstehen drei Diagramme:

Syntaxdiagramme für Zahl, Vorzeichen und Ziffer
  • Diagramm Zahl: Die Option [ <vorzeichen> ] ergibt einen Weg, der am Rechteck Vorzeichen vorbeiführt. Danach folgt <ziffer> { <ziffer> }: eine Ziffer, der beliebig viele Ziffern folgen dürfen. Das ist ein Rechteck Ziffer mit Rückweg, denn die Ziffer kommt mindestens einmal vor.
  • Diagramm Vorzeichen: Der Weg verzweigt in die Terminale + und -. Im Diagramm stehen sie ohne Anführungszeichen, die runden Ecken kennzeichnen sie als Terminale.
  • Diagramm Ziffer: Der Weg verzweigt in die Terminale 0 bis 9. Das Bild kürzt mit … ab.

Wörter mit einem Syntaxdiagramm prüfen

Vier Wörter werden mit den Diagrammen der ganzen Zahl geprüft. Der Weg beginnt im Diagramm Zahl und folgt den Zeichen des Wortes von links nach rechts.

Wort Weg Ergebnis
-12 Der Weg führt durch das Rechteck Vorzeichen, sein Diagramm liefert -. Dann liefert Ziffer die 1. Der Rückweg führt noch einmal zu Ziffer, sie liefert die 2. Der Weg endet am Ausgang. passt
7 Der Weg führt am Vorzeichen vorbei. Ziffer liefert die 7. Der Weg endet am Ausgang. passt
12- Die Ziffern 1 und 2 führen zum Ausgang. Das - bleibt übrig. Ein Vorzeichen steht nur am Anfang. passt nicht
+ Das Vorzeichen + ist lesbar. Danach müsste mindestens eine Ziffer folgen, sie fehlt. passt nicht

Wiederholung mit Trennzeichen als Syntaxdiagramm darstellen

Syntaxdiagramm einer Menge von Ziffern

Dargestellt wird die Regel für eine Menge von Ziffern aus dem Beispiel Erweiterte Form in die Backus-Naur-Form überführen:

<menge> ::= "{" <ziffer> { ";" <ziffer> } "}"
  • Die Terminale { und } stehen am Anfang und am Ende des Weges, jeweils als Element mit runden Ecken.
  • Dazwischen folgt das Rechteck Ziffer.
  • Die Wiederholung { ";" <ziffer> } darf auch keinmal vorkommen. Sie wird deshalb zu einem Rückweg um die Folge aus ; und Ziffer und zusätzlich zu einem Weg, der an dieser Folge vorbeiführt.

Drei Zeichenfolgen werden geprüft:

  • {7}: Der Weg führt durch { und durch Ziffer, dann an der Wiederholung vorbei und durch }. Die Zeichenfolge passt.
  • {4;0;7}: Nach der ersten Ziffer führt der Weg durch ; und Ziffer, über den Rückweg noch einmal durch ; und Ziffer und dann durch }. Die Zeichenfolge passt.
  • {4;}: Nach dem Semikolon muss eine Ziffer folgen, es folgt aber }. Die Zeichenfolge passt nicht.

Rekursive Regel als Syntaxdiagramm darstellen

Syntaxdiagramm für korrekt geklammerte Ausdrücke

Die Regel für korrekt geklammerte Ausdrücke aus dem Beispiel Grammatik in die Backus-Naur-Form übertragen verwendet sich selbst:

<ausdruck> ::= ( <ausdruck> ) <ausdruck> | ε

Die leere Alternative ε wird zu einem Weg ohne Element. Die andere Alternative wird zu einem Weg mit vier Elementen: dem Terminal (, dem Rechteck Ausdruck, dem Terminal ) und noch einmal dem Rechteck Ausdruck. Beide Rechtecke verweisen auf das Diagramm selbst.

Ein Rückweg kann diese Rekursion nicht ersetzen: Zu jeder öffnenden Klammer muss später genau eine schließende folgen, und ein Rückweg zählt nicht mit, wie oft er durchlaufen wurde.

Zwei Wörter werden geprüft:

  • (): Der Weg führt durch (. Für das erste Rechteck wird das Diagramm erneut durchlaufen, und zwar auf dem Weg ohne Element. Danach führt der Weg durch ). Auch für das zweite Rechteck wird das Diagramm auf dem Weg ohne Element durchlaufen.
  • (()): Der Weg beginnt wieder mit (. Für das erste Rechteck wird das Diagramm jetzt auf dem Weg mit den Klammern durchlaufen, er liefert wie eben (). Danach folgen ) und für das zweite Rechteck der Weg ohne Element.

Syntaxdiagramm in die Backus-Naur-Form überführen

Syntaxdiagramm einer Dezimalzahl

Das Diagramm beschreibt Dezimalzahlen wie 3,14 oder 42. Das Rechteck Ziffer verweist auf das Diagramm Ziffer aus dem ersten Beispiel. Gesucht sind die Regeln in der erweiterten BNF und in der BNF ohne Erweiterungen.

Schritt 1: Weg verfolgen. Der Weg führt zuerst durch das Rechteck Ziffer mit Rückweg: eine oder mehrere Ziffern. Danach verzweigt er. Der obere Weg führt direkt zum Ausgang. Der untere Weg führt durch das Terminal , und noch einmal durch ein Rechteck Ziffer mit Rückweg. Der Teil hinter dem Komma ist also eine Option.

Schritt 2: Erweiterte BNF notieren. Der Rückweg wird zu <ziffer> { <ziffer> }, die Option steht in eckigen Klammern, das Komma als Terminal in Anführungszeichen:

<dezimalzahl> ::= <ziffer> { <ziffer> } [ "," <ziffer> { <ziffer> } ]

Schritt 3: BNF ohne Erweiterungen notieren. Das neue Nichtterminal <ziffern> übernimmt die Wiederholung. Aus der Option werden zwei Alternativen, eine ohne und eine mit Nachkommateil:

<dezimalzahl> ::= <ziffern> | <ziffern> , <ziffern>
<ziffern>     ::= <ziffer> | <ziffer> <ziffern>

Schritt 4: Prüfen. Für 42 führt der Weg durch Ziffer, über den Rückweg noch einmal durch Ziffer und dann auf dem oberen Weg zum Ausgang. Für 3,14 führt er einmal durch Ziffer, dann auf dem unteren Weg durch das Komma und zweimal durch Ziffer. Beide Zahlen lassen sich auch mit beiden Fassungen der Regeln bilden. ,5 passt nicht, weil vor dem Komma mindestens eine Ziffer stehen muss. 7, passt nicht, weil hinter dem Komma mindestens eine Ziffer folgen muss.