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.
module L where
import Parser
a = token 'a'
b = token 'b'
l0 = a>-l0>-b |+ epsilon
l1 = epsilon --TODO
l2 = epsilon --TODO
l3 = epsilon --TODO
Subato
