מתווכים ובעיות של LeetCode מתמקדים לעתים קרובות בסובב עצי בינארי.אבל מה לגבי שינוי עץ כללי לתוך עץ אחר?איך אנו פותרים את הבעיה הזו, ואיזה גישות אנו יכולים לקחת?בואו נחקור זאת על ידי בדיקת כיצד אנו מתורגמים סינטקס אחת לעץ אחר. איך הגענו לכאן לא קשה לדמיין סיבות להפוך עץ אחד למשנהו. 
 
 
 
 המרה בין פורמטים שונים, כגון XML ל- HTML. משימות אלגוריתמיות, כולל הסיבוב המפורסם של עצים בינאריים. טרנספורמציות בתוך מתכנתים – לא בהכרח מעץ לעץ, אלא למשל, המרת עץ סינטקס לתוך גרף זרימת בקרה. מעתה ואילך אשתמש במונח מדויק יותר "תרגום" במקום "טרנספורמציה". במאמר זה נדבר על תופעה של אובייקטיביות (למשל, תופעה של אובייקטיביות (למשל, תופעה של אובייקטיביות (למשל, תופעה של אובייקטיביות). אבל כל הדוגמאות כאן יהיו פשוטות, כך שאין צורך במומחיות עמוקה. אסט   המשימה הופיעה בצורה מסובכת למדי: 
 
 
 
 אנחנו רוצים לתמוך בשפות נוספות – כרגע אנחנו מתמודדים רק עם C#, C/C++ ו-Java, אבל היינו רוצים לכלול את JavaScript. אנחנו, צוות Java, רוצים לכתוב את האנליזה החדשה ב-Java. התמיכה המקיפה ביותר עבור JS, יחד עם התמיכה העתידית עבור TS, מגיעה ממכיל TypeScript. עם זאת, זה נכתב בשפה אחרת, אז אנחנו צריכים להעביר את AST באמצעות gRPC. אז איך הגענו לתרגום? 
 
 
 ייצוג protobuf שאנו מקבלים הוא בלתי אפשרי לנתח ישירות כי המבנה אינו משתנה, ואובייקטים מאבדים את הייררכיה שלהם לחלוטין. יש לנו מודל כללי משלהנו נראה כמו רעיון טוב.כך, אנו נמנעים בהתאם לקוד-פרסינג frontend ופשט תמיכה לשפות חדשות. לכן, שלנו נולד: לתרגם את עץ המורכב TypeScript, שנשפך על ידי protobuf, לייצוג שלנו. task מה אנחנו מתורגמים מה בדיוק אנחנו עושים? בואו ניקח בצד (כעת) את הבעיות עם protobuf, אנחנו צריכים להמיר עץ אחד לשני. שניהם הם עצים סינטקס עבור אותה שפה, כך שההבדלים הם קטנים. רוב הצמתים יפותחו באופן isomorphically אחד לאחד, עם רק שינויים קוסמטיים. נניח, מודל אחד עשוי להשתמש שמות, בעוד שהאחרים משתמשים . do...while repeat...until   במקרה זה, הטרנספורמציה שומרת על המבנה "כפי שהוא" – אנחנו פשוט מעתיקים אותו.אבל עשויים להיות תסריטים מורכבים יותר.ב-JavaScript, למשל, יש אינטרפולציה של שורות, הידועה בשם שורות תבניות. מסיבה כלשהי, עץ TypeScript משלב ביטויים בתוך אינטרפולציה וטקסט לקוטר יחיד, בעוד בשפות אחרות, אינטרפולציה מורכבת רשימה שטוחה.   כדי לקבל את העץ על הימין, אנחנו צריכים לחלק את התכונות של לכן, בנוסף לטרנספורמציה ישירה של node-to-node, אנו גם להפוך נכס לחלק נפרד. TemplateSpan אגב, המבצע ההפוך היה נקרא אגרגציה – שילוב של כבלים מרובים לאחד – אבל המשימה שלנו לא דורשת זאת. עד כה, הכל נראה פשוט. אבל מה אם המבנה המקור אינו מתאים לאחד היעד בכלל? בהקשר של AST, ייתכן שאנחנו רוצים לנרמל את המבנה כדי להפוך את זה קל יותר לעבוד עם מאוחר יותר. let a = () -> 1; // source
let a = () -> { return 1 }; // normalized
 כניסה למצב מסך מלא כניסה למצב מסך מלא   כאן, זה רק חוק אקראי הכריח אותנו להוסיף כפתורים לעץ שלא היו שם במקור. כתוצאה מכך, יש לנו: 
 
 
 
 טרנספורמציה של node-to-node: העתקה ישירה, שמשנה את המזהה. טרנספורמציה של רכוש לקוטר: יצירת אלמנטים נוספים מן התכונות של קוטר המקור. קבוצה של כללים אקראי עבור נורמליזציה, אשר הנקודה ואת הרגשות שהם גורמים נלקחים על ידי התמונה למטה.   הסתכלנו על המקרים האלה אחד על אחד, אבל עץ סינטקס נבנה עבור הקובץ המקור כולו. דמיינו כמה כפתורים קובץ עם אלפי שורות קוד יכיל. let a = 2 + 5 בינתיים, אני מקווה שיש לך תחושה של מה אנחנו מנסים לעשות.הגיע הזמן לעבור להתאמן. איך לטפס על העץ מעבר לפני שמחליטים כיצד לבצע טרנספורמציות כאלה, אנחנו צריכים להבין איך לחצות את עץ המקור. הרעיון הראשון עשוי להיות ליישם עץ אפילו כתבתי על אם המטרה שלך היא לתרגם עץ עם מספר קטן של סוגים של כפתורים, זה כנראה הבחירה הנכונה - אבל לא במקרה שלנו. iterator מאמר ספורתי במהירות את הסוגים השונים של כפתורים בתרשים לעיל: יש על - וזו רק שלוש דוגמאות.ב- AST שלנו עבור JavaScript, יש כרגע תחת סוגים, ואת המודל המקור יש כל תוספת פירושה תוספת לכן, אם אנחנו רוצים לכתוב קוד שיכול להישמר ללא דמעות, עדיף לפנות ל . ten 100 even more if דפוס מבקרים אני לא אעמוד על יישום זה - אתה יכול לבדוק את זה דרך הקישור לעיל או בכל מקור אחר.במקום זאת, אני אגיד רק כי הודות לשליחת כפולה, מספר התנאים בעת עבודה עם סוגים שונים של כבל הוא כמעט אפס.זה גם די קל ליישם ירידה חוזרת. מעבורת עץ חוזרת 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 פגע בנו גרם לנו לחשוב קשה, אבל בסופו של דבר, הצלחנו לחקות מבקר על ידי יצירת טרנסגר מבוסס הקובץ, שמתאר את כל סוגי ה-Node שיטות של מבקר כזה הם די רגילים: .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-to-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 נורמליזציה ביטחתי את הרגשות שלי עם התמונה הזאת בפעם האחרונה מסיבה מסוימת – כל מקרה כאן הוא ייחודי. לפעמים אנחנו מקבלים מזל, והנורמליזציה הולכת בצורה חלקה. נורמליזציה אם היא משנה את זרימת השליטה או מה נחשב "מסובך מדי" נשאר לפי שיקול דעתו של המפתחים והמנהל שלהם :) 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;
}
 כניסה למצב מסך מלא כניסה למצב מסך מלא בנוסף ליצירת הצמתים האלה, אנו מסמלים אותם גם כסינתטיים, מכיוון שהם לא היו נוכחים בעץ המקורי - למעשה מתייחסים אליהם כ"ווירטואליים".זה שימושי בניתוח סטטי - עבור heuristics בכללים אבחון, אנו יכולים להסתמך על העובדה כי המפתח לא כתב דברים כאלה. זה רק חפץ של השינויים שלנו, בסדר, זה הכל בשביל השינויים. (var) -> { return console.log(var) } הפיל בחדר בשלב זה, אנחנו מכסים את כל העקרונות הבסיסיים הקשורים לפתרון המשימה. 
 
 
 
 
 אנו עוברים מחדש, שמירה על מצב העץ הנוכחי באמצעות הפרמטרים ומחזירים את הערכים של שיטות הביקור. יש לנו שתי טרנספורמציות טיפוסיות: node-to-node ו-property-to-node. יש לנו שינוי לא טיפוסי אחד: נורמליזציה של עץ. כתוצאה מהתרגום, אנו מקבלים עץ דומה - אבל חדש, שונה בפרטים. כל מה שנשאר הוא לפתור את המשימה.תן לי להזכיר לך: העץ היעד   ועץ המקור הוא הבדל זה נובע בעיקר מהפרטיות של protobuf.This means we would have to   ו שיטות האם אתם מוכנים למרוץ כזה? 100 node types 263 types hand-write visit scan hundreds or thousands of times   הפתרון לבעיה כבר הופיע בטקסט, בדיוק כמו שהמעבר המקורי יכול להיווצר בהתבסס על קובץ, כך שניתן לייצר את הכללים הטיפוסיים לתרגום בהתבסס על כללי הגדרה מסוימים, אבל נדון בזה – וכיצד להתאים לתוך נורמליזציה לא טיפוסית – בזמן אחר. .protoset Afterword זהו סוג של מקרה שפגשתי בעבודתי.אף על פי שסיימתי רק את פני השטח, נגעתי בכמה נקודות מעניינות: טרנספורמציות טיפוסיות, הבחירה בין איטרטור ומבקרים, יישום מבקר לא טריוויאלי. בכל מקרה, אני מקווה שלמדת משהו חדש על עבודה עם עצים.אל תפספסו מאמרים על נושא זה או על אנליזרים חדשים באופן כללי - להירשם ל- 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

האודיו הזה מופק בשפת המקור של הסיפור!

הפיל בחדר: מדוע תרגום AST זה חייב להיות מיוצר על ידי קוד

About Author

הערות

תלו תגים

מאמר זה הוצג ב

Related Stories

97 Stories To Learn About Quicknode

The TechBeat: 5 Low-Cost Cybersecurity Measures SMBs Can’t Afford to Not Implement (3/4/2024)

The TechBeat: Python's Testing Playbook: Building Bulletproof Code (1/18/2024)

The TechBeat: To Focus or Not Focus: How to Find the Right Product-Market Fit (3/10/2024)

97 Stories To Learn About Quicknode

The TechBeat: 5 Low-Cost Cybersecurity Measures SMBs Can’t Afford to Not Implement (3/4/2024)

The TechBeat: Python's Testing Playbook: Building Bulletproof Code (1/18/2024)

The TechBeat: To Focus or Not Focus: How to Find the Right Product-Market Fit (3/10/2024)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps