Syntaxbaum

aus www.iwiki.de, der freien Wissensdatenbank

Ein Syntaxbaum ist eine Baumstruktur die eine syntaktische Struktur einer Zeichenkette entsprechend einer formalen Grammatik darstellt. Ein Programm das einen solchen Syntaxbaum produziert wird Parser genannt. Eingesetzt werden Parser, und damit Syntaxbäume, während der syntaktischen Analyse

Da ein Syntaxbaum ein konkretes Wort darstellt, sind Syntaxbäume geordnet, die Kinder eines Knotens haben also immer eine feste Reihenfolge.

Inhaltsverzeichnis 1 Typen 1.1 konkreter Syntaxbaum (Syntaxbaum) 1.1.1 Beispiel 1.2 abstrakter Syntaxbaum (Parsebaum)

Typen

konkreter Syntaxbaum (Syntaxbaum)

• Die Wurzel des Syntaxbaums ist mit dem Startsymbol S beschriftet.
• Knoten unterhalb der Wurzel sind mit Nichtterminalen beschriftet.
• Die Blätter des Syntaxbaums sind mit Elementen aus dem Alphabet (Terminalen) der Sprache zu dem das Wort gehört beschriftet.

Aus einem konkreten Syntaxbaum sind alle Regeln der Grammatik ablesbar. Anders bei einem abstrakten Syntaxbaum.

Beispiel

Gegeben seien die folgenden Produktionsregeln einer Grammatik:

• 
• 
• 
• 

Ein konkreter Ableitungsbaum für das Wort aab:

                     S
                    / \
                   A   B
                  / \   \
                 a   A   b
                    / \
                   a   A
                        \
                         

abstrakter Syntaxbaum (Parsebaum)

Bei abstrakten Syntaxbäumen werden ausgehend von einem konkreten Syntaxbaum die inneren Knoten mit nur einem Kind weggelassen. Es werden nur die wesentlichen Knoten angezeigt. Diese Bäume werden meistens von Parsern generiert.