logo标签列表

为简单的数学运算生成语法树

javascriptparse-tree
10

我正在尝试生成一个语法树，用于给定包含简单数学运算符（+，-，*，/和括号）的字符串。给定字符串为“1 + 2 * 3”：

它应该返回类似于这样的数组：
["+",
 [1,
  ["*",
   [2,3]
  ]
 ]
]

我写了一个函数，可以将"1 + 2 * 3"转换为[1，"+"，2，"*"，3]。
问题是：我不知道如何给某些运算符设置优先级。
我的代码如下：
function isNumber(ch){
    switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
        case '.':
            return true;
        break;
        default:
            return false;
            break;
    }
}

function generateSyntaxTree(text){
    if (typeof text != 'string') return [];
    var code = text.replace(new RegExp("[ \t\r\n\v\f]", "gm"), "");
    var codeArray = [];
    var syntaxTree = [];

    // Put it in its on scope
    (function(){
        var lastPos = 0;
        var wasNum = false;
        for (var i = 0; i < code.length; i++) {
            var cChar = code[i];
            if (isNumber(cChar)) {
                if (!wasNum) {
                    if (i != 0) {
                        codeArray.push(code.slice(lastPos, i));
                    }
                    lastPos = i;
                    wasNum = true;
                }
            } else {
                if (wasNum) {
                    var n = Number(code.slice(lastPos, i));
                    if (isNaN(n)) {
                        throw new Error("Invalid Number");
                        return [];
                    } else {
                        codeArray.push(n);
                    }
                    wasNum = false;
                    lastPos = i;
                }
            }
        }
        if (wasNum) {
            var n = Number(code.slice(lastPos, code.length));
            if (isNaN(n)) {
                throw new Error("Invalid Number");
                return [];
            } else {
                codeArray.push(n);
            }
        }
    })();

    // At this moment, codeArray = [1,"+",2,"*",3]

    return syntaxTree;
}

alert('Returned: ' + generateSyntaxTree("1 + 2 * 3"));
你需要手动完成这个任务吗？通常这些事情都是通过解析器生成器来完成的，比如ANTLR或者Bison。 - Michael Mrozek
我从零开始做这个，是为了我正在创建的解析器。 - user216441
如果您查看我的更新答案，您将获得一个骨架，用于构建更高级的解析器，基于您的示例的工作实现。从基础开始了解解析的工作原理是很好的，因为这样使用诸如ANTLR、Flex、Bison、yacc等工具就更容易了。 - Ernelli
5个回答
7

如果不使用FLEX/BISON或任何类似的软件包，进行自顶向下解析的方法是首先编写一个可以解析输入并提供令牌的分词器。

基本上，您需要一个分词器，它提供getNextToken、peekNextToken和skipNextToken功能。

然后，您可以使用此结构逐步实现下降过程。

// parser.js
var input, currToken, pos;

var TOK_OPERATOR = 1;
var TOK_NUMBER = 2;
var TOK_EOF = 3;

function nextToken() {
  var c, tok = {};

  while(pos < input.length) {
    c = input.charAt(pos++);
    switch(c) {
      case '+':
      case '-':
      case '*':
      case '/':
      case '(':
      case ')':
    tok.op = c;
    tok.type = TOK_OPERATOR;
    return tok;

      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
    tok.value = c;
    tok.type = TOK_NUMBER;
    return tok;

      default:
    throw "Unexpected character: " + c;
    }
  }
  tok.type = TOK_EOF;
  return tok;
}

function getNextToken() {
  var ret;

  if(currToken)
    ret = currToken;
  else
    ret = nextToken();

  currToken = undefined;

  return ret;
}

function peekNextToken() {
  if(!currToken)
    currToken = nextToken();

  return currToken;
}

function skipNextToken() {
  if(!currToken)
    currToken = nextToken();
  currToken = undefined;
}

function parseString(str) {
  input = str;
  pos = 0;

  return expression();
}


function expression() {
  return additiveExpression();
}

function additiveExpression() {
  var left = multiplicativeExpression();
    var tok = peekNextToken();
    while(tok.type == TOK_OPERATOR && (tok.op == '+' || tok.op == '-') ) {
        skipNextToken();
        var node = {};
        node.op = tok.op;
        node.left = left;
        node.right = multiplicativeExpression();
        left = node;
    tok = peekNextToken();
    }
    return left;
}

function multiplicativeExpression() {
  var left = primaryExpression();
    var tok = peekNextToken();
    while(tok.type == TOK_OPERATOR &&  (tok.op == '*' || tok.op == '/') ) {
        skipNextToken();
        var node = {};
        node.op = tok.op;
        node.left = left;
        node.right = primaryExpression();
        left = node;
    tok = peekNextToken();
    }
    return left;
}

function primaryExpression() {
  var tok = peekNextToken();
  if(tok.type == TOK_NUMBER) {
    skipNextToken();
    node = {};
    node.value = tok.value;
    return node;
  }
  else
  if(tok.type == TOK_OPERATOR && tok.op == '(') {
    skipNextToken();
    var node = expression(); // The beauty of recursion
    tok = getNextToken();
    if(tok.type != TOK_OPERATOR || tok.op != ')')
      throw "Error ) expected";
    return node    
  }
  else
    throw "Error " + tok + " not exptected";
}

正如您所看到的，您始终从请求最低特权操作开始，该操作需要其左右术语为下一个更高特权操作，以此类推。一元运算符的结构略有不同。有趣的是在遇到括号时的递归处理。

以下是一个演示页面，使用解析器并呈现解析树（代码已经准备好了...）

<html>
<head>
<title>tree</title>
<script src="parser.js"></script>
</head>

<body onload="testParser()">

<script>

function createTreeNode(x, y, val, color) {
  var node = document.createElement("div");
  node.style.position = "absolute";
  node.style.left = "" + x;
  node.style.top = "" + y;

  node.style.border= "solid";
  node.style.borderWidth= 1;
  node.style.backgroundColor= color;

  node.appendChild(document.createTextNode(val));

  return node;
};

var yStep = 24;
var width = 800;
var height = 600;

var RED = "#ffc0c0";
var BLUE = "#c0c0ff";

container = document.createElement("div");
container.style.width = width;
container.style.height = height;
container.style.border = "solid";

document.body.appendChild(container);

var svgNS = "http://www.w3.org/2000/svg";

function renderLink(x1, y1, x2, y2)
{
  var left = Math.min(x1,x2);
  var top = Math.min(y1,y2);

  var width = 1+Math.abs(x2-x1);
  var height = 1+Math.abs(y2-y1);

  var svg = document.createElementNS(svgNS, "svg");
  svg.setAttribute("x", left);
  svg.setAttribute("y",  top);
  svg.setAttribute("width", width );
  svg.setAttribute("height", height );

  var line = document.createElementNS(svgNS,"line");

  line.setAttribute("x1", (x1 - left) );
  line.setAttribute("x2", (x2 - left) );
  line.setAttribute("y1", (y1 - top) );
  line.setAttribute("y2", (y2 - top) );
  line.setAttribute("stroke-width",  "1");
  line.setAttribute("stroke",  "black");
  svg.appendChild(line);

  var div = document.createElement("div");
  div.style.position = "absolute";
  div.style.left = left;
  div.style.top = top;
  div.style.width = width;
  div.style.height = height;

  div.appendChild(svg);
  container.appendChild(div);  
}

function getHeight(dom) {
    var h = dom.offsetHeight;
    return h;
}

function getWidth(dom) {
    var w = dom.offsetWidth;
    return w;
}

function renderTree(x, y, node, width, height)
{
    if(height < 1.5*yStep)
    height = 1.5*yStep;

    var val;
    if(node.op) {
      val = node.op;
      color = BLUE;
    }
    else
      if(node.value) {
    val = node.value;
    color = RED;
      }
      else
    val = "?";

    var dom = createTreeNode(x, y, val, color);
    container.appendChild(dom);

    var w = getWidth(dom);
    var h = getHeight(dom);

    var nx, ny;

    var child;

    if(node.left) {
    nx = x - width/2;
    ny = y+height;
    var child = renderTree(nx, ny, node.left, width/2, height/2);
        renderLink(x+w/2, y+h, nx+getWidth(child)/2, ny);
    }

    if(node.right) {
    nx = x + width/2;
    ny = y+height;

    child = renderTree(nx, ny, node.right, width/2, height/2);
        renderLink(x+w/2, y+h, nx+getWidth(child)/2, ny);
    }
    return dom;
}

var root;

function testParser()
{
  var str = "1+2*5-5*(9+2)";

  var exp = document.createElement("div");
  exp.appendChild(document.createTextNode(str));
  container.appendChild(exp);
  var tree = parseString(str);
  renderTree(width/2, 20, tree, width/2, 4*yStep);
}

</script>

</body>
</html>
好的，我无法比维基百科更好地解释它。我已更新我的代码，成为一个完全工作的示例，配备了树形渲染器作为额外功能（仅在Firefox或Chrome中运行）。 - Ernelli
2
类似于其他答案中的方法，这里是另一种递归实现。它具有以下独特的特点：
  • 它生成了在问题中描述的嵌套数组结构。
  • 它支持带符号的数字，因此-1（不带中间空格）可以被解释为字面值，而不一定是运算符。
  • 它支持一元负号，例如这个例子中的第一个负号：-(-1)。它也接受字符串- -1或--1等。
  • 它支持小数，小数点前必须有一个数字。
  • 它使用正则表达式来识别标记。这将匹配数字字面量作为一个标记，以及任何其他单个非空格字符。
  • 当存在语法验证错误时，它会抛出错误，并指示出现错误的输入字符串位置。

所支持的语法可以描述为：

<literal>    ::= [ '-' ] <digit> { <digit> } [ '.' { <digit> } ] ; no white space allowed
<operator2>  ::= '*' | '/'
<operator1>  ::= '+' | '-'
<factor>     ::= '-' <factor> | '(' <expression> ')' | <literal>
<term>       ::= [ <term> <operator2> ] <factor>
<expression> ::= [ <expression> <operator1> ] <term>

尽可能将减号作为<literal>的一部分进行匹配。

交互式片段

function parse(s) {
  // Create a closure for the two variables needed to iterate the input:
  const
    get = ((tokens, match=tokens.next().value) =>
        // get: return current token when it is of the required group, and move forward, 
        //      else if it was mandatory, throw an error, otherwise return undefined
        (group, mandatory) => {
          if (match?.groups[group] !== undefined) 
            return [match?.groups[group], match = tokens.next().value][0];
          if (mandatory) 
            throw `${s}\n${' '.repeat(match?.index ?? s.length)}^ Expected ${group}`;
        }
      )(  // Get iterator that matches tokens with named capture groups.
        s.matchAll(/(?<number>(?:(?<![\d.)]\s*)-)?\d+(?:\.\d*)?)|(?<open>\()|(?<close>\))|(?<add>\+|(?<unary>-))|(?<mul>[*\/])|(?<end>$)|\S/g)
      ),
    // node: Creates a tree node from given operation
    node = (operation, ...values) => [operation, values],
    // Grammar rules implementation, using names of regex capture groups, returning nodes
    factor = (op=get("unary")) => 
      op ? node(op, factor()) : get("open") ? expr("close") : +get("number", 1),
    term = (arg=factor(), op=get("mul")) => 
      op ? term(node(op, arg, factor())) : arg,
    expr = (end, arg=term(), op=get("add")) => 
      op ? expr(end, node(op, arg, term())) : (get(end, 1), arg);
  return expr("end");
}

// I/O Management

const [input, output] = document.querySelectorAll("input, pre");
(input.oninput = () => {
    try {
        output.textContent = JSON.stringify(parse(input.value), null, 2)
    } catch(err) {
        output.textContent = err;
    }
})();
input { width: 100%; margin-bottom: 10px; }
Math expression: <input value="1 + 2 * 3">
<pre></pre>

解释

tokens 是一个基于正则表达式的输入迭代器。该正则表达式使用了回顾断言来确保减号 -- 如果存在 -- 不是一个二元运算符，并且可以包含在数字字面量的匹配中。该正则表达式定义了命名组，因此代码可以依赖名称而不必引用字面字符。

get 使用这个迭代器获取共享变量（match）中的下一个标记，并返回前一个标记。 get 接受一个参数来指定哪个命名组应该有一个匹配项。如果确实如此，则将读取下一个标记，否则 get 将检查是否必须匹配。如果是这样，就会抛出异常，否则函数返回未定义，以便调用者可以尝试另一个语法规则。

term、factor 和 expr 实现了相应名称的语法规则。它们依赖于 get（带参数）来决定在语法规则中采取哪种方式。这些函数都返回树（根节点）。

node 自下而上地构造输出树中的节点。如果树中的节点应该是不同的数组，或者应该执行一些缩减（合并节点）操作，则需要更改此函数。

2

需要做的是使用像flex或ANTLR这样的解析器生成器（在谷歌上搜索可以找到适合您语言的解析器）。

但如果您只是出于兴趣或想学习解析器的工作原理，可以查阅维基百科中有关递归下降解析器的内容。

可以轻松地为简单表达式制作一个简单的递归下降解析器。您可以将语法定义为：

<expression> ::= <term> | <term> <add_op> <expression>
<term> ::= <factor> | <factor> <mul_op> <term>
<factor> ::= ( <expression> ) | <number> 
<add_op> ::= + | -
<mul_op> ::= * | /

注意，通过使<term>的规则包含<factor>的规则，这个语法确保所有乘除操作发生在任何加减操作之下。这确保了这些操作首先被评估。
1
0
我曾经建立过一个有趣的小计算器，也遇到了和你一样的问题。我的解决方法是首先构建语法树而不考虑运算优先级。每个节点都有一个优先级值，当对非常量进行eval时，我会检查左节点：如果它的优先级较低，我会顺时针旋转树：将其带入评估并首先进行评估，右节点同理。然后我只需尝试再次进行评估。这种方法对我来说似乎足够好用。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接