Árvore de análise sintática
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2018) |
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) editar
|
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 |
 |
Referências editar
- Lounden, Kenneth C (1997). Compiler Construction. Principles and Practice. Boston, MA, USA: PWS Publishing Company. ISBN 0-534-93972-4