表达式解析：如何标记化

Question

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

执行此类操作的最佳实践是什么？我是否需要迭代字符串，或者是否有正则表达式可以为我执行此操作？

我需要这个能够支持：

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

出于安全原因，我特别想避免使用

eval()

或类似的内容。此外，

eval()

无论如何也不会为我标记该表达式。

Answer 1

学习编写递归下降解析器。一旦理解了这些概念，您就可以使用任何语言来完成它：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());
  }
}

您可以看到每个语法规则如何转化为过程。我还没有测试过这个；这是给读者的一个练习。

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

有关更多信息，请在维基百科中查找“LL 解析器”和“递归下降解析器”。正如我在一开始所说的，如果您能够理解这些概念（并且与 LALR(1) 状态机配置闭包背后的概念相比，它们很简单），那么您就可以用任何语言为小任务编写解析器，只要因为你有一些基本的字符串能力。享受力量。

Answer 2

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

Answer 3

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

从形式上来说，由于您要操作的语言是常规语言，因此您可以使用正则表达式。但我不推荐给你。

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

Answer 4

我为所有数学表达式 (36) 和属性 (8) 创建了自己的脚本。

所有这些方法和属性都有效，除了 log10、log1p 和 log2

我该如何解决这个问题？

致以诚挚的问候，