Created
March 24, 2019 13:58
-
-
Save OPY-bbt/8ee387122550326f60592b94b7908d19 to your computer and use it in GitHub Desktop.
极客时间-理解编译原理：一个四则运算的解释器
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html lang="en"> | |
| <head> | |
| <meta charset="UTF-8"> | |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> | |
| <meta http-equiv="X-UA-Compatible" content="ie=edge"> | |
| <title>Document</title> | |
| </head> | |
| <body> | |
| <script> | |
| var token = []; | |
| const start = char => { | |
| if (['1', '2', '3', '4', '5', '6', '7', '8', '9', '0'].includes(char)) { | |
| token.push(char); | |
| return inNumber; | |
| } | |
| // 支持负数 | |
| if (char === '-') { | |
| if (tokens.length === 0 || ['+', '-', '*', '/'].includes(tokens[tokens.length - 1].type)) { | |
| token.push(char); | |
| return inNumber; | |
| } | |
| } | |
| if (['+', '-', '*', '/'].includes(char)) { | |
| emmitToken(char, char); | |
| return start | |
| } | |
| if (char === ' ') { | |
| return start; | |
| } | |
| if (['\r', '\n'].includes(char)) { | |
| return start; | |
| } | |
| if (char === 'EOF') { | |
| emmitToken(char, char); | |
| return start; | |
| } | |
| } | |
| const inNumber = char => { | |
| // 支持小数 | |
| if (['1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '.'].includes(char)) { | |
| token.push(char); | |
| return inNumber; | |
| } else { | |
| emmitToken("Number", token.join('')); | |
| token=[]; | |
| return start(char); | |
| } | |
| } | |
| const tokens = []; | |
| function emmitToken(type, value) { | |
| tokens.push({ type, value }); | |
| } | |
| const input = '1 + 1 * 2'; | |
| let state = start; | |
| for(let c of input.split('')) { | |
| state = state(c); | |
| } | |
| state('EOF'); | |
| // 语法分析：根据每个产生式来写一个函数。 | |
| /** | |
| * <AdditiveExpression> ::= | |
| * <MultiplicativeExpression> | |
| * |<AdditiveExpression><+><MultiplicativeExpression> | |
| * |<AdditiveExpression><-><MultiplicativeExpression> | |
| */ | |
| const 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: [source.shift(), 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: [source.shift(), 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); | |
| } | |
| /** | |
| * <MultiplicativeExpression> ::= | |
| * <Number> | |
| * |<MultiplicativeExpression><*><Number> | |
| * |<MultiplicativeExpression></><Number> | |
| */ | |
| const 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: [source.shift(), source.shift(), source.shift()], | |
| } | |
| source.unshift(node); | |
| return MultiplicativeExpression(source); | |
| } | |
| if (source[0].type === 'MultiplicativeExpression' && source[1] && source[1].type === '/') { | |
| let node = { | |
| type: 'MultiplicativeExpression', | |
| operator: '/', | |
| children: [source.shift(), source.shift()], | |
| } | |
| MultiplicativeExpression(source); | |
| node.children.push(source.shift()); | |
| source.unshift(node); | |
| return MultiplicativeExpression(source); | |
| } | |
| if (source[0].type === "MultiplicativeExpression") { | |
| return source[0]; | |
| } | |
| return MultiplicativeExpression(source); | |
| } | |
| 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); | |
| } | |
| console.log(tokens.slice(0)); | |
| const ast = Expression(tokens); | |
| console.log(ast); | |
| 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); | |
| } | |
| } | |
| const result = evaluate(ast); | |
| console.log(result); | |
| </script> | |
| </body> | |
| </html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment