Syntaxbaum

Man betrachte eine formale Grammatik <math>G = \left( N \Sigma P \right)</math> und eine Ableitung <math>S = w_0 w_1 \Rightarrow ... \Rightarrow w_n = w</math>. sei eine Typ-2-Grammatik (vgl. Chomsky-Hierarchie ).

Den zugehörigen Syntaxbaum erhält man indem

1. die Wurzel mit <math>S</math> beschrifte
2. Kinder <math>z_i</math> mit <math>i \in \{ 1 m \}</math> von Knoten <math>A</math> erzeugt wenn <math>w_{i-1} \Rightarrow w_i</math> die Regel <math>A \rightarrow mit <math>z_i \in N \cup \Sigma</math> angewendet

Blätter werden mit <math>w</math> beschriftet.

Unter Umständen können mehrere Ableitungen zum Baum führen.

Siehe auch

• Linksableitung
• Rechtsableitung

Bücher zum Thema Syntaxbaum

Dieser Artikel von Wikipedia unterliegt der GNU FDL.