Árvores de sintaxe abstrata são estruturas de dados amplamente utilizadas em compiladores para representar a estrutura do código do programa. Um AST é geralmente o resultado da fase de análise de sintaxe de um compilador. Ele freqüentemente serve como uma representação intermediária do programa através de várias etapas que o compilador requer, e tem um forte impacto na saída final do compilador.
MotivationEdit
Um AST tem várias propriedades que auxiliam os passos seguintes do processo de compilação:
- Um AST pode ser editado e melhorado com informações como propriedades e anotações para cada elemento que ele contém. Tal edição e anotação é impossível com o código fonte de um programa, uma vez que implicaria mudá-lo.
- Em comparação com o código fonte, um AST não inclui pontuação e delimitadores essenciais (chaves, ponto e vírgula, parênteses, etc.).
- Um AST normalmente contém informações extras sobre o programa, devido às etapas consecutivas de análise pelo compilador. Por exemplo, ele pode armazenar a posição de cada elemento no código fonte, permitindo ao compilador imprimir mensagens de erro úteis.
ASTs são necessárias devido à natureza inerente das linguagens de programação e sua documentação. As linguagens são frequentemente ambíguas por natureza. A fim de evitar esta ambiguidade, as linguagens de programação são frequentemente especificadas como uma gramática livre de contexto (CFG). No entanto, muitas vezes há aspectos das linguagens de programação que um CFG não consegue expressar, mas são parte da linguagem e estão documentados na sua especificação. Estes são detalhes que requerem um contexto para determinar a sua validade e comportamento. Por exemplo, se uma linguagem permite que novos tipos sejam declarados, um CFG não pode prever os nomes desses tipos nem a forma como eles devem ser usados. Mesmo que um idioma tenha um conjunto pré-definido de tipos, a imposição do uso adequado geralmente requer algum contexto. Outro exemplo é a digitação em pato, onde o tipo de um elemento pode mudar, dependendo do contexto. A sobrecarga do operador é outro caso em que o uso correto e a função final são determinados com base no contexto. Java fornece um excelente exemplo, onde o operador ‘+’ é tanto adição numérica quanto concatenação de strings.
Embora existam outras estruturas de dados envolvidas no funcionamento interno de um compilador, o AST executa uma função única. Durante a primeira etapa, a etapa de análise de sintaxe, um compilador produz uma árvore parse. Esta árvore de análise pode ser usada para executar quase todas as funções de um compilador por meio de uma tradução orientada por sintaxe. Embora este método possa levar a um compilador mais eficiente, ele vai contra os princípios da engenharia de software de escrever e manter programas. Outra vantagem que o AST tem sobre uma árvore parse é o tamanho, particularmente a menor altura do AST e o menor número de elementos.
DesignEdit
O design de um AST está muitas vezes intimamente ligado ao design de um compilador e suas características esperadas.
Requisitos principais incluem o seguinte:
- Os tipos variáveis devem ser preservados, assim como a localização de cada declaração no código fonte.
- A ordem das declarações executáveis deve ser explicitamente representada e bem definida.
- Os componentes esquerdo e direito das operações binárias devem ser armazenados e corretamente identificados.
- Os identificadores e seus valores atribuídos devem ser armazenados para as declarações de atribuição.
Estas exigências podem ser usadas para projetar a estrutura de dados para o AST.
Algumas operações sempre exigirão dois elementos, como os dois termos para adição. Entretanto, algumas construções de linguagem requerem um número arbitrariamente grande de filhos, tais como listas de argumentos passados para programas a partir da shell de comando. Como resultado, um AST usado para representar código escrito em tal linguagem também tem que ser flexível o suficiente para permitir a rápida adição de uma quantidade desconhecida de filhos.
Para suportar a verificação do compilador, deve ser possível desdobrar um AST na forma de código fonte. O código fonte produzido deve ser suficientemente similar ao original na aparência e idêntico na execução, após recompilação.
UsageEdit
O AST é usado intensivamente durante a análise semântica, onde o compilador verifica o uso correto dos elementos do programa e da linguagem. O compilador também gera tabelas de símbolos com base no AST durante a análise semântica. Uma travessia completa da árvore permite a verificação da correção do programa.
Após verificar a correção, o AST serve como base para a geração do código. O AST é frequentemente usado para gerar uma representação intermediária (RI), às vezes chamada de linguagem intermediária, para a geração do código.