递归下降语法分析详解

引用

本文以 lichray 设计的 S-dict(t) 配置文件解析器为例，简单介绍了词法分析器的原理，详细讲述了递归下降语法分析器手工构造方法。因为该项目本身已经完成，故此本文拥有一个实际可用的例子，是不可多得的入门教程。

引用

T1 大人说过，技术的迅速贬值是十分残酷的，比如大部分的手工优化代码，早已被编译器们代劳。这篇文章中要说的递归下降语法分析方法也是严重贬值了的技术之一。不过我认为，在享受着别人构造的自动化工具同时，知道其原理还是很重要的。一个典型的例子就是正则表达式——大家都会用，能保证写对的人也很多，但看了专家们的解答后都自愧不如——原因很简单：你会写正则表达式的编译器吗？
不过这篇文章并不是在教你怎样写 yayacc，只是希望你能从中体会到工具的思想并能更好地组织头脑中的 BNF 产生式。当然了，用这种方法手工构造一个代码语法高亮程序也是个不错的想法。

很多人都是从《C 编程语言》这本书上听说递归下降这种优美的语法分析器手工构造方法的，但这“很多人”中的很多人事实上没有看懂或者是看懂了就是构造不出自己的语法分析器。我三个月前完成了自己设计的 S-dict(t) 解析器，找到一个来理清这里面思路的好机会。

S-dict(t) 简介
这是作者设计的一直配置文件和数据交换格式，语法类似 Scheme，支持多种数据类型甚至包括迭代器。具体的示例文件太长，在附件中可获得。它的解析器相当于只把编程语言的解析过程做到语法分析树构造这一步，天然的例子。

main ::= {tree}
tree ::= '(' id leaf ')'
leaf ::= exps | main
exps ::= [{exp}]
exp  ::= id | bool | num | str | arr | low
id   ::  [^#\.\d\(\)\[\]\{\}'"`,;+-][^\s\(\)\[\]\{\}'"`,;]*
bool ::  #t|#f|#T|#F
num  ::  [+-]?[0-9]*\.?[0-9]+([eE][+-]?[0-9]+)?
str  ::  '\'' [{chr}] '\'' | '"' [{chr}] '"'
low  ::  #[^\s\(\)\[\]\{\}'"`,;]*
chr  ::= any-Unicode-character-except-"-or-\-or-control-character | 
		\" | \\ | \0 | \b | \7 | \f | \n | \r | \t | \v | 
		\x two-hex-digits | \u four-hex-digits
number
arr  ::= '[' arrc ']'
arrc ::= [{exp}]
comt ::  ^\s*#.*$

以上它的完整的 E-BNF 产生式，是实现解析器的根据，在下面两章会被用到。

词法分析：到底是什么
《现代编译原理》这本书上对词法分析的介绍尤为生动，生动的结果就是给人一种错觉：词法分析需要完整地解析正则表达式，连接有穷自动机，所以手工实现，难度不亚于给自动机作数学注明。但那只是语言学的理论分析结果。在实际应用中，如果有什么语言的词法分析需要严格地完全连接非确定有穷自动机，那只能说明这个语言设计地很“令人困惑”。
词法分析器只不过是这样的一个程序：你给它要分析的程序源代码，它返回一个数组，数组中的每一项都是正确分割了的词法元素。比如对于一段 S-dict(t) 代码：
(i (name 'lichray')
(age 13))
它应该返回 ['(', 'i', '(', 'name', "'lichray'", ')', '(', 'age', 13, ')', ')']。当然了，这种做法是比较简易的，通用的做法应当是给每个词法元素一个数据类型，然后返回相应的对象/实例/结构。构造它，根据词法元素表照抄即可。

## 这些全是正则表达式
id   ::  [^#\.\d\(\)\[\]\{\}'"`,;+-][^\s\(\)\[\]\{\}'"`,;]*
bool ::  #t|#f|#T|#F
num  ::  [+-]?[0-9]*\.?[0-9]+([eE][+-]?[0-9]+)?
str  ::  '\'' [{chr}] '\'' | '"' [{chr}] '"'
low  ::  #[^\s\(\)\[\]\{\}'"`,;]*
main ::  \(
end  ::  \)
arr ::  \[
narr ::  \]

解析字符串的思路大致是这样：对每个词法元素写一个函数，以一个主函数完成词法元素的判断过程，并调用相应的函数解析。每完成一个元素的解析，就返回拆解下来的结果和字符串的剩余部分，将这些数据，结果、剩余字符串和行号返回给主函数继续。

// 这个函数就可以完成这样的工作
// ssub(string, pattern) 同时返回 pattern 匹配 string 后的结果和余下的字符串
function ssub (s, p) {
	var ss = p.exec(s)[0]
	return [ss, s.slice(ss.length)]
}
// 弹出下一个单词
function word (s) {
	return ssub(s, /^[^\s\(\)\[\]\{\}'"`,;]+/)
}
// 弹出下一个“东西”，仅用于报错
function gew (s) {
	return /^[^\s\(\)\[\]'"]+/.exec(s)[0]
}
// 还真的报错了
function error (m, ln) {
	throw Error (m+" in line "+ln)
}

	// 先给出判断语法元素的函数，它们的参数是剩余的字符串
	// 剩余的字符串没有了，整个代码也到头了
	function isEOF (c) { return c == "" }
	function beLine (c) { return c[0] == '\n' }
	function beSpase (c) { return /\s/.test(c[0]) }
	function beId (c) { return /[^#\.\d\(\)\[\]\{\}'"`,;+-]/.test(c[0]) }
	function beBool (c) { return c[0] == '#' }
	function beNum (c) { return /[-+\d\.]/.test(c[0]) }
	function beStr (c) { return c[0] == '\'' || c[0] == '\"' }
	function beMain (c) { return c[0] == '(' }
	function beEnd (c) { return c[0] == ')' }
	function beArr (c) { return c[0] == '[' }
	function beNarr (c) { return c[0] == ']' }

似乎很繁琐。真的吗？可别忘了我整个程序近400行代码可只写了8行注释哦~`
注意：事实上，S-dict(t) 解析器并没有使用独立的词法分析器，而是把词法分析和语法分析同时完成了，而且本文并非以讲解词法分析为主。所以下面的代码虽然放在源代码文件中时几乎实际可运行，但没有被实际采用。

/* 基本函数 */
// 连接项目与列表
function cons (o, l) {
	return [o].concat(l)
}
// 取列表除去第一项后余下的部分
function cdr (l) {
	return l.slice(1)
}
// 消除左侧除换行之外的空白
function strim (s) {
	return s.replace(/^\s+?(?=\n)?/,'')
}

/* 词法分析器 */
// 标准的正则尾递归优化写法。尽管 JavaScript 不支持优化，但不失为一种很好的组织程序的手段
// 使用时调用 slex(string, [], 1)，参数 t 用来暂存分析数组
function slex (s, t, ln) {
	if (isEOF(s)) return t.reverse()
	var tmp = []
	// 用 ln 参数保存行数
	if (beLine(s)) return slex(cdr(s), ln+1)
	if (beSpase(s)) return slex(strim(s), ln)

	else if (beBool(s)) tmp = bool(s, ln)
	else if (beNum(s)) tmp = num(s, ln)
	else if (beId(s)) tmp = id(s, ln)
	else if (beStr(s)) tmp = str(s, ln)
	else if (beMain(s)) tmp = main(s, ln)
	else if (beEnd(s)) tmp = end(s, ln)
	else if (beArr(s)) tmp = arr(s, ln)
	else if (beNarr(s)) tmp = narr(s, ln)
	else error("Unknown Value: "+gew(s), ln)

	return slex(tmp[1], cons(tmp[0], t), tmp[2])
}

/* 所有的词法元素的解开过程 */
// 每个函数返回的第三个值是新的行号
// 此处省略，详见附件源代码 179-222 行
// 源代码中 arr、narr、main、end 几个函数都是语法分析的版本，
// 以 arr 举例说明这一系列函数的共性
function arr (s, ln) {
	return ['[', cdr(s), ln]
}
// 其他的函数只不过是使用了 ssub() 函数通过正则表达式解析了而已。

这里注意一下：为什么没有 low 词法元素的处理函数？在源代码中也可以看到，因为 low 和 bool 共用同一个起始字符，所以解析函数也被写到了一起。最后一章将会解释这样做的意义。

语法分析：词法分析立体版

语法分析的目的
无论是生成抽象语法树（AST）还是算符优先栈还是别的什么数据结构，我们发现，最终在根据分析结果执行代码时，其实都是在做一个树形过程，都需要逻辑上的一个立体的数据结构。语法分析的，就是通过获取平面的词法分析结果，根据语法结构描述（比如 BNF）输出立体的数据结构。在 S-dict(t) 这个例子中，我们选择的数据结构是 JavaScript 对象构成的树。例如代码
(i (name 'lichray')
(age 13))
的分析结果应该是：
{i: {name: 'lichray', age:13}}
限制是：一个树枝上如果有叶子或其他树枝，整个树枝的下属必须全部是叶子或树枝而不能是数据；数据只能出现在叶子上。

E-BNF 和 BNF
除了知道语法分析的“来龙去脉”，还需要一样描述语法语法结构的形式语言。现在的教科书上所教授的一般是扩展的巴菲斯-劳尔范式(E-BNF)，但是事实，E-BNF 相对于 BNF，存在一个很有意思的问题：那就是自由度过大。除非按照教科书上的方法消除左递归，否则往往很难手工构造。事实上，我上文中给出的 E-BNF 也并非一开始就是那样，

main ::= {tree}
tree ::= '(' id leaf ')'
leaf ::= exps | main

这三句很明显可以被非常直接地合并成

tree ::= '(' id exps | {tree} ')'

一句。但这样你就不得不把构建分析表的工作交给 yacc 之类的工具了，因为你没有写出全部的语法元素。
而 BNF 可以强迫你写出大部分需要递归描述的语法元素，并且可以直接地指定语法的结合方向。S-dict(t) 的 BNF 如下：

// e 代表为空，对应的希腊字母
// 当然也可以消除 e，把为空表现在上级产生式中
main ::= tree | tree main
tree ::= '(' id leaf ')'
leaf ::= exps | main
exps ::= e | exp | exp exps
exp  ::= id | bool | num | str | arr | low
arr  ::= '[' arrc ']'
arrc ::= e | exps

会心一笑：我的 E-BNF 为什么写成了那个怪样子，其实就是从 BNF 逐句转来的。
知道了语法元素的递归方向，不需要消除递归，只需把每个元素的解析过程表示为函数，把要执行的全局代码插入函数体，然后把 BNF 的逻辑直接而机械得转为函数间的递归调用，语法分析器就写出来了。BNF 中只有选择和递归两种逻辑，下面是对它们的编码示例。

// 参数 ls 是词法分析结果
function sdict (ls) {
	var index = ["~"]  //对象树节点名的线型访问栈
	var root = {}      //全局的对象树
	var stack = [root] //对象树节点的线型访问栈

	// 对照 BNF，不难发现解开递归的技巧：
		/* 把对起始符和终结符的处理写在函数中，递归部分一直向下推迟，
		   直到 exps 这个产生式被终结时再调用回 main() */
	// main ::= tree | tree main
	function main (ls, ln) {
		if (ls == false)
			if (!canPop(stack))
				return
			else error("Lack of end quotes", ln)
		else if (beMain(ls[0]))
			tree(cdr(ls), ln)
		else if (beEnd(ls[0]))
			if (canPop(stack)) {
				// 语法分析 main 结束就弹出一个数据栈，一条树枝结束了
				stack.pop()
				main(cdr(ls), ln)
			}
			else error("To many end quotes", ln)
		else error("Wrong Syntax: "+ls[0], ln)
	}

	function tree (ls, ln) {
		// 这是一个一步推导产生式的例子
		// tree ::= '(' id leaf ')'
		if (beId(ls[0])) {
			var tmp = id(ls[0])
			// 这些就是插入的全局数据结构更新代码，向栈中增加索引
			add_index(stack, tmp[0])
			leaf(tmp[1], ln)
		}
		else error("Not an Id: "+ls[0])
	}

	/* 详细参见源文件74-143行，把每个函数处理空白的代码去掉，
	   参数s替换为 ls，函数体内替换为 ls[0] 就是独立语法分析的版本。 */
}

合并词法分析和语法分析
简单的优化
把所有的小函数全部作内联，展开代码到被调用的地方。这样一来，判断起始符号的函数就可以全部消灭（顺便提一句，使用静态多态类型的纯函数式编程语言，如 Haskell、Ocaml、ML，写的语法分析器自动生成器不需要这种优化，因为语言本身就已经帮你做了）。当然了，作为应用“优化”手段的一般代价，就是代码看不懂了。

一趟分析
S-dict(t) 的解析器事实上使用了一趟分析的技术，把词法分析和语法分析合并到一起完成，不使用词法分析生成的中间数组，提高解析效率。方法是把语法分析提取 ls[0] （即当前元素）的过程扩写为从 s （剩余的源代码）中弹出下一个词法元素的过程。实例代码就是源代码中的 sdict() 函数，就不列在这儿了。

引发的联想
从上面三章我们不难看出，词法分析、语法分析、一趟分析其实都是一个非常机械的过程，完全可以用工具自动生成代码。词法分析器生成器是最简单的，可以直接生成全部代码，像 flex 做的那样，连同逻辑一起硬编码；也可以像 lex 那样，提供固定的解析代码，只生成非确定有穷自动机的分析表。语法分析要稍复杂一点，问题在于如何判断什么时候该规约（确定下面调用哪一个分析函数）什么时候该移进（更新分析结果，继续向下递归）。这需要判断终结符和产生式之间的关系。最简单的判断方法是 LL(1)，也就是说统一只向下查看一个字符。这也就是我们这个例子中使用的方法。但这种方法较容易产生歧义，需要使用者自己修正解析代码。这就是 S-dict(t) 中 bool 和 low 的解析写成了一个函数的原因。antlr 就是用了 LL(1) 分析，不过它带有连接词法分析和语法分析的能力。yacc 使用的是 LR() 分析，一种带有回溯能力的强大的自动分析方法，克努特天才的创造。也许以后会有机会给大家讲到这个。

评论

8 楼 DraculaW 2009-01-06  

最近在看自动机的书
和lz的一起看来

7 楼 abruzzi 2009-01-06  

非常不错的文章，特别是竟然采取javascript来实现，更是非同小可。
FP确实很简洁，写起来也比较顺手。可惜很多人不理解。

6 楼 davies 2008-03-01  

javascript 支持尾递归么？

否则 tb[s[0]]+iter(cdr(s)) 会有效率问题吧，不是哪个地方都适合使用 Scheme的风格写代码的。

5 楼 mahudu 2008-02-07  

antlr不是LL(1)的，而是LL(k)的自顶向下的，k可以自己指定，如果过大，效率则会非常低。
bison是自底向上的用来生成语法分析器的，可以方便地处理左递归。

同意xiaolin0105的看法，如果不是手工打造编译前端，用工具做编译器前端真得没什么意思（纯粹地与正则表达式和BNF范式较劲），后端优化和代码生成才是难点。

4 楼 xiaolin0105 2008-02-04  

懒得看了，本科时候就开发过编译器了，parser的construction就是用的recursive descent的方法。。。。这种方法写编译器确实简单，不过现在都是用工具来生成parser tree,然后加semantic analysis，当然semantic analysis也是用的递归下降法。

其实编译器从scanner, parser一直到semantic的实现都没什么新奇的，现在重点在optimization和code generation。

3 楼 lichray 2008-02-02  

什么叫“FP 那些括号”。Haskell 括号比 C 还少。你说的那是 Lisp/Scheme 吧。其实你真正用过了就会发现：括号真方便。在高级编辑器里可以自动高亮配对的括号，一眼就可以看出表达式返回值的位置；在括号之间用 C+[] 键跳来跳去的感觉也很爽，配合正则表达式查找，不需要用 ctags 之类的工具也能快速定位到函数。反正弱智的 ctags 也不懂 Scheme 的函数是啥概念。

C Ruby 太可怜了，因为使用了太多的语法糖来骗取大众的好感。国人开发的 XRuby 的语法分析器是手写的，效率非常高，Ruby 1.9 可能会用。

2 楼 agile_boy 2008-01-31  

写的很详尽，留待以后慢慢研究

1 楼 Beag.Ye 2008-01-21  

文章看了，还是不怎么懂。倒是在源代码里发现一样好东西，可以把一个字符串反序列化的函数：

function str (t) {
	var tb = {
		'\"':'\\"',
		'\\':'\\\\',
		'\b':'\\b',
		'\f':'\\f',
		'\n':'\\n',
		'\r':'\\r',
		'\t':'\\t',
		'\v':'\\v',
	}
	function iter (s) {
		if (s == "")
			return ''
		if (tb[s[0]] != undefined)
			return tb[s[0]]+iter(cdr(s))
		return s[0]+iter(cdr(s))
	}
	return '"'+iter(t)+'"'
}

测了一下好像可以是的，不过要带上 cdr() 的声明。这个东西找了很久，居然在这儿看到了，晕~`