Syntaxbaum

Einfache Sprache

Def. Syntaxbaum

Sei $\mathcal G = (T,V,S,P)$ eine Kontextfreie Grammatik. Der Syntaxbaum für $\mathcal G$ ist ein Baum, der folgende Eigenschaften erfüllt:

1. Interne Knoten (also nicht die Blätter) sind mit einer Variable aus $V$ beschriftet.
2. Blattknoten sind entweder mit einem Terminalsymbol, einer Variable oder $\varepsilon$ beschriftet.
3. Falls interner Knoten einen Kindknoten hat, der mit $\varepsilon$ beschriftet ist, dann hat der interne Knoten nur einen (eben diesen) Kindknoten.
4. Wenn ein interner Knoten mit $A$ beschriftet ist und dessen Kinder von links nach rechts mit $X_1,X_2,\ldots,X_n$ beschriftet sind, dann ist $A\to X_1X_2\ldots X_n$ eine Produktionsregel in $P$.

Falls die Wurzel mit $S$ beschriftet ist, dann ist der Syntaxbaum komplett.

• Ertrag eines Syntaxbaums

Alternative Definition über die Menge aller Syntaxbäume:

Die Menge aller Syntaxbäume einer Kontextfreie Grammatik $\mathcal G = (T, V, S, P)$ ist eine endliche Menge von Bäumen mit total geordneten Kinderknoten und Knoten sind mit $\Sigma\cup\{\varepsilon\}$ beschriftet. Sie ist induktiv definiert durch:

Basiselemente: Jedes Terminalsymbol $t\in T_\varepsilon$ hat einen Baum der nur aus einem Knoten, der mit $t$ beschriftet ist, besteht.

Konstruktionsregel: Wenn $A\to X_0\ldots X_n \in P$ mit $X_i\in\Sigma$ oder falls $n = 0$ dann $X_0 = \varepsilon$; und es existieren die Syntaxbäume $t_0,\ldots,t_n$ so, dass deren Wurzel jeweils $X_i$ ist. Dann ist der Syntaxbaum mit der Wurzel $A$ und den Teilbäumen $t_0,\ldots,t_n$ auch ein Syntaxbaum.

Falls die Wurzel mit $S$ beschriftet ist, dann ist der Syntaxbaum komplett.

????

Das Ergebnis oder auch yield eines Synatxbaumes ist die Konkatenation der Beschriftungen der Knoten von der Wurzel aus.