Produktionsregel: Unterschied zwischen den Versionen
| Zeile 1: | Zeile 1: | ||
| − | Eine | + | Eine Produktionsregel (auch Regel oder genannt) ist in der Theorie formaler Grammatiken eine Regel, die angibt, wie aus Wörtern durch eine Grammatik neue Wörter produziert werden. |
| Zeile 6: | Zeile 6: | ||
---- | ---- | ||
| − | Formal ist eine Produktionsregel p aus einer Grammatik | + | Formal ist eine Produktionsregel p aus einer Grammatik {N , T, P , S } mit Vokabular N, Alphabet T, Regelmenge P und Startsymbol S . |
| + | |||
| + | Eine Produktionsregel ist ein grundlegendes Regelwerk einer formalen Grammatik und dient der Erzeugung einer formalen Sprache. Eine Produktionsregel ist definiert als eine zweistellige Relation (u,v), die paarweise in der Notation u nach v angeschrieben wird. | ||
| + | Die Charakteristik dieser Relation gibt vor, dass die linke Seite aus einem Nonterminal besteht und | ||
| + | die rechte Seite entweder aus dem leeren Wort, als Ende einer Ableitungssequenz, oder einem Terminal gefolgt von einem Nonterminal besteht. | ||
| + | Terminals sind die Grundelemente der Sätze einer formalen Sprache, und können nicht weiter zerlegt werden. Dazu gehören neben den Elementen der jeweiligen Programmiersprache Buchstaben und Ziffern. Beispiele für die terminalen Elemente einer Programmiersprache sind: | ||
| + | |||
| − | |||
Version vom 27. November 2015, 13:21 Uhr
Eine Produktionsregel (auch Regel oder genannt) ist in der Theorie formaler Grammatiken eine Regel, die angibt, wie aus Wörtern durch eine Grammatik neue Wörter produziert werden.
Definition
Formal ist eine Produktionsregel p aus einer Grammatik {N , T, P , S } mit Vokabular N, Alphabet T, Regelmenge P und Startsymbol S .
Eine Produktionsregel ist ein grundlegendes Regelwerk einer formalen Grammatik und dient der Erzeugung einer formalen Sprache. Eine Produktionsregel ist definiert als eine zweistellige Relation (u,v), die paarweise in der Notation u nach v angeschrieben wird. Die Charakteristik dieser Relation gibt vor, dass die linke Seite aus einem Nonterminal besteht und die rechte Seite entweder aus dem leeren Wort, als Ende einer Ableitungssequenz, oder einem Terminal gefolgt von einem Nonterminal besteht. Terminals sind die Grundelemente der Sätze einer formalen Sprache, und können nicht weiter zerlegt werden. Dazu gehören neben den Elementen der jeweiligen Programmiersprache Buchstaben und Ziffern. Beispiele für die terminalen Elemente einer Programmiersprache sind:
Beispiele
Es sei innerhalb einer formalen Grammatik mit den Nichtterminalsymbolen N = \{ A, B \} und den Terminalsymbolen T = \{ a, b \} die Produktionsregel aBa \rightarrow bA definiert. Durch Anwendung dieser Regel kann bei der Erzeugung der durch die Grammatik beschriebenen Sprache zum Beispiel das Wort aBaBaBA zum Wort bABaBA abgeleitet werden, wobei hier das Präfix aBa durch die Konklusion bA ersetzt wird. Es wäre jedoch nach der Definition formaler Grammatiken auch möglich, das zweite Vorkommen des Wortes aBa zu ersetzen, so dass das Wort aBbABA entsteht.
Wäre außerdem die Regel aBa \rightarrow \varepsilon definiert, so könnte das zuvor betrachtete Wort aBaBaBA außerdem in die Wörter BaBA bzw. aBBA abgeleitet werden. (\varepsilon ist die in der Regel verwendete Notation für das leere Wort, ein Wort, das aus keinem einzigen Zeichen besteht.)
Informatik
Wie bereits beschrieben, stellen Produktionsregeln einen grundlegenden Bestandteil formaler Grammatiken dar und werden demnach dazu verwendet, um formale Sprachen zu beschreiben. So werden Produktionsregeln etwa im Rahmen des Compilerbaus dazu verwendet, um eine Programmiersprache zu beschreiben. Produktionsregeln werden hier häufig in der Backus-Naur-Form dargestellt.
Eine kognitive Anwendung haben Produktionsregeln in regelbasierten Systemen: Hier spricht man von Produktionsregeln, wenn die Konklusionen der Regeln, mit denen das System arbeitet, nur aus Konjunktionen von Literalen bestehen.
