https://wiki-de.moshellshocker.dns64.de/api.php?action=feedcontributions&feedformat=atom&user=213.162.73.146Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]2026-06-27T23:29:34ZBenutzerbeiträgeMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Deterministisch_kontextfreie_Sprache&diff=413056Deterministisch kontextfreie Sprache2021-08-08T12:23:44Z<p>213.162.73.146: /* Eigenschaften */ Links hinzugefügt</p>
<hr />
<div>Eine '''deterministisch kontextfreie Sprache''' ist eine [[Formale Sprache|Sprache]], die von einem [[Deterministischer Kellerautomat|deterministischen Kellerautomaten]] akzeptiert wird. Manchmal wird auch der gekürzte Begriff '''deterministische Sprache''' verwendet. Die Definition geht auf [[Seymour Ginsburg]] und [[Sheila A. Greibach|Sheila Greibach]] zurück.<br />
<br />
In Bezug auf Grammatiken findet sich auch die Bezeichnung '''LR(''k'')-Sprache''': Jede [[LR(k)-Grammatik]] beschreibt eine deterministisch kontextfreie Sprache. Umgekehrt gibt es für jede deterministisch kontextfreie Sprache <math>L</math> ein <math>k</math>, so dass <math>L</math> eine LR(''k'')-Sprache ist (d.&nbsp;h. eine LR(''k'')-Grammatik hat). Tatsächlich reicht dafür in jedem Fall <math>k=1</math>, aber nicht <math>k=0</math>. Jedoch lässt sich auch jede deterministisch kontextfreie Sprache, die nicht LR(0) ist, durch Einführung einer eindeutigen Markierung für das Wortende in eine LR(0)-Sprache überführen.<br />
<br />
== Eigenschaften ==<br />
Deterministisch kontextfreie Sprachen haben die für die Praxis sehr nützliche Eigenschaft, dass für sie [[LR-Parser]] existieren, mit welchen in linearer Zeit beim Lesen von links nach rechts entschieden werden kann, ob die Eingabe ein Wort der Sprache ist. Viele in der Praxis verwendete [[Formale Sprache|formale Sprachen]], insbesondere Programmiersprachen, gehören zu dieser Sprachklasse. <br />
<br />
Weiterhin sind die deterministisch kontextfreien Sprachen [[Abgeschlossenheit (algebraische Struktur)|abgeschlossen]] unter:<br />
* Schnittbildung mit [[Reguläre Sprache|regulären Sprachen]]<br />
* [[Komplement (Mengenlehre)|Komplement]]<br />
* Anwendung inverser [[Homomorphismus|Homomorphismen]]<br />
<br />
Sie sind nicht abgeschlossen unter:<br />
* Spiegelung, das heißt Umkehr der Reihenfolge der Zeichen in jedem Wort<br />
* [[Vereinigungsmenge|Vereinigung]]<br />
* [[Schnittmenge|Durchschnitt]]<br />
* [[Konkatenation (Formale Sprache)|Konkatenation]]<br />
* <math>\varepsilon</math>-freien [[Homomorphismus|Homomorphismen]]<br />
<br />
== Verhältnis zu anderen Sprachklassen ==<br />
Da die Konstruktion eines [[LR-Parser]]s aus einer LR(1)-Grammatik für eine deterministisch kontextfreie Sprache häufig zu sehr großen Parse-Tabellen führt, werden in der Praxis leichte Einschränkungen vorgenommen, die zu geringerer Mächtigkeit führen. Die beiden Einschränkungen dieser Art sind [[LALR-Parser|LALR-]] und [[SLR-Parser]].<br />
<br />
Eine weitere Unterklasse der LR(k)-Sprachen bilden die [[LL(k)-Grammatik|LL(k)-Sprachen]]. Diese werden manchmal für bestimmte Anwendungsfälle bevorzugt, da Parser direkt aus einer Grammatik dafür leicht ohne Parsergenerator programmiert werden können (s. [[Rekursiver Abstieg]]). Weiterhin sind während des Parsens Informationen über die genaue Position im Parsebaum verfügbar. Dies ist vor allem deshalb nützlich, weil es auf einfache Weise vererbte Attribute bei der Definition der Semantik zulässt.<br />
<br />
Bei LR-Parsern ist die mögliche Baumkonstellation oberhalb des abgearbeiteten Handle hingegen eine reguläre Sprache. Gängige Parsergeneratoren wie [[yacc]] beschränken sich deshalb auf die Möglichkeit der [[S-attributierte Grammatik|S-Attribution]], die ausschließlich synthetisierte Attribute zulässt. Inzwischen existiert jedoch mit zyacc auch ein Parsergenerator, der [[LR-attributierte Grammatik|LR-Attribution]] erlaubt, d.&nbsp;h. vererbte Attribute in den Fällen, wo sie beim Parsen von links nach rechts eindeutig ausgewertet werden können.<br />
<br />
Die deterministisch kontextfreien Sprachen sind eine echte Teilklasse der [[Kontextfreie Sprache|kontextfreien Sprachen]]. Sie sind unvergleichbar mit den [[Lineare Sprache|linearen Sprachen]], aber eine echte Oberklasse der [[Lineare Sprache|deterministischen linearen Sprachen]]. Weiterhin sind sie eine echte Teilklasse der [[Wachsend kontextsensitive Sprache|deterministischen wachsend kontextsensitiven Sprachen]], die mit den [[Church-Rosser-Sprache]]n übereinstimmen.<br />
<br />
== Literatur ==<br />
* [[Seymour Ginsburg]], [[Sheila A. Greibach]]: ''Deterministic context-free languages''. In: ''Information and Control'' 9, 1966, {{ISSN|0019-9958}}, S. 620–648.<br />
* [[Donald E. Knuth]]: ''On the Translation of Languages from Left to Right''. In: ''Information and Control'' 8, 1965, {{ISSN|0019-9958}}, S. 607–639, (Neuabdruck einer erweiterten Fassung in: Donald E. Knuth: ''Selected Papers on Computer Languages''. Center for the Study of Language and Information, Stanford CA 2003, ISBN 1-575-86381-2, (''CSLI lecture notes'' 139), Kapitel 15).<br />
<br />
== Weblinks ==<br />
* {{Complexity Zoo|DCFL|D#dcfl}}<br />
<br />
[[Kategorie:Theorie formaler Sprachen]]</div>213.162.73.146