ホームページ > 記事 > ウェブフロントエンド > JS で AST 抽象構文ツリーを実装する際の問題について話す

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

coldplay.xixi転載: 2021-02-19 17:45:212401ブラウズ

無料学習の推奨事項: 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 サイトの他の関連記事を参照してください。

JavaScript 正则表达式 String NULL 字符串 Length operator JS console regexp 对象 input

声明：

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

前の記事：Nodejs を使用して簡単な Web クローラー機能を実装します (コードは添付されています)。次の記事：Nodejs を使用して簡単な Web クローラー機能を実装します (コードは添付されています)。

続きを見る