Árvore de análise sintática

Uma árvore de análise sintática, ou simplesmente árvore sintática, é uma estrutura de dados em árvore, que representa a estrutura sintática de uma cadeia de acordo com alguma gramática formal. Em uma árvore sintática, os nós internos são rotulados por símbolos não-terminais da gramática, enquanto os nós folha são rotuladas por símbolos terminais da gramática. Um programa que produz tais árvores é denominado um analisador sintático. Árvores sintáticas podem ser geradas para sentenças em linguagem natural como também durante o processamento de linguagens formais, tais como as linguagens de programação. É importante notar que a árvore sintática e a árvore sintática abstrata são estruturas de dados diferentes apesar de ambas serem relacionadas a construção de compiladores.

Noções Básicas (Compiladores)

Um árvore sintática é uma árvore onde todos os seus nós são nomeados. Os nós internos são nomeados com os não-terminais da gramática e os nós folha são nomeados com os terminais da gramática. Cada filho de um determinado nó, onde este nó tem associado a ele um não-terminal, representa um passo no processo de derivação de uma expressão reconhecida pela gramática. Uma árvore sintática corresponde a várias derivações possíveis de um expressão. Onde todas estas representam a mesma estrutura básica da expressão analisada. É possível então fazer distinção sobre qual processo de derivação está associado a uma árvore sintática. Uma derivação mais à esquerda é o processo de derivação onde o não terminal mais a esquerda é utilizado para seguir no processo de derivação. Já a derivação mais à direita é o processo de derivação onde o não terminal mais a direita é usado para seguir no processo de derivação. Um exemplo de uma árvore de análise sintática pode ser visto na figura ao lado. Neste exemplo a árvore gerada é a da expressão "true | false". Que é derivada a partir da regra "Boolean '|' Boolean" e as constantes true e false são derivadas a partir do não-terminal Boolean.

Árvore de análise sintática da expressão "true | false"

Referências

• Lounden, Kenneth C (1997). Compiler Construction. Principles and Practice. Boston, MA, USA: PWS Publishing Company. ISBN 0-534-93972-4