Drzewo składniowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Drzewo składniowe, drzewo AST (ang. abstract syntax tree) czyli drzewo składni abstrakcyjnej - drzewo etykietowane, wynik przeprowadzenia analizy składniowej zdania (słowa) zgodnie z pewną gramatyką. Każdy węzeł wewnętrzny tego drzewa reprezentują pewną konstrukcję języka, a jego synowie znaczące składowe tej konstrukcji.

W drzewie składniowym, w przeciwieństwie do drzewa wyprowadzenia, pomijane są mało znaczące symbole np. nawiasy, średniki, przecinki. Drzewo składniowe dla wyrażeń arytmetycznych w węzłach wewnętrznych będzie zawierać operatory, zaś w liściach stałe i identyfikatory zmiennych.

Drzewo informatyka.svg


na drzewie opisane jest wyrażenie:
A(B(E,F),C,D(G(I),H(J,K,L)))

  • A i H to operacje trójargumentowe
  • B i D to operacje dwuargumentowe (binarne)
  • G to operacja jednoargumentowa (unarna lub unitarna)
  • E F C I J K L to argumenty

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory : reguły, metody i narzędzia. Warszawa: WNT, 2002. ISBN 83-204-2656-1.
  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Compilers: Principles, Techniques, and Tools (Second Edition). Addison Wesley, 2007. ISBN 0-321-48681-1.