下面来实现一个极简的递归解释器，运行下面的代码：

解析代码

  1. function test(i) {
  2.   if(i==0){
  3.       return 0
  4.   }
  5.   if(i==1) {
  6.     return 1
  7.   }
  8.   return test(i - 2) + test(i - 1)
  9. }
  11. let res = test(7)
  13. console.log(res)

运行结果

image.png

解释器代码

  1. const ast = require('./source.json')
  3. // console.log(ast)
  5. let all = {
  6.     store: [],
  7.     env: []
  8. }
  10. function createEnvironment() {
  11.     let store = {};
  12.     all.store.push(store);
  14.     return {
  15.         get(key) {
  16.             return store[key];
  17.         },
  18.         set(key, object) {
  19.             store[key] = object;
  20.         }
  21.     };
  22. }
  24. function createEnclosedEnvironment(outer) {
  25.     let env = createEnvironment();
  27.     all.env.push(env)
  28.     return {
  29.         get(key) {
  30.             let value = env.get(key);
  31.             return value !== undefined /*易错*/ ? value : outer.get(key);
  32.         },
  33.         set(key, object) {
  34.             env.set(key, object);
  35.         }
  36.     };
  37. }
  40. function run(ast, env) {
  41.     switch (ast.type) {
  42.         case "Program":
  43.             return run_statement(ast.body, env)
  44.         case "ReturnStatement":
  45.             // console.log(ast, env)
  46.             console.log("-------------------------------------")
  47.             return evaluateReturnStatement(ast, env)
  48.         default:
  49.             let res = evaluateExpression(ast, env);
  50.             return res;
  51.     }
  52. }
  54. function evaluateReturnStatement(expression, env) {
  55.     return {
  56.         kind: "Return",
  57.         value: evaluateExpression(expression.argument, env)
  58.     }
  59. }
  61. function evaluateExpression(expression, env) {
  62.     switch (expression.type) {
  63.         case "IfStatement": {
  64.             return evaluateIfElseExpression(expression, env)
  65.         }
  66.         case "BinaryExpression": {
  67.             return evaluateBinaryExpression(expression, env)
  68.         }
  69.         case "Identifier": {
  70.             return evaluateIdentifier(expression, env); // 简化处理
  71.         }
  72.         case "Literal": {
  73.             return expression.value // 简化处理
  74.         }
  75.         case "CallExpression": {
  76.             let call = env.get(expression.callee.name);
  77.             if (call) {
  78.                 let args = get_args(expression.arguments, env)
  79.                 return evaluateCallExpression(call, args, env);
  80.             } else {
  81.                 throw new Error("not found function!")
  82.             }
  83.         }
  84.     }
  85. }
  87. function evaluateIdentifier(expression, env) {
  88.     if (!expression.name) return null;
  89.     let identifierValue = env.get(expression.name);
  90.     if (identifierValue !== undefined /*易错*/ ) return identifierValue;
  91. }
  93. function evaluateBinaryExpression(expression, env) {
  94.     if (!expression.left || !expression.operator || !expression.right) {
  95.         return null;
  96.     }
  97.     let left = evaluateExpression(expression.left, env);
  98.     // 可能为{kind: "Return", value: xx}
  99.     if (typeof left === "object") {
  100.         left = left.value
  101.     }
  102.     let right = evaluateExpression(expression.right, env);
  103.     if (typeof right === "object") {
  104.         right = right.value
  105.     }
  106.     let ops = `${left} ${expression.operator} ${right}`;
  107.     let res = eval(ops)
  108.     console.log(ops, res)
  109.     return res;
  110. }
  112. function evaluateIfElseExpression(expression, env) {
  113.     if (!expression.test || !expression.consequent) return null;
  115.     let test = evaluateExpression(expression.test, env);
  116.     // if (test.kind === ObjectKind.Error) return test;
  118.     if (test && expression.consequent.body) {
  119.         return evaluateStatements(expression.consequent.body, env);
  120.     } else if (expression.alternative /*else 可能函数内部调用函数*/ ) {
  121.         return evaluateStatements(expression.alternative.statements, env);
  122.     }
  124.     return null;
  125. }
  127. function evaluateCallExpression(call, args, env) {
  128.     call.env = env;
  129.     return applyFunction(call, args);
  130. }
  132. function run_statement(statements, env) {
  133.     for (let i of statements) {
  134.         switch (i.type) {
  135.             case "FunctionDeclaration": {
  136.                 env.set(i.id.name, i);
  137.                 break;
  138.             }
  139.             case "VariableDeclaration": {
  140.                 for (let dec of i.declarations) {
  141.                     if (dec.init.type === "CallExpression") { // 执行函数
  142.                         let call = env.get(dec.init.callee.name);
  143.                         if (call) {
  144.                             let args = get_args(dec.init.arguments, env)
  145.                             let res = evaluateCallExpression(call, args, env);
  146.                             if (typeof res === "object") { // 可能为{kind: "Return", value: xx}
  147.                                 res = res.value
  148.                             }
  149.                             env.set(dec.id.name, res);
  150.                         } else {
  151.                             throw new Error("not found function!")
  152.                         }
  153.                     } else {
  154.                         env[dec.id.name] = dec.init;
  155.                     }
  156.                 }
  157.                 break;
  158.             }
  159.             case "ExpressionStatement": { // console.log
  160.                 if (i.expression) {
  161.                     let args = [];
  162.                     for (let item of i.expression.arguments) {
  163.                         args.push(env.get(item.name))
  164.                     }
  165.                     let opt = `${i.expression.callee.object.name}.${i.expression.callee.property.name}(${args.join(",")})`
  166.                     console.log(opt)
  167.                     eval(opt)
  168.                 }
  169.                 break;
  170.             }
  171.             default: {
  172.                 console.log(i)
  173.             }
  174.         }
  175.     }
  176. }
  178. function applyFunction(fn, args) {
  179.     let {
  180.         body,
  181.         params
  182.     } = fn;
  183.     let env = fn.env;
  184.     if (env && params && args) env = encloseEnvironment(params, args, env);
  185.     if (env && body) return evaluateStatements(body.body, env);
  187.     return null;
  188. }
  190. function encloseEnvironment(params, args, outer) {
  191.     let env = createEnclosedEnvironment(outer);
  193.     for (let i = 0; i < params.length; i++) {
  194.         env.set(params[i].name, args[i]);
  195.     }
  197.     return env;
  198. }
  200. function evaluateStatements(statements, env) {
  201.     let object = null;
  203.     for (let statement of statements) {
  204.         object = run(statement, env);
  205.         if (object && object.kind === "Return") return object;
  206.     }
  208.     return object.value;
  209. }
  211. function get_args(arguments, env) {
  212.     let output = []
  213.     for (let arg of arguments) {
  214.         output.push(evaluateExpression(arg, env))
  215.     }
  216.     return output;
  217. }
  220. const env = createEnvironment();
  222. run(ast, env)

在线AST

  1. {
  2.   "type": "Program",
  3.   "start": 0,
  4.   "end": 150,
  5.   "body": [
  6.     {
  7.       "type": "FunctionDeclaration",
  8.       "start": 0,
  9.       "end": 113,
  10.       "id": {
  11.         "type": "Identifier",
  12.         "start": 9,
  13.         "end": 13,
  14.         "name": "test"
  15.       },
  16.       "expression": false,
  17.       "generator": false,
  18.       "async": false,
  19.       "params": [
  20.         {
  21.           "type": "Identifier",
  22.           "start": 14,
  23.           "end": 15,
  24.           "name": "i"
  25.         }
  26.       ],
  27.       "body": {
  28.         "type": "BlockStatement",
  29.         "start": 17,
  30.         "end": 113,
  31.         "body": [
  32.           {
  33.             "type": "IfStatement",
  34.             "start": 21,
  35.             "end": 46,
  36.             "test": {
  37.               "type": "BinaryExpression",
  38.               "start": 24,
  39.               "end": 28,
  40.               "left": {
  41.                 "type": "Identifier",
  42.                 "start": 24,
  43.                 "end": 25,
  44.                 "name": "i"
  45.               },
  46.               "operator": "==",
  47.               "right": {
  48.                 "type": "Literal",
  49.                 "start": 27,
  50.                 "end": 28,
  51.                 "value": 0,
  52.                 "raw": "0"
  53.               }
  54.             },
  55.             "consequent": {
  56.               "type": "BlockStatement",
  57.               "start": 29,
  58.               "end": 46,
  59.               "body": [
  60.                 {
  61.                   "type": "ReturnStatement",
  62.                   "start": 34,
  63.                   "end": 42,
  64.                   "argument": {
  65.                     "type": "Literal",
  66.                     "start": 41,
  67.                     "end": 42,
  68.                     "value": 0,
  69.                     "raw": "0"
  70.                   }
  71.                 }
  72.               ]
  73.             },
  74.             "alternate": null
  75.           },
  76.           {
  77.             "type": "IfStatement",
  78.             "start": 49,
  79.             "end": 76,
  80.             "test": {
  81.               "type": "BinaryExpression",
  82.               "start": 52,
  83.               "end": 56,
  84.               "left": {
  85.                 "type": "Identifier",
  86.                 "start": 52,
  87.                 "end": 53,
  88.                 "name": "i"
  89.               },
  90.               "operator": "==",
  91.               "right": {
  92.                 "type": "Literal",
  93.                 "start": 55,
  94.                 "end": 56,
  95.                 "value": 1,
  96.                 "raw": "1"
  97.               }
  98.             },
  99.             "consequent": {
  100.               "type": "BlockStatement",
  101.               "start": 58,
  102.               "end": 76,
  103.               "body": [
  104.                 {
  105.                   "type": "ReturnStatement",
  106.                   "start": 64,
  107.                   "end": 72,
  108.                   "argument": {
  109.                     "type": "Literal",
  110.                     "start": 71,
  111.                     "end": 72,
  112.                     "value": 1,
  113.                     "raw": "1"
  114.                   }
  115.                 }
  116.               ]
  117.             },
  118.             "alternate": null
  119.           },
  120.           {
  121.             "type": "ReturnStatement",
  122.             "start": 79,
  123.             "end": 111,
  124.             "argument": {
  125.               "type": "BinaryExpression",
  126.               "start": 86,
  127.               "end": 111,
  128.               "left": {
  129.                 "type": "CallExpression",
  130.                 "start": 86,
  131.                 "end": 97,
  132.                 "callee": {
  133.                   "type": "Identifier",
  134.                   "start": 86,
  135.                   "end": 90,
  136.                   "name": "test"
  137.                 },
  138.                 "arguments": [
  139.                   {
  140.                     "type": "BinaryExpression",
  141.                     "start": 91,
  142.                     "end": 96,
  143.                     "left": {
  144.                       "type": "Identifier",
  145.                       "start": 91,
  146.                       "end": 92,
  147.                       "name": "i"
  148.                     },
  149.                     "operator": "-",
  150.                     "right": {
  151.                       "type": "Literal",
  152.                       "start": 95,
  153.                       "end": 96,
  154.                       "value": 2,
  155.                       "raw": "2"
  156.                     }
  157.                   }
  158.                 ],
  159.                 "optional": false
  160.               },
  161.               "operator": "+",
  162.               "right": {
  163.                 "type": "CallExpression",
  164.                 "start": 100,
  165.                 "end": 111,
  166.                 "callee": {
  167.                   "type": "Identifier",
  168.                   "start": 100,
  169.                   "end": 104,
  170.                   "name": "test"
  171.                 },
  172.                 "arguments": [
  173.                   {
  174.                     "type": "BinaryExpression",
  175.                     "start": 105,
  176.                     "end": 110,
  177.                     "left": {
  178.                       "type": "Identifier",
  179.                       "start": 105,
  180.                       "end": 106,
  181.                       "name": "i"
  182.                     },
  183.                     "operator": "-",
  184.                     "right": {
  185.                       "type": "Literal",
  186.                       "start": 109,
  187.                       "end": 110,
  188.                       "value": 1,
  189.                       "raw": "1"
  190.                     }
  191.                   }
  192.                 ],
  193.                 "optional": false
  194.               }
  195.             }
  196.           }
  197.         ]
  198.       }
  199.     },
  200.     {
  201.       "type": "VariableDeclaration",
  202.       "start": 115,
  203.       "end": 132,
  204.       "declarations": [
  205.         {
  206.           "type": "VariableDeclarator",
  207.           "start": 119,
  208.           "end": 132,
  209.           "id": {
  210.             "type": "Identifier",
  211.             "start": 119,
  212.             "end": 122,
  213.             "name": "res"
  214.           },
  215.           "init": {
  216.             "type": "CallExpression",
  217.             "start": 125,
  218.             "end": 132,
  219.             "callee": {
  220.               "type": "Identifier",
  221.               "start": 125,
  222.               "end": 129,
  223.               "name": "test"
  224.             },
  225.             "arguments": [
  226.               {
  227.                 "type": "Literal",
  228.                 "start": 130,
  229.                 "end": 131,
  230.                 "value": 7,
  231.                 "raw": "7"
  232.               }
  233.             ],
  234.             "optional": false
  235.           }
  236.         }
  237.       ],
  238.       "kind": "let"
  239.     },
  240.     {
  241.       "type": "ExpressionStatement",
  242.       "start": 134,
  243.       "end": 150,
  244.       "expression": {
  245.         "type": "CallExpression",
  246.         "start": 134,
  247.         "end": 150,
  248.         "callee": {
  249.           "type": "MemberExpression",
  250.           "start": 134,
  251.           "end": 145,
  252.           "object": {
  253.             "type": "Identifier",
  254.             "start": 134,
  255.             "end": 141,
  256.             "name": "console"
  257.           },
  258.           "property": {
  259.             "type": "Identifier",
  260.             "start": 142,
  261.             "end": 145,
  262.             "name": "log"
  263.           },
  264.           "computed": false,
  265.           "optional": false
  266.         },
  267.         "arguments": [
  268.           {
  269.             "type": "Identifier",
  270.             "start": 146,
  271.             "end": 149,
  272.             "name": "res"
  273.           }
  274.         ],
  275.         "optional": false
  276.       }
  277.     }
  278.   ],
  279.   "sourceType": "module"
  280. }