4

我希望在 Javascript 代码中标记类 Java/Javascript 的表达式。我的输入将是一个包含表达式的字符串，输出需要是一个标记数组。

做这样的事情的最佳做法是什么？我需要迭代字符串还是有一个正则表达式可以为我做这个？

我需要这个能够支持：

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

出于安全原因，我特别想避免使用eval()或任何类似的东西。此外，eval()无论如何都不会为我标记表达式。

4

3 回答 3

11

学习编写递归下降解析器。一旦你理解了这些概念，你就可以用任何语言来做：Java、C++、JavaScript、SystemVerilog，……随便什么。如果你可以处理字符串，那么你可以解析。

递归下降解析是一种基本的解析技术，可以很容易地手动编码。如果您无法访问（或不想欺骗）解析器生成器，这将很有用。

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

一个简单的例子：涉及数字、加法和乘法的表达式（这说明了运算符的优先级）。一、语法：

expr ::= 术语
         | expr "+" 项

术语 ::= 因子
         | 术语“*”因子

因子 ::= /[0-9/+ （我在这里使用正则表达式）

现在编写解析器（包括词法分析器；使用递归下降，您可以将两者放在一起）。我从未使用过 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 解析器”和“递归下降解析器”。正如我在开头所说，如果你能理解这些概念（与 LALR(1) 状态机配置闭包背后的概念相比，它们很简单），那么你就可以用任何语言为小任务编写解析器，只要因为你有一些基本的字符串能力。享受权力。

于 2009-05-22T18:14:04.143 回答
0

对于速度不重要的简单词法分析器，我通常为每种标记编写一个正则表达式，并反复尝试将每个标记依次与输入的开头匹配。（确保你最终不会使用 O(n^2) 算法！）像 lex 这样的工具会产生更高效的词法分析器，因为它将正则表达式组合到一个状态机中。

于 2009-05-22T17:44:07.437 回答
0

您需要实现一个词法分析器。您可以使用js/cc来完成，也可以自己实现有限自动机。

因为，正式地，您将操作的语言是正则的，您可以使用正则表达式。但我不推荐给你。

虽然我从来没有用过 js/cc，但我会先尝试一下，如果它不起作用，我会尝试自己构建一个词法分析器。

于 2009-05-22T17:44:47.777 回答