如何写一个Parser

2016-07-23 / modified at 2022-04-04 / 2.3k words / 10 mins

️This article has been over 2 years since the last update.

解释器（Parser），顾名思义，就是对数据处理的实现。是一个能够输入一个命令或者描述后，内部进行运算，并输出数据的工具。

举个例子，计算器、网页、py、c甚至CPU都是解释器，它们在不同层面上对数据进行处理，高级的有动态语言的shell交互，底层的有CPU的机器码，都是对一行行命令码的解释。

通过对解释器进行了解，首先直观上能够抽象化很多算法类问题的输入处理，同时由于解释器内部使用了多种数据结构，提高自己的实战能力。

看了垠神的《怎样写一个Parser》，写的太棒了，用的也是计算器的例子，可惜垠神用的是Scheme语言。自己一直想动手用Java实现，终于抽出2天时间，参考多本书籍，最终本文代码能够实现"3*2-8*(3-(4*2))"这类的计算式。

阅读前最好了解一点编译原理

将文本转为Token枚举(String->Enum)
将中缀表达式转为后缀表达式
AST实现
遍历计算

将文本转为Token

这一步相当于词法分析，即对字符串中的每一个值进行提取与映射，目前可以用yacc等工具进行自动化处理，当然为了了解原理，下文为手工代码。

由于这里的Token非常少，所以用枚举进行了定义。为了简化开发，我们在这里不考虑空格，浮点等数值。

enum TokenType {

	ADD('+'), SUB('-'), MUL('*'), DIV('/'), 
	LEFT('('), RIGHT(')'), NUM('i');
	
	char name;
	
	TokenType(char tokenName) {
	  this.name = tokenName;
	}
}

class Token {
	TokenType type;
	int val;
}

接着就是字符串处理了，我们首先过滤了一些奇葩的输入，接着逐个子节地处理Token

private List<Token> getToken(String a) {
  //简单处理一下匹配
  //不支持Regex平衡组
  if (!a.matches("^[\(\d]?[\d\+\-\*\/\(\)]*[\)\d]?$")) {
    throw new IllegalArgumentException("can't parse the token");
  }
  final List<Token> tokens = new ArrayList<Token>();
  char c;
  Token token;

  StringBuilder sb = new StringBuilder();
  TokenType type;
  for (int i = 0; i < a.length(); i++) {
    c = a.charAt(i);
    if (isDigital(c)) {
      sb.append(c);
    } else if ((type = getOperatorToken(c)) != null) {
      if (sb.length() != 0) {
        token = new Token(TokenType.NUM, Integer.valueOf(sb.toString()));
        tokens.add(token);
        sb.setLength(0);
      }
      token = new Token(type, 0);
      tokens.add(token);
    } else {
      //never
      throw new IllegalArgumentException("bad character: " + c);
    }
  }
  //末尾的
  if (sb.length() != 0) {
    token = new Token(TokenType.NUM, Integer.valueOf(sb.toString()));
    tokens.add(token);
  }
  return tokens;
}

这样，我们接下来就不用各种奇葩的黑科技与字符串打交道了，而转移到更高层的抽象中。

这段代码的执行效果是这样的：

运行前

1	"334+32+2/(24)"

运行后

1	[334, ADD, 3, MUL, 2, ADD, 2, DIV, LEFT, 2, MUL, 4, RIGHT]

在Racket中，可以用Lex进行实现

; 引入工具库与前缀
(require parser-tools/lex)
(require (prefix-in : parser-tools/lex-sre))
; +-x/的正则表达式
(define-lex-abbrevs (op (:or #\+ #\- #\* #\/)))
; [a-z]|[A-Z]的正则表达式
(define-lex-abbrevs (word (:or (char-range # #\z) (char-range #\A #\Z))))
; \d 的正则表达式
(define-lex-abbrevs (digest (char-range ##\9)))
; \d+\.?\d*
(define-lex-abbrevs (float (:: (:+ digest) (:? #\.) (:* digest))))
(define calc-lexer
  (lexer
   [(:+ word)
    (cons (string->symbol lexeme)
          (calc-lexer input-port))]
   [#\( 
    (cons 'L
          (calc-lexer input-port))]
   [#\)
    (cons 'R 
          (calc-lexer input-port))]
   [float
    ; =>
    (cons (string->number lexeme)
          (calc-lexer input-port))]
   [op
    (cons (string->symbol lexeme)
          (calc-lexer input-port))]
   [whitespace 
    (calc-lexer input-port)]
   [(eof)
    '()]))
(calc-lexer (open-input-string "-3*(88 + 12333.44444)-(4*5)"))

将中缀表达式转为后缀表达式

此部分为语法分析的前部分，将对有括号的表达式进行处理，生成逆波兰表达式，即后缀表达式。各位可以把此步骤看成一个用栈实现的排序。

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

主要思路是这样的：我们首先需要知道，运算优先级[\(\)] > [\*\/] > [\+\-]，那么如何区分优先级呢？通过创建一个维护操作符的栈来实现。如下代码，当for循环中的token进入栈时，如果优先级比栈顶高，就直接入栈；如果优先级比栈顶低或者相等，就把栈顶元素赶出来，直到找到比栈中元素优先级更低的为止。

关于左右括号，其实不用太在意，它们与加减乘除不相互影响。for循环中，遇到左括号直接进栈，遇到右括号时在栈中找左括号，并取出中间的元素。

下面实际上就是在做模式匹配，实在不明白的，可以在switch打断点调试。

//Reverse Polish notation，RPN，或逆波兰记法
private List<Token> rnpList(List<Token> orign) {
  //输出结果
  List<Token> output = new ArrayList<Token>();
  //操作数的栈,用于处理优先
  Stack<Token> stack = new Stack<Token>();
  for (Token token : orign) {
    switch (token.getType()) {
      case NUM:
        output.add(token);
        break;
      case ADD:
      case SUB:
        //如果有高的或者同级的(+,-,*,/,),就把他们赶走,自己住进去
        while (!stack.isEmpty() && (!stack.peek().getType().equals(TokenType.LEFT)
            && !stack.peek().getType().equals(TokenType.RIGHT))) {
          output.add(stack.pop());
        }
        stack.push(token);
        break;
      case MUL:
      case DIV:
        //如果有高的(*,/),就把他们赶走,自己住进去
        while (!stack.isEmpty() && ((stack.peek().getType().equals(TokenType.MUL) || stack.peek()
            .getType()
            .equals(TokenType.DIV)))) {
          output.add(stack.pop());
        }
        stack.push(token);
        break;
      //处理左右括号
      case LEFT:
        //左括号优先级最高,直接入栈
        stack.push(token);
        break;
      case RIGHT:
        //找到左括号为止,全部出栈,不含括号
        while (!stack.isEmpty() && !stack.peek().getType().equals(TokenType.LEFT)) {
          output.add(stack.pop());
        }
        //去掉左括号
        if (!stack.isEmpty()) {
          stack.pop();
        }
        break;
    }
  }
  while (!stack.isEmpty()) {
    output.add(stack.pop());
  }
  return output;
}

通过这一步，我们去掉了括号，并变成了极容易被计算机计算的表达式。

运行前

1	[334, ADD, 3, MUL, 2, ADD, 2, DIV, LEFT, 2, MUL, 4, RIGHT]

运行后

1	[334, 3, 2, MUL, ADD, 2, 2, 4, MUL, DIV, ADD]

AST实现

构造抽象语法树(AST)，用于描述计算的实现

static class AST {
	Token operator;
	Token left;
	Token right;
	
	public AST(Token operator, Token left, Token right) {
	  this.operator = operator;
	  this.left = left;
	  this.right = right;
	}
	
	public int calc() {
	  switch (operator.getType()) {
	    case ADD:
	      return left.val + right.val;
	    case SUB:
	      return left.val - right.val;
	    case MUL:
	      return left.val * right.val;
	    case DIV:
	      return left.val / right.val;
	    default:
	      throw new IllegalArgumentException("can't execute: " + operator);
	  }
	}
}

遍历计算

这一步最简单，后缀计算，任何一本数据结构的书，在讲栈结构时都有这个教程

private int calc(List<Token> rnp) {
  Stack<Token> cache = new Stack<Token>();
  for (Token token : rnp) {
    switch (token.getType()) {
      case NUM:
        cache.push(token);
        break;
      default:
        Token b = cache.pop();
        Token a = cache.pop();
        AST ast = new AST(token, a, b);
        Token token1 = new Token(TokenType.NUM,ast.calc());
        System.out.println("token = " + token1 + "," + a + "," + b + "," + token);
        cache.push(token1);
    }
  }
  return cache.pop().val;
}

效果

调用效果如下

input = "3+4*5+(444+2)-3*(3/5)"
token = [3, ADD, 4, MUL, 5, ADD, LEFT, 444, ADD, 2, RIGHT, SUB, 3, MUL, LEFT, 3, DIV, 5, RIGHT]
output = [3, 4, 5, MUL, ADD, 444, 2, ADD, ADD, 3, 3, 5, DIV, MUL, SUB]
token = 4,5,MUL
token = 3,20,ADD
token = 444,2,ADD
token = 23,446,ADD
token = 3,5,DIV
token = 3,0,MUL
token = 469,0,SUB
test.calc(a); = 469

用Lisp实现

扩展用，有兴趣可以看下

#lang racket
; 定义一个名为 eval-ast,入参为exp的函数
(define eval-ast
  (λ (exp)
    (match exp
      [(? number? leaf) leaf] ;说明已经是叶子
      [`(,op,l,r)        ;对S表达式进行遍历
       (let ([v1 (eval-ast l)]
             [v2 (eval-ast r)])
         (match op
           [`+ (+ v1 v2)]
           [`- (- v1 v2)]
           [`* (* v1 v2)]
           [`/ (/ v1 v2)]))])))
; 执行计算
(eval-ast `(+ 1 (+ (* 2 5) (/ 2 4))))
;; => 11.5

相比Java中用String/枚举与t.left == null的实现，这里代码没有一行废话; 同时由于支持类型推导，避免了Java中各种int转换与小数点的问题

总结

尽量不要与String打交道，代码不但非常丑，以后也不好维护（类似于VO与DO的关系）
如果不喜欢递归这类函数调用，尽量用栈，思路将非常清晰。
将条件最小化，千万不要跨一大步实现小数点、空格等额外因素。

附录

打印BinaryTree，二叉树的深度遍历，方便进行直观理解

; racket draw Binary Tree
#lang racket
; 导入绘图工具类
(require pict pict/tree-layout)
; 判断Token是否是单个元素
(define (atom? x) (not (or (pair? x) (null? x))))
; 定义一个名为gen-ast,入参为exp的函数
(define gen-ast
  (λ (exp)
    (match exp
      [(? atom? leaf)   ;如果为叶子
       (tree-layout #:pict (text (~v leaf)))] 
      [`(,op,l,r)        ;对S表达式进行遍历
       (let ([v1 (gen-ast l)]
             [v2 (gen-ast r)])
         (tree-layout #:pict (text (~v op)) v1 v2))])))
; 将生成的 tree-layout 赋值到 tree 变量
(define tree (gen-ast `(+ 1 (+ (* 2 5) (/ 2 4)))))
; 执行绘图
(naive-layered tree)

生成的结果是这样的

参考

http://www.yinwang.org/blog-cn/2012/08/01/interpreter
http://blog.csdn.net/sgbfblog/article/details/8001651
《自制编程语言（图灵设计丛书）》
《学习正则表达式（图灵设计丛书）》

AST