Entrevistadores e problemas LeetCode muitas vezes se concentram em rotar árvores binárias. Mas e sobre transformar uma árvore geral em outra? Como resolvemos este problema, e que abordagens podemos tomar? Vamos explorar isso examinando como traduzimos uma sintaxe em outra árvore. Como chegamos aqui Não é difícil imaginar as razões para transformar uma árvore em outra. 
 
 
 
 Conversão entre diferentes formatos, como XML para HTML. Tarefas algorítmicas, incluindo a infame rotação de árvores binárias. Transformações dentro dos compiladores – não necessariamente de árvore em árvore, mas, por exemplo, converter uma árvore de sintaxe em um gráfico de fluxo de controle. A partir de agora, usarei um termo mais preciso “tradução” em vez de “transformação”. A partir de agora, estamos trabalhando em um sistema de análise de código estático, de modo que o nosso trabalho se sobrepõe aos compiladores em termos de ferramentas. Mas todos os exemplos aqui serão simplificados, por isso não é necessário nenhum conhecimento profundo. São   A tarefa surgiu de uma forma bastante complexa: 
 
 
 
 Queremos suportar mais idiomas – atualmente, lidamos apenas com C#, C/C++ e Java, mas gostaríamos de incluir o JavaScript. Nós, a equipe Java, queremos escrever o novo analisador em (surpreendentemente) Java. O suporte mais abrangente para o JS, juntamente com o suporte futuro para o TS, vem do compilador TypeScript. No entanto, está escrito em um idioma diferente, por isso precisamos transferir o AST através do gRPC. Para maximizar o desempenho, usamos protobuf. Como acabamos com a tradução? 
 
 
 A representação protobuf que recebemos é impossível de analisar diretamente porque a estrutura é imutável, e os objetos perdem sua hierarquia completamente. Ter nosso próprio modelo generalizado parece ser uma boa ideia. Desta forma, evitamos dependendo do front-end de codificação e simplificamos o suporte para novos idiomas. Assim, o nosso nasceu: traduzir a árvore compiladora TypeScript, mastigada pelo protobuf, em nossa própria representação. task O que estamos traduzindo Vamos deixar de lado (por enquanto) os problemas com protobuf, precisamos converter uma árvore em outra. Ambos são árvores de sintaxe para a mesma língua, então as diferenças são menores. A maioria dos nós mapeará isomorficamente um a um, com apenas variações cosméticas. Digamos que um modelo possa usar nome, enquanto os outros usam . do...while repeat...until   Neste caso, a transformação preserva a estrutura "como está" - estamos apenas duplicando.Mas pode haver cenários mais complexos.No JavaScript, por exemplo, há interpolação de string, conhecida como cadeias de modelo. Por alguma razão, a árvore TypeScript combina expressões dentro da interpolação e texto em um único nó, enquanto em outros idiomas, a interpolação consiste de uma lista plana.   Para obter a árvore à direita, precisamos dividir as propriedades da Assim, além da transformação direta de nó a nó, também transformamos uma propriedade em um nó separado. TemplateSpan By the way, a operação reversa seria chamada de agregação - fusão de vários nós em um - mas nossa tarefa não exigia isso. Até agora, tudo parece simples. Mas e se a estrutura de origem não corresponde ao alvo? No contexto da AST, podemos querer normalizar a estrutura para facilitar o trabalho com mais tarde. Por exemplo, sempre adicione um corpo às funções da seta: let a = () -> 1; // source
let a = () -> { return 1 }; // normalized
 Entrar no modo de tela cheia Sair do modo de tela cheia   Aqui, esta é apenas uma regra arbitrária que nos obriga a adicionar nós à árvore que não estavam lá originalmente. Como resultado, temos: 
 
 
 
 Node-to-node transformação: duplicação direta, no máximo mudando o identificador. Transformação de propriedade para nó: criação de elementos de árvore adicionais a partir das propriedades dos nós de origem. um conjunto de regras arbitrárias para normalização, cujo ponto e os sentimentos que eles causam são capturados pela imagem abaixo.   Nós analisamos esses casos um por um, mas uma árvore de sintaxe é construída para todo o arquivo de origem.Na prática, tudo será misturado – e em uma escala enorme. Imagine quantos nós um arquivo com milhares de linhas de código vai conter. let a = 2 + 5 Agora, espero que você tenha uma ideia do que estamos tentando fazer.É hora de passar para a prática. Como escalar a árvore Travessia Antes de decidir como realizar tais transformações, precisamos descobrir como atravessar a árvore da fonte. A primeira solução pode ser criar uma árvore Eu até escrevi um Se o seu objetivo é traduzir uma árvore com um pequeno número de tipos de nós, esta é provavelmente a escolha certa – mas não no nosso caso. iterador Artigo Eu rapidamente contei os diferentes tipos de nós nos diagramas acima: há cerca de — e isso é apenas três exemplos. Em nosso AST para JavaScript, existem atualmente abaixo de origem, e o modelo de origem tem Cada tipo significa um adicional Assim, se quisermos escrever código que possa ser mantido sem lágrimas, é melhor recorrer ao . ten 100 even more if Visitante Pattern Eu não vou ficar sobre sua implementação - você pode verificá-lo através do link acima ou em qualquer outra fonte. Em vez disso, eu só direi que, graças ao duplo envio, o número de condições ao trabalhar com diferentes tipos de nós é quase zero. Travessia de árvore recursiva interface Node {
    void accept(Visitor v);
}

interface Visitor {
    void visitBinary(Binary n);
    void visitLiteral(Literal n);
}

class Binary implements Node {
    private final Node left;
    private final Node right;

    public Binary(Node left, Node right) {
        this.left = left;
        this.right = right;
    }

    @Override public void accept(Visitor v) {
        v.visitBinary(this);
    }
}

class Literal implements Node {
    private final int value;

    public Literal(int value) {
        this.value = value;
    }

    @Override public void accept(Visitor v) {
        v.visitLiteral(this);
    }
}

class Scanner implements Visitor {
    public void scan(Node n) {
        n.accept(this); 
    }

    @Override public Binary visitBinary(Binary n) {
        scan(n.getLeft());
        scan(n.getRight());
    }

    @Override public void visitLiteral(Literal n) {

    }
}
 Entrar no modo de tela cheia Sair do modo de tela cheia E o protobuf? Um leitor atento notará que o protobuf digeriu nosso modelo para travessia, então de que dupla expedição estamos falando? Protobuf nos machucou e nos fez pensar muito, mas, no final, conseguimos imitar um visitante, gerando um cruzeiro baseado em arquivo, que descreve todos os tipos de nós. métodos de tal visitante são bastante comuns: .protoset visit @Override
public void visitBinaryExpression(BinaryExpression binaryExpression) {
    scan(binaryExpression.getToken());
    scan(binaryExpression.getLeft());
    scan(binaryExpression.getRight());
}
 Entrar no modo de tela cheia Sair do modo de tela cheia Isso foi conseguido através de um   Implementação : inocente scan public final void scan(Object node) {
    switch (node) {
      case BinaryExpression binaryExpression ->
          visitBinaryExpression(binaryExpression);
      case UnaryExpression unaryExpression -> 
          visitUnaryExpression(unaryExpression);
      case LiteralExpression literalExpression -> 
          visitLiteralExpression(literalExpression);
      // 121 LOC more
    }
}
 Entrar no modo de tela cheia Sair do modo de tela cheia É difícil chamar essa solução elegante, mas funciona.Então, vamos concordar sobre o seguinte. 
 
 
 Nosso visitante é realmente um pouco incomum. O princípio de funcionamento permanece o mesmo, já que mantemos a capacidade de escrever lógica nos métodos de visita sem declarações manuscritas. Tradução de árvores Ok, nós descobrimos os cenários de tradução e a travessia.Agora podemos finalmente passar para a tradução. O Node-to-Node Vamos começar com o caso mais simples.Se estamos construindo uma árvore, precisamos armazená-la em algum lugar.A maneira mais fácil é devolver o nó atual de cada Se herdarmos do scanner acima, adicionando um valor de retorno genérico e um segundo argumento genérico para métodos de antemão, obtemos algo assim: visit visit interface Visitor<R, P> {
    R visitBinary(Binary n, P parent);
    R visitLiteral(Literal n, P parent);
}

class Builder extends Scanner<JsNode, JsNode> {
    @Override
    public JsNode visitBinary(Binary n, JsNode parent) {
        var left = (JsExpression) scan(n.getLeft());
        var right = (JsExpression) scan(n.getRight());
        return new JsBinary(left, right);
    }

    @Override 
    public JsNode visitLiteral(Literal n, JsNode parent) {
        return new JsLiteral(n.getValue());
    }
}
 Entrar no modo de tela cheia Sair do modo de tela cheia Desta forma muito simples, podemos duplicar a estrutura da árvore. Para evitar confusão, marquei os nós da árvore-alvo com o prefixo no início do nome da classe. Js Propriedade do Node Este caso não é muito mais complicado, mas aqui precisaremos do pai que passamos.Em vez de copiar diretamente, adicionamos um pouco de lógica.Vamos voltar ao mesmo exemplo de interpolação: @Override
public JsNode visitTemplateSpan(TemplateSpan templateSpan, JsNode parent) {
    var interpolation = (Interpolation) parent;
    var expr = new InterpolationExpression();
    interpolation.add(expr);
    interpolation.setExpression(
        scan(templateSpan.getExpression())
    );

    // tail is optional
    if (templateSpan.hasTemplateTail()) {
        interpolation.add(new InterpolationText(
            templateSpan.getTemplateTail().getValue()
        ));
    }

    return null;
}
 Entrar no modo de tela cheia Sair do modo de tela cheia Desde que escapamos Nós voltamos - já anexamos as crianças através do pai passado como uma discussão. TemplateSpan null Normalização Eu expresso minhas emoções com essa imagem na última vez por uma razão – cada caso aqui é único. Às vezes temos sorte, e a normalização é perfeita. normalização se alterar o fluxo de controle ou se O que conta como "muito complicado" permanece ao critério do desenvolvedor e de seu gerente :) avoid too As funções de seta que eu dei como exemplo anteriormente normalizam bastante simplesmente, embora ainda existissem detalhes a serem considerados. O O método parece aproximadamente assim: visit @Override
public JsNode visitArrowFunction(
    ArrowFunction arrowFunction,
    JsNode parent
) {
    var func = new JsArrowFunction();
    // link inside
    scan(arrowFunction.getParameterDeclarationList(), func);

    // OK
    if (arrowFunction.hasBlock()) {
        func.setBlock(
            scan(arrowFunction.getBlock())
        );
    } else if (arrowFunction.hasExpression()) {
        var normalized = normalizeArrow(
            arrowFunction
        );
        func.setBlock(normalized);
    }

    return func;
}
 Entrar no modo de tela cheia Sair do modo de tela cheia A transformação está escondida em : normalizeArrow public JsBlock normalizeArrow(ArrowFunction f) {
    var block = new JsCodeBlock();
    block.setFlag(Flag.SYNTHETIC);

    var ret = new JsReturn();
    ret.setFlag(Flag.SYNTHETIC);
    block.addStatement(ret);

    var expr = scan(f.getExpression());
    ret.setExpression(expr);

    return block;
}
 Entrar no modo de tela cheia Sair do modo de tela cheia Além de criar esses nós, também os marcamos como sintéticos, uma vez que eles não estavam presentes na árvore inicial - tratando-os efetivamente como "virtuais".É útil na análise estática - para heurísticas em regras de diagnóstico, podemos explicar o fato de que o desenvolvedor não escreveu coisas como — é apenas um artefato de nossas transformações.Ok, isso é tudo para as transformações. (var) -> { return console.log(var) } O elefante na sala Neste ponto, cobrimos todos os princípios básicos relacionados com a solução da tarefa. 
 
 
 
 
 Nós atravessamos recursivamente, preservando o estado atual da árvore através dos parâmetros e valores de retorno dos métodos de visita. Existem duas transformações típicas: node-to-node e propriedade-to-node. Temos uma transformação atípica: a normalização da árvore. Como resultado da tradução, obtemos uma árvore semelhante – mas uma nova, diferente em detalhes. Tudo o que resta é resolver a tarefa.Deixe-me lembrar: a árvore-alvo tem   A árvore da fonte tem Esta diferença é em grande parte devido às especificidades do protobuf.   e Métodos Pronto para uma corrida dessas? 100 node types 263 types hand-write visit scan hundreds or thousands of times   A solução para o problema já apareceu no texto, assim como o cruzeiro original poderia ser gerado com base no arquivo, então as regras de tradução típicas podem ser geradas com base em alguma regra de configuração.Mas vamos cobrir isso - e como se encaixar na normalização atípica - em outro momento. .protoset Depois do Este é o tipo de caso que eu encontrei no meu trabalho. embora eu tenha apenas esculpido a superfície, eu toquei em vários pontos interessantes: transformações típicas, a escolha entre um iterador e um visitante, uma implementação de visitante não trivial. Nós também olhamos para ele através da lente da análise estática - nós sintéticos e a abordagem para a normalização. Em qualquer caso, espero que você tenha aprendido algo novo sobre o trabalho com árvores.Não perca artigos sobre este tópico ou sobre novos analisadores em geral - assine o PVS-Studio Nosso artigo mensal Você é bem-vindo a experimentar a ferramenta gratuitamente . O Twitter Digestão aqui Se você quiser seguir meus posts, assine o meu pessoal . Blog do

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Read My Stories

Este áudio é produzido no idioma original da história!

O elefante na sala: por que esta tradução AST deve ser gerada por código

About Author

COMENTARIOS

Rótulos

ESTE ARTIGO FOI APRESENTADO EM

Related Stories

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Navegando pelas águas: desenvolvendo aplicações RAG de nível de produção com data lakes

Criando produtos criptográficos centrados no usuário: a importância do feedback do cliente

O guia completo para uma migração bem-sucedida para a nuvem: estratégias e práticas recomendadas

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Navegando pelas águas: desenvolvendo aplicações RAG de nível de produção com data lakes

Criando produtos criptográficos centrados no usuário: a importância do feedback do cliente

O guia completo para uma migração bem-sucedida para a nuvem: estratégias e práticas recomendadas

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps