imported>Aka: /* Weblinks */ https

2021-07-30T21:12:01Z

Weblinks: https

Neue Seite

Eine '''Rechtsableitung''' (auch '''rechtskanonische Ableitung''', {{enS|''rightmost derivation''}}) ist in der [[Theoretische Informatik|Theoretischen Informatik]] eine Folge von [[Ableitung (Informatik)|Ableitung]]sschritten, 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-Parser|LR(k)-Sprachen]]) einfach zu berechnen ist.

Um [[formale Sprache]]n, wie zum Beispiel Programmiersprachen, zu erzeugen, werden [[formale Grammatik]]en aufgestellt, mit denen ihren Produktionsregeln entsprechend [[Wort (Theoretische Informatik)|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 [[Kontextfreie Grammatik|kontextfreien Grammatiken]]) an jeder Stelle eines Wortes [[Ableitung (Informatik)|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 [[Formale Sprache|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 mehrdeutige Sprache|Inhärent mehrdeutigen Sprache]]. Mit einer eindeutigen Grammatik kann der zu der Ableitung passende [[Syntaxbaum]] mit einem [[LR-Parser]] erzeugt werden.

== Siehe auch ==
* [[Rechtsreduktion]]
* [[Inhärent mehrdeutige Sprache]]
* [[Syntaxbaum]]
* [[LR-Parser]]

== Quellen ==
* [[Alfred V. Aho]], Ravi Sethi, [[Jeffrey Ullman|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 ==
* [https://books.google.at/books?id=N4V2q941AD8C&pg=PA92&hl=de Informatik Handbuch - 3.1.3 Kanonische Ableitungen und Mehrdeutigkeit]

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Compilerbau]]

Rechtsableitung - Versionsgeschichte

imported>Aka: /* Weblinks */ https