aus Wikipedia, der freien Enzyklopädie
Ein Syntax- oder Ableitungsbaum ist eine baumförmige Darstellung einer Ableitung .
Man betrachte eine formale Grammatik
G
=
(
N
,
Σ
,
P
,
S
)
{\displaystyle G=\left(N,\Sigma ,P,S\right)}
S
=
w
0
⇒
w
1
⇒
.
.
.
⇒
w
n
=
w
{\displaystyle S=w_{0}\Rightarrow w_{1}\Rightarrow ...\Rightarrow w_{n}=w}
G
{\displaystyle G}
Chomsky-Hierarchie ).
Den zugehörigen Syntaxbaum erhält man, indem man
die Wurzel mit
S
{\displaystyle S}
Kinder
z
i
{\displaystyle z_{i}}
i
∈
{
1
,
.
.
.
,
m
}
{\displaystyle i\in \{1,...,m\}}
A
{\displaystyle A}
w
i
−
1
⇒
w
i
{\displaystyle w_{i-1}\Rightarrow w_{i}}
A
→
z
1
.
.
.
z
m
{\displaystyle A\rightarrow z_{1}...z_{m}}
z
i
∈
N
∪
Σ
{\displaystyle z_{i}\in N\cup \Sigma }
Blätter werden mit
w
{\displaystyle w}
Bei mehrdeutigen Grammatiken können mehrere Ableitungen zum gleichen Baum führen.
Siehe auch
