Grammatik für Sprache2'
Regeln im Format W -> W1 | W2 | ... | Wk stehen für eine Reihe von alternativen Regeln für W:
W -> W1, W -> W2 , .... ,W -> Wk.
Das Symbol 'e' steht für eine leere Wortkette. Es wird benötigt, um überflüssige Nichtterminale aus dem Input zu löschen.
|
Nun sind alle Zutaten bekannt, die für Grammatiken nötig sind.
- Terminalalphabet: Das Vokabular, die Symbole der Sprache
- Nichtterminalalphabet: Ein Alphabet für die zusätzlichen versteckten Symbole
- Regeln der Form Wortkette1 -> Wortkette2, durch die die Struktur der Wörter und der Umfang der Sprache beschrieben wird.
Prinzipiell gilt, das nur Nichtterminalsymbole ersetzt werden können.
Einmal produziert verbleiben die Terminalsymbole in der Wortkette.
Ein Symbol aus dem Nichtterminalalphabet wird besonders hervorgehoben.
Es ist das erste, hierarchisch gesehen oberste Symbol, von dem jeder Satz ausgeht.
Meist verwendet man "S" als Kurzform für Satz (bzw. Sentence).
Mit allgemeinen Grammatiken sind alle Sprachen beschreibbar.
Eine Einteilung in unterschiedliche Sprachklassen ist möglich durch Beschränkungen des Regelformats.
So darf in einigen Grammatiktypen nicht mehr jede beliebige Zeichenkette durch eine beliebige andere ersetzt werden.
Diese Einschränkungen sind z.B.
- Symbole dürfen nur in bestimmten Kontexten - neben vorgegebenen Nachbarsymbolen - durch andere ersetzt werden.
- Es darf genau ein Nichtterminal unabhängig vom Kontext ersetzt werden.
- Es darf genau ein Nichtterminal durch ein Terminal und ein Nichtterminal ersetzt werden.
|
1
2
3
Übersicht: Sprachklassen
