Deterministisch kontextfreie Sprache

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.

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 $L$ ein $k$, so dass $L$ eine LR(k)-Sprache ist (d. h. eine LR(k)-Grammatik hat). Tatsächlich reicht dafür in jedem Fall $k=1$, aber nicht $k=0$. 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.

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 Sprachen
• Komplement
• Anwendung inverser Homomorphismen

Sie sind nicht abgeschlossen unter:

• Spiegelung, das heißt Umkehr der Reihenfolge der Zeichen in jedem Wort
• 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 (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.

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, Sheila A. Greibach: Deterministic context-free languages. In: Information and Control 9, 1966, ISSN 0019-9958, S. 620–648.
• 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).

Weblinks

• DCFL. In: Complexity Zoo. (englisch)