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 サイトの他の関連記事を参照してください。

このウェブサイトの声明

この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

脱衣画像を無料で

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

神レベルのコード編集ソフト（SublimeText3）

ホットトピック

Gmailメールのログイン入り口はどこですか？

7563

CakePHP チュートリアル

1385

Steamのアカウント名の形式は何ですか

Win11 Activation Key Permanent

NYTの接続はヒントと回答です

Related knowledge

WebSocket と JavaScript を使用してオンライン音声認識システムを実装する方法 Dec 17, 2023 pm 02:54 PM

WebSocket と JavaScript を使用してオンライン音声認識システムを実装する方法はじめに: 技術の継続的な発展により、音声認識技術は人工知能の分野の重要な部分になりました。 WebSocket と JavaScript をベースとしたオンライン音声認識システムは、低遅延、リアルタイム、クロスプラットフォームという特徴があり、広く使用されるソリューションとなっています。この記事では、WebSocket と JavaScript を使用してオンライン音声認識システムを実装する方法を紹介します。

WebSocket と JavaScript: リアルタイム監視システムを実装するための主要テクノロジー Dec 17, 2023 pm 05:30 PM

WebSocketとJavaScript：リアルタイム監視システムを実現するためのキーテクノロジーはじめに：インターネット技術の急速な発展に伴い、リアルタイム監視システムは様々な分野で広く利用されています。リアルタイム監視を実現するための重要なテクノロジーの 1 つは、WebSocket と JavaScript の組み合わせです。この記事では、リアルタイム監視システムにおける WebSocket と JavaScript のアプリケーションを紹介し、コード例を示し、その実装原理を詳しく説明します。 1.WebSocketテクノロジー

JavaScript と WebSocket を使用してリアルタイムのオンライン注文システムを実装する方法 Dec 17, 2023 pm 12:09 PM

JavaScript と WebSocket を使用してリアルタイムオンライン注文システムを実装する方法の紹介: インターネットの普及とテクノロジーの進歩に伴い、ますます多くのレストランがオンライン注文サービスを提供し始めています。リアルタイムのオンライン注文システムを実装するには、JavaScript と WebSocket テクノロジを使用できます。 WebSocket は、TCP プロトコルをベースとした全二重通信プロトコルで、クライアントとサーバー間のリアルタイム双方向通信を実現します。リアルタイムオンラインオーダーシステムにおいて、ユーザーが料理を選択して注文するとき

WebSocketとJavaScriptを使ったオンライン予約システムの実装方法 Dec 17, 2023 am 09:39 AM

WebSocket と JavaScript を使用してオンライン予約システムを実装する方法今日のデジタル時代では、ますます多くの企業やサービスがオンライン予約機能を提供する必要があります。効率的かつリアルタイムのオンライン予約システムを実装することが重要です。この記事では、WebSocket と JavaScript を使用してオンライン予約システムを実装する方法と、具体的なコード例を紹介します。 1. WebSocket とは何ですか? WebSocket は、単一の TCP 接続における全二重方式です。

JavaScript と WebSocket: 効率的なリアルタイム天気予報システムの構築 Dec 17, 2023 pm 05:13 PM

JavaScript と WebSocket: 効率的なリアルタイム天気予報システムの構築はじめに: 今日、天気予報の精度は日常生活と意思決定にとって非常に重要です。テクノロジーの発展に伴い、リアルタイムで気象データを取得することで、より正確で信頼性の高い天気予報を提供できるようになりました。この記事では、JavaScript と WebSocket テクノロジを使用して効率的なリアルタイム天気予報システムを構築する方法を学びます。この記事では、具体的なコード例を通じて実装プロセスを説明します。私たちは

JavaScriptでinsertBeforeを使用する方法 Nov 24, 2023 am 11:56 AM

使用法: JavaScript では、insertBefore() メソッドを使用して、DOM ツリーに新しいノードを挿入します。このメソッドには、挿入される新しいノードと参照ノード (つまり、新しいノードが挿入されるノード) の 2 つのパラメータが必要です。

簡単な JavaScript チュートリアル: HTTP ステータスコードを取得する方法 Jan 05, 2024 pm 06:08 PM

JavaScript チュートリアル: HTTP ステータスコードを取得する方法、特定のコード例が必要です序文: Web 開発では、サーバーとのデータ対話が頻繁に発生します。サーバーと通信するとき、多くの場合、返された HTTP ステータスコードを取得して操作が成功したかどうかを判断し、さまざまなステータスコードに基づいて対応する処理を実行する必要があります。この記事では、JavaScript を使用して HTTP ステータスコードを取得する方法を説明し、いくつかの実用的なコード例を示します。 XMLHttpRequestの使用

JavaScript と WebSocket: 効率的なリアルタイム画像処理システムの構築 Dec 17, 2023 am 08:41 AM

JavaScript は Web 開発で広く使用されているプログラミング言語であり、WebSocket はリアルタイム通信に使用されるネットワークプロトコルです。 2 つの強力な機能を組み合わせることで、効率的なリアルタイム画像処理システムを構築できます。この記事では、JavaScript と WebSocket を使用してこのシステムを実装する方法と、具体的なコード例を紹介します。まず、リアルタイム画像処理システムの要件と目標を明確にする必要があります。リアルタイムの画像データを収集できるカメラデバイスがあるとします。

See all articles

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

ホットAIツール

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

AI Hentai Generator

人気の記事

ホットツール

メモ帳++7.3.1

SublimeText3 中国語版

ゼンドスタジオ 13.0.1

ドリームウィーバー CS6

SublimeText3 Mac版

ホットトピック