Kontextfreie Grammatiken sind sehr beliebt für die Beschreibung natürlicher Sprachen. Zumindest in der Theorie und solange es nicht zu kompliziert wird, eignen sie sich gut dafür, Syntax in den Griff zu kriegen. Warum interessieren sich manche Computerlinguistien dann so für nicht kontextfreie Grammatikformalismen wie SRCG, das ich in Teil 1 vorgestellt und in Teil 2 in die Chomsky-Hierarchie eingeordnet habe?

Schauen wir uns ein Fragment der deutschen Sprache an, das aus Nebensätzen wie diesen besteht:

(1.1) dass wir das Haus anstreichen
(1.2) dass wir dem Hans das Haus anstreichen helfen
(1.3) dass wir die Kinder dem Hans das Haus anstreichen helfen lassen

Es wird z.B. durch die folgende kleine kontextfreie Grammatik mit Startsymbol S‘ beschrieben. Von Finitheit, Numerus und Genus sehen wir mal großzügig ab und beachten nur Kasus (n für Nominativ, d für Dativ, a für Akkusativ):

(2.1) S‘ → C S
(2.2) S → NPn VP
(2.3) VP → NPa Va
(2.4) VP → NPd VP Vdv
(2.5) VP → NPa VP Vav
(2.6) NPn → PRPn
(2.7) NPa → Da N
(2.8) NPd → Dd N
(2.9) C → dass
(2.10) PRPn → wir
(2.11) Da → das
(2.12) Dd → dem
(2.13) N → Haus
(2.14) N → Hans
(2.15) N → Kinder
(2.16) Va → anstreichen
(2.17) Vdv → helfen
(2.18) Vav → lassen

Die Grammatik beschreibt Sätze wie in (1.1-3) nicht nur, sie liefert auch linguistisch plausible Strukturen dafür. Erstens trägt sie der Beobachtung Rechnung, dass Sprache wie Lego ist: Sätze sind aus Teilen (Phrasen oder Konstituenten) zusammengesetzt, die ihrerseits wiederum aus Phrasen bestehen, bis man bei den kleinsten Bausteinen anlangt, den Wörtern. Phrasen gleicher Kategorie sind untereinander austauschbar. Z.B. sind sowohl das Haus anstreichen als auch dem Hans das Haus anstreichen helfen Verbalphrasen (VP) und können daher beide auf dass wir folgen und einen Satz bilden (1.1, 1.2), auch wenn sie in sich unterschiedlich aufgebaut sind, einmal nach Regel (2.3) und einmal nach Regel (2.4). Umgekehrt kann dieselbe Konstituente, z.B. das Haus anstreichen in verschiedenartigen Kontexten auftauchen (1.1, 1.2., 1.3), weil sowohl (2.2) als auch (2.4) als auch (2.5) das VP-Symbol auf der rechten Seite haben.

Zweitens modellieren die Regeln die lokalen Abhängigkeiten zwischen Verben und ihren Argumenten: helfen ist zum Beispiel ein Verb, das eine Nominalphrase im Dativ als Argument nehmen kann (wem man hilft) sowie eine Verbalphrase (wobei man hilft). Ich habe das in der Grammatik mal so kodiert, dass helfen die Kategorie Vdv hat (Verb mit Dativ-Nominalphrase und Verbalphrase). Analog ist lassen Vav (Akkusativ-Nominalphrase, wen oder was man lässt; Verbalphrase, was man ihn, sie oder es tun lässt) und streichen nur Va (Akkusativ-Nominalphrase, was man streicht). Regeln 2.3-5 sorgen dafür, dass jede Verbalphrase mit einem Verb (dem Kopf der Phrase) und dazu passenden Argumenten aufgebaut wird.

Ein Ableitungsbaum veranschaulicht die syntaktische Struktur eines Satzes, hier die von (1.3):

Übersetzen wir nun unsere drei Beispielsätze ins Zürichdeutsche nach Shieber (1985):

(3.1) das mer es huus aastriche
(3.3) das mer em Hans es huus hälfe aastriche
(3.3) das mer d’chind em Hans es huus lönd hälfe aastriche

Es fällt auf, dass die Verben am Ende in der umgekehrten Reihenfolge stehen. Wenn wir weiterhin davon ausgehen, dass z.B. in (3.3) d’chind direkt mit lönd zusammenhängt, em Hans direkt mit hälfe und es huus direkt mit aastriche, was zweifellos sinnvoll ist, dann stellen wir fest, dass unsere Verbalphrasen nicht mehr verschachtelt sind wie im Hochdeutschen, sondern sich „überkreuzen“. Ein Baumdiagramm zu (3.3) sieht dann so aus:

Man spricht auch von unterbrochenen Konstituenten, weil zwischen den Wörtern, die zu den niedrigeren beiden VPs gehören, Wörter auftauchen, die nicht dazu gehören.

Es ist einigermaßen offensichtlich, dass das keine kontextfreie Ableitung mehr ist. Eine 2-SRCG dazu indes gibt es:

(4.1) S’(XY) → C(X) S(Y)
(4.2) S(XYZ) → NPn(X) VP(Y,Z)
(4.3) VP(XY,ZU) → NPa(X) VP(Y,U) Vav(Z)
(4.4) VP(XY,ZU) → NPd(X) VP(Y,U) Vdv(Z)
(4.5) VP(X,Y) → NPa(X) Va(Y)
(4.6) NPn(X) → PRPn(X)
(4.7) NPd(XY) → Dd(X) N(Y)
(4.8) NPa(XY) → Da(X) N(Y)
(4.9) C(das) → ε
(4.11) PRPn(mer) → ε
(4.12) Dn(d’) → ε
(4.13) Dd(em) → ε
(4.13) N(huus) → ε
(4.14) N(Hans) → ε
(4.15) N(chind) → ε
(4.16) Va(aastriche) → ε
(4.17) Vdv(hälfe) → ε
(4.18) Vav(lönd) → ε

Die Idee ist, VPs zwei Argumente zu geben, das erste für die Argumente der Verben, das zweite für die Verben selbst. Hängt von einer Verbalphrase VP1 eine zweite Verbalphrase VP2 ab, bilden die Argumente von VP2 die Basis, VP1 hängt ihr NP-Argument und ihr Verb jeweils vorne an, wie in Regeln (4.3-4) zu sehen.

Eine VP in dieser Grammatik ist auch nicht nur einfach eine Aneinanderreihung von Nominalphrasen, gefolgt von einer gleich langen Aneinanderreihung von Verben – das würde man zur Not auch noch mit einer kontextfreien Grammatik hinkriegen, wenn auch mit einer anderen Struktur (vgl. die erste Beispielgrammatik in Teil 1). Nein, die Regeln „checken“ ja, ob eine Nominalphrase zum Verb passt (z.B. Dativ für helfen, aber Akkusativ für lassen). Falsche Sätze wie dieser sind nicht ableitbar (lönd verlangt Akkusativ, nicht Dativ):

(5.1) *das mer em chind em Hans es huus lönd hälfe aastriche

Das ist der Kern des Arguments von Shieber (1985) dafür, dass natürliche Sprachen im Allgemeinen nicht kontextfrei sind.

In Teil 4: Was man dagegen einwenden kann und warum es so oder so nützlich sein kann, unterbrochene Konstituenten (also ein wenig Kontextfreiheit) bei der Analyse natürlicher Sprachen zuzulassen.

Sehr konkrete Pläne habe ich für Teil 4 noch nicht. Erst mal bin ich gespannt, ob meine werten Leser Fragen und Kommentare hierzu haben und wenn ja, welche. Daraus ergibt sich dann vielleicht eine klarere Vision für Teil 4.

Ausgelöst durch Prüfungsvorbereitung und Schreiben an der Masterarbeit habe ich mich in letzter Zeit viel mit Typen formaler Grammatiken beschäftigt, die alle kontextfreien Sprachen beschreiben können und darüber hinaus einige, aber nicht alle kontextsensitiven Sprachen. Einen solchen Grammatikformalismus, nämlich Simple Range Concatenation Grammars (SRCG), habe ich in Teil 1 dieser Serie vorgestellt. In Teil 3 werde ich Anwendungen auf natürliche Sprache skizzieren.

Heute ist Teil 2 dran und damit die Vogelperspektive: Wo stehen wir auf der Chomsky-Hierarchie der formalen Sprachen? Ich kopiere dazu einfach Herrn Raus Übersicht über die Chomksy-Hierarchie, füge aber zwei weitere Stufen, also zwei weitere Klassen von Sprachen ein.

• Chomsky 0: Alle Sprachen, die sich überhaupt durch eine Grammatik beschreiben lassen.
• Chomsky 1: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine kontextsensitive Grammatik beschreiben lassen.
• PTIME aka P: Die Sprachen, bei denen das Wortproblem in Polynomialzeit entscheidbar ist. Range Concatenation Grammars (RCG) können genau diese Sprachen beschreiben. PTIME ist eine Teilmenge von Chomsky 0; ist es auch eine Teilmenge von Chomsky 1? Ich weiß es nicht, vielleicht weiß es auch niemand, aus dieser Übersicht geht es jedenfalls nicht hervor. Für Aufklärung bin ich dankbar.
• Eine Teilmenge sowohl von Chomksy 1 als auch von PTIME sind die Sprachen, die sich durch Simple Range Concatenation Grammars (SRCG) beschreiben lassen. So weit ich weiß, hat diese Klasse von Sprachen keinen einschlägigen Namen. SRCG ist eine eingeschränkte Variante von RCG, aber immer noch deutlich mächtiger als kontextfreie Grammatiken (CFG). Es gehört zu den so genannten „schwach kontextsensitiven“ (mildly context-sensitive) Grammatikformalismen, die vor allem im Zusammenhang mit natürlicher Sprache interessant sind – wo kontextfreie Grammatiken für eine adäquate Beschreibung nicht mehr ausreichen, man aber wegen Effizienz und Theoriedesign auch nicht zu weit darüber hinausgehen will. Dieselbe Klasse von Sprachen lässt sich durch die mit SRCG auch sonst so gut wie identischen Formalismen Linear Context-free Rewriting Systems (LCFRS) und Multiple Context-free Grammars (MCFG) beschreiben.
• Chomsky 2: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine kontextfreie Grammatik beschreiben lassen.
• Chomsky 3: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine reguläre Grammatik beschreiben lassen.

Die originale vierstufige Chomksy-Hierarchie bietet ein schönes Zwiebelschalenmodell, bei dem jede Sprachenmenge die nächste strikt einschließt:

Diese Schönheit habe ich durch mein Unwissen, ob PTIME eine Teilmenge von Chomsky 1 ist, zerstört. Bedenkt man aber, dass Chomsky 1, also die Klasse der kontextsensitiven Sprachen, meines Wissens weder theoretisch noch praktisch besonders interessante Eigenschaften hat, kann man sie rausschmeißen und aus der obigen Auflistung durchaus wieder eine schöne Zwiebel basteln:

Doch Vorsicht: In einem Vortrag habe ich einmal ein entsprechendes Diagramm für die verschiedenen schwach kontextsensitiven Grammatikformalismen gesehen, die es heute so gibt. Es sah ungefähr so aus:

In Teil 3: Warum man arguably schwach kontextsensitive Grammatikformalismen braucht, um natürliche Sprache zu beschreiben.

Nachbemerkung 1: mildly context-sensitive klingt schwammig, ist aber relativ präzise definiert. Der Begriff bezieht sich im Gegensatz z.B. zu context-sensitive und context-free nicht auf Sprachen, sondern auf Mengen von Sprachen. Eine Menge von Sprachen ist schwach kontextsensitiv genau dann, wenn sie einerseits alle kontextfreien Sprachen enthält und überdies kreuzende Abhängigkeiten beschreiben kann (siehe dazu Teil 3), andererseits aber nur Sprachen enthält, die in polynomieller Zeit parsbar sind (also eine Teilmenge von PTIME ist) und überdies konstantes Wachstum aufweisen. Für Details siehe Joshi (1985) oder Kallmeyer (2010). Trotz dieser präzisen Definition gibt es noch keinen Grammatikformalismus, von dem man wüsste, dass er die größtmögliche schwach kontextsensitive Menge von Sprachen beschreibt. Obwohl SRCG nach heutigem Kenntnisstand der mächtigste schwach kontextsensitive Formalismus ist, kann es also gut sein, dass es eine schwach kontextsensitive Menge von Sprachen gibt, die Sprachen enthält, die SRCG nicht beschreiben kann.

Nachbemerkung 2: Joshi (1985) hat mildly context-sensitive als terminus technicus eingeführt und, so bilde ich mir ein, extra nicht weakly genommen, weil dieses Wort im Zusammenhang mit formalen Grammatiken schon eine ganz andere Bedeutung hat, nämlich bei schwacher Äquivalenz. Deswegen finde ich die deutsche Übersetzung schwach kontextsensitiv etwas unglücklich. Hätte man nicht gelinde kontextsensitiv nehmen können?

Nachbemerkung 3: Wo wir schon bei Terminologiekritik sind. Das Begriffspaar kontextfrei und kontextsensitiv hat mich schon immer geärgert. Das klingt so komplementär. Tatsächlich ist aber jede kontextfreie Sprache auch eine kontextsensitive Sprache, siehe Zwiebel. Diese begriffliche Verwirrung ist ein Grund mehr, sich mit der Klasse der kontextsensitiven Sprachen überhaupt nicht mehr zu beschäftigen. *g*

In Herrn Raus Blog gibt es eine schöne mehrteilige Einführung in formale Sprachen, formale Grammatiken und die Chomksy-Hierarchie. Unter anderem werden dort reguläre Grammatiken, kontextfreie Grammatiken und kontextsensitive Grammatiken vorgestellt. Ich will heute einen weniger bekannten Grammatikformalismus vorstellen: Simple Range Concatenation Grammars (SRCG) (zu deutsch etwa: einfache Intervallverkettungsgrammatiken).

SRCGs können alle kontextfreien Sprachen beschreiben und darüber hinaus einige, aber nicht alle kontextsensitiven Sprachen. Genaueres dazu sage ich in Teil 2 dieser Serie, bevor ich in Teil 3 andeute, wozu das speziell bei natürlichen Sprachen (also so etwas wie Englisch, Deutsch, Niederländisch oder Zürichdeutsch) und damit für die Computerlinguistik von Nutzen sein kann.

Fangen wir mit einer guten alten kontextfreien Grammatik an. Hier sind die Regeln einer kontextfreien Grammatik, die die Sprache {aⁿbⁿ|n≥0} erzeugt, also die Sprache, die aus den Wörtern ε (das leere Wort), ab, aabb, aaabbb usw. besteht.

(1.1) S → aSb
(1.2) S → ε

Wenn wir diese Grammatik als SRCG schreiben, sehen die Regeln so aus:

(2.1) S(aXb) → S(X)
(2.2) S(ε) → ε

Vergleichen wir Regeln (1.1) und (2.1): Beide Regeln besagen, dass man aus dem Symbol S alle Wörter ableiten kann, die mit a losgehen, in der Mitte aus etwas bestehen, das man wiederum aus S ableiten kann, und mit b enden. Die Beschreibung „dessen, was man ableiten kann“, steht bei SRCG nicht auf der rechten Seite des Pfeils, sondern in Klammern neben dem Symbol der linken Seite. Es wird die Variable X verwendet, die auf der rechten Seite in dem Ausdruck S(X) wieder auftaucht: Der sagt, dass X etwas sein muss, das man aus S ableiten kann.

Regel (2.2) besagt wie Regel (1.2), dass man aus S den leeren String ableiten kann, und zwar bedingungslos – es tauchen keine weiteren Symbole auf, deswegen ist auch die rechte Seite leer (geschrieben wie der leere String als ε).

Eine andere SRCG für dieselbe Sprache wäre die hier:

(3.1) S(XY) → A(X, Y)
(3.2) A(aX, bY) → A(X, Y)
(3.3) A(ε, ε) → ε

Hier taucht ein neues Nichtterminal auf, A. Was hinter A in Klammern steht, besteht aus zwei Teilen, man sagt: A ist zweistellig oder: A hat zwei Argumente. Eins für den a-Teil der Wörter und eins für den b-Teil.

Damit sind wir beim wesentlichen Unterschied zwischen SRCG und CFG: In CFGs kann man aus einem Nichtterminal einen Teilstring des Wortes ableiten, in SRCGs auch mehrere Teilstrings, technisch ausgedrückt: Tupel von Teilstrings.

Die Grammatik im Beispiel funktioniert so: Regel (3.3) sagt, dass aus A das Tupel ⟨ε, ε⟩ ableitbar ist, also zweimal der leere String. Regel (3.2) sagt: Wenn aus A das Tupel ⟨X, Y⟩ ableitbar ist (rechte Seite), dann ist aus A auch das Tupel ⟨aX, bY⟩ ableitbar (linke Seite). Generativ, prozedural und salopp ausgedrückt klatscht diese Regel vorne an das erste Argument von A ein a und an das zweite ein b. Diesen Prozess kann man beliebig oft wiederholen, bis man so viele a’s und b’s hat, wie man will – aber immer für beide Argumente gleichzeitig, sodass die Anzahl der a’s und b’s gleich bleibt. Schließlich kommt Regel (3.1) zum Zuge, die die beiden Argumente von A in das einzige Argument von S konkateniert (verkettet).

Man kann diesen Prozess auch in der umgekehrten Reihenfolge schreiben, als Ableitung. Eine Ableitung beginnt mit dem Startsymbol und dem Wort, das man ableiten will, und gelangt über die Anwendung von Regeln zu ε. Hier eine beispielhafte Ableitung für das Wort aabb:

S(aabb)  ⇒_(3.1) A(aa, bb)  ⇒_(3.2) A(a, b)  ⇒_(3.2) A(ε, ε)  ⇒_(3.3) ε

Weil jede Ableitung mit genau einem String beginnt (eben dem Wort, das man ableiten will), muss das Startsymbol immer einstellig sein. Die Stelligkeit ist für jedes Nichtterminal festgelegt, d.h. innerhalb einer Grammatik kann A z.B. nicht einmal mit zwei und einmal mit drei Argumenten auftauchen.

Während sich bei jeder Anwendung einer CFG-Regel an einer Stelle im abzuleitenden Wort etwas ändert – ein Nichtterminal wird durch etwas ersetzt – kann sich bei der Anwendung einer SRCG-Regel an mehreren Stellen etwas ändern. So ändert sich bei jeder Anwendung unserer Regel (3.2) sowohl vorne etwas (ein a wird hinzugefügt) als auch in der Mitte (ein b wird hinzugefügt). Leicht lässt sich das auf drei Stellen ausdehnen, sodass die Grammatik die Sprache {aⁿbⁿcⁿ|n≥1} beschreibt, für die es schon keine CFG mehr gibt. Man gibt A einfach ein drittes Argument:

(4.1) S(XYZ) → A(X, Y, Z)
(4.2) A(aX, bY, cZ) → A(X, Y, Z)
(4.3) A(ε, ε, ε) → ε

Das ist jetzt eine so genannte 3-SRCG, d.h. eine SRCG, wo die Nichtterminale maximal 3 Argumente haben. Die Zeitkomplexität des Wortproblems (algorithmisch zu bestimmen, ob ein gegebenes Wort zu der von der Grammatik erzeugten Sprache gehört) nimmt für k-SRCGs mit steigendem k exponenziell zu (übrigens auch mit der maximalen Länge der rechten Regelseite, die bisher in allen Beispielen 0 oder 1 war). CFGs entsprechen 1-SRCGs, wie ganz oben illustriert, wo wir eine CFG direkt in eine 1-SRCG übersetzt haben.

Für die Form der Regeln einer SRCG gibt es zwei wichtige Einschränkungen: Auf der rechten Seite muss jedes Argument nicht mehr und nicht weniger als eine Variable enthalten (während auf der linken Seite Folgen von Terminalen, Variablen oder auch ganz leere Argumente erlaubt sind). Außerdem muss jede Variable, die in einer Regel vorkommt, auf der linken und auf der rechten Seite der Regel je genau einmal vorkommen. Ohne diese Einschränkungen hätte man die noch einmal deutlich mächtigeren und komplexeren Range Concatenation Grammars (RCG) (Boullier 1998).

In Teil 2 schauen wir uns etwas genauer an, welche Klassen von Sprachen SRCG und RCG beschreiben und wo man diese auf der Chomksy-Hierarchie einordnen kann.

Nachbemerkung 1: Aus pädagogischen Gründen habe ich immer „Regel“ und „Nichtterminal“ geschrieben, im RCG-Jargon sagt man eigentlich „Klausel“ und „Prädikat“ dazu. Wer schon einmal in Prolog programmiert hat, bei der klingt jetzt vielleicht ein Glöcklein. Ja, eine (S)RCG lässt sich mit trivialen Änderungen in der Syntax als Logikprogramm lesen. Leider ist das dann noch lange kein praxistauglicher Parser, wie ja auch Prologs im Kern kontextfreie Definite Clause Grammars (DCG) gewissen Beschränkungen unterworfen sind. Parsing-Algorithmen für RCG, SRCG und weitere Formalismen gibt’s in Kallmeyer (2010).

Nachbemerkung 2: Das war jetzt gewissermaßen auch eine Einführung in Linear Context-free Rewriting Systems (LCFRS) (Vijay-Shanker et al. 1987, Weir 1988) und Multiple Context-free Grammars (MCFG) (Seki et al. 1991). Diese beiden Grammatiktypen beschreiben dieselbe Klasse von Sprachen wie SRCG und unterscheiden sich auch sonst nur minimal davon.