2.3 Syntaxdarstellungen

Die Syntax einer Programmiersprache legt fest, welche Zeichenreihen bzw. Folgen von Wörtern korrekt formulierte (,,syntaktisch korrekte``) Programme der Sprache darstellen und welche nicht. Zur Überprüfung der syntaktischen Korrektheit eines Programms muß deshalb zuvor die Syntax der Programmiersprache formal beschrieben werden. Hierzu existieren verschiedene Möglichkeiten. In den folgenden zwei Unterabschnitten werden die zwei gängigsten vorgestellt, nämlich die Syntaxdiagramme  und die Backus-Naur-Form .

Sowohl Syntaxdiagramme als auch die Backus-Naur-Form sind Techniken zur Darstellung sogenannter kontextfreier Programmiersprachen . Die meisten Programmiersprachen sind jedoch kontextsensitiv , d.h. es lassen sich nicht alle Regeln zur Beschreibung der Syntax mit den beiden Techniken beschreiben. Nicht formulierbare Eigenschaften der Syntax werden daher umgangssprachlich ergänzt.

2.3.1 Syntaxdiagramme

Bei den Syntaxdiagrammen  handelt es sich um eine graphische und daher sehr übersichtliche Notation zur Definition der Syntax einer Programmiersprache. Syntaxdiagramme sind folgendermaßen definiert:

• Zur Beschreibung der Syntax einer Sprache existiert in der Regel eine Menge von Syntaxdiagrammen, die zusammen die Syntax definieren. In der Menge existiert genau ein übergeordnetes Syntaxdiagramm, bei dem die Definition beginnt.
• Jedes Syntaxdiagramm besitzt einen Namen (Bezeichnung).
• Jedes Syntaxdiagramm besteht aus runden und eckigen Kästchen sowie aus Pfeilen.
• In jedem rechteckigen Kästchen steht die Bezeichnung eines (anderen) Syntaxdiagramms der Menge von Syntaxdiagrammen (ein sogenanntes Nicht-Terminalsymbol ).
• In jedem runden Kästchen steht ein Wort (Token , Terminalsymbol ) der Sprache.
• Aus jedem Kästchen führt genau ein Pfeil hinaus und genau einer hinein.
• Pfeile dürfen sich aufspalten und zusammengezogen werden.
• Jedes Syntaxdiagramm besitzt genau einen Pfeil, der von keinem Kästchen ausgeht (eintretender Pfeil) und genau einen Pfeil, der zu keinem Kästchen führt (austretender Pfeil).

Token einer Programmiersprache werden durch die Lexikalik der Sprache definiert. Sie stellen die kleinsten zusammenhängenden Grundsymbole einer Sprache, bswp.:

• einfache und zusammengesetzte Symbole (+, <=, (, ...).
• Schlüsselwörter (reservierte Wörter) 
• Bezeichner 
• Konstanten

Trennzeichen  (Zeichen für die Trennung von Token) wie Blanks, Tabulatoren oder Zeilenumbrüche sowie Kommentare werden im allgemeinen nicht in den Syntaxdiagrammen berücksichtigt.

Mit Hilfe von Syntaxdiagrammen kann festgestellt werden, ob eine bestimmte Zeichenfolge (ein Programm) syntaktisch korrekt ist. Dazu fängt man bei dem eintretenden Pfeil des übergeordneten Syntaxdiagramm an und verfolgt die Pfeile. Erreicht man ein rundes Kästchen, so muß das entsprechende Token als nächstes in der Zeichenfolge auftreten. Erreicht man ein eckiges Kästchen, springt man in das entsprechend bezeichnete Syntaxdiagramm. Existieren alternative Wege, so wählt man den entsprechenden aus. Gibt es keinen Weg durch die Syntaxdiagramme, so ist das Programm syntaktisch nicht korrekt. Nach der Abarbeitung der Zeichenfolge muß der austretende Pfeil des übergeordneten Syntaxdiagramms erreicht worden sein. Sonst ist das Programm ebenfalls nicht syntaktisch korrekt.

Das Prinzip, nach dem Syntaxdiagramme arbeiten, läßt sich durch eine Analogie veranschaulichen: In einem Zoo gibt es eine Menge von Gehegen mit verschiedenen Tieren. Die Gehege können durch Besucher auf Wegen erreicht werden. Wegen der großen Besucherzahlen dürfen dabei die Wege jeweils nur in einer Richtung begangen werden. Es existieren Kreuzungen, an denen mehrere Wege eingeschlagen werden können. In Abbildung werden anhand eines Syntaxdiagramms (Wegeplan des Zoos) die möglichen Wege durch den Zoo veranschaulicht. Die Gehege stellen dabei die Token dar. Der Übersichtlichkeit halber ist der Plan in zwei Teilpläne (Zoo, Säugetiere) aufgeteilt.

Ein Fotograph möchte nun im Zoo eine Fotoserie erstellen. Dabei muß (!) er jeweils ein Foto schießen, wenn er an einem Gehege vorbei kommt. Er orientiert sich an dem Wegeplan. Offenbar kann er die möglichen Bildsequenzen ermitteln, indem er die möglichen Wege durch den Zoo nachvollzieht. Erreicht er im Plan das eckige Kästchen Säugetiere, so zeigt der Teilplan Säugetiere den weiteren Weg, bis er diesen wieder verläßt und am Ausgang des eckigen Kästchens Säugetiere seinen Weg fortsetzt.

  

Abbildung: Wegeplan im Zoo als Syntaxdiagramm

Mögliche Bildsequenzen sind zum Beispiel:

• Schlangen Delphine
• Schlangen Elephanten Pinguine Delphine
• Schlangen Elephanten Pinguine Affen Delphine
• Schlangen Elephanten Pinguine Elephanten Pinguine Delphine

Dahingegen sind folgende Bildsequenzen nicht möglich:

• Elephanten Delphine (weil der Fotograph anfangs auf jeden Fall zuerst am Schlangengehege vorbeikommt)
• Schlangen Pinguine (weil der Fotograph am Ende seines Zoobesuchs auf jeden Fall am Delphingehege vorbeikommt)
• Schlangen Elephanten Affen Delphine (weil der Fotograph zwischen dem Besuch des Elephanten- und Affengeheges auf jeden Fall einmal am Pinguingehege vorbeigehen muß)
• Schlangen Pinguine Schlangen Delphine (weil der Fotograph nur am Anfang seines Zoobesuchs am Schlangengehege vorbeikommt)

2.3.2 Backus-Naur-Form

Bei der Backus-Naur-Form  (BNF)  handelt es sich um eine textuelle Beschreibungsform für die Syntax von Programmiersprachen. Das Äquivalent zu einem einzelnen Syntaxdiagramm wird hier Produktion  oder BNF-Regel  genannt. Produktionen besitzen eine linke und eine rechte Seite, die durch das Metazeichen ::= getrennt sind. Auf der linken Seite stehen jeweils einzelne Nicht-Terminalsymbole, die immer in spitze Klammern gesetzt werden. Die rechte Seite enthält Folgen von Terminalsymbolen, Nicht-Terminalsymbolen und dem Meta-Symbol |. Terminalsymbole werden in Hochkommata gesetzt. Das Meta-Symbol | bedeutet ,,oder`` und entspricht einem sich aufspaltendem Pfeil in den Syntaxdiagrammen. Das ,,e`` (bzw. Epsilon) steht für einen leeren Weg.

Das Zoo-Beispiel aus Abbildung wird in der BNF folgendermaßen formuliert:

  <Zoo>                  ::= "Schlangen" <Saeugetiere-und-mehr>

  <Saeugetiere-und-mehr> ::= <Saeugetiere> 
                             "Pinguine" 
                             <Saeugetiere-und-mehr> 
                             |
                             <Saeugetiere> "Delphine"

  <Saeugetiere>          ::= "Elefanten" | 
                             "Affen" |
                             e

Im Laufe der Zeit sind einige Abkürzungsmöglichkeiten entwickelt worden, die zu besser lesbaren Produktionen führen:

• [...] bedeutet: Symbole oder Symbolfolgen innerhalb der Klammern können auch weggelassen werden.
• {...} bedeutet: Symbole oder Symbolfolgen innerhalb der Klammern können beliebig oft wiederholt oder auch ganz weggelassen werden.
• (...|...) bedeutet: genau ein alternatives Symbol oder eine alternative Symbolfolge innerhalb der Klammern muß auftreten.

Das Zoo-Beispiel kann damit folgendermaßen formuliert werden:

  <Zoo>         ::= "Schlangen" 
                    <Saeugetiere>
                    {"Pinguine" <Saeugetiere>}
                    "Delphine"

  <Saeugetiere> ::= ("Elefanten" | 
                     "Affen" |
                     e
                    )