HSG

Aktuelle Seite: HSG/Fächer/Informatik/Material

Sprachen mit Klammerstrukturen nach Informatik heute, Band 2, S. 100

Es sollen Grammatiken für Sprachen mit ineinandergeschachtelten Klammern entwickelt werden. Als terminale Zeichen seien nur
T = { ( , p , ) } zugelassen. Das Symbol p soll grundsätzlich zwischen zwei Klammern stehen, leere Klammern dürfen nicht vorkommen. Wohlgeformte Worte der Sprache sind z.B. ((p)(p)) oder (((p)(p)(p))(p)).

Aufgabe 1

Zunächst soll mit einem Syntaxdiagramm und einer Backus-Naur-Grammatik im Gold-Parser ein Regelsystem für eine Sprache angegeben werden, die lediglich eine Aneinanderreihung des Terms (p) erlaubt.

Lösung


ih2s100a.grm

Aufgabe 2

Das Regelsystem aus Aufgabe 1 ist so zu erweitern, dass auch ineinandergeschachtelte Klammern vorkommen können.

Lösung


ih2s100b.grm

Tests

Welcher der Worte gehören zur Sprache aus Aufgabe 2?

a) (((p)(p)(p))p)    b) (p)((p)(p))   c) (((p)(p))((p)(p)))(p))

Während die Äquivalenz der Regelsysteme (beide erzeugen die gleiche Sprache) im Fall 1 augenscheinlich scheint, so könnte man im Fall 2 durchaus Zweifel anmelden.
Wenn auch Tests einen Beweis nicht ersetzen können, so können sie doch Fehler aufdecken. Ein gewisses Problem ist dabei die Erzeugung bzw. Auswahl der Testdaten. Häufig wählt man - ohne böse Absicht - gerade die Testdaten, die Fehler unentdeckt lassen. Ein Zufallsverfahren könnte hier mehr Objektivität hereinbringen. Im Folgenden sei eine rekursive Pascal-Funktion RTerm vorgestellt, die gemäß dem Syntax-Diagramm (auch das ist natürlich in Zweifel zu ziehen) zufällig Worte der Sprache erzeugt, die wiederum im Gold-Parser getestet werden können.

  function RTerm : string;
  var
    s : string;
  begin
    s := '(';
    if random
  syntaxdiagramm.zip

Wie man sieht, werden teilweise Wortungetüme erzeugt, die man bequem mit "Copy 'n Paste" im GoldParser testen kann. Ein Beispiel sei hier angeführt: