Kontextfreie Sprachen

---

Kontextfreie Sprachen  sind ausdrucksfähiger als reguläre Sprachen. Bei ihren Grammatiken besteht die linke Seite einer Ersetzungsregel ebenfalls nur aus einem einzigen Nicht-Terminalzeichen. Es besteht jedoch keine Einschränkung hinsichtlich der rechten Seite.
Die im Abschnitt über Formale Sprachen angegebenen Beispiele von Grammatiken sind durchweg kontextfrei. Diese Sprachen haben damit grundsätzliche Bedeutung zur Beschreibung natürlicher und künstlicher Sprachen wie Programmiersprachen.

Bei der Übersetzung von Programmiersprachen arbeiten Parser entweder aufsteigend (bottom-up) von den Terminalzeichen bis zum Startzeichen oder absteigend (top-down) vom Startzeichen bis zu den Terminalzeichen.
Die grammatikalische Struktur von Ausdrücken lässt sich durch Syntaxbäume veranschaulichen.

Beispiel: Arithmetische Terme
Terminalzeichen: { +, -, *, /, ( , ), a, b, ..., z } 
Nicht-Terminalzeichen: { T,S,F,V}
Startzeichen: T.

Die Produktionsregeln: ( G 1 )

(1) T  --> S | S + T | S - T

(2) S  --> F | F * S | F / S

(3) F  --> V | ( T )

(4) V  --> a | b | ...| z

Der arithmetische Term  a + b + c   lässt sich nun top-down  als Linksableitung  herleiten. Das am weitesten links stehende Nicht - Terminalzeichen  wird in einer Linksableitung zuerst ersetzt :

T => S + T
=> F + T
=> V + T
=> a + T
=> a + S
=> a + F * S
=> a + V * S
=> a + b * S
=> a + b * F
=> a + b* V
=> a + b * c

Bei einer Rechtsableitung wird das am weitesten rechts stehende Nicht - Terminalzeichen zuerst ersetzt:

T => S + T => S + S => S + F * S => S + F * F => S + F * V => S + F * c => S + V * c => S + b * c
    => F + b * c => V + b * c =>  a + b * c

Liest man diese Ableitungsfolge in umgekehrter Reihenfolge, also von den Terminalzeichen ausgehend, erhält man eine Bottom-up-Zerlegung des Ausdrucks.
Links- wie Rechtsableitung führen zum gleichen Syntaxbaum!

Mehrdeutige Grammatiken

Die Produktionsregeln der Grammatik (G 1) aus dem Beispiel werden durch die folgenden Regeln ersetzt:

(G 2)          (1) T  --> V | ( T ) | T + T | T * T                (2) V   --> a | b | c | .  .  .| z

Man kann zeigen, dass (G 1) äquivalent zu (G 2) ist, d.h. beide Grammatiken erzeugen die gleiche Sprache. (G 2) ist offenbar einfacher. Der Ausdruck a + b * c  lässt sich aber auf zwei verschiedene Weisen als Linksableitung herstellen: 
Beginnt man mit  T => T + T , erhält man den linken Baum. Fängt man mit  T => T * T  an, so bekommt man den rechten Baum . 

Die Bäume stimmen in ihrer Struktur nicht überein! Eine solche Grammatik wie  (G 2)  bezeichnet man als mehrdeutig. Einsetzen von Zahlenwerten in die Variablen führen entsprechend zu unterschiedlichen Resultaten.

[Start]