Rechtsableitung

Eine Rechtsableitung (auch rechtskanonische Ableitung, engl: rightmost derivation) ist in der Theoretischen Informatik eine Folge von Ableitungsschritten, bei der stets das am weitesten rechts stehende sogenannte Nichtterminalsymbol durch Anwendung einer Produktionsregel ersetzt wird. Sie ist für den Compilerbau wichtig, weil mit ihr der Syntaxbaum für eine bestimmte Klasse von Programmiersprachen (LR(k) Sprachen) einfach zu berechnen ist.

Um formale Sprachen, wie zum Beispiel Programmiersprachen, zu erzeugen, werden formale Grammatiken aufgestellt, mit denen ihren Produktionsregeln entsprechend Wörter abgeleitet und erzeugt werden können. Die Rechtsableitung ist eine Folge von Schritten, die von einem Startsymbol ausgehend ein Wort der formalen Sprache erzeugt. In den formalen Grammatiken werden die sogenannten Nichtterminalsymbole abgeleiteter Wörter verwendet, um die innere Struktur der Sprache zu beschreiben. Diese Nichtterminalen könnten (in kontextfreien Grammatiken) an jeder Stelle eines Wortes ersetzt werden. Im Fall der Rechtsableitung legt man sich darauf fest, immer den rechtesten Nichtterminalen zu ersetzen. Wenn immer der linkeste ersetzt wird, spricht man entsprechend von Linksableitung.

Beispiel

Es sei G = (N,T,P,S) eine Grammatik mit den Nichtterminalsymbolen N = {E}, den Terminalsymbolen T = {a,b,c, + , * ,(,)}, dem Startsymbol S = E und den folgenden Produktionsregeln P:

$\begin{align}\\ (1) E &\rightarrow E+E \\ (2) E &\rightarrow E*E \\ (3) E &\rightarrow (E) \\ (4) E &\rightarrow \mathrm a \\ (5) E &\rightarrow \mathrm b \\ (6) E &\rightarrow \mathrm c \\ \end{align}$

Es gibt zwei Rechtsableitungen für das Wort a + b * c, was zeigt, dass die Grammatik mehrdeutig und dementsprechend ungeeignet zur Beschreibung einer formalen Sprache ist.

Rechtsableitung 1:

$\begin{align}\\ E & =(1)\rightarrow E+E\\ & =(2)\rightarrow E+E*E\\ & =(6)\rightarrow E+E*c\\ & =(5)\rightarrow E+b*c\\ & =(4)\rightarrow a+b*c\\ \end{align}$

Rechtsableitung 2:

$\begin{align}\\ E & =(2)\rightarrow E*E\\ & =(6)\rightarrow E*c\\ & =(1)\rightarrow E+E*c\\ & =(5)\rightarrow E+b*c\\ & =(4)\rightarrow a+b*c\\ \end{align}$

Wenn es für eine Sprache keine Grammatik gibt, die nur eine Rechtsableitung für jedes Wort der beschriebenen Sprache besitzt, spricht man von einer Inhärent mehrdeutigen Sprache. Mit einer eindeutigen Grammatik kann der zu der Ableitung passende Syntaxbaum mit einem LR-Parser erzeugt werden.

Quellen

• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers. Principles, Techniques and Tools. Addison-Wesley, Reading MA u. a. 1986, ISBN 0-201-10088-6, S. 196-197.
• Seppo Sippu, Eljas Soisalon-Soininen: Parsing Theory. 1: Languages and Parsing. Springer Verlag, Berlin u. a. 1988, ISBN 3-540-13720-3, (EATCS monographs on theoretical computer science 15).
• Peter Rechenberg, Gustav Pomberger (Hrsg.): Informatik Handbuch 4. aktualisierte und erweiterte Ausgabe. Springer Hanser, München u. a. 2006, ISBN 3-446-40185-7, S. 92.

Weblinks

• Informatik Bandbuch - 3.1.3 Kanonische Ableitungen und Mehrdeutigkeit

Siehe auch

• Rechtsreduktion
• Inhärent mehrdeutige Sprache
• Syntaxbaum
• LR-Parser