表达式解析:如何标记化

学习编写递归下降解析器。一旦理解了这些概念,就可以用任何语言进行:Java、C++、JavaScript、System Verilog、……无论什么。如果您可以处理字符串,那么您可以解析。

递归下降解析是一种基本的解析技术,很容易用手工编码。如果您没有访问解析器生成器的权限(或者不想用它来愚弄),那么这很有用。

在递归下降解析器中,语法中的每个规则都被转换为解析规则的过程。如果您需要参考其他规则,那么您可以通过调用它们来做到这一点——它们只是过程。

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

expr ::= term
         | expr "+" term

term ::= factor
         | term "*" factor

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

现在编写解析器(包括lexer;通过递归下降,您可以将两者结合在一起)。我从未使用过JavaScript,所以让我们在(R生锈)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 parser”和“recursive descence parser”。正如我在开始时所说,如果您能够理解这些概念(与lalr(1)状态机配置闭包背后的概念相比,它们很简单),那么只要您具有一些基本的字符串功能,就可以为任何语言的小任务编写解析器。享受权力。

对于速度不重要的简单lexer,我通常为每种令牌编写一个regex,并反复尝试在输入开始时依次匹配每种令牌。(确保您不会使用O(n^2)算法!)像lex这样的工具将产生更高效的lexer,因为它将regex组合成一个状态机。

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

因为从形式上讲,您将要操作的语言是正则的,所以您可以使用正则表达式。但我不推荐给你。

尽管我从未使用过JS/CC,但我会先尝试使用它,如果它不起作用,我会自己构建一个词汇分析器。