انٹرویوٹرز اور LeetCode مسائل اکثر بائنری درختوں کو روٹنگ پر توجہ مرکوز کرتے ہیں. لیکن ایک عام درخت کو ایک دوسرے میں تبدیل کرنے کے بارے میں کیا؟ ہم اس مسئلہ کو کس طرح حل کرسکتے ہیں، اور ہم کیا نقطہ نظر لے سکتے ہیں؟ ہم اس کی تحقیق کرتے ہیں کہ ہم کس طرح ایک سیٹاکس کو دوسرے درخت میں ترجمہ کرتے ہیں. ہم یہاں کیسے آئے ایک درخت کو دوسرے درخت میں تبدیل کرنے کے لئے وجوہات کو تصور کرنے کے لئے مشکل نہیں ہے. 
 
 
 
 مختلف فارمیٹس، جیسے XML کو HTML میں تبدیل کریں. Algorithmic کاموں، جس میں بائبل درختوں کی روٹنگ بھی شامل ہے. کمپیوٹرز میں تبدیلیاں - ضروری طور پر درخت سے درخت نہیں، لیکن مثال کے طور پر، ایک سیٹاکس درخت کو کنٹرول فلائٹ گراف میں تبدیل کرنا. اب سے، میں "تغیر" کے بجائے "تغیر" کا زیادہ درست لفظ استعمال کروں گا. اس کے علاوہ، ہم نے اس کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات کی مصنوعات ( لیکن یہاں تمام مثالیں سادہ ہوں گی، لہذا کوئی گہری مہارت کی ضرورت نہیں ہے. اسٹ   یہ کام کافی پیچیدہ طریقے سے کیا گیا ہے: 
 
 
 
 ہم زیادہ زبانوں کی حمایت کرنا چاہتے ہیں - فی الحال، ہم صرف C#، C / C++، اور جاوا کا انتظام کرتے ہیں، لیکن ہم جاوا اسکرپٹ شامل کرنا چاہتے ہیں. ہم، جاوا ٹیم، نئے تجزیہ کار کو جاوا میں لکھنا چاہتے ہیں. JS کے لئے سب سے زیادہ جامع حمایت، TS کے لئے مستقبل کی حمایت کے ساتھ ساتھ، TypeScript کمپیوٹر سے آتا ہے. تاہم، یہ ایک مختلف زبان میں لکھا جاتا ہے، لہذا ہم gRPC کے ذریعے AST منتقل کرنے کی ضرورت ہے. زیادہ سے زیادہ کارکردگی کے لئے، ہم protobuf استعمال کرتے ہیں. ترجمہ کیسے ختم ہو گیا؟ 
 
 
 protobuf کی نمائندگی جو ہم حاصل کرتے ہیں، براہ راست تجزیہ کرنے کے لئے ناممکن ہے کیونکہ ساخت غیر متغیر ہے، اور اشیاء کو مکمل طور پر ان کی ہائیریارکشن کھو دیتے ہیں. ہمارے اپنے عام طور پر ماڈل رکھنے کے لئے ایک اچھا خیال لگتا ہے. اس طرح، ہم کوڈ پاریسنگ فارنڈ پر منحصر ہونے سے بچتے ہیں اور نئے زبانوں کے لئے سپورٹ کو آسان بناتے ہیں. اور ہمارا پیدا ہوا: TypeScript کمپیوٹر درخت کا ترجمہ کریں، protobuf کی طرف سے چمک دیا، ہماری اپنی نمائندگی میں. task ہم کیا ترجمہ کرتے ہیں ہم بالکل کیا کر رہے ہیں؟ چلو (اب تک) protobuf کے ساتھ مسائل کو چھوڑ دیں، ہمیں ایک درخت کو دوسرے میں تبدیل کرنے کی ضرورت ہے. دونوں ایک ہی زبان کے لئے سٹیکس درخت ہیں، لہذا اختلافات چھوٹے ہیں. زیادہ تر نڈوز ایک سے ایک کے ساتھ ایکسوممرک نقشہ کریں گے، صرف مصنوعی تبدیلیوں کے ساتھ. استعمال کرتے ہیں، جبکہ دوسروں کو . do...while repeat...until   اس صورت میں، تبدیلی ساخت "کیسی ہے" کو برقرار رکھتی ہے - ہم صرف اسے دوبارہ کر رہے ہیں. لیکن زیادہ پیچیدہ سکرینز ہوسکتے ہیں. کسی وجہ سے، TypeScript درخت انٹروپشن اور متن کے اندر بیانات کو ایک واحد نوت میں ملتا ہے، جبکہ دیگر زبانوں میں، انٹروپشن ایک فلیٹ فہرست سے ہوتا ہے.   درخت کو دائیں طرف حاصل کرنے کے لئے، ہمیں اس کی خصوصیات کو تقسیم کرنے کی ضرورت ہے. دو (یا کم) نوتوں میں نوت۔ لہذا، براہ راست نوت کو نوت میں تبدیل کرنے کے علاوہ، ہم ایک خصوصیات کو ایک منفرد نوت میں تبدیل کرتے ہیں. TemplateSpan اس کے علاوہ، اس برعکس عمل کو مجموعی طور پر کہا جائے گا - ایک میں کئی نیٹ ورکوں کو منسلک کرنا - لیکن ہمارے کام کو اس کی ضرورت نہیں تھی. اب تک، سب کچھ سادہ لگتا ہے. لیکن اگر ذریعہ کی ساخت کسی بھی مقصد کے ساتھ مطابقت نہیں کرتا ہے تو کیا؟ AST کنکشن میں، ہم بعد میں کام کرنے کے لئے آسان بنانے کے لئے ساخت کو معمول بنانا چاہتے ہیں. let a = () -> 1; // source
let a = () -> { return 1 }; // normalized
 پورے سکرین موڈ داخل کریں پورے سکرین موڈ خارج کریں   یہاں، یہ صرف ایک عارضی قاعدہ ہے جو ہمیں درخت پر نیٹ ورک شامل کرنے کے لئے مجبور کرتا ہے جو ابتدائی طور پر وہاں نہیں تھے. نتیجے کے طور پر، ہم ہیں: 
 
 
 
 node-to-node transformation: Direct duplication، زیادہ سے زیادہ شناختی اثرات کو تبدیل کرنے کے. property-to-node transformation: source nodes کے خصوصیات سے اضافی درخت عناصر تخلیق. normalization کے لئے arbitrary قوانین کی ایک سیٹ، جس کے نقطہ نظر اور ان کی وجہ سے احساسات مندرجہ ذیل تصویر کی طرف سے پکڑا جاتا ہے.   ہم ان واقعات کو ایک ایک پر غور کرتے ہیں، لیکن پورے ذریعہ فائل کے لئے ایک سنتک درخت بنا دیا جاتا ہے. کم از کم چار نڈوز ہے. صرف تصور کریں کہ ہزاروں کوڈ لائنوں کے ساتھ ایک فائل میں کتنے نڈوز شامل ہوں گے. let a = 2 + 5 اب، مجھے امید ہے کہ آپ کو اس بات کا احساس ہے کہ ہم کیا کرنے کی کوشش کر رہے ہیں. درخت پر چڑھنے کے لئے کس طرح ٹریفک اس طرح کے تبدیلیوں کو کیسے انجام دینے کا فیصلہ کرنے سے پہلے، ہمیں یہ سمجھنے کی ضرورت ہے کہ ذرائع کے درخت کو کیسے گزرنا ہے. پہلا خیال ایک درخت بنانے کے لئے ہو سکتا ہے میں نے بھی لکھا ہے ایک اگر آپ کا مقصد چھوٹی تعداد میں نڈو قسم کے ساتھ ایک درخت کا ترجمہ کرنا ہے تو، یہ شاید صحیح انتخاب ہے - لیکن ہمارے معاملے میں نہیں. iterator کے مضامین میں نے جلدی سے اوپر ڈائریکٹ میں مختلف نڈو قسموں کو شمار کیا: وہاں تقریبا —اور یہ صرف تین مثالیں ہیں. ہمارے AST کے لئے جاوا اسکرپٹ، اس وقت کے تحت ہیں مثال کے طور پر، اور ماڈل کے ذریعہ ہے ہر قسم کا مطلب ایک اضافی لہذا، اگر ہم کوڈ لکھنا چاہتے ہیں جو آنکھوں کے بغیر برقرار رکھا جا سکتا ہے تو، یہ بہتر ہے کہ نوٹنگ کے لئے رجوع کریں . ten 100 even more if ملاحظہ کریں Pattern میں اس کی تنصیب پر ٹھیک نہیں کروں گا - آپ اوپر کے لنک کے ذریعے یا کسی بھی دوسرے ذریعہ پر چیک کرسکتے ہیں. اس کے بجائے، میں صرف یہ کہنا چاہوں گا کہ دوگنا ڈسپلے کے لئے شکریہ، مختلف نڈو قسم کے ساتھ کام کرتے وقت شرائط کی تعداد تقریبا صفر ہے. ٹرانسپورٹ ٹرانسپورٹ 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 نے ہمارے ماڈل کو ٹرانسپورٹ کے لئے پھینک دیا ہے، لہذا ہم کیا ڈبل ڈسپلے کے بارے میں بھی بات کر رہے ہیں؟ کوئی. Protobuf نے ہمیں سختی سے سوچنے کی کوشش کی لیکن آخر میں، ہم ایک ٹرانسفر کی بنیاد پر ایک ٹرانسفر پیدا کرکے ایک زائر کو متعارف کر سکتے ہیں فائل، جس میں تمام نڈو اقسام کی وضاحت کی جاتی ہے. اس طرح کے زائرین کے طریقوں کافی عام ہیں: .protoset visit @Override
public void visitBinaryExpression(BinaryExpression binaryExpression) {
    scan(binaryExpression.getToken());
    scan(binaryExpression.getLeft());
    scan(binaryExpression.getRight());
}
 پورے سکرین موڈ داخل کریں پورے سکرین موڈ خارج کریں ہم نے اس کے ذریعے ایک   نافذ کرنے کے: نافرمان 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
    }
}
 پورے سکرین موڈ داخل کریں پورے سکرین موڈ خارج کریں یہ حل خوبصورت کہا جانا مشکل ہے، لیکن یہ کام کرتا ہے. لہذا، ہم مندرجہ ذیل میں اتفاق کریں. 
 
 
 ہمارے زائر واقعی کچھ غیر معمولی ہے. کام کے اصول ایک ہی رہتا ہے، کیونکہ ہم دستاویزات کے بغیر دورے کے طریقوں میں منطق لکھنے کی صلاحیت کو برقرار رکھتا ہے. درختوں کا ترجمہ ٹھیک ہے، ہم ترجمہ کے سکرین اور ٹرانسپورٹ کو سمجھ چکے ہیں. اب ہم آخر میں ترجمہ پر منتقل کر سکتے ہیں. Node سے Node ہم سب سے زیادہ سادہ کیس سے شروع کریں. اگر ہم ایک درخت بناتے ہیں تو، ہمیں اسے کسی جگہ ذخیرہ کرنے کی ضرورت ہے. سب سے آسان طریقہ یہ ہے کہ ہر ایک سے موجودہ نوڈ کو واپس کرنا ہے. اگر ہم اسکرین کے اوپر سے وارث ہیں تو، ایک عام واپسی کے معیار اور ایک عام دوسرا معیار کو شامل کرتے ہیں طریقوں سے پہلے، ہم کچھ اس طرح حاصل کرتے ہیں: 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 زمرہ:Node اس معاملے میں زیادہ پیچیدہ نہیں ہے، لیکن یہاں ہمیں والدین کی ضرورت ہوگی جو ہم منتقل کرتے ہیں. براہ راست کاپی کرنے کے بجائے، ہم تھوڑا منطق شامل کرتے ہیں. @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;
}
 پورے سکرین موڈ داخل کریں پورے سکرین موڈ خارج کریں جب ہم نے کھو دیا ہم واپس - ہم نے پہلے سے ہی والدین کے ذریعے بچوں کو ایک بحث کے طور پر منتقل کیا ہے. TemplateSpan null معیاری میں نے آخری بار اس تصویر کے ساتھ اپنے احساسات کا اظہار کیا ایک وجہ سے - یہاں ہر صورت میں منفرد ہے. بعض اوقات ہم خوش قسمت ہو جاتے ہیں، اور معیاری طور پر چلتا ہے. دوسرے اوقات، یہ ایک مشکل ہے. normalization اگر یہ کنٹرول فلور کو تبدیل کرتا ہے یا "بہت پیچیدہ" کے طور پر شمار کیا جاتا ہے کہ ڈویلپر اور ان کے مینیجر کی ہدایت پر رہتا ہے :) avoid too پرچم کے افعال جو میں نے پہلے ایک مثال کے طور پر دیا ہے، بہت سادہ طور پر معمول بناتے ہیں، اگرچہ اب بھی تفصیلات پر غور کرنے کی ضرورت تھی. کے یہ طریقہ تقریبا اس طرح لگتا ہے: 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;
}
 پورے سکرین موڈ داخل کریں پورے سکرین موڈ خارج کریں ان نوتوں کی تخلیق کے علاوہ، ہم ان کو مصنوعی کے طور پر بھی مارکیٹ کرتے ہیں، کیونکہ وہ ابتدائی درخت میں موجود نہیں تھے - مؤثر طریقے سے ان کو "ویٹیکل" کے طور پر علاج کرتے ہیں. یہ سٹیٹک تجزیہ میں مفید ہے - تشخیص کے قوانین میں heuristics کے لئے، ہم اس حقیقت کا سبب بن سکتے ہیں کہ ڈویلپر نے ایسی چیزیں نہیں لکھا. یہ صرف ہماری تبدیلیوں کا ایک آرٹویٹ ہے، ٹھیک ہے، یہ تبدیلیوں کے لئے سب کچھ ہے. (var) -> { return console.log(var) } کمرے میں Elephant اس وقت تک، ہم نے کام کو حل کرنے کے لئے متعلق تمام بنیادی اصولوں کا احاطہ کیا ہے. 
 
 
 
 
 ہم مندرجہ ذیل طریقوں کے پیرامیٹرز اور واپسی کے معیار کے ذریعے موجودہ درخت کی حالت کو برقرار رکھتا ہے. ہمارے پاس دو عام تبدیلیاں ہیں: نائٹ-to-نائٹ اور نائٹ-to-نائٹ ملکیت. ہمارے پاس ایک غیر معمولی تبدیلی ہے: درخت کی معیاری. ترجمہ کے نتیجے میں، ہم ایک اسی طرح کے درخت حاصل کرتے ہیں - لیکن ایک نیا، تفصیلات میں مختلف. سب کچھ باقی ہے یہ کام کو حل کرنے کے لئے ہے. مجھے آپ کو یاد رکھنا چاہئے: ہدف درخت کے بارے میں ہے   اور اس درخت کے ذریعہ یہ فرق بنیادی طور پر protobuf کی خصوصیات کی وجہ سے ہے.اس کا مطلب یہ ہے کہ ہم   اور طریقوں اس طرح کے مقابلے کے لئے تیار؟ میں نہیں ہوں. 100 node types 263 types hand-write visit scan hundreds or thousands of times   مسئلہ کا حل پہلے سے ہی متن میں ظاہر ہوا ہے۔ اسی طرح اصل ٹرانسفرر کی بنیاد پر پیدا کیا جا سکتا ہے۔ فائل، لہذا عام ترجمہ کے قوانین کو کچھ ترتیب کے قاعدہ پر مبنی کوڈ پیدا کیا جا سکتا ہے. لیکن ہم اس کے بارے میں پوچھیں گے - اور غیر معمولی معیاری میں شامل کرنے کے لئے کس طرح - کسی دوسرے وقت. .protoset کے بعد اس طرح کے معاملے میں میں نے اپنے کام میں ملاقات کی ہے. اگرچہ میں نے صرف سطح پر چمک دیا ہے، میں نے کئی دلچسپ نقطہ نظر پر مشتمل کیا ہے: عام تبدیلیوں، ایک iterator اور ایک زائر کے درمیان انتخاب، ایک غیر مختصر زائر ایپلی کیشن. کسی بھی صورت میں، مجھے امید ہے کہ آپ نے درختوں کے ساتھ کام کرنے کے بارے میں کچھ نیا سیکھا ہے. اس موضوع پر مضامین یا عام طور پر نئے تجزیہ کاروں کے بارے میں نہیں بھولنا-PVS-Studio پر دستخط کریں ہمارے ماہانہ مضامین ! آپ مفت کے لئے آلے کا تجربہ کرنے کے لئے خوش آمدید ہیں . ٹویٹر ڈیزائن یہاں اگر آپ میری پوسٹس کی پیروی کرنا چاہتے ہیں تو، میرے ذاتی . بلاگ

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

Read My Stories

یہ آڈیو کہانی کی اصل زبان میں تیار کی گئی ہے!

کمرے میں Elephant: کیوں اس AST ترجمہ کو کوڈ پیدا کیا جانا چاہئے

About Author

تبصرے

ہینگ ٹیگز

یہ مضمون اس میں پیش کیا گیا تھا۔

Related Stories

AI Search Traffic Marketshare for Calling HackerNoon Blogs: 52% OpenAI, 30% Amazon & 18% Perplexity

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

"Growing Businesses Gives Me a Sense of Purpose." says Flow Ninja Founder/CEO

Urbain Grandier by Alexandre Dumas - Table of Links

AI Search Traffic Marketshare for Calling HackerNoon Blogs: 52% OpenAI, 30% Amazon & 18% Perplexity

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

"Growing Businesses Gives Me a Sense of Purpose." says Flow Ninja Founder/CEO

Urbain Grandier by Alexandre Dumas - Table of Links

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps