Benutzer:陰陽 阴阳/Ableitung (Informatik)

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoVorlage:SSen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor 陰陽 阴阳 auf.

QS

1. So wie der Artikel präsentiert wird, ist er ein schlechter Artikel und hat eher etwas von einem Auszug aus einem Lehrbuch an sich.

Die Wikipedia ist eine allgemeine E

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoVorlage:SSen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor 陰陽 阴阳 auf.

nzyklopädie und kein Fachbuch und sollte auch für Laien verständlich sein. Auszug aus Wikipedia:Wie schreibe ich gute Artikel

2. „Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik voraus“ ist kein guter Ansatz, zum Mindesten sollte die Einleitung jedem Leser ermöglichen zu verstehen, um was es geht, wofür es ist, wer oder was es bracht und für wen oder was es von Bedeutung ist.

3. Die Relevanz ist aus dem Artikel nicht klar erkennbar; wenn das Thema eine Relevanz hat, sollte diese auch klar für jeden erkennbar und nachvollziehbar sein.

4. Die Ratschläge für „Wie schreibe ich gute Artikel“ sollten starker beachtet werden.

5. Keine Quellen, keine Literatur.

6. Gibt es praktische Beispiele, die für jeden nachvollziehbar sind, woran man den Sinn, die Verwendung erkennen kann? Kein mathematisches Beispiel.

7. Hinweis von Herr Klaeren: „Ziemlich schräg und unfertig. Ableitungen und Reduktionen sollten nicht ohne Not vermischt werden. Das Bsp. zur Ableitung verwendet in Wirklichkeit Reduktionen.“

--Strelok 15:55, 15. Nov. 2009 (CET)

Ein bisschen korrigiert und ausgebaut. Man darf m.E. nicht schlechterdings CFGs voraussetzen, den ganze Ableitungsmechanismus gibt's für recht viel allgemeinere generative Sprachklassen genauso, deshalb hab ich's zunächst mal wenigstens aufs Niveau gehoben, wo die gesamte Chomsky-Hierarchie mit dabei ist. Dann kann man leider nicht mehr von dem letzten Vorkommnis einer linken Seite einer Produktion reden, denn was wäre das? Der Teilstring, der am weitesten rechts anfängt — oder aufhört? Entsprechend führt Salomaa den Begriff der Rechtsableitung nur für CFGs ein. Die daraus rührenden Kautelen machen alles natürlich etwas schwieriger zu formulieren.

Vielleicht sollte man auch, weil der Begriff der Ableitung bei den Semi-Thue-Systemen schon ganz entsprechend existiert, ihn dafür auch mit abhandeln; dann für Chomsky-Grammatiken; dann für CFGs. Dann bekäme man allerdings von der Sprachklasse abhängige Definitionen, mit der schwierigsten für CG0, so oder so, in der Mitten, ich bezweifle, das das den unbewanderten Lesern unbedingt helfen würde. Vor allem auch die zwei Alphabete bei CGs gegen das eine bei STSs dürften höchst verwirren.

Oder sollte man die Definitionen in die entsprechenden Sprachklassen verschieben und dort dann so etwas wie verallgemeinert eine entsprechende Definition für die umfassende Grammatikklasse der ... hinzufügen?

-- Silvicola Diskussion Silvicola 21:30, 24. Nov. 2009 (CET)

@ Silvicola. Sind Sie der Ansicht das die Einleitung und Ihre Ausführungen einem Laien oder Lesern mit Grundkenntnissen ein Einblick verschafft um was es geht?--Strelok 23:03, 24. Nov. 2009 (CET)

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+) Begründung: Ziemlich schräg und unfertig. Ableitungen und Reduktionen sollten nicht ohne Not vermischt werden. Das Bsp. zur Ableitung verwendet in Wirklichkeit Reduktionen. --Herbert Klaeren 16:17, 14. Nov. 2009 (CET)

Eine Ableitung ist in der Theoretischen Informatik eine Folge von Ableitungsschritten, die nach den Produktionsregeln einer formalen Grammatik ein Wort der von ihre beschriebenen formalen Sprache erzeugt. Zur übersichtlichen Darstellung dieser Schritte verwendet man häufig Syntaxbäume.

Ableitungssysteme sind Semi-Thue-Systeme, meistens werden sie spezieller durch eine Grammatik vom Chomsky-Typ bestimmt. Im Folgenden beschränken wir uns auf diesen Fall und gehen davon aus, dass eine formale Sprache vorliegt, die durch eine Chomsky-Grammatik $G=\left(N,\Sigma ,P,S\right)$ beschrieben ist.

Darin ist $\Sigma$ das endliche Alphabet der beschriebenen Sprache; $N$ ist die endliche Menge der Nichtterminalsymbole, die, ohne selbst Zeichen der beschriebenen Sprache zu sein, ihre Struktur bestimmen; $P$ ist die endliche Menge der Produktionen, sie legen die erlaubten Termersetzungen fest; $S\in N$ ist das Startsymbol, Ausgangspunkt des Ersetzungsmechanismus, der bei geeigneter Steuerung jedes einzelne Wort der Sprache hervorbringen kann.

Definitionen

Sei $G=\left(N,\Sigma ,P,S\right)$ eine Chomsky-Grammatik.

Satzform

Eine Satzform x aus G ist eine Folge von Symbolen aus $N$ oder $\Sigma$ : $x\in \left(N\cup \Sigma \right)^{*}$.

Ableitungsschritt unter Verwendung einer bestimmten Produktion

Einen Ableitungsschritt unter Verwendung von p, der x nach y überführt, wobei $p=\alpha \rightarrow \beta$ sei, schreibt man als $x\Rightarrow _{p}y$. Seien $x,y$ zwei Satzformen:

$x\Rightarrow _{p}y\,\,\Leftrightarrow _{Def}\,\,\exists _{u,v\in \left(N\cup \Sigma \right)^{*}}\,\,x=u\alpha v\land y=u\beta v$

Dass ein Ableitungsschritt unter Verwendung der Produktion $p=\alpha \rightarrow \beta$ die Satzform x in die Satzform y überführt, heißt also gerade, dass man in x $\alpha$ so finden kann, dass nach der Ersetzung dort durch $\beta$ gerade y entsteht.

Ableitungsschritt

Einen Ableitungsschritt von x nach y schreibt man als $x\Rightarrow _{G}y$ ; oder auch nur als $x\Rightarrow y$, wenn das gemeinte G offenkundig ist. Seien $x,y$ zwei Satzformen:

$x\Rightarrow _{G}y$ (bzw. $x\Rightarrow y$) $\,\,\Leftrightarrow _{Def}\,\,\exists _{p\in P}\,\,x\Rightarrow _{p}y$

Dass ein Ableitungsschritt die Satzform x in die Satzform y überführt, heißt also gerade, dass man in x einen Teil finden kann, der gleich der linken Seite irgendeiner der Produktionen ist und dass nach dessen dortiger Ersetzung mit dem rechten Teil derselben Produktion dann y entsteht.

Ableitungsstück

4. Einen Ableitungsstück ist eine endliche Folge $\left(w_{0},...,w_{n}\right)$ von Satzformen, worin jede folgende stets aus der unmittelbaren Vorgängerin durch einen Ableitungsschritt hervorgeht. Geschrieben kurz

$w_{0}\Rightarrow _{G}w_{1}\Rightarrow _{G}\cdots \Rightarrow _{G}w_{n}$

Ableitung

5. Eine Ableitung ist ein Ableitungsstück $w_{0}\Rightarrow _{G}w_{1}\Rightarrow _{G}\cdots \Rightarrow _{G}w_{n}$, das vom Startsymbol $S$ zu einer Satzform führt, die kein Nichtterminalsymbol mehr enthält: $w_{0}=S$, $w_{n}\in \Sigma ^{*}$

Erzeugte Sprache

6. Die von G erzeugte Sprache $L(G)$ ist die Menge aller Worte über dem Zeichenalphabet $\Sigma$, die am Ende einer Ableitung stehen; man sagt auch, die ableitbar sind.

$L(G):=\{w\in \Sigma ^{*}|S\Rightarrow _{G}\cdots \Rightarrow _{G}w\}$

Im allgemeinen sind auf eine Satzform mehrere verschiedene Produktionen anwendbar, und ein und dieselbe Produktion kann auch an verschiedenen Stellen anwendbar sein.

Rechtsableitung

Eine Ableitung heißt Rechtsableitung (englisch rightmost derivation), wenn in jedem ihrer Einzelschritte immer das am weitestens rechts stehende Nichtterminalsymbol der Satzform gemäß einer Produktion ersetzt wird.

Beachte: Von Rechtsableitung spricht man nur, wenn eine kontextfreie Grammatik (Chomsky-Grammatik vom Typ 2) vorliegt; solche Grammatiken sind auch der in der Praxis der Informatik am häufigsten auftretende Sprachtyp. In diesem Fall hat jede Produktion die einfache Gestalt $A\rightarrow \alpha$, alle linken Seiten sind also einzelne Nichtterminalsymbole, die rechten bleiben beliebig. Der einzelne Ableitungsschritt ersetzt deshalb ein Vorkommnis eines Nichtterminalsymbols $A$ in der Ausgangs-Satzform durch eine der möglichen rechten Seiten $\alpha$ mit $A\rightarrow \alpha \in P$.

Im Falle von Rechtsableitungen genügt die Angabe allein der Folge angewandter Produktionen, um den Gesamt-Ersetzungsvorgang (welche Ersetzungen an welchen Stellen?)und sein Ergebnis eindeutig zu beschreiben, was für beliebige Ableitungen nicht so ist, weil eine auftretende Satzform etwa Nichtterminalsymbole mehrfach enthalten kann.

Im Bereich des Compilerbaus sind Rechtsableitungen bedeutsam, weil für eine dort wichtige Sprachklasse, die LR(k)-Sprachen, eine effiziente Methode der Syntaxanalyse bekannt ist, der wesentlich dieser Begriff zugrunde liegt.

Linksableitung

Analog zur Rechtsableitung spricht man von einer Linksableitung (englisch leftmost derivation), wenn immer das am weitesten links stehende Nichtterminalsymbol ersetzt wird.

Linksableitungen spielen eine gewisse Rolle bei der Syntaxanalyse von LL(k)-Grammatiken, aber nicht in dem Maße wie die Rechtsableitungen bei den wegen ihrer größeren Erzeugungsmächtigkeit wichtigeren Klasse der LR(k)-Grammatiken. Diese scheinbare Asymmetrie folgt aus der Konvention, Eingabezeichenketten von links nach rechts zu lesen und zu verarbeiten.

Beispiele

Sprache der Strichzahlen

Die Sprache der Strichzahlen wird etwa erzeugt von

$G_{1}=\left(\{Z\},\{i\},\{Z\rightarrow i,Z\rightarrow iZ\},Z\right)$.

Die Ableitung, die zur 5-Strichzahl führt, ist etwa:

$Z\Longrightarrow _{Z\rightarrow iZ}iZ\Longrightarrow _{Z\rightarrow iiZ}iZ\Longrightarrow _{Z\rightarrow iiiZ}iZ\Longrightarrow _{Z\rightarrow iZ}iiiiZ\Longrightarrow _{Z\rightarrow i}iiiii$

Im Falle dieser Grammatik enthält jede Satzform keinmal oder genau einmal die Z, die in diesem Falle auch stets am Ende der Satzform steht. Es sind also alle Ableitungen Rechtsableitungen. Jedes Strichzahl hat mit dieser Grammatik genau eine mögliche Ableitung.

Dieselbe Sprache wird ebenfalls erzeugt von der Grammatik

$G_{2}=\left(\{Z\},\{i\},\{Z\rightarrow i,Z\rightarrow ZZ\},Z\right)$.

Das folgende ist damit eine Ableitung für die 3-Strichzahl:

$Z\Longrightarrow _{Z\rightarrow ZZ}ZZ\Longrightarrow _{Z\rightarrow ZZ}ZZZ\Longrightarrow _{Z\rightarrow i}ZZi\Longrightarrow _{Z\rightarrow i}Zii\Longrightarrow _{Z\rightarrow i}iii$.

Man beachte, im zweiten Schritt bleibt hierbei unklar, ob das rechte oder das linke $Z$ in $ZZ$ durch ein weiteres $ZZ$ ersetzt wird; beidesmal entsteht zunächst $ZZZ$. Mit der Angabe, dass es sich um eine Rechtsableitung handle, wird die Ersetzungsstelle eindeutig. Dieselbe Eindeutigkeit wird erreicht, wenn man immer die genaue Stelle der Ersetzung, den sogenannten Henkel (englisch handle) mit angibt.

Reduktion

Umgekehrt kann ein Wort (der Eingabetext) auch anhand der Grammatik zerlegt werden, um diejenige Ableitung zu erhalten, die dieses Wort produziert. Diesen Vorgang nennt man auch parsen. Die umgekehrt durchlaufene Folge der Ableitungsschritte nennt man auch die Reduktion des Wortes.

Quellen

• A. Aho, R. Sethi, J.D. Ullman: Compilers - Principles, Techniques and Tools. S. 196-197. Addison-Wesley, 1986
• S. Sippu, E. Soisalon-Soininen: Parsing Theory. Springer Verlag, 1988
• Arto K. Salomaa: Formale Sprachen, Springer Verlag, 1978, ISBN 3-540-09030-4

Siehe auch

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