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.

Im Bezug auf Grammatiken findet sich auch die Bezeichnung LR(k)-Sprache. Strenggenommen gibt es zwar deterministisch-kontextfreie Sprachen, die keine LR(0)-Sprachen sind, jedoch lassen sie sich durch Einführung einer eindeutigen Markierung für das Ende der Eingabe 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.

Verhältnis zu anderen Sprachklassen

Da die Konstruktion eines LR-Parsers aus einer LR(1)-Grammatik für eine deterministsch 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 Defintion 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.

Literatur

• Seymour Ginsburg und Sheila 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.