Árvores de sintaxe abstrata em programação: um guia completo

Informatec Digital » Recursos » Árvores de sintaxe abstrata em programação: um guia completo

Árvores de sintaxe abstrata em programação são um daqueles conceitos que inicialmente soam muito teóricos, mas, uma vez que você se familiariza com eles, percebe que estão em toda parte: compiladores, interpretadores , análise de código, ferramentas de refatoração e até mesmo em linguagens de consulta de dados estruturados. Elas são, essencialmente, a maneira como uma máquina "entende" a estrutura de um programa além do texto simples.

Embora às vezes confundidas com árvores de análise sintática clássicas, as árvores de sintaxe abstrata (ASTs) têm suas próprias regras. Uma árvore de sintaxe abstrata não é apenas um desenho bonito: é uma estrutura de dados compacta e bem projetada que elimina tudo o que é supérfluo na sintaxe concreta (parênteses, vírgulas, palavras-chave redundantes, etc.) e se concentra no essencial: quais operações são realizadas, sobre quais valores e em que ordem.

O que exatamente é uma árvore sintática abstrata (AST)?

Na teoria de linguagens de programação, uma árvore sintática abstrata (AST) é uma estrutura em forma de árvore que representa a sintaxe de um programa, mas de forma simplificada em comparação com uma árvore de análise sintática concreta. Ela contém as mesmas informações essenciais que uma árvore de análise sintática, porém organizadas de maneira mais compacta e gerenciável.

Uma árvore de análise sintática contém todas as produções da gramática e todos os símbolos terminais, incluindo parênteses, vírgulas, ponto e vírgula e outros elementos puramente sintáticos. A AST, por outro lado, remove esses detalhes que não contribuem para o significado semântico e retém apenas a estrutura lógica das expressões e frases.

Em termos de implementação, uma AST geralmente é composta de objetos de nó com um tipo que indica que tipo de construção sintática ela é (constante, identificador, aplicação de função, operador binário, etc.) e propriedades adicionais que descrevem seu conteúdo: valor, nome, filhos, lista de argumentos e assim por diante.

A beleza da AST reside no fato de que ela facilita as fases posteriores do compilador ou interpretador, como verificação de tipos, otimizações ou geração de código , pois oferece uma visão clara da estrutura do programa, sem ruído sintático.

Diferença entre uma árvore sintática concreta e uma árvore sintática abstrata

Para entender completamente a contribuição de uma AST, é útil primeiro comparar a árvore de análise sintática concreta com a abstrata. Imagine uma gramática simples que reconhece expressões aritméticas como "a + 4 * 5" . A árvore de análise sintática concreta reflete com precisão a aplicação de cada regra gramatical: símbolos não terminais, terminais, parênteses, operadores, etc.

Essa árvore em particular costuma ser profunda e possui muitos nós intermediários que servem apenas para manter a estrutura formal da gramática. Por exemplo, pode haver nós para "Expressão", "Termo", "Fator" e, em seguida, símbolos terminais como "+" , "*" , identificadores e números. Cada produção se torna um ramo da árvore, aumentando a complexidade estrutural.

A árvore sintática abstrata para essa mesma expressão, por outro lado, limita-se a representar as operações e operandos reais . Assim, em vez de vários níveis de "Expressão" e "Termo", poderíamos ter um nó raiz representando a adição, com dois filhos: à esquerda, um identificador a e, à direita, um nó de multiplicação cujos filhos são os valores 4 e 5. Nós puramente gramaticais desaparecem e partes da estrutura são reordenadas ou condensadas.

Isso significa que a AST e a árvore sintática concreta contêm as mesmas informações semânticas , mas a primeira as apresenta de forma muito mais direta e compacta. Essa condensação é fundamental para trabalhar de forma eficiente com o código em ferramentas de análise ou execução.

Árvores e alfabetos com função de aridade

Para formalizar essas árvores do ponto de vista matemático, geralmente se utiliza a ideia de um alfabeto com uma função de aridade . Em vez de simplesmente um conjunto de símbolos, define-se um alfabeto no qual cada símbolo está associado a um número que indica quantos filhos ele pode ter na árvore.

Um alfabeto com função de aridade é, informalmente, um par constituído por um conjunto finito de símbolos e uma função que atribui a cada símbolo um número natural (incluindo zero). Esse número indica a aridade do símbolo: se for 0, o símbolo comporta-se como uma folha; se for 1, comporta-se como um nó unário; se for 2, é binário; e assim por diante. Também é comum permitir símbolos de aridade variável para operadores como listas de argumentos.

Símbolos de aridade 0 correspondem às folhas da árvore (por exemplo, constantes ou identificadores). Símbolos de aridade 1 são usados ​​para construções que envolvem uma única expressão filha. Símbolos de aridade 2 representam operações binárias clássicas, como adição, multiplicação, atribuição, etc. E símbolos de aridade variável permitem modelar construções que aceitam um número indeterminado de subárvores, como uma chamada de função com múltiplos parâmetros.

A partir desse alfabeto com aridade, o conjunto de todas as árvores possíveis pode ser definido: começando com a árvore vazia (quando considerada), adicionando todos os símbolos de aridade 0 e variável, e estendendo indutivamente: se um símbolo é k-ário, ele pode ser colocado como o nó pai de k subárvores já construídas. Isso resulta na linguagem (ou termo) de árvores associada ao alfabeto.

Linguagem de árvores e a noção de um nó

O conjunto de todas as árvores formadas com um alfabeto e sua função de aridade é chamado, neste contexto, de linguagem de árvores ou linguagem de termos . É o equivalente, mas para estruturas de árvores, ao que o fecho de Kleene é para cadeias de caracteres.

Assim como na análise de strings usamos o termo tokens para nos referirmos às ocorrências de símbolos do alfabeto em uma sequência, ao trabalhar com árvores geralmente usamos o termo nós . Um nó é, essencialmente, uma ocorrência específica de um símbolo do alfabeto com aridade localizada em uma posição particular na árvore.

Dessa perspectiva, essa linguagem em árvore é para os nós o que um conjunto de strings é para as ocorrências de tokens. Cada árvore é interpretada como uma estrutura construída passo a passo a partir do alfabeto, e os nós são as peças individuais que materializam fisicamente seus símbolos.

Essa perspectiva é muito útil no desenvolvimento de analisadores sintáticos e geradores de AST (Árvore Sintática Abstrata) , pois permite raciocinar sobre as regras de construção dessas árvores de maneira análoga à gramática de strings, mas trabalhando diretamente com estruturas hierárquicas.

Aridade dos nós em uma AST específica: o caso do ovo

Passando da teoria para um exemplo prático, muitos materiais didáticos utilizam a linguagem Egg para ilustrar a construção e manipulação de ASTs (Árvores Sintáticas Abstratas). Nesse contexto, são utilizados diversos tipos principais de nós, cada um com uma aridade bem definida , o que facilita bastante a sua manipulação.

Em uma AST típica do Egg, os nós VALUE são considerados folhas: eles representam literais como strings ou números. Eles não têm filhos; armazenam apenas um valor. Da mesma forma, os nós WORD , que são usados ​​para identificadores (nomes de variáveis, nomes de funções, etc.), também são tratados como folhas com uma propriedade que armazena o nome.

O nó chave em Egg é o tipo APPLY , que representa a aplicação de uma função ou operador. Este tipo de nó possui dois filhos conceituais: um filho OPERATOR que aponta para a expressão que está sendo aplicada; e um filho ARGS , que na verdade é um nó ARRAY especial responsável por manter uma coleção de subárvores, uma para cada argumento.

Portanto, os arrays são uma maneira natural de introduzir aridade variável na AST: um APPLY sempre tem dois componentes (operador e lista de argumentos), mas essa lista interna pode conter zero, uma ou várias subárvores, dependendo da chamada específica que está sendo representada.

Anatomia detalhada dos linfonodos AST no ovo

Em termos de implementação, os nós da AST do Egg são tipicamente representados como objetos com propriedades , o que se encaixa perfeitamente com linguagens como JavaScript. Todos os nós compartilham uma propriedade comum: `type` , que identifica o tipo do nó (VALUE, WORD, APPLY, ARRAY, etc.) e, portanto, a estrutura que o restante do objeto terá.

Os nós VALUE são usados ​​para constantes literais . Eles contêm uma propriedade, geralmente chamada de valor , onde o número ou a string que representam é armazenado. Eles não possuem filhos adicionais porque seu conteúdo é completamente descrito por esse literal.

Os nós de palavra são reservados para identificadores : nomes de variáveis, nomes de funções, nomes de parâmetros e similares. Normalmente, possuem uma propriedade `name` que armazena o identificador como uma string. Semelhantes aos nós de valor, atuam como folhas na árvore, pois seu único propósito é fornecer esse nome.

Os nós de aplicação representam aplicações ou chamadas. Eles incluem uma propriedade `operator` , que aponta para a expressão (outro nó) que está sendo aplicada, e uma propriedade `args` , que se vincula a um nó `ARRAY`. Este último é um nó específico dentro da AST, cuja finalidade é armazenar a lista de argumentos da aplicação .

O nó ARRAY pode ser entendido como um contêiner estruturado para outros nós, representando uma sequência de subárvores. Do ponto de vista da aridade, ele introduz flexibilidade porque permite chamadas sem argumentos, com um argumento ou com múltiplos argumentos dentro da mesma instrução APPLY, sem a necessidade de alterar a definição do tipo de nó principal.

Exemplo de AST: aplicação simples com um valor

Para visualizar tudo isso, vamos pensar na representação de uma instrução simples, como a aplicação de uma função X com um único argumento 5. A AST gerada pelo analisador sintático corresponde a um termo construído com nós VALUE, WORD e APPLY , seguindo as regras de Egg.

Em um nível conceitual, teríamos um nó APPLY na raiz. Sua propriedade operator apontaria para um nó WORD chamado X, e sua propriedade args se referiria a um nó ARRAY contendo um único elemento: um nó VALUE com o valor numérico 5. Dessa forma, a estrutura reflete claramente a quem e ao que a aplicação está sendo feita.

Se quiséssemos explicitar todos os atributos, poderíamos escrever uma notação mais detalhada mostrando o tipo, o operador, os argumentos, o nome e o valor. Essa notação mais verbosa é muito útil para depurar o analisador sintático ou para entender como uma expressão textual é traduzida em um objeto de árvore dentro do interpretador.

Em implementações reais, essa árvore é normalmente serializada como JSON para facilitar o armazenamento, a transmissão ou a inspeção. De fato, ferramentas e módulos, como o pacote evm2term no ecossistema npm, fornecem representações compactas dessas ASTs para facilitar a análise ou transformação.

Exemplo de AST: adição e multiplicação aninhadas

Outro caso típico é uma expressão um pouco mais complexa, como "+(a, *(4, 5))" . Aqui temos uma operação de adição cujo primeiro argumento é o identificador a e cujo segundo argumento é o resultado da multiplicação de 4 por 5. A AST resultante dessa expressão reflete essa estrutura aninhada.

Na raiz da árvore, teríamos novamente um nó APPLY representando a operação de adição. Seu operador seria um nó WORD chamado "+", enquanto seus argumentos estariam em um nó ARRAY com dois elementos: o primeiro, um WORD chamado "a"; o segundo, outro nó APPLY representando a multiplicação.

Essa segunda instrução APPLY teria como operador uma PALAVRA chamada "*" e como argumentos um ARRAY com dois nós VALUE: um com o valor 4 e o outro com o valor 5. Vista como um todo, a estrutura mostra claramente que a ordem de avaliação consiste em multiplicar 4 por 5 e, em seguida, adicionar o resultado a a.

Se expandirmos a notação para incluir todos os atributos, veremos os tipos de todos os nós, seus nomes ou valores específicos e os relacionamentos entre eles. Essa descrição explícita corresponde à implementação real no interpretador Egg, onde cada nó é um objeto com as propriedades mencionadas.

Gramática de árvore e gramática de analisador sintático

A forma como essas ASTs são geradas não é arbitrária: ela se baseia no que é chamado de Gramática de Árvore . Em uma formulação típica, tal gramática é definida como uma quádrupla composta por um alfabeto com aridade, um conjunto finito de variáveis ​​sintáticas (não terminais), um conjunto finito de regras de produção e um símbolo inicial.

Em cada regra de produção, uma variável é substituída por uma árvore cuja raiz é um símbolo do alfabeto com aridade, e cujos filhos são, por sua vez, variáveis ​​ou árvores já definidas. Essa estrutura lembra as gramáticas regulares ou livres de contexto clássicas, mas adaptada à geração direta de árvores em vez de sequências de símbolos.

Relacionada a essa definição mais formal está a gramática específica que o analisador sintático do Egg usa para produzir suas árvores. Essa gramática, geralmente apresentada informalmente na documentação, descreve exatamente quais combinações de palavras-chave, operadores, parênteses e assim por diante são aceitas na linguagem e como elas se traduzem em nós dos tipos VALUE, WORD, APPLY e ARRAY.

Essa gramática de árvore pode ser vista como um caso especial do que é conhecido na literatura como Gramática de Árvore Regular . A ideia é ter regras bem definidas para converter uma sequência de tokens de entrada em uma AST estruturada que possa então ser interpretada ou compilada.

Notação de Dewey: coordenadas dentro de uma árvore

Uma vez que temos a AST (Árvore Sintática Abstrata), frequentemente precisamos nos referir a subárvores específicas : por exemplo, o segundo argumento de uma função, o operador de uma expressão, etc. Uma maneira muito elegante de fazer isso é a chamada notação decimal de Dewey, que utiliza o esquema empregado para numerar seções e subseções em documentos.

Nessa notação, partindo de uma árvore t, uma subárvore é representada por uma sequência de números separados por pontos . Cada número indica a posição de um filho (geralmente começando em 1) e a sequência desce na árvore. Assim, uma expressão como t/2.1.3 refere-se ao terceiro filho do primeiro filho do segundo filho de t.

A definição indutiva dessa notação é simples: a string vazia se refere à árvore inteira; se uma string consiste em um número seguido por mais números separados por pontos, ela é interpretada tomando-se primeiro a subárvore filha correspondente ao índice indicado e, em seguida, aplicando-se a mesma lógica recursivamente ao restante da string.

Por exemplo, se tivermos uma árvore t que representa uma expressão como "+(a, *(4,5))", com um nó raiz APPLY para adição, um nó filho WORD chamado "+" e outro nó filho APPLY para multiplicação, podemos identificar posições específicas. Assim, t/1 poderia ser o nó WORD com o operador "+", t/2.1 o identificador "a" e t/2.2.2.1 o nó VALUE com o valor 4, se numerarmos os filhos adequadamente.

Essa forma de fornecer "coordenadas" dentro de uma AST é muito útil para indicar locais específicos ao relatar erros, navegar na árvore ou aplicar transformações locais a nós específicos sem ambiguidade.

Notações equivalentes em programação e ferramentas

A ideia por trás da notação de Dewey não é exclusiva da teoria das árvores; na verdade, ela aparece repetidamente em muitas notações práticas que usamos diariamente em programação e manipulação de dados estruturados, mesmo que nem sempre tenhamos consciência disso.

Quando escrevemos expressões com o operador ponto em uma linguagem de programação , como objeto.propriedade.subpropriedade, estamos fazendo algo muito semelhante: percorrendo uma árvore de objetos aninhados, selecionando um filho a cada passo pelo nome, em vez de pelo número da posição. Partindo de um nó raiz, descemos para nós mais internos.

O mesmo padrão aparece em sistemas de arquivos do tipo Unix, onde o operador de barra (/) é usado para separar diretórios: /src/js/tutu.js descreve um caminho da raiz do sistema de arquivos até um recurso específico, percorrendo níveis sucessivos de uma estrutura em árvore.

No mundo dos documentos estruturados, linguagens como XPath usam notações muito semelhantes para selecionar nós em uma árvore XML. Uma consulta como "A//B/*" escolhe o primeiro filho (qualquer que seja o seu nome) de cada elemento B que seja descendente de um elemento A na posição apropriada em relação ao contexto atual, usando barras simples e duplas para indicar níveis de profundidade.

Outra ferramenta bastante conhecida, a linguagem jq , utiliza um sistema paralelo para navegar em estruturas JSON, permitindo a seleção de subobjetos por meio de caminhos compostos, filtros e expressões. Todas essas notações são simplesmente maneiras diferentes de expressar caminhos em uma árvore , muito semelhantes à notação decimal de Dewey, mas adaptadas aos seus respectivos domínios.

Árvores de análise sintática em linguística e programação

Além do mundo dos compiladores, as árvores sintáticas também são usadas na linguística para representar a estrutura das frases. Nesse contexto, elas são chamadas de árvores de derivação ou árvores de análise sintática, que mostram como uma frase é decomposta em sintagmas, palavras e categorias gramaticais.

Nessas árvores, assim como na programação, encontramos três tipos básicos de nós: um nó raiz , que representa a frase completa ou a estrutura global; nós internos ou de ramificação, que funcionam como nós pais e agrupam subconjuntos da frase; e nós folha, que geralmente correspondem às palavras específicas que aparecem na string de entrada.

O nó raiz é único: toda a estrutura da árvore se sustenta a partir dele. Os nós de ramificação estão localizados imediatamente abaixo da raiz ou de outros nós pais e servem para organizar hierarquicamente as partes da sentença ou do programa. Os nós folha, por outro lado, encontram-se no nível mais baixo da árvore e não possuem filhos, fechando assim a estrutura de ramificação.

Essas árvores são consideradas ferramentas pedagógicas poderosas porque ajudam a decompor frases complexas em elementos gerenciáveis. O mesmo se aplica à programação: uma AST bem construída permite visualizar rapidamente quais operações estão encadeadas, quais expressões estão aninhadas e como o fluxo de avaliação ocorre.

Dependendo do objetivo da análise, podemos encontrar diferentes tipos de árvores de análise . Algumas enfatizam as dependências entre palavras ou componentes (por exemplo, quem depende de quem em uma frase), enquanto outras se concentram no agrupamento em sintagmas ou constituintes, resultando em duas famílias principais.

Árvores sintáticas por dependência e por constituinte

Um dos tipos mais conhecidos é a árvore sintática baseada em dependências . Nessa variante, todas as palavras da frase ou todos os elementos relevantes são tratados como nós folha, e as ligações entre eles indicam relações de dependência direta (por exemplo, um verbo principal e seu sujeito). Como resultado, árvores com menos nós são frequentemente produzidas em comparação com outros esquemas.

Essa simplicidade as torna especialmente convenientes para iniciantes e para certas tarefas de processamento de linguagem, pois a estrutura se concentra em quem depende de quem, sem introduzir tantos nós intermediários. Aplicada à programação, a ideia é ater-se apenas às relações essenciais, omitindo floreios gramaticais.

No outro extremo, temos árvores sintáticas baseadas em constituintes, que distinguem entre nós raiz, nós de ramificação interna e nós folha, e tornam visíveis todos os agrupamentos relevantes. Essas árvores geralmente contêm mais nós e refletem a estrutura hierárquica da sentença ou do programa com maior detalhe.

Os modelos de árvore de constituintes mais comuns exibem frases longas com inúmeros nós folha, vários níveis de ramificação e um nó raiz bem definido. Eles são especialmente úteis para analisar frases complexas ou programas com múltiplas camadas de estruturas aninhadas.

Tanto nas árvores de dependência quanto nas de constituintes, exemplos e recursos visuais estão disponíveis como modelos, permitindo que você simplesmente preencha os nós com as informações desejadas. Isso economiza tempo e evita a necessidade de criar o diagrama do zero sempre que você quiser ilustrar uma estrutura.

Aplicações práticas e ferramentas relacionadas à AST

As Árvores Sintáticas Abstratas (ASTs) não são apenas um conceito teórico: elas são ativamente utilizadas em uma infinidade de ferramentas do dia a dia por qualquer pessoa que trabalhe com código. Compiladores, interpretadores, minificadores, formatadores de código e analisadores estáticos quase sempre dependem de uma AST para executar suas funções.

Um compilador típico pega o código-fonte, o tokeniza, o analisa e gera uma árvore sintática abstrata. A partir daí, realiza verificações semânticas (tipos, escopo de variáveis, usos incorretos de construções) e aplica otimização de código percorrendo e transformando a árvore sintática abstrata antes de produzir o código de máquina, ou bytecode.

Ferramentas como linters ou formatadores também funcionam na AST: elas analisam a estrutura para detectar padrões problemáticos, más práticas ou inconsistências e propõem alterações que mantêm a estrutura semântica da árvore, mas ajustam a apresentação do código.

No ecossistema JavaScript, por exemplo, existem diversas bibliotecas que expõem a AST em formato JSON, facilitando o uso por outras ferramentas para realizar refatorações, gerar documentação automática ou criar visualizações da estrutura de programas complexos.

Mesmo em áreas um pouco mais especializadas, como instrumentação para medir a cobertura de testes ou a transformação de código-fonte em outras linguagens, a AST (Árvore Sintática Abstrata) é a base sobre a qual muitas soluções modernas se fundamentam, pois permite trabalhar em um nível de abstração bastante confortável entre o texto bruto e o código de máquina.

Em conjunto, as árvores de sintaxe abstrata são a peça-chave que conecta a gramática formal de uma linguagem, sua representação interna no compilador ou interpretador e as ferramentas avançadas que usamos para escrever, analisar e transformar código de forma segura e eficiente. Compreender como elas são construídas, como navegar por elas (com conceitos como a notação decimal de Dewey) e quais tipos de nós estão envolvidos (VALOR, PALAVRA, APLICAR, estruturas de aridade fixa ou variável, etc.) nos ajuda a ver com muito mais clareza o que a máquina está realmente fazendo ao processar um programa.