JS で AST 抽象構文ツリーを実装する際の問題について話す-jsチュートリアル-php.cn

ホームページ

ウェブフロントエンド

jsチュートリアル

JS で AST 抽象構文ツリーを実装する際の問題について話す

coldplay.xixi

Feb 19, 2021 pm 05:45 PM

javascript

JS で AST 抽象構文ツリーを実装する際の問題について話す

無料学習の推奨事項: JavaScript 学習チュートリアル

フロントエンドの AST 抽象構文ツリーの問題

四則演算
正規表現
字句解析
構文解析
完全なコード

四則演算

まず、今回のコードがLL構文解析に基づいていることは明らかで、四則混合演算の機能を実装しています。まず定義を見てみましょう:
TokenNumber:
· 1 2 3 4 5 6 7 8 9 0 組み合わせ
演算子:
- * /
WhiteSpace:
<sp></sp>## のいずれか# LineTerminator:

プロダクションを見てください:

JS で AST 抽象構文ツリーを実装する際の問題について話す

# #正規表現

最初に正規表現の一致原理を実装します:

<script>
    var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g

    var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"];

    function tokenize(source) {
        var result = null;
        while(true) {
            result = regexp.exec(source);

            if(!result) break;

            for(var i = 1; i <= dictionary.length; i ++) {
                if(result[i])
                    console.log(dictionary[i - 1]);
            }
            console.log(result);
        }
    }

    tokenize("1024 + 10 * 25");</script>

この時点で、ページの実行中の印刷結果を確認します:

ここで exec メソッドが使用されていることに言及する価値があります。exec() メソッドは、文字列内の正規表現の一致を取得するために使用されます。 JS で AST 抽象構文ツリーを実装する際の問題について話すその構文を見てみましょう:

RegExpObject.exec(string)
exec() は一致するテキストを見つけると、結果の配列を返します。それ以外の場合は null を返します。この配列の 0 番目の要素は正規表現に一致するテキスト、1 番目の要素は RegExpObject の 1 番目の部分式 (存在する場合) に一致するテキスト、2 番目の要素は RegExpObject の 1 番目の部分表現に一致するテキストです。 2 つの部分式 (存在する場合) など。配列要素と長さのプロパティに加えて、exec() メソッドは 2 つのプロパティを返します。 Index 属性は、一致するテキストの最初の文字の位置を宣言します。 input 属性には、取得した文字列 string が格納されます。非グローバル RegExp オブジェクトの exec() メソッドが呼び出されたときに返される配列は、String.match() メソッドによって返される配列と同じであることがわかります。

ただし、RegExpObject がグローバル正規表現である場合、exec() の動作は少し複雑になります。 RegExpObject の lastIndex プロパティで指定された文字から文字列 string の取得を開始します。 exec() は、式に一致するテキストを見つけると、一致後の一致テキストの最後の文字の隣の位置に RegExpObject の lastIndex プロパティを設定します。これは、 exec() メソッドを繰り返し呼び出すことで、文字列内の一致するすべてのテキストを反復処理できることを意味します。 exec() は一致するテキストが見つからなくなると、null を返し、lastIndex プロパティを 0 にリセットします。

字句解析

この部分では、上記のコードを最適化します。

まず第一に、今述べたこと:

RegExpObject がグローバル正規表現である場合、exec() の動作は少し複雑になります。 RegExpObject の lastIndex プロパティで指定された文字から文字列 string の取得を開始します。 exec() は、式に一致するテキストを見つけると、一致後の一致テキストの最後の文字の隣の位置に RegExpObject の lastIndex プロパティを設定します。
次に、一致する文字がない状況を考慮して判断する必要があります。

<script>
    var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g

    var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"];

    function* tokenize(source) {
        var result = null;
        var lastIndex = 0;
        while(true) {
            lastIndex = regexp.lastIndex;
            result = regexp.exec(source);

            if(!result) break;

            if(regexp.lastIndex - lastIndex > result[0].length)
                break;
            
            let token = {
                type: null,
                value: null
            }

            for(var i = 1; i <= dictionary.length; i ++) {
                if(result[i])
                    token.type = dictionary[i - 1];
            }
            token.value = result[0];
            yield token        }
        yield {
            type: &#39;EOF&#39;
        }
    }

    for (let token of tokenize("1024 + 10 * 25")) {
        console.log(token)
    }</script>

上記のように、regexp.lastIndex - lastIndex

と ## があります。 # result[0] の長さを比較して、一致しない文字列があるかどうかを判断します。 関数全体をジェネレーター関数の形式に変更します。操作の結果を見てみましょう:

JS で AST 抽象構文ツリーを実装する際の問題について話す構文分析

最初にチャンクを作成します。プロダクションです。全体のコード構造を見てみましょう:

<script>
    var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g

    var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"];

    function* tokenize(source) {
        var result = null;
        var lastIndex = 0;
        while(true) {
            lastIndex = regexp.lastIndex;
            result = regexp.exec(source);

            if(!result) break;

            if(regexp.lastIndex - lastIndex > result[0].length)
                break;
            
            let token = {
                type: null,
                value: null
            }

            for(var i = 1; i <= dictionary.length; i ++) {
                if(result[i])
                    token.type = dictionary[i - 1];
            }
            token.value = result[0];
            yield token        }
        yield {
            type: &#39;EOF&#39;
        }
    }

    let source = [];

    for(let token of tokenize("10 * 25")) {
        if (token.type !== "Whitespace" && token.type !== "LineTerminator")
            source.push(token);
    }

    function Expression(tokens) {

    }

    function AdditiveExpression(source){

    }

    function MultiplicativeExpresson(source) {
        console.log(source);
    }

    MultiplicativeExpresson("10 * 25")</script>

まず、

MultiplicativeExpresson

から勉強してみましょう。これは 4 つの状況に分かれています:

function MultiplicativeExpresson(source) {
	//如果是数字则进行封装
     if(source[0].type === "Number") {
         let node = {
             type: "MultiplicativeExpresson",
             children:[source[0]]
         }
         source[0] = node;
         return MultiplicativeExpresson(source)
     }

     //如果是乘号或者除号，则将三项出栈，进行重组
     if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "*") {
         let node = {
             type: "MultiplicativeExpresson",
             operator: "*",
             children: []
         }
         node.children.push(source.shift());
         node.children.push(source.shift());
         node.children.push(source.shift());
         source.unshift(node);
         return MultiplicativeExpresson(source)
     }

     if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "/") {
         let node = {
             type: "MultiplicativeExpresson",
             operator: "*",
             children: []
         }
         node.children.push(source.shift());
         node.children.push(source.shift());
         node.children.push(source.shift());
         source.unshift(node);
         return MultiplicativeExpresson(source)
     }

     //递归结束的条件
     if(source[0].type === "MultiplicativeExpresson")
         return source[0];

     return MultiplicativeExpresson(source);
 }

見てみましょう。ソースが "10 * 25 / 2" の場合、

console.log(MultiplicativeExpresson(source)) を呼び出します。最終的な実行結果: 次に見てみましょう
AdditiveExpression JS で AST 抽象構文ツリーを実装する際の問題について話すは
MultiplicativeExpresson と本質的に同じです。相違点はコード内でマークされています:

    function AdditiveExpression(source){
        if(source[0].type === "MultiplicativeExpresson") {
            let node = {
                type: "AdditiveExpression",
                children:[source[0]]
            }
            source[0] = node;
            return AdditiveExpression(source)
        }

        //如果是乘号或者除号，则将三项出栈，进行重组
        if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "+") {
            let node = {
                type: "AdditiveExpression",
                operator: "+",
                children: []
            }
            node.children.push(source.shift());
            node.children.push(source.shift());
            //考虑到第三个数可能时Number 需要在这里再次调用一下 MultiplicativeExpresson 做处理
            MultiplicativeExpresson(source);
            node.children.push(source.shift());
            source.unshift(node);
            return AdditiveExpression(source)
        }

        if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "-") {
            let node = {
                type: "AdditiveExpression",
                operator: "-",
                children: []
            }
            node.children.push(source.shift());
            node.children.push(source.shift());
            MultiplicativeExpresson(source);
            node.children.push(source.shift());
            source.unshift(node);
            return AdditiveExpression(source)
        }

        //递归结束的条件
        if(source[0].type === "AdditiveExpression")
            return source[0];

        //第一次进循环 调用
        MultiplicativeExpresson(source);
        return AdditiveExpression(source);
    }

我们看一下当source为"10 * 25 / 2"时调用console.log(AdditiveExpression(source))最后运行的结果：
JS で AST 抽象構文ツリーを実装する際の問題について話す
那么Expression的代码逻辑就很好表达了：

function Expression(tokens) {
     if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "EOF") {
         let node = {
             type: "Expression",
             children: [source.shift(), source.shift()]
         }
         source.unshift(node);
         return node;
     }
     AdditiveExpression(source);
     return Expression(source);
 }

看下运行后的结果：
JS で AST 抽象構文ツリーを実装する際の問題について話す
以上就是所有的js解析抽象语法树的代码。

完整代码

<script>
    var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g

    var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"];

    function* tokenize(source) {
        var result = null;
        var lastIndex = 0;
        while(true) {
            lastIndex = regexp.lastIndex;
            result = regexp.exec(source);

            if(!result) break;

            if(regexp.lastIndex - lastIndex > result[0].length)
                break;
            
            let token = {
                type: null,
                value: null
            }

            for(var i = 1; i <= dictionary.length; i ++) {
                if(result[i])
                    token.type = dictionary[i - 1];
            }
            token.value = result[0];
            yield token        }
        yield {
            type: &#39;EOF&#39;
        }
    }

    let source = [];

    for(let token of tokenize("10 * 25 / 2")) {
        if (token.type !== "Whitespace" && token.type !== "LineTerminator")
            source.push(token);
    }

    function Expression(tokens) {
        if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "EOF") {
            let node = {
                type: "Expression",
                children: [source.shift(), source.shift()]
            }
            source.unshift(node);
            return node;
        }
        AdditiveExpression(source);
        return Expression(source);
    }

    function AdditiveExpression(source){
        if(source[0].type === "MultiplicativeExpresson") {
            let node = {
                type: "AdditiveExpression",
                children:[source[0]]
            }
            source[0] = node;
            return AdditiveExpression(source)
        }

        //如果是乘号或者除号，则将三项出栈，进行重组
        if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "+") {
            let node = {
                type: "AdditiveExpression",
                operator: "+",
                children: []
            }
            node.children.push(source.shift());
            node.children.push(source.shift());
            //考虑到第三个数可能时Number 需要在这里再次调用一下 MultiplicativeExpresson 做处理
            MultiplicativeExpresson(source);
            node.children.push(source.shift());
            source.unshift(node);
            return AdditiveExpression(source)
        }

        if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "-") {
            let node = {
                type: "AdditiveExpression",
                operator: "-",
                children: []
            }
            node.children.push(source.shift());
            node.children.push(source.shift());
            MultiplicativeExpresson(source);
            node.children.push(source.shift());
            source.unshift(node);
            return AdditiveExpression(source)
        }

        //递归结束的条件
        if(source[0].type === "AdditiveExpression")
            return source[0];

        //第一次进循环 调用
        MultiplicativeExpresson(source);
        return AdditiveExpression(source);
    }

    function MultiplicativeExpresson(source) {
        if(source[0].type === "Number") {
            let node = {
                type: "MultiplicativeExpresson",
                children:[source[0]]
            }
            source[0] = node;
            return MultiplicativeExpresson(source)
        }

        //如果是乘号或者除号，则将三项出栈，进行重组
        if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "*") {
            let node = {
                type: "MultiplicativeExpresson",
                operator: "*",
                children: []
            }
            node.children.push(source.shift());
            node.children.push(source.shift());
            node.children.push(source.shift());
            source.unshift(node);
            return MultiplicativeExpresson(source)
        }

        if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "/") {
            let node = {
                type: "MultiplicativeExpresson",
                operator: "*",
                children: []
            }
            node.children.push(source.shift());
            node.children.push(source.shift());
            node.children.push(source.shift());
            source.unshift(node);
            return MultiplicativeExpresson(source)
        }

        //递归结束的条件
        if(source[0].type === "MultiplicativeExpresson")
            return source[0];

        return MultiplicativeExpresson(source);
    }

    console.log(Expression(source))</script>

相关免费学习推荐：javascript（视频）

以上がJS で AST 抽象構文ツリーを実装する際の問題について話すの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明

この記事はCSDNで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。

JavaScriptはCで書かれていますか？証拠を調べるApr 25, 2025 am 12:15 AM

はい、JavaScriptのエンジンコアはCで記述されています。1）C言語は、JavaScriptエンジンの開発に適した効率的なパフォーマンスと基礎となる制御を提供します。 2）V8エンジンを例にとると、そのコアはCで記述され、Cの効率とオブジェクト指向の特性を組み合わせて書かれています。3）JavaScriptエンジンの作業原理には、解析、コンパイル、実行が含まれ、C言語はこれらのプロセスで重要な役割を果たします。

JavaScriptの役割：WebをインタラクティブでダイナミックにするApr 24, 2025 am 12:12 AM

JavaScriptは、Webページのインタラクティブ性とダイナミズムを向上させるため、現代のWebサイトの中心にあります。 1）ページを更新せずにコンテンツを変更できます。2）Domapiを介してWebページを操作する、3）アニメーションやドラッグアンドドロップなどの複雑なインタラクティブ効果、4）ユーザーエクスペリエンスを改善するためのパフォーマンスとベストプラクティスを最適化します。

CおよびJavaScript：接続が説明しましたApr 23, 2025 am 12:07 AM

CおよびJavaScriptは、WebAssemblyを介して相互運用性を実現します。 1）CコードはWebAssemblyモジュールにコンパイルされ、JavaScript環境に導入され、コンピューティングパワーが強化されます。 2）ゲーム開発では、Cは物理エンジンとグラフィックスレンダリングを処理し、JavaScriptはゲームロジックとユーザーインターフェイスを担当します。

Webサイトからアプリまで：JavaScriptの多様なアプリケーションApr 22, 2025 am 12:02 AM

JavaScriptは、Webサイト、モバイルアプリケーション、デスクトップアプリケーション、サーバー側のプログラミングで広く使用されています。 1）Webサイト開発では、JavaScriptはHTMLおよびCSSと一緒にDOMを運用して、JQueryやReactなどのフレームワークをサポートします。 2）ReactNativeおよびIonicを通じて、JavaScriptはクロスプラットフォームモバイルアプリケーションを開発するために使用されます。 3）電子フレームワークにより、JavaScriptはデスクトップアプリケーションを構築できます。 4）node.jsを使用すると、JavaScriptがサーバー側で実行され、高い並行リクエストをサポートします。

Python vs. JavaScript：ユースケースとアプリケーションと比較されますApr 21, 2025 am 12:01 AM

Pythonはデータサイエンスと自動化により適していますが、JavaScriptはフロントエンドとフルスタックの開発により適しています。 1. Pythonは、データ処理とモデリングのためにNumpyやPandasなどのライブラリを使用して、データサイエンスと機械学習でうまく機能します。 2。Pythonは、自動化とスクリプトにおいて簡潔で効率的です。 3. JavaScriptはフロントエンド開発に不可欠であり、動的なWebページと単一ページアプリケーションの構築に使用されます。 4. JavaScriptは、node.jsを通じてバックエンド開発において役割を果たし、フルスタック開発をサポートします。

JavaScript通訳者とコンパイラにおけるC/Cの役割Apr 20, 2025 am 12:01 AM

CとCは、主に通訳者とJITコンパイラを実装するために使用されるJavaScriptエンジンで重要な役割を果たします。 1）cは、JavaScriptソースコードを解析し、抽象的な構文ツリーを生成するために使用されます。 2）Cは、Bytecodeの生成と実行を担当します。 3）Cは、JITコンパイラを実装し、実行時にホットスポットコードを最適化およびコンパイルし、JavaScriptの実行効率を大幅に改善します。

JavaScript in Action：実際の例とプロジェクトApr 19, 2025 am 12:13 AM

現実世界でのJavaScriptのアプリケーションには、フロントエンドとバックエンドの開発が含まれます。 1）DOM操作とイベント処理を含むTODOリストアプリケーションを構築して、フロントエンドアプリケーションを表示します。 2）node.jsを介してRestfulapiを構築し、バックエンドアプリケーションをデモンストレーションします。

JavaScriptとWeb：コア機能とユースケースApr 18, 2025 am 12:19 AM

Web開発におけるJavaScriptの主な用途には、クライアントの相互作用、フォーム検証、非同期通信が含まれます。 1）DOM操作による動的なコンテンツの更新とユーザーインタラクション。 2）ユーザーエクスペリエンスを改善するためにデータを提出する前に、クライアントの検証が実行されます。 3）サーバーとのリフレッシュレス通信は、AJAXテクノロジーを通じて達成されます。

See all articles