Termersetzung
Bei der Termersetzung werden die Produktionsregeln einer Grammatik, ausgehend vom Startsymbol, schrittweise angewendet. Auf diese Weise wird ein Wort erzeugt, welches Teil der Sprache ist, die durch die jeweilige Grammatik beschrieben wird. Bei der Anwendung einer Produktionsregel sprechen wir auch vom Ableiten eines Wortes.
Ein Beispiel
Die folgende Grammatik \(G\) beschreibt die Sprache, in der auf ein \(\text{x}\) eine beliebige Zeichenkette von \(\text{x}\) und \(\text{y}\) folgt:
Gegeben ist \(G = (\text{V}, \sum, \text{P}, \text{S})\)
- \(\text{V} = \{\text{S}, \text{A}, \text{X}, \text{Y}\}\)
- \( \sum = \{\text{x}, \text{y}\} \)
- \( \text{P} = \{\text{S} \rightarrow \text{XA},\hspace{0.2cm} \text{A} \rightarrow \text{XA} | \text{YA} | \epsilon,\hspace{0.2cm} \text{X} \rightarrow \text{x},\hspace{0.2cm}\text{Y} \rightarrow \text{y}\} \)
Wie mit Hilfe dieser Grammatik ein Wort gebildet wird, lässt sich im folgenden nachvollziehen, indem wir schrittweise das Wort \(\text{xyxx}\) erzeugen. Damit möchten wir demonstrieren, wie die Grammatik zur Beschreibung einer Sprache funktioniert:
| Vorgehensweise | Ergebnis |
|---|---|
Begonnen wird stets mit dem Startsymbol \(\text{S}\). | \(\text{S}\) |
Das Startsymbol wird mit der hier einzig anwendbaren Regel abgeleitet: \(\text{S} \rightarrow \text{XA}\). | \(\text{XA}\) |
Da nach dem \(\text{x}\) ein \(\text{y}\) folgen soll, wird auf das \(\text{A}\) die Regel \(\text{A} \rightarrow \text{YA}\) angewendet | \(\text{XYA}\) |
Das Wort soll auf \(\text{xx}\) enden, weswegen zweimal in Folge auf das \(\text{A}\) die Regel \(\text{A} \rightarrow \text{XA}\) angewendet wird | \(\text{XYXXA}\) |
Weitere Ersetzungen von \(\text{A}\) sind nicht mehr notwendig, | \(\text{XYXX}\) |
Zum Schluss werden alle Variablen durch die entsprechenden Terminalsymbole (\(\text{X} \rightarrow \text{x}\), \(\text{Y} \rightarrow \text{y}\)) ersetzt | \(\text{xyxx}\) |
Die schrittweise Anwendung der Produktionsregeln kann auch in einem Ableitungsbaum visualisiert werden: