Los entrevistadores y los problemas de LeetCode a menudo se centran en rotar árboles binarios. Pero ¿qué pasa con transformar un árbol general en otro? ¿Cómo solucionamos este problema, y qué enfoques podemos tomar? Exploremos esto examinando cómo traducimos una sintaxis en otro árbol. Cómo llegamos aquí No es difícil imaginar las razones para transformar un árbol en otro. 
 
 
 
 Convertir entre diferentes formatos, como XML a HTML. Tareas algorítmicas, incluyendo la infame rotación de árboles binarios. Transformaciones dentro de los compiladores, no necesariamente de árbol a árbol, sino, por ejemplo, convertir un árbol de sintaxis en un gráfico de flujo de control. A partir de ahora, usaré un término más preciso “traducción” en lugar de “transformación”. En el estudio PVS-Studio, desarrollamos análisis de código estático, por lo que nuestro trabajo se sobrepone con compiladores en términos de herramientas. Pero todos los ejemplos aquí serán simplificados, por lo que no se requiere experiencia profunda. Este   La tarea surgió de una manera bastante compleja: 
 
 
 
 Queremos soportar más idiomas, actualmente solo manejamos C#, C/C++ y Java, pero nos gustaría incluir JavaScript. Nosotros, el equipo de Java, queremos escribir el nuevo analizador en (sorprendentemente) Java. El soporte más completo para JS, junto con el futuro soporte para TS, proviene del compilador TypeScript. Sin embargo, está escrito en un idioma diferente, por lo que debemos transferir el AST a través de gRPC. Para maximizar el rendimiento, usamos protobuf. ¿Cómo acabamos con la traducción? 
 
 
 La representación de protobuf que recibimos es imposible de analizar directamente porque la estructura es inalterable, y los objetos pierden su jerarquía por completo. Tener nuestro propio modelo generalizado parece una buena idea.De esta manera, evitamos dependiendo del frontend de codificación y simplificamos el soporte para nuevos idiomas. Así, nuestro nació: Traducir el árbol del compilador TypeScript, masticado por protobuf, en nuestra propia representación. task Lo que estamos traduciendo Vamos a poner de lado (por ahora) los problemas con protobuf, necesitamos convertir un árbol en otro. Ambos son árboles de sintaxis para el mismo idioma, por lo que las diferencias son menores. La mayoría de los nodos mapearán isomorficamente uno a uno, con sólo variaciones cosméticas. Digamos, un modelo podría usar el nombre, mientras que el otro utiliza . do...while repeat...until   En este caso, la transformación mantiene la estructura "como está" -estamos simplemente duplicándola.Pero pueden existir escenarios más complejos.En JavaScript, por ejemplo, hay interpolación de cuerdas, conocida como cuerdas de plantilla. Por alguna razón, el árbol de TypeScript combina expresiones dentro de la interpolación y el texto en un único nodo, mientras que en otros idiomas, la interpolación consiste en una lista plana.   Para obtener el árbol a la derecha, necesitamos dividir las propiedades de la nodo en dos (o menos) nodos. por lo tanto, además de la transformación directa de nodo a nodo, también transformamos una propiedad en un nodo separado. TemplateSpan Por cierto, la operación inversa se llamaría agregación, fusionando varios nodos en uno, pero nuestra tarea no lo requería. Hasta ahora, todo parece sencillo.Pero qué pasa si la estructura de origen no coincide en absoluto con la meta?En el contexto de AST, podríamos querer normalizar la estructura para que sea más fácil trabajar con más adelante.Por ejemplo, siempre añade un cuerpo a las funciones de flecha: let a = () -> 1; // source
let a = () -> { return 1 }; // normalized
 Entrar en modo de pantalla completa Salir en modo de pantalla completa   Aquí, esta es solo una regla arbitraria que nos obliga a añadir nodos al árbol que no estaban allí originalmente. Como resultado, tenemos: 
 
 
 
 Transformación de nodo a nodo: Duplicación directa, al máximo cambiando el identificador. Transformación de propiedad a nodo: Creación de elementos de árboles adicionales a partir de las propiedades de los nodos de fuente. un conjunto de reglas arbitrarias para la normalización, cuyo punto y los sentimientos que causan son capturados por la imagen de abajo.   Hemos examinado estos casos uno por uno, pero se construye un árbol de sintaxis para todo el archivo de origen. En la práctica, todo se mezclará -y a gran escala. Imagina cuántos nodos contendrá un archivo con miles de líneas de código. let a = 2 + 5 Por ahora, espero que tengas un sentido de lo que estamos tratando de hacer.Es hora de pasar a la práctica. Cómo subir al árbol Travesía Antes de decidir cómo realizar tales transformaciones, necesitamos averiguar cómo cruzar el árbol de la fuente. La primera idea podría ser implementar un árbol Incluso he escrito un Si tu objetivo es traducir un árbol con un pequeño número de tipos de nodos, esta es probablemente la elección correcta, pero no en nuestro caso. iterador Artículo Conté rápidamente los diferentes tipos de nodos en los diagramas de arriba: hay aproximadamente —y eso son solo tres ejemplos. En nuestro AST para JavaScript, hay actualmente bajo tipo, y el modelo de fuente tiene Cada uno de ellos supone un suplemento declaración al decidir cómo manejar un nodo. por lo tanto, si queremos escribir código que pueda mantenerse sin lágrimas, es mejor recurrir al . ten 100 even more if Patrocinador Visitante No me detendré en su implementación -puede comprobarlo a través del enlace de arriba o en cualquier otra fuente. En lugar de eso, simplemente diré que gracias al doble envío, el número de condiciones cuando se trabaja con diferentes tipos de nodos es casi cero. Travesía recursiva de árboles 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 en modo de pantalla completa Salir en modo de pantalla completa ¿Y el prototipo? Un lector atento notará que el protobuf ha digerido nuestro modelo para la travesía, así que ¿de qué doble envío estamos hablando? Protobuf nos hizo daño nos hizo pensar duro. pero al final, logramos emular a un visitante generando un crucer basado en una archivo, que describe todos los tipos de nodos. Los métodos de tal visitante son bastante comunes: .protoset visit @Override
public void visitBinaryExpression(BinaryExpression binaryExpression) {
    scan(binaryExpression.getToken());
    scan(binaryExpression.getLeft());
    scan(binaryExpression.getRight());
}
 Entrar en modo de pantalla completa Salir en modo de pantalla completa Lo conseguimos a través de un   La Implementación: 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 en modo de pantalla completa Salir en modo de pantalla completa Es difícil llamar esta solución elegante, pero funciona. 
 
 
 Nuestro visitante es realmente un poco inusual. El principio de funcionamiento permanece el mismo, ya que mantenemos la capacidad de escribir lógica en los métodos de visita sin declaraciones escritas a mano. Traducción de árboles Bueno, nos enteramos de los escenarios de traducción y de la travesía.Ahora por fin podemos pasar a la traducción. Nódulo de Nódulo Comencemos con el caso más simple.Si estamos construyendo un árbol, necesitamos almacenarlo en algún lugar.La forma más fácil es devolver el nodo actual de cada Si heredamos del escáner anterior, agregando un valor de retorno genérico y un segundo argumento genérico para métodos de antemano, obtenemos algo así: 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 en modo de pantalla completa Salir en modo de pantalla completa De esta manera muy simple, podemos duplicar la estructura del árbol. Para evitar confusión, marco los nodos del árbol objetivo con el prefijo al principio del nombre de la clase. Js Propiedad de Node Este caso no es mucho más complicado, pero aquí necesitaremos al padre que pasamos. En lugar de copiar directamente, añadimos un poco de lógica. Volvamos al mismo ejemplo de interpolación: @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 en modo de pantalla completa Salir en modo de pantalla completa Desde que salimos Nosotros volvemos — ya hemos adherido a los niños a través del padre pasado como una discusión. TemplateSpan null Normalización Expresé mis emociones con esa imagen la última vez por una razón —cada caso aquí es único.A veces tenemos suerte, y la normalización va sin problemas.Otras veces, es un problema.En general, adoptamos la siguiente regla del pulgar: normalización si cambia el flujo de control o es Lo que cuenta como "demasiado complicado" permanece a la discreción del desarrollador y su gerente :) avoid too Las funciones de flecha que di como ejemplo anteriormente normalizan bastante simplemente, aunque todavía había detalles que considerar. El El método se ve aproximadamente así: 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 en modo de pantalla completa Salir en modo de pantalla completa La transformación se esconde en : 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 en modo de pantalla completa Salir en modo de pantalla completa Además de crear estos nodos, también los marcamos como sintéticos, ya que no estaban presentes en el árbol inicial, tratándolos efectivamente como "virtuales". —Es sólo un artefacto de nuestras transformaciones.Ok, eso es todo para las transformaciones. (var) -> { return console.log(var) } El elefante en la habitación Hasta este punto, hemos cubierto todos los principios básicos relacionados con la solución de la tarea. 
 
 
 
 
 Pasamos recursivamente, preservando el estado actual del árbol a través de los parámetros y devolviendo los valores de los métodos de visita. Tenemos dos transformaciones típicas: node-to-node y propiedad-to-node. Tenemos una transformación atípica: la normalización del árbol. Como resultado de la traducción, obtenemos un árbol similar, pero un nuevo, diferente en detalles. Todo lo que queda es resolver la tarea. Déjame recordarle: el árbol objetivo tiene   El árbol de la fuente tiene Esta diferencia se debe en gran medida a las especificidades del protobuf.   y Métodos ¿Estás preparado para una carrera como esta? 100 node types 263 types hand-write visit scan hundreds or thousands of times   La solución al problema ya ha aparecido en el texto. al igual que el transbordador original podría generarse basado en el archivo, por lo que las reglas de traducción típicas pueden ser generadas por código basándose en alguna regla de configuración. pero cubriremos esto —y cómo encajar en la normalización atípica— en otro momento. .protoset Posteriormente Este es el tipo de caso que he encontrado en mi trabajo.Aunque sólo he escudriñado la superficie, he tocado varios puntos interesantes: transformaciones típicas, la elección entre un iterador y un visitante, una implementación de visitante no trivial. También lo hemos mirado a través de la lente del análisis estático - nodos sintéticos y el enfoque para la normalización. En cualquier caso, espero que hayas aprendido algo nuevo sobre el trabajo con los árboles. No te pierdas los artículos sobre este tema o sobre los nuevos analizadores en general – suscríbete a PVS-Studio Nuestro artículo mensual ¡Está bienvenido a probar la herramienta gratis . En Twitter Digesto Aquí Si quieres seguir mis publicaciones, suscríbete a mi personal . El blog

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 audio es producido en el idioma original de la historia!

El elefante en la habitación: por qué esta traducción de AST debe ser generada por código

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Navegando por las aguas: desarrollo de aplicaciones RAG de nivel de producción con lagos de datos

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Crecimiento de las criptomonedas: creación de perfiles de usuarios eficaces

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Navegando por las aguas: desarrollo de aplicaciones RAG de nivel de producción con lagos de datos

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Crecimiento de las criptomonedas: creación de perfiles de usuarios eficaces

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps