G = (N, T, P, S)
|
Zur Charakterisierung von Sprachen wird auf Grammatiken zurückgegriffen.
Phrasenstrukturgrammatiken sind eine elegante Möglichkeit durch eine endlich lange Beschreibung eine oft unendlich große Menge zu beschreiben.
Dabei werden nicht nur die zulässigen Wörter, sondern auch deren interne Struktur charakterisiert.
Eine Grammatik G = (N, T, P, S) besteht aus vier Komponenten:
- einem Terminalalphabet T, bestehend aus denjenigen Zeichen, aus denen ein Satz der Sprache bestehen kann,
- einem Nichtterminalalphabet N, Hilfssymbole, die zur korrekten Beschreibung der Struktur nötig sind; in den eigentlichen Sprachäußerungen sind sie nicht sichtbar,
- dem Startsymbol S - auch Startaxiom genannt - ein besonderes Nichtterminal, von dem der Wortbildungsprozess ausgeht
- und den Regeln oder Produktionen P; das sind Paare der Form x->y oder (x,y), wobei x durch y ersetzt werden kann.
Die generative Kraft von Grammatiken liegt in den Regeln: eine Regel w1→w2 besagt, dass die Zeichenkette w1
durch die Zeichenkette der rechten Regelseite - w2 - ersetzt werden kann.
|
1
2
3
4
5
Ableitung und Parse