Árvore de sintaxe abstrata - Abstract syntax tree

Uma árvore de sintaxe abstrata para o seguinte código do algoritmo euclidiano :
enquanto b ≠ 0 
se a> b
a: = a - b
else
b: = b - a
retornar a

Na ciência da computação , uma árvore de sintaxe abstrata ( AST ), ou apenas árvore de sintaxe , é uma representação em árvore da estrutura sintática abstrata do texto (geralmente código-fonte ) escrito em uma linguagem formal . Cada nó da árvore denota uma construção que ocorre no texto.

A sintaxe é "abstrata" no sentido de que não representa todos os detalhes que aparecem na sintaxe real, mas apenas os detalhes estruturais ou relacionados ao conteúdo. Por exemplo, os parênteses de agrupamento estão implícitos na estrutura da árvore, portanto, não precisam ser representados como nós separados. Da mesma forma, uma construção sintática como uma instrução if-condition-then pode ser denotada por meio de um único nó com três ramificações.

Isto distingue árvore sintática abstrata de árvores de sintaxe de concreto, tradicionalmente designada árvores de análise . Árvores de análise são normalmente construídas por um analisador durante a tradução do código-fonte e o processo de compilação . Depois de construída, informações adicionais são adicionadas ao AST por meio de processamento subsequente, por exemplo, análise contextual .

Árvores de sintaxe abstrata também são usadas em sistemas de análise e transformação de programas .

Aplicação em compiladores

Á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. Geralmente serve como uma representação intermediária do programa por meio de vários estágios que o compilador requer e tem um forte impacto na saída final do compilador.

Motivação

Um AST tem várias propriedades que auxiliam nas etapas seguintes do processo de compilação:

  • Um AST pode ser editado e aprimorado com informações como propriedades e anotações para cada elemento que ele contém. Tal edição e anotação são impossíveis com o código-fonte de um programa, pois implicaria em alterá-lo.
  • Comparado ao código-fonte , um AST não inclui pontuação e delimitadores não essenciais (chaves, ponto-e-vírgulas, parênteses, etc.).
  • Um AST geralmente 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 que o compilador imprima mensagens de erro úteis.

Os ASTs são necessários devido à natureza inerente das linguagens de programação e sua documentação. As línguas são freqüentemente ambíguas por natureza. Para evitar essa ambigüidade, as linguagens de programação são frequentemente especificadas como uma gramática livre de contexto (CFG). No entanto, muitas vezes existem aspectos das linguagens de programação que um CFG não pode expressar, mas são parte da linguagem e estão documentados em sua especificação. São detalhes que requerem um contexto para determinar sua validade e comportamento. Por exemplo, se uma linguagem permite que novos tipos sejam declarados, um CFG não pode prever os nomes de tais tipos nem a maneira como eles devem ser usados. Mesmo se uma linguagem tiver um conjunto predefinido de tipos, a aplicação de um uso adequado geralmente requer algum contexto. Outro exemplo é a digitação de 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 a adição numérica quanto a concatenação de strings.

Embora existam outras estruturas de dados envolvidas no funcionamento interno de um compilador, o AST executa uma função exclusiva. Durante o primeiro estágio, o estágio de análise de sintaxe , um compilador produz uma árvore de análise. Esta árvore de análise pode ser usada para realizar quase todas as funções de um compilador por meio de tradução direcionada à sintaxe. Embora esse 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 de análise é o tamanho, principalmente a altura menor do AST e o menor número de elementos.

Projeto

O design de um AST geralmente está intimamente ligado ao design de um compilador e seus recursos esperados.

Os requisitos principais incluem o seguinte:

  • Os tipos de variáveis ​​devem ser preservados, bem como a localização de cada declaração no código-fonte.
  • A ordem das instruções executáveis ​​deve ser explicitamente representada e bem definida.
  • Os componentes esquerdo e direito das operações binárias devem ser armazenados e identificados corretamente.
  • Os identificadores e seus valores atribuídos devem ser armazenados para instruções de atribuição.

Esses requisitos podem ser usados ​​para projetar a estrutura de dados para o AST.

Algumas operações sempre exigirão dois elementos, como os dois termos para adição. No entanto, algumas construções de linguagem requerem um número arbitrariamente grande de filhos, como listas de argumentos passadas para programas a partir do shell de comando . Como resultado, um AST usado para representar o código escrito em tal linguagem também deve ser flexível o suficiente para permitir a adição rápida de uma quantidade desconhecida de filhos.

Para suportar a verificação do compilador, deve ser possível desparafusar um AST na forma de código-fonte. O código-fonte produzido deve ser suficientemente semelhante ao original na aparência e idêntico na execução, após a recompilação.

Uso

O AST é usado intensamente 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 exatidão do programa.

Depois de verificar a exatidão, o AST serve como base para a geração do código. O AST é freqüentemente usado para gerar uma representação intermediária (IR), às vezes chamada de linguagem intermediária , para a geração de código.

Veja também

Referências

  • Este artigo é baseado em material retirado do Dicionário Online Gratuito de Computação anterior a 1 de novembro de 2008 e incorporado sob os termos de "relicenciamento" do GFDL , versão 1.3 ou posterior.

Leitura adicional

  • Jones, Joel. "Idiomas de implementação de árvore de sintaxe abstrata" (PDF) . Citar diário requer |journal=( ajuda ) (visão geral da implementação de AST em várias famílias de idiomas)
  • Neamtiu, Iulian; Foster, Jeffrey S .; Hicks, Michael (17 de maio de 2005). Compreendendo a evolução do código-fonte usando a correspondência de árvore de sintaxe abstrata . MSR'05. Saint Louis, Missouri: ACM. CiteSeerX  10.1.1.88.5815 .
  • Baxter, Ira D .; Yahin, Andrew; Moura, Leonardo; Sant 'Anna, Marcelo; Bier, Lorraine (16-19 de novembro de 1998). Detecção de clones usando árvores de sintaxe abstrata (PDF) . Proceedings of ICSM'98 . Bethesda, Maryland: IEEE .
  • Fluri, Beat; Würsch, Michael; Pinzger, Martin; Gall, Harald C. "Change Distilling: Tree Differencing para Fine-Grained Source Change Extraction" (PDF) . Citar diário requer |journal=( ajuda )( link direto para PDF )
  • Würsch, Michael. Aprimorando a Detecção de Mudanças no Código-Fonte com base na Árvore Sintaxe Abstrata (Tese de Diploma).
  • Falleri, Jean-Rémy; Morandat, Floréal; Blanc, Xavier; Martinez, Matias; Monperrus, Martin. Diferenciação de código-fonte precisa e refinada (PDF) . Proceedings of ASE 2014 . doi : 10.1145 / 2642937.2642982 .
  • Lucas, Jason. "Reflexões sobre a árvore de sintaxe abstrata do Visual C ++ (AST)" .

links externos