Compilerbau: Kontextfreie Grammatiken

Definition	Kontextfreie Grammatik

	4-Tupel
	G = (T, N, P, S)

T	Terminalsymbole, nicht leere endliche Menge

N	Nichtterminalsymbole, nicht leere endliche Menge

	N ∩ T = {}

P	Regelmenge, Produktionen, nicht leer

Regel	X ::= Y₁ Y₂ ... Y_n
	mit
	X ∈ N, Y_i ∈ N ∪ T, n ≥ 0

S	Startsymbol
	S ∈ N

Ableitungsschritt
gegeben	x ∈ (N ∪ T)* p ::= q ∈ P x = x₁px₂

Ableitungsschritt	p wird in x durch die rechte Seite q ersetzt
	y = x₁qx₂

Notation	für einen Ableitungsschritt
	x ⊢ y

Ableitungsfolge	x₀ ⊢ x₁ ⊢ x₂ ⊢ ... ⊢ x_n
kurz	x₀ ⊢^* x_n

Satzform	eine Zeichenreihe w ∈ (N ∪ T)^* mit
	S ⊢^* w

Satz	eine Zeichenreihe w ∈ T^* mit
	S ⊢^* w

Spache L(G)	L(G) = { w \| w ∈ T^* · S ⊢^* w}
	Alle aus dem Startsymbol erzeugbaren Wörter über T

Ableitungsbaum Syntaxbaum	Eine Ableitungsfolge kann als Baum dargestellt werden

	Die Reihenfolge der Ableitungsschritte innerhalb einer Satzform hat keinen Einfluss auf die grammatikalische Struktur eines Satzes
	Dieses gilt nicht mehr für kontextsenitive oder Typ-0-Grammatiken

	Die ausgewählten Regeln sind entscheident

systematische Ableitungsstrategien
Linksableitung	im Baum (oder im Wort) wird immer das am weitesten links stehende (das erste) Nichtterminalsysmbol abgeleitet

Rechtssableitung	im Baum (oder im Wort) wird immer das am weitesten rechts stehende (das letzte) Nichtterminalsysmbol abgeleitet

Beispiel	G = (T, N, P, S) mit T = { i, +, , (, ) } N = { E } P = { E ::= E + E (1) , E ::= E E (2) , E ::= ( E ) (3) , E ::= i (4) } S = E

?	L(G) = { ... } ?

Kunst	bei der Konstruktion eines Ableitungsbaums: Auswahl der richtigen Regeln

	Sonst: Sackgasse

Kunst	bei der Konstruktion eines Ableitungsbaums: effiziente Auswahl der richtigen Regeln

	Sonst: Parser unbrauchbar

Ziel	parsen mit einer Zeitkomplexität von O(n)

	Für jede kontextfreie Sprache kann ein Wort in der Zeitkomplexität O(n³) erkannt werden.

Strategie	Die Eingabe von links nach rechts verarbeiten, dabei den Baum schrittweise aufbauen und bei der Auswahl der Regeln möglichst wenig in der Eingabe vorausschauen.

Definition	Eine Grammatik ist mehrdeutig, wenn es zu (mindestens) einem Wort aus der Sprache zwei unterschiedliche Ableitungsbäume gibt.

Problem	Semantik wird mit Hilfe des Syntaxbaums definiert

	mehrere Syntaxbäume ==> mehrere Bedeutungen

	mehrere Syntaxbäume ==> kein deterministischer Parser ==> ineffizient

Aufgabe	Zu einer Sprache L(G) mit einer mehrdeutigen Grammatik G eine Grammatik G' finden, so dass gilt:
	L(G) = L(G')

	Diese ist nicht immer möglich.
	Ob eine Grammatik mehrdeutig ist, ist im Allgemeinen nicht entscheidbar.

Mehrdeutige Sprachen	Definition: Eine Sprache L ist mehrdeutig, wenn für alle G mit L(G) = L gilt: G ist mehrdeutig.

	Assoziativitäten und Prioritäten von Operatoren werden festgelegt.

	Ableitungsbaum wird größer.
	Viele Knoten ohne Informationsgehalt.

Kontextfreie Grammatiken

Mehrdeutige Grammatiken