Parsing • 最简单的 Parser 写法——含回朔的递归自顶而下分析

如果你听了老师上课讲的那一大坨根本没人听得懂的parse方法之后认为自己这辈子都造不出编译器了，那么本文介绍含回朔的递归自顶而下分析法正是你所需要的，这种方式非常容易想到，也非常容易编写，除了文法分析之外，对于词法分析，这个方法也可以一手包办，而且足以应付绝大多数编程语言的构造。

我们先结合一个例子来看一下这玩意怎么使的：

主要思想

含回朔的递归自顶而下分析法的主要思想是：将每个非终结符（推导式左边）的分析写成一个函数，将右侧的内容组合写在函数体里面，如果这个函数从左向右匹配某段代码字符串成功，就返回存放了对应信息的结构体和剩下的字符串，否则返回Error。

实践

我们要分析的文法是： $$ \displaylines { Expression \rightarrow Ident | Constant | InBrackets \mid Expression * Expression | Expression + Expression \\ InBrackets \rightarrow '(' Expression')' \\ Ident \rightarrow [a-zA-Z][a-zA-Z0-9]* \\ Constant \rightarrow [0-9]* } $$

上面的例子可以写成四个函数¹：

fn expression(code: string) -> (Expresion, string) | Error;
fn in_brackets(code: string) -> (InBrackets, string) | Error;
fn ident(code: string) -> (Ident, string) | Error;
fn constant(code: string) -> (Constant, string) | Error;

那么函数体怎么写呢？

alt、many0和tag

我们首先针对|和*，定义两个函数：

// 接受一组parser函数和字符串作为参数，返回其中最早成功匹配的parser的匹配结果，相当于|
fn alt<R>(parsers: Vec<Fn(string) -> (R, string) | Error>, input: string) -> (R, string) | Error {
	for parser in parsers {
		if parser(input) != Error {
			return parser(input)
		}
	}
	return Error
}

// 接受一个parser函数，返回其重复匹配0次以上的结果，相当于*
fn many0(parser: Fn(string) -> (R, string) | Error, input: string) -> (Vec<R>, string) | Error {
	result = new Vec();
	while parser(input) != error {
		r, input = parser(input)
		result.push(r)
	}
	return (result, input)
}

在实现一个tag函数来识别某些指定的字面量²：

fn tag(tagname: string, code: string) -> (string, string) | Error {
	if code.starts_with(tagname) {
		return tagname, code[len(tagname):]
	} else {
		return Error
	}
}

然后就可以实现上面的几个函数了：

fn mul(code: string) -> (Expression, string) | Error {
	// 识别左操作数, ? 代表如果它前面的函数返回Error，则当前函数也返回Error
	lhs, rest = expression(code)?
	// 识别*号
	op, rest = tag("*", rest)?
	// 识别右操作数
	rhs, rest = expression(rest)?
	return Expression {lhs, "*", rhs}
}

// add 函数同理，*变为+

fn expression(code: string) -> (Expresion, string) | Error {
	// 注意这里的顺序，优先级越低操作符对应的函数越要在前面
	// 不理解的话考虑一下1+2*3会怎么被parse就知道了
	return alt([
		add,
		mul,
		ident,
		constant,
		in_brackets,
	], code)
}
fn in_brackets(code: string) -> (InBrackets, string) | Error {
	bracket, rest = tag("(",code)?
	expr, rest = expression(rest)?
	bracket, rest = tag(")",code)?
	return InBrackets(expr), rest
}
fn ident(code: string) -> (Ident, string) | Error {
	return alt(tag("a", code), tag("b", code),........) 
}
fn digit(code: string) -> (string, string) | Error {
	return alt(tag("0", code), tag("1", code),........) 
}
fn constant(code: string) -> (Constant, string) | Error {
	return many0(digit, code)
}

左递归

实际写出来之后会发现这里有一个问题：

fn expression(code: string) -> (Expresion, string) | Error {
	return alt([
		add,
		mul,
		ident,
		constant,
		in_brackets,
	], code)
}

其中的mul，间接调用了expression(code)，而这时又会反过去调用mul(code)，且其中的code参数一直没有变化，add也有这个问题，这样在程序中就会造成无限递归。

这也是为什么课上说在做自顶而下文法分析的时候要先消除左递归的原因。

怎么消除也很简单，我们要让mul和add至少从code中“消耗”一个优先级比其自身高的expression，即：

fn higher_than_mul(code: string) -> (Expression, string) | Error {
	return alt([
		ident,
		constant,
		in_brackets
	], code)
}

fn mul(code: string) -> (Expression, string) | Error {
	// 识别左操作数, 消耗掉一个优先级高于*结果的语法元素
	lhs, rest = higher_than_mul(code)?
	// 识别*号
	op, rest = tag("*", rest)?
	// 识别右操作数
	rhs, rest = expression(rest)?
	return Expression {lhs, "*", rhs}
}

// add 同理，你应该自己能想到的

实际上就相当于将Expression部分的文法改成了： $$ \displaylines { Expression \rightarrow Add | Mul | Ident | Constant | InBrackets \\ Add \rightarrow HigherThanAdd + Expression \\ Mul \rightarrow HigherThanMul * Expression \\ HigherThanMul \rightarrow Ident | Constant|InBrackets \\ HigherThanAdd \rightarrow Mul | HighterThanMul } $$ 和书上讲的消除左递归的方案是不是很像？

这样一个简单表达式的parser就完成了。

优势与不足

优势

这种parser的优势有：

• 容易理解与实现
• 写出的代码是完全可读可调试的
• 这种分析器可以分析 $LL(k)$ 文法，在实践中，这一分析器可以应用于几乎所有可能会碰到的文法，当然，除了C++之外，C++不是$CFG$……。

不足

这种parser的不足有：

• 效率问题，回朔可能会带来一定的性能问题，因此可能不适用于一些极其要求性能的场合³
• 一般来说生成的所有运算符都是右结合的，上面的例子由于加法和乘法都有交换律所以也没关系，但是减法和除法就会出现问题，需要在 AST 上做 hack 解决，hack 的一个方案如下：

  • 将文法的相应部分改写成： $$ \displaylines { Add \rightarrow HigherThanAdd\ (+ HigherThanAdd)* \\ Mul \rightarrow HigherThanMul\ (* HigherThanMul)* \\ } $$

    然后将 parse 得到的东西用如下方法转换（折叠）为 AST：

    fn to_ast(first: RValue, rest: Vec<(String, RValue)>) -> BinOp {
      let mut current_lhs = first;
      for (op, value) in rest.into_iter() {
          current_lhs = BinOp {
              operator: op,
              lhs: Box::new(current_lhs),
              rhs: Box::new(value),
          }
          .into()
      }
      current_lhs.try_into().unwrap()
    }