Rechtsableitung - LinkFang.de





Rechtsableitung


Eine Rechtsableitung (auch rechtskanonische Ableitung, englisch 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 Nichtterminale könnten (in kontextfreien Grammatiken) an jeder Stelle eines Wortes ersetzt werden. Im Fall der Rechtsableitung legt man sich darauf fest, immer das am weitesten rechts stehende Nichtterminal zu ersetzen. Wenn immer das am weitesten links stehende ersetzt wird, spricht man entsprechend von Linksableitung.

Beispiel

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

[math]\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}[/math]

Es gibt zwei Rechtsableitungen für das Wort [math]a+b*c[/math], was zeigt, dass die Grammatik mehrdeutig ist. Darum sollte sie zur Beschreibung der formalen Sprache nicht verwendet werden.

Rechtsableitung 1:

[math]\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}[/math]

Rechtsableitung 2:

[math]\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}[/math]

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.

Siehe auch

Quellen

Weblinks


Kategorien: Compilerbau | Theorie formaler Sprachen

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Rechtsableitung (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.