インタビュー者やLeetCodeの問題はしばしばバイナリの木を回転させることに焦点を当てていますが、一般的な木を別の木に変換するにはどうすればよいですか? この問題をどのように解決するか、そしてどのようなアプローチを取ることができますか? それでは、どのようにして1つの構文を別の木に翻訳するかを調べてみましょう。 どうやってここに到着したか ある木を別の木に変える理由を想像するのは難しくありません。 
 
 
 
 XML を HTML に変換するなど、さまざまな形式の間の変換。 悪名高いバイナリツリーの回転を含むアルゴリズム的タスク。 コンパイラ内の変換 - 必ずしも木から木への変換ではなく、例えば、シンタクスツリーをコントロールフローグラフに変換します。 これからは、「変容」の代わりに「翻訳」というより正確な用語を使うつもりです。 トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > しかし、ここではすべての例が簡素化されるので、深い専門知識は必要ありません。 AST   課題はかなり複雑な方法で現れた: 
 
 
 
 我々はより多くの言語をサポートしたい - 現在、我々はC#、C/C++、およびJavaのみを扱っていますが、JavaScriptを含めたいと思います。 私たちJavaチームは(驚くほど)Javaで新しいアナライザを書きたいです。 JSのための最も包括的なサポートは、TSの将来のサポートとともに、TypeScriptコンパイラから来ています。しかし、それは別の言語で書かれているので、私たちはgRPC経由でASTを転送しなければなりません。 では、翻訳はどうやって終わったのでしょうか。 
 
 
 私たちが受け取るプロトボフの表現は、構造が変わらないため、直接分析することは不可能で、物体はその階層を完全に失う。 独自の一般化されたモデルを持つことは良いアイデアのように思えるので、コードパッシングフロントエンドによっては避け、新しい言語のサポートを簡素化します。 したがって、私たちの 生まれた: protobuf によって咀嚼された TypeScript コンパイラの木を私たちの自身の表現に翻訳します。 task What we are translating (私たちが翻訳しているもの) 正確に何をしているのか? protobuf との問題を一方的に置きましょう、私たちは一つの木を別の木に変換する必要があります。両方とも同じ言語のシンタクスツリーなので、違いは小さいのです。ほとんどのノードは、化粧品の変異のみを含む一対一の形態でマッピングします。 名前を付けると、他の人は . do...while repeat...until   この場合、トランスフォーメーションは構造を「現状のまま」維持します―我々は単にそれを複製しているだけです。しかし、より複雑なシナリオが存在する可能性があります。 何らかの理由で、TypeScript ツリーは、インターポレーションとテキスト内の表現を単一のノードに組み合わせる一方で、他の言語では、インターポレーションはフラット リストで構成されます。   木を右に取るには、木の属性を分割する必要があります。 したがって、直接のノードからノードへの変換に加えて、私たちはプロパティを別個のノードに変換します。 TemplateSpan ちなみに、逆の操作は、複数のノードを1つに合併するという集約と呼ばれるが、私たちの仕事はそれを必要としなかった。 これまでのところ、すべてはシンプルに見えます。しかし、ソース構造がターゲットにまったく一致しない場合はどうですか? ASTの文脈では、後で作業を容易にするために構造を正常化したいかもしれません。 let a = () -> 1; // source
let a = () -> { return 1 }; // normalized
 全画面モード 全画面モード 全画面モード 全画面モード   ここでは、これは単なる任意のルールで、当初そこにはなかった木にノードを追加することを強制します。 その結果、我々は: 
 
 
 
 node-to-node transformation:Direct duplication, at most changing the identifier.ノード-to-ノード変換:直接の複製、最大で識別子を変更する。 property-to-node transformation: ソースノードの属性から追加のツリー要素を作成する。 正常化のための任意のルールのセットで、そのポイントと彼らが引き起こす感情は、下の画像でキャプチャされています。   我々はこれらのケースを一つずつ調べてみたが、ソースファイル全体のためのシンタクスツリーが構築されている。 少なくとも4つのノードを持っているだけで、数千行のコードを持つファイルに何つのノードが含まれているかを想像してください。 let a = 2 + 5 今のところ、私はあなたが私たちが何をしようとしているかという感覚を持っていることを願っています. それは練習に移行する時間です。 木を登る方法 トラベル このような変換を実行する方法を決定する前に、源の木をどのように渡るかを把握する必要があります。 最初のアイデアは、木を作ることかもしれません。 I have even written an あなたの目標は、ノードタイプの少ない数の木を翻訳することである場合、これはおそらく正しい選択です - しかし私たちのケースではそうではありません。 ITERATOR 記事 I quickly counted the different node types in the diagrams above: そこには、 —and that’s just three examples. In our AST for JavaScript, there are currently under タイプ、およびソースモデルは それぞれのタイプは、追加の ノードをどのように処理するかを決定する際のステートメント だから、涙なしで維持できるコードを書きたいなら、より良い方法はノードに戻ることです。 . ten 100 even more if パターン パターン 私はその実装に留まりません - あなたは上記のリンクまたは他のどのソースでそれをチェックすることができます。代わりに、私はただ、ダブルディスパッチのおかげで、異なるノードタイプで作業する場合の条件の数はほぼゼロです。 Recursive Tree Traveller ツリートラベル 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) {

    }
}
 全画面モード 全画面モード 全画面モード 全画面モード Protobufとは? 注意深い読者は、プロトボフが私たちのモデルを通過するために消化したことに気付くでしょう、だから私たちは何のダブルディスパイスについて話しているのですか? 何もありません。 Protobufは私たちを傷つけたが、結局、私たちは訪問者を模することに成功した。 すべてのノードタイプを記述するファイル。 このような訪問者の方法はかなり一般的です: .protoset visit @Override
public void visitBinaryExpression(BinaryExpression binaryExpression) {
    scan(binaryExpression.getToken());
    scan(binaryExpression.getLeft());
    scan(binaryExpression.getRight());
}
 全画面モード 全画面モード 全画面モード 全画面モード 私たちはこれをAを通じて得ました。   実施: 無実 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
    }
}
 全画面モード 全画面モード 全画面モード 全画面モード このソリューションをエレガントと呼ぶのは難しいですが、効果がありますので、次に合意しましょう。 
 
 
 本当に訪問者はちょっと珍しい。 作業の原理は同じであり、我々は論理を書く能力を維持し、手書きの文句なしで訪問方法。 木の翻訳 さて、翻訳のシナリオとトラベルを見つけたので、ようやく翻訳に移ります。 ノードノード 最も単純なケースから始めましょう. 木を建てる場合は、どこかに保存する必要があります. 最も簡単な方法は、各ノードから現在のノードを返すことです スキャナーから相続する場合、一般的な返還値と一般的な第二の論点を加えると、 方法を事前に、私たちは、このようなものを得ます: 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());
    }
}
 全画面モード 全画面モード 全画面モード 全画面モード この非常に単純な方法で、私たちは木の構造を複製することができます. 混乱を避けるために、私はターゲットの木のノードをプレフィックスでマークします クラス名の初めに Js 不動産ノード このケースはあまり複雑ではありませんが、ここでは私たちが渡す親が必要になります。直接コピーする代わりに、私たちは少し論理を追加します。 @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;
}
 全画面モード 全画面モード 全画面モード 全画面モード SKIPPED 以来 わたしたちは戻る — we have already attached the children through the parent passed as an argument. すでに両親を通じて子供を結びつけた。 TemplateSpan null 標準化 私は最後にその写真で私の感情を表現した理由 - ここではそれぞれがユニークです. 時には私たちは幸運に恵まれ、正常化はシームレスに進んでいます. 他の時には、それは困難です. 一般的に、我々は次の指のルールを採用しました: コントロール フローを変更する場合、または 「複雑すぎる」とみなされるものは、開発者とそのマネージャーの判断に留まります :) avoid too 先ほど例として示した矢印関数はかなり単純に正常化したが、まだ検討すべき詳細があった。 THE この方法は、大体こんな感じです。 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;
}
 全画面モード 全画面モード 全画面モード 全画面モード 変換は隠れている。 : 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;
}
 全画面モード 全画面モード 全画面モード 全画面モード これらのノードを作成することに加えて、最初の木には存在しなかったので、それらを合成としてマークします - 効果的にそれらを「仮想」と扱います。 —It’s just an artifact of our transformations. Ok, that’s all for the transformations. —それは私たちの変容のアーティファクトにすぎません。 (var) -> { return console.log(var) } 部屋の中の象 この時点で、私たちは課題の解決に関連するすべての基本原則をカバーしました。 
 
 
 
 
 We traverse recursively, preserving the current tree state via the parameters and return values of the visit methods. 訪問方法のパラメータと値を介して現在の樹の状態を保存します。 我々には2つの典型的な変換がある:node-to-node と property-to-node。 我々には1つの非典型的な変容がある:樹木の正常化。 翻訳の結果、私たちは似たような木を得るが、細部に異なる新しい木を得る。 残っているのは、課題を解決することだけです. あなたに思い出させてください:ターゲットツリーは、   源泉の木は、 この違いは、主にプロトボフの特性によるものであり、これは我々が   そして 方法 こんなレースの準備はできていますか? 100 node types 263 types hand-write visit scan hundreds or thousands of times   問題の解決策はすでにテキストに現れています. Just as the original traverser could be generated based on the 典型的な翻訳ルールは、いくつかの構成ルールに基づいてコード生成されることができますが、私たちはこれをカバーします - そして、非典型的な正常化にどのように適合するか - 別の時間に。 .protoset Afterword これは私の仕事で出会ったようなケースです。私は表面をわずかに見たが、いくつかの興味深い点に触れた:典型的な変換、イテラターと訪問者との間の選択、非トリビアな訪問者実装。 いずれにせよ、私はあなたが木の作業について新しいことを学んだことを願っています。このトピックに関する記事や、一般に新しいアナリストについての記事を逃さないでください — subscribe to PVS-Studio 私たちの月刊記事 あなたは無料でツールを試すことを歓迎します。 . Twitterについて ディーゼル ここ If you would like to follow my posts, subscribe to my personal . ブログ

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

Read My Stories

このオーディオは、ストーリーの元の言語で制作されています。

The Elephant in the Room: Why This AST Translation Must Be Code-Generated オリジナルタイトル

About Author

コメント

ラベル

この記事は

Related Stories

デジタルノマドの皆さん、タイの新しい DTV ビザについて知っておくべきこと

ワークフローを10倍に向上させる方法: 必須アプリ17選

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

フォーラムからフィードへ: ソーシャルメディアアルゴリズムがデジタルインタラクションを形作る仕組み

デジタルノマドの皆さん、タイの新しい DTV ビザについて知っておくべきこと

ワークフローを10倍に向上させる方法: 必須アプリ17選

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

フォーラムからフィードへ: ソーシャルメディアアルゴリズムがデジタルインタラクションを形作る仕組み

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps