Árvore de Derivação

Agora que já aprendemos sobre parsing e suas principais técnicas, vamos avançar para o estudo das árvores de derivação e da árvore de sintaxe abstrata (AST).
No processo de análise sintática, depois que a sequência de tokens é validada, torna-se fundamental representá-la em uma estrutura que evidencie sua hierarquia. Para isso, utilizamos representações em árvore, que organizam visualmente como os elementos da linguagem se relacionam.

Existem dois tipos principais:

• • Árvore de Derivação (Parse Tree): mostra de forma detalhada cada aplicação das regras da gramática, incluindo todos os símbolos terminais e não-terminais.
  • Árvore de Sintaxe Abstrata (AST): apresenta uma versão mais simplificada e próxima da lógica do programa, eliminando símbolos auxiliares e redundâncias, mas preservando a estrutura essencial da sentença.

Árvore de Derivação (Parse Tree)

A Árvore de Derivação é uma representação completa de como uma sentença é formada a partir da gramática. Ela explicita cada regra aplicada, exibindo tanto os símbolos não-terminais quanto os terminais, o que a torna bastante detalhada.

Características principais:

• • Mostra o passo a passo da derivação de acordo com a gramática.
  • Pode se tornar extensa, principalmente em gramáticas com muitos símbolos intermediários.
  • É usada principalmente em contextos acadêmicos e teóricos, pois permite compreender a estrutura formal de uma linguagem.
  • Serve como base para a construção da AST, que é uma versão mais enxuta.

 Exemplo – expressão (2 + 3) * 4: 

                    <expr>
                     /        \
            <expr>         *
             /        \            \

   ( <expr> + <term> )  <factor>
          |        |        |               |
         2       +       3              4

Nesse exemplo, cada parte da gramática está representada explicitamente, o que permite acompanhar como a sentença foi derivada regra por regra.

Material complementar:
Logo abaixo, você encontrará um vídeo do Felipe Louza – UFU que explica em detalhes o conceito de Árvore de Derivação (Parse Tree). Ele mostra passo a passo como uma sentença é gerada a partir das regras da gramática, evidenciando os símbolos terminais e não-terminais. Esse recurso é especialmente útil para consolidar o entendimento sobre a estrutura completa de uma expressão ou programa e para servir de base ao estudo teórico de compiladores e análise sintática.