重学前端学习笔记（二十八）--通过四则运算的解释器快速理解编译原理

hot_pot_Leo 发布于2019-08-23 17:58 / 2762人阅读

摘要：实现状态机可能产生四种输入元素，其中只有两种，状态机的第一个状态就是根据第一个输入字符来判断进入了哪种状态用函数表示状态，用表示状态的迁移关系，用值表示下一个状态。运行状态机输出结果四语法分析语法分析根据每一个产生式来写一个函数。

笔记说明

重学前端是程劭非（winter）【前手机淘宝前端负责人】在极客时间开的一个专栏，每天10分钟，重构你的前端知识体系，笔者主要整理学习过程的一些要点笔记以及感悟，完整的可以加入winter的专栏学习【原文有winter的语音】，如有侵权请联系我，邮箱：kaimo313@foxmail.com。

一、分析

按照编译原理相关的知识，将其分成几个步骤。

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

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

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

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

二、定义四则运算 2.1、定义词法

Token

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

Operator: +、-、*、/ 之一

Whitespace：

LineTerminator：

2.2、定义语法

语法定义多数采用 BNF。巴科斯范式(BNF: Backus-Naur Form 的缩写)是由 John Backus 和 Peter Naur 首次引入一种形式化符号来描述给定语言的语法（最早用于描述ALGOL 60 编程语言）。JavaScript 标准里面就是一种跟 BNF 类似的自创语法。

1、加法是由若干个乘法再由加号或者减号连接成的：

 ::=
    

 ::=
    
    |<+>
    |<->

2、可把普通数字当成乘法的一种特例：

 ::=
    
    |<*>
    |

上面就是四则运算的定义。

三、词法分析：状态机

词法分析：把字符流变成 token 流，有两种方案，一种是状态机，一种是正则表达式，它们是等效的。

3.1、实现状态机

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

var token = [];
function 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 === "
" || char === "
") {
        return start;
    }
}
function 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 = [];
        // put back char
        return start(char);
    }
}

// 用函数表示状态，用 if 表示状态的迁移关系，用 return 值表示下一个状态。

3.2、运行状态机

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 语法分析根据每一个产生式来写一个函数。

4.1、写好函数名

function AdditiveExpression( ){

}
function MultiplicativeExpression(){

}

4.2、假设已经拿到 token

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

4.3、AdditiveExpression处理

1、三种情况

 ::=
    
    |<+>
    |<->

2、AdditiveExpression 的写法

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);
    }
}

4.4、函数 Expression 处理

1、把解析好的 token 传给的顶层处理函数 Expression。

Expression(tokens);

2、如果 Expression 收到第一个 token，是个 Number，就需要对产生式的首项层层展开，根据所有可能性调用相应的处理函数，这个过程在编译原理中称为求 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);
// 输出结果 children: Array(1) children: Array(3)还可以继续展开。。。
{
    type: "Expression",
    children: [
        {
            type: "AdditiveExpression",
            operator: "+",
            children: [
                {
                    type: "AdditiveExpression",
                    children: Array(1)
                },
                {
                    type: "+",
                    value: "+"
                },
                {
                    type: "MultiplicativeExpression",
                    operator: "*",
                    children: Array(3)
                }
            ]
        },
        {
            type: "EOF"
        }
    ]
}

五、解释执行

得到了 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);
    }
}

个人总结

这下完全懵逼了 _(:3」∠)_

云服务器 GPU云服务器二十八深度学习的理解怎么理解前端工程师学习前端的网站

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/104453.html

重学前端学习笔记（二十八）--通过四则运算的解释器快速理解编译原理

摘要：实现状态机可能产生四种输入元素，其中只有两种，状态机的第一个状态就是根据第一个输入字符来判断进入了哪种状态用函数表示状态，用表示状态的迁移关系，用值表示下一个状态。运行状态机输出结果四语法分析语法分析根据每一个产生式来写一个函数。笔记说明重学前端是程劭非（winter）【前手机淘宝前端负责人】在极客时间开的一个专栏，每天10分钟，重构你的前端知识体系，笔者主要整理学习过程的一些要点...

Towers 2019-08-02 15:14 评论0 收藏0
重学前端学习笔记（二十八）--通过四则运算的解释器快速理解编译原理

摘要：实现状态机可能产生四种输入元素，其中只有两种，状态机的第一个状态就是根据第一个输入字符来判断进入了哪种状态用函数表示状态，用表示状态的迁移关系，用值表示下一个状态。运行状态机输出结果四语法分析语法分析根据每一个产生式来写一个函数。笔记说明重学前端是程劭非（winter）【前手机淘宝前端负责人】在极客时间开的一个专栏，每天10分钟，重构你的前端知识体系，笔者主要整理学习过程的一些要点...

Crazy_Coder 2019-08-30 11:06 评论0 收藏0
重学前端学习笔记（十八）--JavaScript的闭包和执行上下文

摘要：申明与赋值立即执行的函数表达式，通过创建一个函数，并且立即执行，来构造一个新的域，从而控制的范围。函数接受一个的形参，该参数是一个对象引用，并执行了。在最新的标准中，引入了一个新概念。笔记说明重学前端是程劭非（winter）【前手机淘宝前端负责人】在极客时间开的一个专栏，每天10分钟，重构你的前端知识体系，笔者主要整理学习过程的一些要点笔记以及感悟，完整的可以加入winter的专栏...

silencezwm 2019-08-02 16:18 评论0 收藏0
重学前端学习笔记（十八）--JavaScript的闭包和执行上下文

摘要：申明与赋值立即执行的函数表达式，通过创建一个函数，并且立即执行，来构造一个新的域，从而控制的范围。函数接受一个的形参，该参数是一个对象引用，并执行了。在最新的标准中，引入了一个新概念。笔记说明重学前端是程劭非（winter）【前手机淘宝前端负责人】在极客时间开的一个专栏，每天10分钟，重构你的前端知识体系，笔者主要整理学习过程的一些要点笔记以及感悟，完整的可以加入winter的专栏...

liaorio 2019-08-26 13:48 评论0 收藏0