Aktuell bin ich bei meiner Zwölften beim Thema „Formale Sprachen“. Bislang haben wir über Grammatiken gesprochen und werden kommende Stunde dann die EBNF einführen, um uns so die Darstellung der Produktionen zu erleichtern.

Um ein Bedürfnis nach erleichterter Schreibweise ein wenig zu motivieren, haben wir bislang die Produktionen in der Form

  1. <Variable1> -> <Variable2>a
  2. <Variable1> -> <Variable2>b
  3. <Variable2> -> a

aufgeschrieben und dann zusehends schwierigere Aufgaben formuliert. Angefangen hatten wir noch mit den Bezeichnungen der S- und U-Bahnen in München:

  1. <Start> -> S<Ziffer>
  2. <Start> -> U<Ziffer>
  3. <Ziffer> -> 1
  4. <Ziffer> -> 2
  5. <Ziffer> -> 3
  6. <Ziffer> -> 4
  7. <Ziffer> -> 5
  8. <Ziffer> -> 6
  9. <Ziffer> -> 7
  10. <Ziffer> -> 8
  11. <Ziffer> -> 9

Aber schon bei den KFZ-Kennzeichen wird es schwierig. Vor allem, weil dann doch viele unterschiedliche Lösungen von Produktionen vorhanden waren und nicht jedem immer klar war, warum seine Lösung denn nun richtig ist oder nicht.

Aufgabe

Schön wäre es daher gewesen, wenn es eine Möglichkeit gäbe, sozusagen alle erzeugbaren Wörter einer Grammatik ausgeben zu lassen.

Ein großes Problem sind allerdings die rekursiven Definitionen bei den Regeln. So werden Palindrome beispielweise wie folgt erzeugt:

  1. <Palindrom> -> ε|<Zahl>|0<Palindrom>0|1<Palindrom>1|2<Palindrom>2…|9<Palindrom>9
  2. <Zahl> -> 0|1|2|3|4|5|6|7|8|9

Die Rekursion in der Regel führt dabei zwangsläufig irgendwann zum Absturz StackOverflow des Programms.

Um dies zu verhindern, beschränke ich die Anzahl der Rekursionen händisch.

Bei den die Produktionen für KFZ-Kennzeichen mache ich es ähnlich:

  1. Landkreis -> Grossbuchstabe | Grossbuchstabe Grossbuchstabe | Grossbuchstabe Grossbuchstabe Grossbuchstabe

Und das Problem der ODER-Verknüpfung löse ich so, dass ich per Zufall eine der Möglichkeiten auswähle: JavaScript.

Welche bessere Möglichkeit gäbe es, um möglichst alle bzw. viele Wörter einer Grammatik zu erzeugen? Ich denke da vor allem noch an Bäume. Wobei ich beim Durchlauf-Algorithmus noch schwanke. Denn einfach alle Blätter ausgeben wäre nicht sinnvoll.