Intervijas dalībnieki un LeetCode problēmas bieži koncentrējas uz bināro koku rotāciju. Bet ko par vispārēja koku pārveidošanu citā? Kā mēs atrisinām šo problēmu un kādas pieejas mēs varam izmantot? Kā mēs šeit nonācām Nav grūti iedomāties iemeslus, kāpēc pārvērst vienu koku citā. 
 
 
 
 Konvertēšana starp dažādiem formātiem, piemēram, XML uz HTML. Algoritmiskie uzdevumi, ieskaitot slaveno bināro koku rotāciju. Pārveidojumi kompilatoros – ne vienmēr no koka uz koku, bet, piemēram, sintakses koka pārveidošana kontroles plūsmas grafikā. No šī brīža es izmantošu precīzāku terminu “tulkošana” nevis “pārveidošana”. Tātad, ja mēs runājam par to, ko mēs darām, mēs runājam par to, ko mēs darām, un mēs runājam par to, ko mēs darām, mēs runājam par to, ko mēs darām, un mēs runājam par to, ko mēs darām. Bet visi piemēri šeit tiks vienkāršoti, tāpēc nav nepieciešama dziļa pieredze. AST   Uzdevums parādījās diezgan sarežģītā veidā: 
 
 
 
 Mēs vēlamies atbalstīt vairāk valodu – pašlaik mēs apstrādājam tikai C#, C/C++ un Java, bet mēs vēlētos iekļaut JavaScript. Mēs, Java komanda, vēlamies rakstīt jaunu analizatoru (pārsteidzoši) Java. Visaptverošākais atbalsts JS, kopā ar turpmāko atbalstu TS, nāk no TypeScript kompilators. Tomēr tas ir rakstīts citā valodā, tāpēc mums ir jāpārsūta AST, izmantojot gRPC. Kā mēs nonācām pie tulkojuma? 
 
 
 Protobufa pārstāvību, ko mēs saņemam, nav iespējams tieši analizēt, jo struktūra ir nemainīga, un objekti pilnībā zaudē savu hierarhiju. Šādā veidā mēs izvairāmies atkarībā no koda-parsing frontend un vienkāršot atbalstu jaunām valodām. Tādējādi mūsu ir dzimis: tulkot TypeScript kompilatoru koku, kas košļājams ar protobuf, mūsu pašu pārstāvniecībā. task Ko mēs tulkojam Ko tieši mēs darām? Ļaujiet mums novērst (pašlaik) problēmas ar protobuf, mums ir nepieciešams pārvērst vienu koku citā. Abi ir sintakses koki vienai un tai pašai valodai, tāpēc atšķirības ir nelielas. Lielākā daļa mezglu kartēs izomorfiski viens pret vienu, ar tikai kosmētiskām variācijām. nosaukums, bet pārējie izmanto . do...while repeat...until   Šajā gadījumā transformācija saglabā struktūru "kā tas ir" - mēs to vienkārši dublējam.Bet var būt sarežģītāki scenāriji.JavaScript, piemēram, ir virkņu interpolācija, kas pazīstama kā veidnes virknes. Kādu iemeslu dēļ TypeScript koks apvieno interpolācijas un teksta izteiksmes vienā mezglā, savukārt citās valodās interpolācija sastāv no plakanā saraksta.   Lai iegūtu koku pa labi, mums ir nepieciešams sadalīt īpašības Tātad, papildus tiešai mezglu pārveidošanai, mēs arī pārvēršam īpašību atsevišķā mezgā. TemplateSpan Starp citu, pretējo darbību sauc par agregāciju - vairāku mezglu apvienošanu vienā - bet mūsu uzdevums to neprasa. Līdz šim viss šķiet vienkāršs. Bet ko tad, ja avota struktūra vispār neatbilst mērķa struktūrai? AST kontekstā mēs varam vēlēties normalizēt struktūru, lai vēlāk būtu vieglāk strādāt. let a = () -> 1; // source
let a = () -> { return 1 }; // normalized
 Ievadiet pilna ekrāna režīmu Izejiet pilna ekrāna režīmā   Šeit tas ir tikai patvaļīgs noteikums, kas liek mums pievienot mezglus kokam, kas sākotnēji nebija tur. Tā rezultātā mums ir: 
 
 
 
 Node-to-Node transformācija: Tieša dublēšana, maksimāli mainot identifikatoru. īpašuma pārveidošana uz mezglu: papildu koka elementu izveidošana no avota mezglu īpašībām. patvaļīgu normalizācijas noteikumu kopums, kura jēgu un sajūtas, ko tās izraisa, uztver zemāk esošais attēls.   Mēs apskatījām šos gadījumus viens pēc otra, bet sintakses koks tiek izveidots visam avota failam.Praktikā viss tiks sajaukts kopā – un milzīgā mērogā. Vienkārši iedomājieties, cik daudz mezglu saturēs fails ar tūkstošiem koda līniju. let a = 2 + 5 Līdz šim, es ceru, ka jums ir sajūta par to, ko mēs cenšamies darīt. Kā uzkāpt uz koku Pārceļošana Pirms izlemt, kā veikt šādas transformācijas, mums ir jāizdomā, kā šķērsot avota koku. Iespējams, ka pirmais solis ir izveidot koku. Esmu pat uzrakstījis Ja jūsu mērķis ir tulkot koku ar nelielu skaitu mezglu tipu, tas, iespējams, ir pareizā izvēle, bet ne mūsu gadījumā. iterators Raksts Es ātri aprēķināju dažādus mezglu veidus iepriekš minētajās diagrammās: ir aptuveni — un tas ir tikai trīs piemēri. mūsu AST JavaScript, pašlaik ir zemāk veidiem, un avota modelis ir Katrs no tiem nozīmē papildu Tātad, ja mēs vēlamies rakstīt kodu, ko var uzturēt bez asarām, labāk ir vērsties pie . ten 100 even more if Apmeklētāju modelis Es neesmu apmierināts ar tā īstenošanu - jūs varat to pārbaudīt, izmantojot iepriekš minēto saiti vai jebkuru citu avotu. Tā vietā es tikai saku, ka, pateicoties dubultam nosūtījumam, nosacījumu skaits, strādājot ar dažādiem mezglu veidiem, ir gandrīz nulle. Atpakaļceļš caur koku 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) {

    }
}
 Ievadiet pilna ekrāna režīmu Izejiet pilna ekrāna režīmā Kā ir ar protobāzi? Uzmanīgs lasītājs atzīmēs, ka protobuf ir sagremojis mūsu modeli šķērsošanai, tāpēc par kādu dubultu nosūtīšanu mēs pat runājam? Protobuf mūs ievainoja, padarot mūs domāt grūti. bet galu galā, mums izdevās imitēt apmeklētāju, ģenerējot šķērsgriezēju, pamatojoties uz failu, kas apraksta visus mezglu veidus. Šāda apmeklētāja metodes ir diezgan parastas: .protoset visit @Override
public void visitBinaryExpression(BinaryExpression binaryExpression) {
    scan(binaryExpression.getToken());
    scan(binaryExpression.getLeft());
    scan(binaryExpression.getRight());
}
 Ievadiet pilna ekrāna režīmu Izejiet pilna ekrāna režīmā Tas tika panākts, izmantojot   Īstenošana : Nevainīgs 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
    }
}
 Ievadiet pilna ekrāna režīmu Izejiet pilna ekrāna režīmā Šo risinājumu ir grūti saukt par elegantu, bet tas darbojas. 
 
 
 Mūsu apmeklētājs patiešām ir nedaudz neparasts. Darbības princips paliek tāds pats, jo mēs saglabājam spēju rakstīt loģiku vizīšu metodēs bez roku rakstītiem, ja paziņojumiem. Koku tulkošana Labi, mēs izdomājām tulkošanas scenārijus un šķērsošanu.Tagad mēs beidzot varam pāriet uz tulkošanu. Node-to-node Sāksim ar vienkāršāko gadījumu.Ja mēs būvējam koku, mums ir nepieciešams to kaut kur uzglabāt.Visvienkāršākais veids ir atgriezt pašreizējo mezglu no katra ja mēs mantojam no iepriekš minētā skenera, pievienojot ģenērisko atgriezenisko vērtību un ģenērisko otro argumentu metodes iepriekš, mēs iegūstam kaut ko tādu: 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());
    }
}
 Ievadiet pilna ekrāna režīmu Izejiet pilna ekrāna režīmā Šādā ļoti vienkāršā veidā mēs varam dublēt koku struktūru. Lai izvairītos no neskaidrībām, es marķēju mērķa koku mezglus ar prefiksu klases nosaukuma sākumā. Js Nekustamā īpašuma nodalījums Šis gadījums nav daudz sarežģītāks, bet šeit mums būs nepieciešams vecāks, kuru mēs nododam. Tā vietā, lai tieši kopētu, mēs pievienojam nedaudz loģikas. @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;
}
 Ievadiet pilna ekrāna režīmu Izejiet pilna ekrāna režīmā Kopš esam izlidojuši Mēs atgriežamies — mēs jau esam piestiprinājuši bērnus caur vecāku kā argumentu. TemplateSpan null Normalizācija Es pēdējo reizi izteicu savas emocijas ar šo attēlu kāda iemesla dēļ – katrs gadījums šeit ir unikāls. Dažreiz mums ir paveicies, un normalizācija notiek nevainojami. normalizācija, ja tā maina kontroles plūsmu vai ir Kas tiek uzskatīts par "pārāk sarežģītu" paliek pēc izstrādātāja un viņu menedžera ieskatiem :) avoid too Šāviena funkcijas, ko es minēju kā piemēru agrāk, normalizējas diezgan vienkārši, lai gan joprojām bija detaļas, kas jāapsver. Tās Metode izskatās aptuveni šādi: 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;
}
 Ievadiet pilna ekrāna režīmu Izejiet pilna ekrāna režīmā Pārveidošanās slēpjas : 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;
}
 Ievadiet pilna ekrāna režīmu Izejiet pilna ekrāna režīmā Papildus šo mezglu izveidei mēs tos marķējam arī kā sintētiskus, jo sākotnējā kokā tie nebija klāt, efektīvi apstrādājot tos kā "virtuālus". — tas ir tikai mūsu transformāciju artefakts.Ok, tas ir viss transformācijām. (var) -> { return console.log(var) } Ziloņi istabā Līdz šim mēs esam aptvēruši visus pamatprincipus, kas saistīti ar uzdevuma risināšanu. 
 
 
 
 
 Mēs šķērsojam recursīvi, saglabājot pašreizējo koku stāvokli, izmantojot apmeklējuma metožu parametrus un atgriežot vērtības. Mums ir divas tipiskas transformācijas: mezgls uz mezglu un īpašums uz mezglu. Mums ir viena netipiska transformācija: koku normalizācija. Tulkojuma rezultātā mēs iegūstam līdzīgu koku, bet jaunu, atšķirīgu detaļās. Viss, kas paliek, ir atrisināt uzdevumu. Ļaujiet man jums atgādināt: mērķa koks ir par   Un avota koks ir Šī atšķirība lielā mērā ir saistīta ar protobuf īpatnībām.   un Metodes Vai es esmu gatavs šādai sacīkstēm? 100 node types 263 types hand-write visit scan hundreds or thousands of times   Problēmas risinājums jau ir parādījies tekstā. tāpat kā sākotnējo šķērsgriezēju var ģenerēt, pamatojoties uz failu, tāpēc tipisko tulkošanas noteikumus var kodēt, pamatojoties uz dažiem konfigurācijas noteikumiem. bet mēs aptversim šo - un to, kā iekļauties netipiskajā normalizācijā - citā laikā. .protoset Pēcvārds Lai gan es esmu tikai skumdinājis virsmu, es esmu pieskāris vairākiem interesantiem punktiem: tipiskajām transformācijām, izvēlei starp iteratoru un apmeklētāju, ne-triviālu apmeklētāju īstenošanu. Jebkurā gadījumā, es ceru, ka jūs uzzinājāt kaut ko jaunu par darbu ar kokiem.Nepalaidiet garām rakstus par šo tēmu vai par jauniem analizatoriem kopumā – abonējiet PVS-Studio Mūsu ikmēneša raksts Jūs esat laipni aicināti izmēģināt rīku bez maksas . Tiešsaistes Digitāli Šeit Ja vēlaties sekot manām ziņām, abonējiet manu personīgo . Blogs

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

Read My Stories

Šis audio ir izveidots stāsta oriģinālvalodā!

Ziloņi telpā: kāpēc šis AST tulkojums ir jāizveido ar kodu

About Author

KOMENTĀRI

PAKARINĀT TAGUS

ŠIS RAKSTS TIKS PĀRSTRĀDĀTS

Related Stories

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps