首页 > 其他分享 >（小实验）理解编译原理：一个四则运算的解释器

（小实验）理解编译原理：一个四则运算的解释器

时间：2024-03-25 10:15:20浏览次数：25  
标签：node 解释器 return source 四则运算 char 编译 type children

在前面的课程中，我在 JavaScript 和 CSS 的部分，多次提到了编译原理相关的知识。这一部分的知识，如果我们从编译原理“龙书”等正规的资料中学习，就会耗费掉不少的时间，所以我在这里设计了一个小实验，帮助你快速理解编译原理相关的知识。

今天的内容比较特殊，我们来做一段详细的代码实验，详细的代码我放在了文章里，如果你正在收听音频，可以点击文章查看详情。

分析

按照编译原理相关的知识，我们来设计一下工作，这里我们分成几个步骤。

  • 定义四则运算：产出四则运算的词法定义和语法定义。

  • 词法分析：把输入的字符串流变成 token。

  • 语法分析：把 token 变成抽象语法树 AST。

  • 解释执行：后序遍历 AST，执行得出结果。

定义四则运算

四则运算就是加减乘除四种运算，例如：

1 + 2 * 3

首先我们来定义词法，四则运算里面只有数字和运算符，所以定义很简单，但是我们还要注意空格和换行符，所以词法定义大概是下面这样的。

  • Token

    • Number: 1 2 3 4 5 6 7 8 9 0 的组合

    • Operator: + 、-、 *、 / 之一

  • Whitespace: <sp>

  • LineTerminator：<LF> <CR>

这里我们对空白和换行符没有任何的处理，所以词法分析阶段会直接丢弃。

接下来我们来定义语法，语法定义多数采用 BNF，但是其实大家写起来都是乱写的，比如 JavaScript 标准里面就是一种跟 BNF 类似的自创语法。

不过语法定义的核心思想不会变，都是几种结构的组合产生一个新的结构，所以语法定义也叫语法产生式。

因为加减乘除有优先级，所以我们可以认为加法是由若干个乘法再由加号或者减号连接成的：

<Expression> ::= 
    <AdditiveExpression><EOF>
<AdditiveExpression> ::= 
    <MultiplicativeExpression>
    |<AdditiveExpression><+><MultiplicativeExpression>
    |<AdditiveExpression><-><MultiplicativeExpression>

　　这种 BNF 的写法类似递归的原理，你可以理解一下，它表示一个列表。为了方便，我们把普通数字也得当成乘法的一种特例了。

<MultiplicativeExpression> ::= 
    <Number>
    |<MultiplicativeExpression><*><Number>
    |<MultiplicativeExpression></><Number>

好了，这就是四则运算的定义了。

词法分析：状态机

词法分析部分，我们把字符流变成 token 流。词法分析有两种方案，一种是状态机，一种是正则表达式，它们是等效的，选择你喜欢的就好，这里我都会你介绍一下状态机。

根据分析，我们可能产生四种输入元素，其中只有两种 token，我们状态机的第一个状态就是根据第一个输入字符来判断进入了哪种状态：

var token = [];const start = char => {    if(char === '1' 
        || char === '2'
        || char === '3'
        || char === '4'
        || char === '5'
        || char === '6'
        || char === '7'
        || char === '8'
        || char === '9'
        || char === '0'
    ) {
        token.push(char);        return inNumber;   
    }    if(char === '+' 
        || char === '-'
        || char === '*'
        || char === '/'
    ) {        emmitToken(char, char);        return start
    }    if(char === ' ') {        return start;
    }    if(char === '\r' 
        || char === '\n'
    ) {        return start;
    }
}const inNumber = char => {    if(char === '1' 
        || char === '2'
        || char === '3'
        || char === '4'
        || char === '5'
        || char === '6'
        || char === '7'
        || char === '8'
        || char === '9'
        || char === '0'
    ) {
        token.push(char);        return inNumber;
    } else {        emmitToken("Number", token.join(""));
        token = [];        return start(char); // put back char
    }
}

这个状态机非常简单，它只有两个状态，因为我们只有 Number 不是单字符的 token。

这里我的状态机实现是非常经典的方式：用函数表示状态，用 if 表示状态的迁移关系，用 return 值表示下一个状态。

下面我们来运行一下这个状态机试试看：

function emmitToken(type, value) {    console.log(value);
}var input = "1024 + 2 * 256"var state = start;for(var c of input.split(''))
    state = state(c);state(Symbol('EOF'))

运行后我们发现输出如下：

1024
+
2
*
256

这是我们想要的答案。

语法分析：LL

做完了词法分析，我们开始进行语法分析，LL 语法分析根据每一个产生式来写一个函数，首先我们来写好函数名：

function AdditiveExpression( ){

}function MultiplicativeExpression(){
    
}

为了便于理解，我们就不做流式处理了，实际上一般编译代码都应该支持流式处理。

所以我们假设 token 已经都拿到了：

var tokens = [{    type:"Number",    value: "1024"}, {    type:"+"
    value: "+"}, {    type:"Number",    value: "2"}, {    type:"*"
    value: "*"}, {    type:"Number",    value: "256"}, {    type:"EOF"}];

每个产生式对应着一个函数，例如：根据产生式，我们的 AdditiveExpression 需要处理三种情况：

<AdditiveExpression> ::= 
    <MultiplicativeExpression>
    |<AdditiveExpression><+><MultiplicativeExpression>
    |<AdditiveExpression><-><MultiplicativeExpression>

那么 AddititveExpression 中就要写三个 if 分支，来处理三种情况。

AdditiveExpression 的写法是根传入的节点，利用产生式合成新的节点

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

那么下一步我们就把解析好的 token 传给我们的顶层处理函数 Expression。

Expression(tokens);

接下来，我们看 Expression 该怎么处理它。

我们 Expression 收到第一个 token，是个 Number，这个时候，Expression 就傻了，这是因为产生式只告诉我们，收到了 AdditiveExpression 怎么办。

这个时候，我们就需要对产生式的首项层层展开，根据所有可能性调用相应的处理函数，这个过程在编译原理中称为求“closure”。

function Expression(source){    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 === "MultiplicativeExpression") {        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());        MultiplicativeExpression(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());        MultiplicativeExpression(source);
        node.children.push(source.shift());
        source.unshift(node);        return AdditiveExpression(source);
    }    if(source[0].type === "AdditiveExpression")        return source[0];    MultiplicativeExpression(source);    return AdditiveExpression(source);
}function MultiplicativeExpression(source){    if(source[0].type === "Number") {        let node = {            type:"MultiplicativeExpression",            children:[source[0]]
        }
        source[0] = node;        return MultiplicativeExpression(source);
    } 
    if(source[0].type === "MultiplicativeExpression" && source[1] && source[1].type === "*") {        let node = {            type:"MultiplicativeExpression",            operator:"*",            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        node.children.push(source.shift());
        source.unshift(node);        return MultiplicativeExpression(source);
    }    if(source[0].type === "MultiplicativeExpression"&& source[1] && source[1].type === "/") {        let node = {            type:"MultiplicativeExpression",            operator:"/",            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        node.children.push(source.shift());
        source.unshift(node);        return MultiplicativeExpression(source);
    }    if(source[0].type === "MultiplicativeExpression")        return source[0];    return MultiplicativeExpression(source);
};var source = [{    type:"Number",    value: "3"}, {    type:"*",    value: "*"}, {    type:"Number",    value: "300"}, {    type:"+",    value: "+"}, {    type:"Number",    value: "2"}, {    type:"*",    value: "*"}, {    type:"Number",    value: "256"}, {    type:"EOF"}];var ast = Expression(source);console.log(ast);

解释执行

得到了 AST 之后，最困难的一步我们已经解决了。这里我们就不对这颗树做任何的优化和精简了，那么接下来，直接进入执行阶段。我们只需要对这个树做遍历操作执行即可。

我们根据不同的节点类型和其它信息，写 if 分别处理即可：

function evaluate(node) {    if(node.type === "Expression") {        return evaluate(node.children[0])
    }    if(node.type === "AdditiveExpression") {        if(node.operator === '-') {            return evaluate(node.children[0]) - evaluate(node.children[2]);
        }        if(node.operator === '+') {            return evaluate(node.children[0]) + evaluate(node.children[2]);
        }        return evaluate(node.children[0])
    }    if(node.type === "MultiplicativeExpression") {        if(node.operator === '*') {            return evaluate(node.children[0]) * evaluate(node.children[2]);
        }        if(node.operator === '/') {            return evaluate(node.children[0]) / evaluate(node.children[2]);
        }        return evaluate(node.children[0])
    }    if(node.type === "Number") {        return Number(node.value);
    }
}

​

 总结

在这个小实验中，我们通过一个小实验学习了编译原理的基本知识，小实验的目的是帮助你理解 JavaScript 课程中涉及到的编译原理基本概念，它离真正的编译原理学习还有很大的差距。

通过实验，我们了解了产生式、词法分析、语法分析和解释执行的过程。

最后留给你一些挑战，你可以根据自己的水平选择： 补全 emmitToken，使得我们的代码能完整工作起来。

​

 

标签：node,解释器,return,source,四则运算,char,编译,type,children
From： https://www.cnblogs.com/cybozu/p/18093752

相关文章

  • makefile编译第二讲
    更多精彩内容在公众号。关注公众号，加v，免费送你两本makefile电子书。轻松掌握makefileGNU 的 make 很强大， 它可以自动推导文件以及文件依赖关系后面的命令，于是我们就没必要去在每一个[.o]文件后都写上类似的命令，因为，我们的 make 会自动识别，并自己推导命令只要 make ......
  • 【QT+QGIS跨平台编译】之九十：【QGIS_Crashhandler+Qt跨平台编译】（一套代码、一套框架，
    文章目录一、QGIS_Crashhandler介绍二、QGIS下载三、文件分析四、pro文件五、编译实践一、QGIS_Crashhandler介绍  QGIS_Crashhandler模块是QGIS中的一个重要组成部分，它提供了QGIS程序的错误崩溃处理与跟踪。二、QGIS下载QGIS网址：QGISSourceDownload......
  • Docker重新编译webBenchmark镜像
    1.编译环境SystemVersion：Centos8DockerVersion：WebBenchmarkVersion：webBenchmark_linux_arm2.编写Dockerfile1.创建编译目录mkdirnetworkdownload2.创建Dockerfile文件并编写2.1创建Dockerfile文件touchDockerfile2.2编写Dockerfile文件FROMalp......
  • 预编译防sql
    参考：https://forum.butian.net/share/1559预编译防sql注入预编译机制可以提升效率，支持预编译机制的数据库有Oracle、Mysql、MicrosoftSQLServer、PostgreSQL、MongoDB等。预编译可以用于防止sql注入，它是先构建语法树，再带入变量预编译使用mysql为例preparestatement_name......
  • 实现一个自动生成小学四则运算题目的命令行程序
    一.项目作者姓名:陈炜烽麦润泽学号：31220047763122004785Github项目地址：https://github.com/iFortheFuture/teamwork二.PSP表格##PersonalSoftwareProcessStagesPersonalSoftwareProcessStages预估时间(分钟)实际时间(分钟)Planning3030Estimate45......
  • 编译实践学习 Part3
    License:CCBY-SA4.0闲话看了半天文档终于懂了Bison里怎么处理带|的语法了。为什么info要做成Emacs格式啊？Vimer无能狂怒（Lv3.1一元表达式首先当然是设计AST了。这里我用std::varient，不知道有没有更优雅的写法。classPrimaryExpAST:publicBaseAST{public......
  • 【Linux应用开发】gcc编译过程
            gcc是一个c编译器，​可以将源代码转换为可执行程序。编译过程包括了预处理、编译、汇编和链接这四个阶段。预处理（Preprocessing）：在预处理阶段，源代码会经过预处理器的处理，包括展开宏定义、包含头文件、条件编译等操作。预处理器会生成一个经过预处理的中间文件......
  • gcc编译步骤与常用参数
    1.gcc编译步骤与常用参数1.1.编译步骤源码hello.c只有寥寥几行代码#include<stdio.h>intmain(void){printf("hello\n");}执行-E预处理，得到hello.i，生成了很长的.i文件-S编译helloc.s，这一步是最重要的，得到的反汇编文件，可以看出很多问题：-c汇编得到hello.......
  • FFmpeg开发笔记（八）Linux交叉编译Android的FFmpeg库
    ​《FFmpeg开发实战：从零基础到短视频上线》一书的“12.1.2 交叉编译Android需要的so库”介绍了如何在Windows环境交叉编译Android所需FFmpeg的so库，接下来介绍如何在Linux环境交叉编译Android所需FFmpeg的so库。1、下载Linux版本的android-ndk-r21e登录Linux服务器（比如华为云的......
  • vue3 动态编译组件失败：Component provided template option but runtime compilation
    根据vue3官方文档路由，写了如下一个简单的页面来模拟路由的实现。为了减少*.vue文件的个数，在这个但页面中，使用defineComponent通过object定义组件。<scriptsetup>import{ref,computed,defineComponent}from'vue'constHome=defineComponent({template:`......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99