Intervjueri i problemi LeetCode često se usredotočuju na rotaciju binarnih stabala. Ali što je s transformiranjem općeg stabla u drugo? Kako riješimo ovaj problem, i koje pristupe možemo poduzeti? Kako smo došli ovdje Nije teško zamisliti razloge za pretvaranje jednog stabla u drugo. 
 
 
 
 Konvertiranje između različitih formata, kao što je XML u HTML. Algoritmički zadaci, uključujući zloglasnu rotaciju binarnih stabala. Transformacije unutar kompilera – ne nužno od stabla do stabla, već, na primjer, pretvaranje sintaksnog stabla u grafikon protoka kontrole. Od sada ću koristiti precizniji izraz "prevod" umjesto "transformacije". Istraživanje je provedeno na temelju znanstvenih studija, a istraživanje je provedeno na temelju znanstvenih studija, a istraživanje je provedeno na temelju znanstvenih studija ( Ali svi primjeri ovdje će biti pojednostavljeni, tako da nije potrebna duboka stručnost. AST   Zadaća se pojavila na prilično kompliciran način: 
 
 
 
 Želimo podržati više jezika – trenutno se bavimo samo C#-om, C/C++-om i Java-om, ali želimo uključiti JavaScript. Mi, Java tim, želimo napisati novi analizator u (iznenađujuće) Java. Najobuhvatnija potpora za JS, zajedno s budućom potporom za TS, dolazi iz kompilatora TypeScript. Međutim, napisano je na drugom jeziku, tako da moramo prenijeti AST preko gRPC-a. Kako smo završili s prijevodom? 
 
 
 Predstavljanje protobufa koje primamo nemoguće je analizirati izravno jer je struktura nepromjenjiva, a objekti gube svoju hijerarhiju u potpunosti. Na taj način izbjegavamo ovisnost o frontendu kodiranja i pojednostavljujemo podršku za nove jezike. Dakle, naša Rođen: Prevedite TypeScript kompilator stablo, žvakanje protobuf, u našu vlastitu reprezentaciju. task Što mi prevodimo Što točno radimo? Odvojimo (za sada) probleme s protobufom, moramo pretvoriti jedno stablo u drugo. Oba su sintaksna stabla za isti jezik, tako da su razlike male. Većina čvorova će isomorphically map one-to-one, s samo kozmetičkim varijacijama. Recimo, jedan model može koristiti naziva, dok drugi koriste . do...while repeat...until   U tom slučaju, transformacija čuva strukturu "kako je" - mi je samo duplikiramo, ali mogu postojati složeniji scenariji. Iz nekog razloga, TypeScript stablo kombinira izraze unutar interpolacije i teksta u jedan čvor, dok se u drugim jezicima interpolacija sastoji od ravne liste.   Da bismo dobili stablo na desnoj strani, moramo podijeliti svojstva Tako, osim izravne transformacije od čvorova do čvorova, također pretvaramo svojstvo u zasebni čvor. TemplateSpan Usput, obrnuta operacija bi se zvala agregiranje - spajanje više čvorova u jedan - ali naš zadatak to nije zahtijevao. Do sada, sve izgleda jednostavno. Ali što ako izvorna struktura uopće ne odgovara ciljanom? U kontekstu AST-a, možda bismo željeli normalizirati strukturu kako bismo lakše radili s njom kasnije. Na primjer, uvijek dodajte tijelo funkcijama strelice: let a = () -> 1; // source
let a = () -> { return 1 }; // normalized
 Izlazak iz režima punog zaslona   Ovdje, ovo je samo proizvoljno pravilo koje nas prisiljava da dodamo čvorove na stablo koje nisu bile tamo izvorno. Kao rezultat toga, imamo: 
 
 
 
 Transformacija od čvorova do čvorova: izravna duplikacija, najviše mijenjajući identifikator. Transformacija od svojstva do čvorova: Stvaranje dodatnih elementova stabla iz svojstava izvornih čvorova. skup proizvoljnih pravila za normalizaciju, čija su točka i osjećaji koje uzrokuju uhvaćeni na slici ispod.   Razmotrili smo ove slučajeve jedan po jedan, ali za cijelu izvornu datoteku izgrađeno je sintaksno drvo.U praksi će se sve miješati zajedno – i na ogromnoj razini. Samo zamislite koliko će čvorova sadržavati datoteka s tisućama redaka koda. let a = 2 + 5 Do sada, nadam se da imate osjećaj za ono što pokušavamo učiniti. Kako se popeti na drvo prijevoz Prije nego što odlučimo kako provesti takve transformacije, moramo shvatiti kako prijeći izvorno stablo. Prva ideja mogla bi biti uvođenje drveta Čak sam i napisao jedan Ako je vaš cilj prevesti stablo s malim brojem tipova čvorova, to je vjerojatno pravi izbor - ali ne u našem slučaju. iterator Članak Brzo sam izračunao različite vrste čvorova u gornjim diagramima: postoje oko —i to su samo tri primjera. U našoj AST za JavaScript, trenutačno postoje vrsta, a izvorni model ima Svaka vrsta znači dodatak Stoga, ako želimo napisati kod koji se može održavati bez suza, bolje je obratiti pozornost na . ten 100 even more if Posjetiteljski pattern Neću se zadržavati na njegovoj provedbi – možete je provjeriti putem link-a iznad ili na bilo kojem drugom izvoru. Umjesto toga, reći ću samo da zahvaljujući dvostrukom rasporedu, broj uvjeta prilikom rada s različitim tipovima čvorova je gotovo nula. Recursivni stablo prolaznik 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) {

    }
}
 Izlazak iz režima punog zaslona Što je s Protobufom? Pažljiv čitatelj će primijetiti da je protobuf probavio naš model za prijelaz, pa o kakvoj dvostrukoj pošiljci čak i govorimo? Protobuf nas je povrijedio, ali na kraju smo uspjeli emulirati posjetitelja stvaranjem putnika temeljenog na datoteka, koja opisuje sve vrste čvorova. metode takvog posjetitelja prilično su uobičajene: .protoset visit @Override
public void visitBinaryExpression(BinaryExpression binaryExpression) {
    scan(binaryExpression.getToken());
    scan(binaryExpression.getLeft());
    scan(binaryExpression.getRight());
}
 Izlazak iz režima punog zaslona To smo ostvarili putem   Uvođenje : Nedužan 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
    }
}
 Izlazak iz režima punog zaslona Teško je nazvati ovo rješenje elegantnim, ali to djeluje. 
 
 
 Naš posjetitelj je zapravo malo neobičan. Načelo rada ostaje isto, jer zadržavamo sposobnost pisanja logike u metodama posjeta bez ručno pisanih ako izjava. Prevođenje drveća U redu, shvatili smo scenarije prijevoda i prelazak.Sada konačno možemo preći na prijevod. Sljedeći članakNode-to-node Počnimo od najjednostavnijeg slučaja.Ako gradimo stablo, moramo ga negdje pohraniti.Najlakši način je vratiti trenutni čvor iz svakog Ako naslijedimo iz gore navedenog skenera, dodajući generičku povratnu vrijednost i generički drugi argument za metode unaprijed, dobivamo nešto ovako: 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());
    }
}
 Izlazak iz režima punog zaslona Na ovaj vrlo jednostavan način, možemo duplirati strukturu stabla. kako bi se izbjegla zbunjenost, označavam čvorove ciljanog stabla s prefiksom na početku imena razreda. Js Nekretnina-to-node Ovaj slučaj nije mnogo kompliciraniji, ali ovdje će nam trebati roditelj koji prolazimo. Umjesto da kopiramo izravno, dodamo malo logike. @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;
}
 Izlazak iz režima punog zaslona Nakon što smo preskočili Vraćamo se - već smo pripojili djecu preko roditelja prošli kao argument. TemplateSpan null Normaliziranje Izrazio sam svoje osjećaje s tom slikom posljednji put iz nekog razloga – svaki slučaj ovdje je jedinstven. Ponekad imamo sreće, a normalizacija ide glatko. normalizira ako mijenja protok kontrole ili je Što se računa kao "previše komplicirano" ostaje na diskreciji programera i njihovog menadžera :) avoid too Funkcije strelice koje sam dao kao primjer ranije normaliziraju vrlo jednostavno, iako je još uvijek bilo detalja koje treba razmotriti. Naš Metoda izgleda otprilike ovako: 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;
}
 Izlazak iz režima punog zaslona Transformacija se krije u : 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;
}
 Izlazak iz režima punog zaslona Osim stvaranja tih čvorova, također ih označavamo kao sintetičke, jer nisu bile prisutne u početnom stabla - učinkovito ih tretiraju kao "virtualne". —to je samo artefakt naših transformacija.U redu, to je sve za transformacije. (var) -> { return console.log(var) } Slon u sobi Do ove točke, pokrili smo sva osnovna načela povezana s rješavanjem zadatka. 
 
 
 
 
 Mi prolazimo recursivno, čuvajući trenutno stanje stabla kroz parametre i vraćanje vrijednosti metoda posjeta. Imamo dvije tipične transformacije: čvor na čvor i svojstvo na čvor. Imamo jednu atipičnu transformaciju: normalizaciju stabla. Kao rezultat prijevoda, dobivamo slično stablo - ali novo, različito u detaljima. Sve što preostaje je riješiti zadatak.Neka vas podsjetim: ciljno stablo ima oko   Izvorno stablo ima Ta je razlika uglavnom posljedica specifičnosti protobuf-a.   i Metode Jeste li spremni za takvu utrku? 100 node types 263 types hand-write visit scan hundreds or thousands of times   Rješenje problema već se pojavilo u tekstu. baš kao što je izvorni prijevoznik mogao biti generiran na temelju datoteke, tako da se tipična pravila prijevoda mogu generirati kodom na temelju nekog pravila konfiguracije. ali to ćemo pokriti - i kako se uklopiti u atipičnu normalizaciju - neko drugo vrijeme. .protoset Posljednje riječi Iako sam samo skimirao površinu, dotaknuo sam nekoliko zanimljivih točaka: tipične transformacije, izbor između iteratora i posjetitelja, ne-trivijalna implementacija posjetitelja. U svakom slučaju, nadam se da ste naučili nešto novo o radu s drvećem.Ne propustite članke o ovoj temi ili o novim analizatorima općenito – pretplatite se na PVS-Studio Naš mjesečni članak Dobrodošli isprobati alat besplatno . Twitter digesti ovdje Ako želite pratiti moje postove, pretplatite se na moje osobne . Blogovi

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

Read My Stories

Ovaj zvuk je proizveden na izvornom jeziku priče!

Slon u sobi: Zašto ovaj AST prijevod mora biti generiran kodom

About Author

KOMENTARI

VIJESI OZNAKE

OVAJ ČLANAK JE PREDSTAVLJEN U

Related Stories

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps