DCFL

Eine deterministisch kontextfreie Sprache ist eine Sprache, die von einem deterministischen Kellerautomaten akzeptiert wird. Manchmal wird auch der gekürzte Begriff deterministische Sprache verwendet. Die Definition geht auf Seymour Ginsburg und Sheila Greibach zurück.

Im Bezug auf Grammatiken findet sich auch die Bezeichnung LR(k)-Sprache: Jede LR(k)-Grammatik beschreibt eine deterministisch-kontextfreie Sprache. Strenggenommen gilt die Umkehrung zwar nicht, denn es gibt deterministisch-kontextfreie Sprachen, die keine LR(0)-Sprachen sind (d.h. nicht als LR(0)-Grammatik darstellbar sind), jedoch lassen sie sich durch Einführung einer eindeutigen Markierung für das Wortende in eine solche überführen.

Eigenschaften

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 Sprachen, insbesondere Programmiersprachen, gehören zu dieser Sprachklasse.

Weiterhin sind die deterministisch kontextfreien Sprachen abgeschlossen unter:

• Schnittbildung mit regulären Mengen
• Komplement
• Anwendung inverser Homomorphismen

Sie sind nicht abgeschlossen unter:

• Spiegelung
• Vereinigung
• Durchschnitt
• Konkatenation
• $\varepsilon$-freien Homomorphismen

Verhältnis zu anderen Sprachklassen

Da die Konstruktion eines LR-Parsers 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- und SLR-Parser

Eine weitere Unterklasse der LR(k)-Sprachen bilden die 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. 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.

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-Attribution, die ausschließlich synthetisierte Attribute zulässt. Inzwischen existiert jedoch mit zyacc auch ein Parsergenerator, der LR-Attribution erlaubt, d.h. vererbte Attribute in den Fällen, wo sie beim Parsen von Links nach Rechts eindeutig ausgewertet werden können.

Die deterministisch kontextfreien Sprachen sind eine echte Teilklasse der kontextfreien Sprachen. Sie sind unvergleichbar mit den linearen Sprachen, aber eine echte Oberklasse der deterministischen linearen Sprachen. Weiterhin sind sie eine echte Teilklasse der deterministischen wachsend kontextsensitiven Sprachen, die mit den Church-Rosser-Sprachen übereinstimmen.

Literatur

• Seymour Ginsburg und Sheila A. Greibach: Deterministic context-free languages, Information and Control  9 (1966), 620–648.
• Donald E. Knuth, On the Translation of Languages from Left to Right, Information and Control  8 (1965), 607–639. Neuabdruck einer erweiterten Fassung in Selected Papers on Computer Languages, Kapitel 15.