社区
学习
工具库
AI工具
休闲
搜索
简体中文
首页 web前端 js教程 谈谈JS实现AST抽象语法树问题

谈谈JS实现AST抽象语法树问题

coldplay.xixi
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 的组合
Operator:
- * / 之一
WhiteSpace:
<sp></sp>
LineTerminator:
<lf></lf> <cr></cr>

看下产生式：
谈谈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>
登录后复制

此时我们看一下页面的运行打印结果：
谈谈JS实现AST抽象语法树问题
值得一提的是这里用到了exec方法，exec() 方法用于检索字符串中的正则表达式的匹配。
我们看一下它的语法：
RegExpObject.exec(string)

如果 exec() 找到了匹配的文本，则返回一个结果数组。否则，返回 null。此数组的第 0 个元素是与正则表达式相匹配的文本，第 1 个元素是与 RegExpObject 的第 1 个子表达式相匹配的文本（如果有的话），第 2 个元素是与 RegExpObject 的第 2 个子表达式相匹配的文本（如果有的话），以此类推。除了数组元素和 length 属性之外，exec() 方法还返回两个属性。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] 的长度进行比较，判断是否有字符串没有匹配上。
将整个函数改成generator函数的形式，我们看下运行的结果：
谈谈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来进行研究，它分为四种情况：

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);
 }
登录后复制

我们看一下当source为"10 * 25 / 2"时调用console.log(MultiplicativeExpresson(source))最后运行的结果：
谈谈JS实现AST抽象语法树问题
接下来看AdditiveExpression 本质上和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中文网其他相关文章！

本站声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

显示更多

热门文章

刺客信条阴影：贝壳谜语解决方案
3 周前 By DDD
Windows 11 KB5054979中的新功能以及如何解决更新问题
2 周前 By DDD
在哪里可以找到原子中的起重机控制钥匙卡
3 周前 By DDD
节省R.E.P.O.解释（并保存文件）
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影 - 如何找到铁匠，解锁武器和装甲定制
4 周前 By DDD
显示更多

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版，非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

显示更多

热门话题

gmail邮箱登陆入口在哪里
7563
15
CakePHP 教程
1385
52
steam的账户名称是什么格式
84
11
win11激活密钥永久
61
19
NYT连接提示和答案
28
99
显示更多
Related knowledge
如何使用WebSocket和JavaScript实现在线语音识别系统 如何使用WebSocket和JavaScript实现在线语音识别系统 Dec 17, 2023 pm 02:54 PM

如何使用WebSocket和JavaScript实现在线语音识别系统引言：随着科技的不断发展，语音识别技术已经成为了人工智能领域的重要组成部分。而基于WebSocket和JavaScript实现的在线语音识别系统，具备了低延迟、实时性和跨平台的特点，成为了一种被广泛应用的解决方案。本文将介绍如何使用WebSocket和JavaScript来实现在线语音识别系

WebSocket与JavaScript：实现实时监控系统的关键技术 WebSocket与JavaScript：实现实时监控系统的关键技术 Dec 17, 2023 pm 05:30 PM

WebSocket与JavaScript：实现实时监控系统的关键技术引言：随着互联网技术的快速发展，实时监控系统在各个领域中得到了广泛的应用。而实现实时监控的关键技术之一就是WebSocket与JavaScript的结合使用。本文将介绍WebSocket与JavaScript在实时监控系统中的应用，并给出代码示例，详细解释其实现原理。一、WebSocket技

如何利用JavaScript和WebSocket实现实时在线点餐系统 如何利用JavaScript和WebSocket实现实时在线点餐系统 Dec 17, 2023 pm 12:09 PM

如何利用JavaScript和WebSocket实现实时在线点餐系统介绍：随着互联网的普及和技术的进步，越来越多的餐厅开始提供在线点餐服务。为了实现实时在线点餐系统，我们可以利用JavaScript和WebSocket技术。WebSocket是一种基于TCP协议的全双工通信协议，可以实现客户端与服务器的实时双向通信。在实时在线点餐系统中，当用户选择菜品并下单

如何使用WebSocket和JavaScript实现在线预约系统 如何使用WebSocket和JavaScript实现在线预约系统 Dec 17, 2023 am 09:39 AM

如何使用WebSocket和JavaScript实现在线预约系统在当今数字化的时代，越来越多的业务和服务都需要提供在线预约功能。而实现一个高效、实时的在线预约系统是至关重要的。本文将介绍如何使用WebSocket和JavaScript来实现一个在线预约系统，并提供具体的代码示例。一、什么是WebSocketWebSocket是一种在单个TCP连接上进行全双工

JavaScript和WebSocket：打造高效的实时天气预报系统 JavaScript和WebSocket：打造高效的实时天气预报系统 Dec 17, 2023 pm 05:13 PM

JavaScript和WebSocket：打造高效的实时天气预报系统引言：如今，天气预报的准确性对于日常生活以及决策制定具有重要意义。随着技术的发展，我们可以通过实时获取天气数据来提供更准确可靠的天气预报。在本文中，我们将学习如何使用JavaScript和WebSocket技术，来构建一个高效的实时天气预报系统。本文将通过具体的代码示例来展示实现的过程。We

javascript中如何使用insertBefore javascript中如何使用insertBefore Nov 24, 2023 am 11:56 AM

用法：在JavaScript中，insertBefore()方法用于在DOM树中插入一个新的节点。这个方法需要两个参数：要插入的新节点和参考节点（即新节点将要被插入的位置的节点）。

简易JavaScript教程：获取HTTP状态码的方法 简易JavaScript教程：获取HTTP状态码的方法 Jan 05, 2024 pm 06:08 PM

JavaScript教程：如何获取HTTP状态码，需要具体代码示例前言：在Web开发中，经常会涉及到与服务器进行数据交互的场景。在与服务器进行通信时，我们经常需要获取返回的HTTP状态码来判断操作是否成功，根据不同的状态码来进行相应的处理。本篇文章将教你如何使用JavaScript获取HTTP状态码，并提供一些实用的代码示例。使用XMLHttpRequest

JavaScript和WebSocket：打造高效的实时图像处理系统 JavaScript和WebSocket：打造高效的实时图像处理系统 Dec 17, 2023 am 08:41 AM

JavaScript是一种广泛应用于Web开发的编程语言，而WebSocket则是一种用于实时通信的网络协议。结合二者的强大功能，我们可以打造一个高效的实时图像处理系统。本文将介绍如何利用JavaScript和WebSocket来实现这个系统，并提供具体的代码示例。首先，我们需要明确实时图像处理系统的需求和目标。假设我们有一个摄像头设备，可以采集实时的图像数

See all articles