Beispiele für Klammersprachen

Die Sprache der Rechenausdrücke

Rechenausdrücke sind Ausdrücke, in denen Zahlen, Rechenzeichen und Klammern vokommen können. Sie begegnen uns überall, wo kompliziertere Rechnungen dargestellt werden müssen.

Im folgenden wollen wir uns auf die Klammer- und Rechenstruktur solcher Rechenausdrücke konzentrieren. Die Zahlen soll nur eine untergeordnete Rolle spielen. Wir ersetzen daher jede Zahl durch das Symbol z. Zusätzlich betrachten wir der Einfachheit halber nur Rechenausdrücke mit den Rechenzeichen + und *. Entscheidend für die so vereinfachten Rechenausdrücke ist die korrekte Klammerung: Zu jeder öffnenden Klammer muss es - an passender Stelle - eine schließende Klammer geben.

Die folgende Auflistung zeigt anhand einiger Rechenausdrücke, wie die Klammer- und Rechenstruktur im Folgenden dargestellt werden soll.

12+5              z+z
4*(12+5)          z*(z+z)
3+5*(7+4)         z+z*(z+z)
((2+6)+5)*(7+4)   ((z+z)+z)*(z+z)
...

Die Sprache L_RA der vereinfachten Rechenausdrücke soll genau solche Klammer- und Rechenstrukturen beschreiben. Sie basiert auf dem Alphabet Σ = {z, +, *, (, )}. Präzise beschreiben kann man sie mit der folgenden Grammatik (beachte, dass A hier das Startsymbol ist):

A -> A + S
A -> S
S -> S * F
S -> F
F -> ( A )
F -> z 

Aufgabe 1

Zeige mit Hilfe einer Ableitung, dass das Wort z*(z+z) (einfach) bzw. das Wort z+z*(z+z) (schwieriger) mit Hilfe der Grammatik erzeugt werden kann.

Programmiersprachen

Als Beispiel für eine sehr einfache Programmiersprache betrachten wir die Sprache, mit der man den Roboter Karol steuern kann.

Auch hier kommen Klammerstrukturen vor. Bei einer Solange-Anweisung werden Beginn und Ende mit den Schlüsselwörtern SOLANGE und *SOLANGE gekennzeichnet.

Wir wollen Programme wie das oben gezeigte vereinfacht darstellen. Mit dem Symbol e soll eine elementare Anweisung beschrieben werden, mit dem Symbol b eine Bedingung. Mit den Symbolen s und * sollen Beginn und Ende einer SOLANGE-Anweisung gekennzeichnet werden. Das oben gezeigte Programm würde dann folgendermaßen abstrahierend bechrieben:

e
e
s b
 s b
  e
 *
 e
*

bzw. in kompakter Form

eesbsbe*e*

Aufgabe 2

Entwickle eine Grammatik für die Sprache L_RP der vereinfachten Roboterprogramme. Du kannst sie auch selbstständig um Symbole zur Kennzeichnung von Fallunterscheidungen erweitern.

XML

XML benutzt sogenannte Tags zur Auszeichnung von Informationsbausteinen. Anfangs- und Endtags bilden dabei jeweils Klammerpaare (siehe XML).

<?xml version="1.0" encoding="iso-8859-1"?>
<buch>
  <autor>
    <name>Borik</name>
    <vorname>Otto</vorname>
    <hrsg></hrsg>
  </autor>
  <titel>
    Meyers Schachlexikon
  </titel>
  <verlag>
    Meyers Lexikonverlag
  </verlag>
  <erscheinungsort>
    Mannheim
  </erscheinungsort>
  <erscheinungsjahr>
    1993
  </erscheinungsjahr>
  <isbn>
    3-411-08811-7
  </isbn>
</buch>

XML erlaubt es dem Benutzer, solche Klammerpaare selbst festzulegen und somit flexibel komplexe Klammerstrukturen zu entwickeln.

Die Sprache L_MyXML soll vereinfachte XML-artige Ausdrücke beschreiben. Jedes zu dieser Sprache gehörende Wort soll aus einem Anfangstag, einem Text und einem Endtag bestehen. Anfangs- und Endtag sollen im Wesentlichen identisch sein. Die Tag-Bezeichner sind beliebige nicht-leere Zeichenketten, die nur aus den Buchstaben a und b bestehen. Der Text zwischen den Anfangs- und End-Tag soll nur aus den Buchstaben a, b und c bestehen. Zur Sprache L_MyXML gehört beispielsweise das Wort <ab>acaa</ab>.

Die Sprache L_MyXML kann mit folgender Grammatik beschrieben werden:

S -> <aAT>
S -> <bBT>
T -> aAT
T -> bBT
T -> M
Aa -> aA
Ab -> bA
AM -> Ma
Ba -> aB
Bb -> bB
BM -> Mb
M -> >N
N -> aN
N -> bN
N -> cN
N -> </

Aufgabe 3

(a) Erstelle eine Ableitung des Worts <ab>acaa</ab>.

(b) Vergleiche die gezeigte Grammatik mit den Grammatiken in Aufgabe 1 und 2. Inwiefern ist die hier vorliegende Grammatik komplexer?