Eine Produktionsregel ist ein grundlegendes Regelwerk einer formalen Grammatik und dient der Erzeugung einer formalen Sprache. Für den Begriff der Produktionsregel existieren weitere Bezeichnungen: Produktion, Regel oder auch Ersetzungsregel. Mit Produktionssystem benennt man eine definierte Menge von Produktionsregeln. Produktionsregeln werden u.a. in der Computerlinguistik oder im Compilerbau zur Beschreibung einer formalen Sprache verwendet.
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.
T = {=, :=, begin, end, while, repeat, if ....}
Nonterminals kennzeichnen dagegen eine syntaktische Kategorie; sie sind im wesentlichen Hilfssymbole, die für die Erzeugung und Erkennung der Sätze der formalen Sprache durch die Grammatik dienen. Zur Unterscheidung werden Nonterminals in