Einfache Grammatiken

Mit der kleinen Bibliothe Parser, können Sie kontextfreie Grammatiken in Haskell definieren.

• Ein Terminal aus einem einzigen Zeichen ist mit der Funktion token definierbar.
• Die Sequenz der Zeichen auf der rechten Seite einer Produktion kann mit dem Operator >- gebildet werden.
• Zwei Regel für dasselbe Terminalsymbol können mit dem Operator |+ verknüpft werden.
• Die Konstante epsilon steht für das leere Wort.

Beispiel: Grammatik der Sprache:
\[L_0 = \{a^nb^n | n = 0, 1, \dots\}\] Wird durch folgende Grammatik erzeugt:
\[ l_0 \rightarrow a l_0 b\\ l_0 \rightarrow \epsilon \] Die Formulierung dieser Grammtik finden Sie in der Lösungseingabe definiert.

 

Definieren Sie in Haskell Grammatiken für die folgenden drei Sprachen:

• \[L_1 = \{a^nb^m | m ≤ n, n = 1, 2, \dots\}\]
• \[L_2 = \{a^nb^m | m ≥ n, n = 1, 2, \dots\}\]
• \[L_3 = \{a^nb^m | m ≥ n, n = 0, 1, \dots\}\]

Die Grammatiken sollen dabei frei von Linksrekursionen sein.