表达式解析:如何标记化

Question

我想在Javascript代码中标记类似Java/Javascript的表达式.我的输入将是一个包含表达式的字符串,输出需要是一个标记数组.

做这样的事情的最佳做法是什么？我是否需要迭代字符串或者是否有正则表达式为我执行此操作？

我需要这个能够支持:

• 数字和字符串文字(单引号和双引号,带引号转义)
• 基本的数学和布尔运算符和比较器(+, - ,*,/,!和,不,<,>等)
• 使用递归进行对象访问的点和括号表示法(foo.bar,foo ['bar'],foo [2] [prop])
• 带嵌套的括号
• 三元运算符(foo？bar:'baz')
• 函数调用(foo(bar))

eval()出于安全原因,我特别希望避免使用或任何类型的东西.此外,eval()无论如何都不会为我表达这个表达.

Answer 1

学习编写递归下降解析器.一旦理解了这些概念,就可以用任何语言来实现:Java,C++,JavaScript,SystemVerilog,......等等.如果你可以处理字符串,那么你可以解析.

递归下降解析是一种可以轻松手动编码的解析基本技术.如果您无权访问(或不想愚弄)解析器生成器,这将非常有用.

在递归下降解析器中,语法中的每个规则都会转换为解析规则的过程.如果你需要参考其他规则,那么你可以通过调用它们来实现 - 它们只是程序.

一个简单的例子:涉及数字,加法和乘法的表达式(这说明了运算符优先级).一,语法:

expr ::= term
         | expr "+" term

term ::= factor
         | term "*" factor

factor ::= /[0-9/+ (I'm using a regexp here)

现在编写解析器(包括词法分析器;使用递归下降,你可以将两者放在一起).我从来没有使用过JavaScript,所以让我们在(生锈的)Java中尝试这个:

class Parser {
  string str;
  int idx; // index into string

  Node parseExpr() throws ParseException
  {
    Node op1 = parseTerm();
    Node op2;

    while (idx < str.size() && str.charAt(idx) == '+') {
      idx++;
      op2 = parseTerm();
      op1 = new AddNode(op1, op2);
    }
    return op1;
  }

  Node parseTerm() throws ParseException
  {
    Node op1 = parseFactor();
    Node op2;

    while (idx < str.size() && str.charAt(idx) == '*') {
      idx++;
      op2 = parseFactor();
      op1 = new MultNode(op1, op2);
    }
    return op1;
  }

  Node parseFactor() throws ParseException
  {
    StringBuffer sb = new StringBuffer();
    int old_idx = idx;

    while (idx < str.size() && str.charAt(idx) >= '0' && str.charAt(idx) <= '9') {
      sb.append(str.charAt(idx));
      idx++;
    }
    if (idx == old_idx) {
      throw new ParseException();
    }
    return new NumberNode(sb.toString());
  }
}

您可以看到每个语法规则如何转换为过程.我没有测试过这个; 这是读者的练习.

您还需要担心错误检测.实际编译器需要从解析错误中恢复,以尝试解析其输入的其余部分.像这样的单行表达式解析器根本不需要尝试恢复,但它确实需要确定存在解析错误并标记它.如果您的语言允许,最简单的方法是抛出异常,并在解析器的入口点捕获它.我在上面的示例中没有检测到所有可能的解析错误.

有关更多信息,请在Wikipedia中查找"LL parser"和"Recursive descent parser".正如我在开始时所说的那样,如果你能理解这些概念(并且它们与LALR(1)状态机配置闭包背后的概念相比很简单)那么你就有权为任何语言的小任务编写一个解析器.因为你有一些基本的字符串功能.享受力量.