Eine rechtslineare Grammatik ist eine spezielle formale Grammatik. Mittels rechtslinearer Grammatiken lassen sich beliebige reguläre Sprachen erzeugen. Ihre Besonderheit besteht in der Einschränkung ihrer Regelmenge: Die Regeln einer rechtslinearen Grammatik G = {N, Σ, P, S} (zur Erläuterung siehe formale Grammatik) dürfen nur die Form

A -> wB oder C -> $\backslash epsilon$

aufweisen, wobei A und B Nichtterminalsymbole aus N und w ein Wort aus Σ ist. Dies bedeutet anschaulich, dass ein Wort durch die Anwendung einer Regel nur auf der rechten Seite wachsen kann, indem dort genau ein Nichtterminalsymbol aus N angefügt wird.

Eine wichtige Eigenschaft rechtslinearer Grammatiken besteht darin, dass sie genau die Sprachen erzeugen, die von endlichen Automaten erkannt werden können. Rechtslineare Grammatiken, endliche Automaten und reguläre Sprachen sind somit lediglich verschiedene Darstellungen desselben Mechanismus.

Linkslineare Grammatik

---

Die Definition von linkslinearen Grammatiken erfolgt analog und definiert dieselbe Sprachklasse, da die regulären Sprachen unter Spiegelung abgeschlossen sind. Der Unterschied in der Beschränkung der Regeln besteht darin, dass neue Nichtterminalsymbole nur links angefügt werden dürfen, d.h. die Regeln haben statt A -> wB die Form A -> Bw.

Compilerbau