3

假设您具有以下功能

var action = (function () {

  var a = 42;
  var b = 2;

  function action(c) {
    return a + 4 * b + c;
  }

  return action;
}());

// how would you parse action into it's serialized LISP / AST format?
var parsed = parse(action);

是否有可能有一个函数引用该函数action并输出 LISP 格式(lambda (c) (plus (plus 42 (multiply 4 2)) c))

我们被允许对action可以做的事情进行一些限制。

  • 正文应该只是一个表达式
  • 它应该是一个纯函数
  • 任何自由变量都是常数

主要问题是给定一个函数，您可以使用一系列输入调用它的源代码，您能否找到正确的值来替换自由变量？

对于上面的示例，您知道 a 和 b 是常数，您可以智能地绘制几个值的输出并查看模式，然后就知道常数是什么。

问题：

您将如何编写一个函数，该函数采用函数引用及其源代码，并为该函数生成某种形式的 AST，并用任何自由变量替换它们的运行时值。

AST 格式的一个示例是代码的 LISP 等价物。

我基本上想序列化和反序列化函数并让它表现相同

应该注意的是，如果传递{ a: a, b: b }给分析函数，问题就会变得微不足道。那就是作弊。

用例：

我想生成一个与语言无关的纯 JavaScript 函数形式，这样我就可以有效地将它传递给 C++，而不需要我的库的用户使用 DSL 来创建这个函数

假设您有一个数据库驱动程序

var cursor = db.table("my-table").map(function (row) {
  return ["foo", row.foo]
})

您想在运行时确定函数是什么并将其转换为 AST 格式，以便您可以使用高效的查询构建器将其转换为 SQL 或数据库具有的任何查询引擎。

这意味着您不必编写：

var cursor = db.table("my-table").map(function (rowQueryObject) {
    return db.createArray(db.StringConstant("foo"), rowQueryObject.getProperty("foo"))
})

这是 DB 库可以使用查询对象执行的功能，让您无需冗长的方法即可构建查询对象转换。

4

2 回答 2

1

这是一个完整的解决方案（使用 parse 函数可访问的变量目录）：

var CONSTANTS = { 
   a: 42,
   b: 2,
   c: 4
};

function test() {
    return a + 4 * b + c;
}

function getReturnStatement(func) {
    var funcStr = func.toString();
    return (/return\s+(.*?);/g).exec(funcStr)[1];
}

function replaceVariables(expr) {
    var current = '';
    for (var i = 0; i < expr.length; i += 1) {
        while (/[a-zA-Z_$]/.test(expr[i]) && i < expr.length) {
            current += expr[i];
            i += 1;
        }
        if (isNumber(CONSTANTS[current])) {
            expr = expr.replace(current, CONSTANTS[current]);
        }
        current = '';
    }
    return expr;
}

function isNumber(arg) {
    return !isNaN(parseInt(arg, 10));
}      

function tokenize(expr) {
    var tokens = [];
    for (var i = 0; i < expr.length; i += 1) {
        if (isWhitespace(expr[i])) {
            continue;
        } else if (isOperator(expr[i])) {
            tokens.push({
                type: 'operator',
                value: expr[i]
            });
        } else if (isParentheses(expr[i])) {
            tokens.push({
                type: 'parant',
                value: expr[i]
            });
        } else {
            var num = '';
            while (isNumber(expr[i]) && i < expr.length) {
                num += expr[i];
                i += 1;
            }
            i -= 1;
            tokens.push({
                type: 'number',
                value: parseInt(num, 10)
            });
        }
    }
    return tokens;
}

function toPrefix(tokens) {
    var operandStack = [],
        operatorStack = [],
        current,
        top = function (stack) {
            if (stack) {
                return stack[stack.length - 1];
            }
            return undefined;
        };

    while (tokens.length) {
        current = tokens.pop();
        if (current.type === 'number') {
            operandStack.push(current);
        } else if (current.value === '(' || 
                !operatorStack.length || 
                (getPrecendence(current.value) >
                 getPrecendence(top(operatorStack).value))) {

            operatorStack.push(current);
        } else if (current.value === ')') {
            while (top(operatorStack).value !== '(') {
                var tempOperator = operatorStack.pop(),
                    right = operandStack.pop(),
                    left = operandStack.pop();
                operandStack.push(tempOperator, left, right);
            }
            operatorStack.pop();
        } else if (getPrecendence(current.value) <= 
                getPrecendence(top(operatorStack).value)) {
            while (operatorStack.length &&
                    getPrecendence(current.value) <=
                    getPrecendence(top(operatorStack).value)) {

                tempOperator = operatorStack.pop();
                right = operandStack.pop();
                left = operandStack.pop();
                operandStack.push(tempOperator, left, right);
            }
        }

    }

    while (operatorStack.length) {
        tempOperator = operatorStack.pop();
        right = operandStack.pop();
        left = operandStack.pop();
        operandStack.push(tempOperator, left, right);
    }

    return operandStack;
}

function isWhitespace(arg) {
    return (/^\s$/).test(arg);
}

function isOperator(arg) {
    return (/^[*+\/-]$/).test(arg);
}

function isParentheses(arg) {
    return (/^[)(]$/).test(arg);
}

function getPrecendence(operator) {
    console.log(operator);
    switch (operator) {
        case '*':
            return 4;
        case '/':
            return 4;
        case '+':
            return 2;
        case '-':
            return 2;
        default:
            return undefined;
    }
}

function getLispString(tokens) {
    var result = '';
    tokens.forEach(function (e) {
        if (e)
            switch (e.type) {
            case 'number':
            result += e.value;
            break;
            case 'parant':
            result += e.value;
            break;
            case 'operator':
            result += getOperator(e.value);
            break;
            default:
            break;
        }
        result += ' ';
    });
    return result;
}

function getOperator(operator) {
    switch (operator) {
        case '+':
            return 'plus';
        case '*':
            return 'multiplicate';
        case '-':
            return 'minus';
        case '\\':
            return 'divide';
        default:
            return undefined;
    }
}

var res = getReturnStatement(test);
console.log(res);
res = replaceVariables(res);
console.log(res);
var tokens = tokenize(res);
console.log(tokens);
var prefix = toPrefix(tokens);
console.log(prefix);
console.log(getLispString(prefix));

我只是写了它，所以风格可能存在一些问题，但我认为这个想法很清楚。

您可以使用方法获取函数体.toString。之后可以使用正则表达式匹配return语句

(/return\s+(.*?);/g).exec(funcStr)[1];

注意这里必须使用分号才能成功匹配！在下一步中，使用该CONSTANTS对象将所有变量转换为数值（我看到您还剩下一些参数，因此您可能需要在此处进行少量修改）。之后，字符串被标记化，以便于解析。在下一步中，中缀表达式被转换为前缀表达式。在最后一步，我构建了一个字符串，它将使输出看起来像您需要的那样（+- plus，--minus等等）。

于 2013-01-16T10:06:49.067 回答
0

由于我不确定您是否能够在调用该方法后获得该方法的主体，所以这是一个替代解决方案：

var a = 42;
var b = 2;

function action(c) {
  return a + 4 * b + c;
}

/**
 * get the given func body
 * after having replaced any available var from the given scope
 * by its *real* value
 */
function getFunctionBody(func, scope) {
  // get the method body
  var body = func.toString().replace(/^.*?{\s*((.|[\r\n])*?)\s*}.*?$/igm, "$1");  
  var matches = body.match(/[a-z][a-z0-9]*/igm);
  // for each potential var
  for(var i=0; i<matches.length; i++) {
    var potentialVar = matches[i];
    var scopedValue = scope[potentialVar];
    // if the given scope has the var defined
    if(typeof scopedValue !== "undefined") {
      // add "..." for strings
      if(typeof scopedValue === "string") {
        scopedValue = '"' + scopedValue + '"';
      }
      // replace the var by its scoped value
      var regex = new RegExp("([^a-z0-9]+|^)" + potentialVar + "([^a-z0-9]+|$)", "igm");
      var replacement = "$1" + scopedValue + "$2";
      body = body.replace(regex, replacement);
    }
  }
  return body;
}

// calling
var actionBody = getFunctionBody(action, this);

// log
alert(actionBody);

印刷：

return 42 + 4 * 2 + c;

演示

然后，您必须实现自己的function toLISP(body)功能或您可能需要的任何其他功能。

请注意，它不适用于复杂的作用域变量，例如var a = {foo: "bar"}.

于 2013-01-16T09:48:03.877 回答