资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/重学前端学习笔记（二十八）--通过四则运算的解释器快速理解编译原理

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

Crazy_Coder / 2177人阅读

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

笔记说明 
</>复制代码 
  1. 重学前端是程劭非（winter）【前手机淘宝前端负责人】在极客时间开的一个专栏，每天10分钟，重构你的前端知识体系，笔者主要整理学习过程的一些要点笔记以及感悟，完整的可以加入winter的专栏学习【原文有winter的语音】，如有侵权请联系我，邮箱：kaimo313@foxmail.com。
一、分析 
</>复制代码 
  1. 按照编译原理相关的知识，将其分成几个步骤。

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

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

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

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

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

Token

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

Operator: +、-、*、/ 之一

Whitespace：

LineTerminator：

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

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

</>复制代码 
  1.  ::=
  2.     
  3.  ::=
  4.     
  5.     |<+>
  6.     |<->

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

</>复制代码 
  1.  ::=
  2.     
  3.     |<*>
  4.     |

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

三、词法分析：状态机 
</>复制代码 
  1. 词法分析：把字符流变成 token 流，有两种方案，一种是状态机，一种是正则表达式，它们是等效的。
3.1、实现状态机 
</>复制代码 
  1. // 可能产生四种输入元素，其中只有两种 token，状态机的第一个状态就是根据第一个输入字符来判断进入了哪种状态
  2. var token = [];
  3. function start(char) {
  4.     if(char === "1" || char === "2"|| char === "3"
  5.         || char === "4"|| char === "5"|| char === "6"|| char === "7"
  6.         || char === "8"|| char === "9"|| char === "0") {
  7.         token.push(char);
  8.         return inNumber;
  9.     }
  10.     if(char === "+" || char === "-" || char === "*" || char === "/") {
  11.         emmitToken(char, char);
  12.         return start
  13.     }
  14.     if(char === " ") {
  15.         return start;
  16.     }
  17.     if(char === "
  18. " || char === "
  19. ") {
  20.         return start;
  21.     }
  22. }
  23. function inNumber(char) {
  24.     if ( char === "1" || char === "2" || char === "3"
  25.         || char === "4"|| char === "5" || char === "6" || char === "7"
  26.         || char === "8" || char === "9" || char === "0") {
  27.         token.push(char);
  28.         return inNumber;
  29.     } else {
  30.         emmitToken("Number", token.join(""));
  31.         token = [];
  32.         // put back char
  33.         return start(char);
  34.     }
  35. }
  36. // 用函数表示状态，用 if 表示状态的迁移关系，用 return 值表示下一个状态。
3.2、运行状态机 
</>复制代码 
  1. function emmitToken(type, value) {
  2.     console.log(value);
  3. }
  4. var input = "1024 + 2 * 256"
  5. var state = start;
  6. for(var c of input.split(""))
  7.     state = state(c);
  8. state(Symbol("EOF"))
  9. // 输出结果
  10. 1024
  11. +
  12. 2
  13. *
  14. 256
四、语法分析：LL 
</>复制代码 
  1. LL 语法分析根据每一个产生式来写一个函数。
4.1、写好函数名 
</>复制代码 
  1. function AdditiveExpression( ){
  2. }
  3. function MultiplicativeExpression(){
  4. }
4.2、假设已经拿到 token 
</>复制代码 
  1. var tokens = [{
  2.     type:"Number",
  3.     value: "1024"
  4. }, {
  5.     type:"+",
  6.     value: "+"
  7. }, {
  8.     type:"Number",
  9.     value: "2"
  10. }, {
  11.     type:"*",
  12.     value: "*"
  13. }, {
  14.     type:"Number",
  15.     value: "256"
  16. }, {
  17.     type:"EOF"
  18. }];
4.3、AdditiveExpression处理

1、三种情况

</>复制代码 
  1.  ::=
  2.     
  3.     |<+>
  4.     |<->

2、AdditiveExpression 的写法

</>复制代码 
  1. AdditiveExpression 的写法是根传入的节点，利用产生式合成新的节点。
</>复制代码 
  1. function AdditiveExpression(source){
  2.     if(source[0].type === "MultiplicativeExpression") {
  3.         let node = {
  4.             type:"AdditiveExpression",
  5.             children:[source[0]]
  6.         }
  7.         source[0] = node;
  8.         return node;
  9.     }
  10.     if(source[0].type === "AdditiveExpression" && source[1].type === "+") {
  11.         let node = {
  12.             type:"AdditiveExpression",
  13.             operator:"+",
  14.             children:[source.shift(), source.shift(), MultiplicativeExpression(source)]
  15.         }
  16.         source.unshift(node);
  17.     }
  18.     if(source[0].type === "AdditiveExpression" && source[1].type === "-") {
  19.         let node = {
  20.             type:"AdditiveExpression",
  21.             operator:"-",
  22.             children:[source.shift(), source.shift(), MultiplicativeExpression(source)]
  23.         }
  24.         source.unshift(node);
  25.     }
  26. }
4.4、函数 Expression 处理

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

</>复制代码 
  1. Expression(tokens);

2、如果 Expression 收到第一个 token，是个 Number，就需要对产生式的首项层层展开，根据所有可能性调用相应的处理函数，这个过程在编译原理中称为求 closure。

</>复制代码 
  1. function Expression(source){
  2.     if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "EOF" ) {
  3.         let node = {
  4.             type:"Expression",
  5.             children:[source.shift(), source.shift()]
  6.         }
  7.         source.unshift(node);
  8.         return node;
  9.     }
  10.     AdditiveExpression(source);
  11.     return Expression(source);
  12. }
  13. function AdditiveExpression(source){
  14.     if(source[0].type === "MultiplicativeExpression") {
  15.         let node = {
  16.             type:"AdditiveExpression",
  17.             children:[source[0]]
  18.         }
  19.         source[0] = node;
  20.         return AdditiveExpression(source);
  21.     }
  22.     if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "+") {
  23.         let node = {
  24.             type:"AdditiveExpression",
  25.             operator:"+",
  26.             children:[]
  27.         }
  28.         node.children.push(source.shift());
  29.         node.children.push(source.shift());
  30.         MultiplicativeExpression(source);
  31.         node.children.push(source.shift());
  32.         source.unshift(node);
  33.         return AdditiveExpression(source);
  34.     }
  35.     if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "-") {
  36.         let node = {
  37.             type:"AdditiveExpression",
  38.             operator:"-",
  39.             children:[]
  40.         }
  41.         node.children.push(source.shift());
  42.         node.children.push(source.shift());
  43.         MultiplicativeExpression(source);
  44.         node.children.push(source.shift());
  45.         source.unshift(node);
  46.         return AdditiveExpression(source);
  47.     }
  48.     if(source[0].type === "AdditiveExpression")
  49.         return source[0];
  50.     MultiplicativeExpression(source);
  51.     return AdditiveExpression(source);
  52. }
  53. function MultiplicativeExpression(source){
  54.     if(source[0].type === "Number") {
  55.         let node = {
  56.             type:"MultiplicativeExpression",
  57.             children:[source[0]]
  58.         }
  59.         source[0] = node;
  60.         return MultiplicativeExpression(source);
  61.     }
  62.     if(source[0].type === "MultiplicativeExpression" && source[1] && source[1].type === "*") {
  63.         let node = {
  64.             type:"MultiplicativeExpression",
  65.             operator:"*",
  66.             children:[]
  67.         }
  68.         node.children.push(source.shift());
  69.         node.children.push(source.shift());
  70.         node.children.push(source.shift());
  71.         source.unshift(node);
  72.         return MultiplicativeExpression(source);
  73.     }
  74.     if(source[0].type === "MultiplicativeExpression"&& source[1] && source[1].type === "/") {
  75.         let node = {
  76.             type:"MultiplicativeExpression",
  77.             operator:"/",
  78.             children:[]
  79.         }
  80.         node.children.push(source.shift());
  81.         node.children.push(source.shift());
  82.         node.children.push(source.shift());
  83.         source.unshift(node);
  84.         return MultiplicativeExpression(source);
  85.     }
  86.     if(source[0].type === "MultiplicativeExpression")
  87.         return source[0];
  88.     return MultiplicativeExpression(source);
  89. };
  90. var source = [{
  91.     type:"Number",
  92.     value: "3"
  93. }, {
  94.     type:"*",
  95.     value: "*"
  96. }, {
  97.     type:"Number",
  98.     value: "300"
  99. }, {
  100.     type:"+",
  101.     value: "+"
  102. }, {
  103.     type:"Number",
  104.     value: "2"
  105. }, {
  106.     type:"*",
  107.     value: "*"
  108. }, {
  109.     type:"Number",
  110.     value: "256"
  111. }, {
  112.     type:"EOF"
  113. }];
  114. var ast = Expression(source);
  115. console.log(ast);
  116. // 输出结果 children: Array(1) children: Array(3)还可以继续展开。。。
  117. {
  118.     type: "Expression",
  119.     children: [
  120.         {
  121.             type: "AdditiveExpression",
  122.             operator: "+",
  123.             children: [
  124.                 {
  125.                     type: "AdditiveExpression",
  126.                     children: Array(1)
  127.                 },
  128.                 {
  129.                     type: "+",
  130.                     value: "+"
  131.                 },
  132.                 {
  133.                     type: "MultiplicativeExpression",
  134.                     operator: "*",
  135.                     children: Array(3)
  136.                 }
  137.             ]
  138.         },
  139.         {
  140.             type: "EOF"
  141.         }
  142.     ]
  143. }
五、解释执行 
</>复制代码 
  1. 得到了 AST 之后，只需要对这个树做遍历操作执行即可。
</>复制代码 
  1. // 根据不同的节点类型和其它信息，用 if 分别处理即可：
  2. function evaluate(node) {
  3.     if(node.type === "Expression") {
  4.         return evaluate(node.children[0])
  5.     }
  6.     if(node.type === "AdditiveExpression") {
  7.         if(node.operator === "-") {
  8.             return evaluate(node.children[0]) - evaluate(node.children[2]);
  9.         }
  10.         if(node.operator === "+") {
  11.             return evaluate(node.children[0]) + evaluate(node.children[2]);
  12.         }
  13.         return evaluate(node.children[0])
  14.     }
  15.     if(node.type === "MultiplicativeExpression") {
  16.         if(node.operator === "*") {
  17.             return evaluate(node.children[0]) * evaluate(node.children[2]);
  18.         }
  19.         if(node.operator === "/") {
  20.             return evaluate(node.children[0]) / evaluate(node.children[2]);
  21.         }
  22.         return evaluate(node.children[0])
  23.     }
  24.     if(node.type === "Number") {
  25.         return Number(node.value);
  26.     }
  27. }
个人总结

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

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

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

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

相关文章

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

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

    Towers 评论0 收藏0

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

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

    hot_pot_Leo 评论0 收藏0

  • 重学前端学习笔记（十八）--JavaScript的闭包和执行上下文

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

    silencezwm 评论0 收藏0

  • 重学前端学习笔记（十八）--JavaScript的闭包和执行上下文

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

    caikeal 评论0 收藏0

发表评论

登陆后可评论

0条评论

Crazy_Coder

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<