author: Kevin Lynx email: zmhn320#163.com date: 3.9.2009
语法分析
语法分析接收词法分析阶段的token集合为输入，将这些没有关系的tokens整理为相互
之间有关系的结构。书面点的说法叫语法树。
每一次让我写这些文绉绉的概念真让我受不了:D。
语法树
语法树简单来说就是一个以token作为每个节点的树型结构。例如我们有表达式age =
age + 1;，在词法阶段它被整理为token集合：age, =, age, +, 1。那么在经过语法分析后
，这些tokens将被整理为大致如下的树形结构：
=
/ \
age +
/ \
age 1
整理成这样的结构有什么好处？就kl解释器而言，最直接的好处就是我可以递归地解释
这棵树执行。例如：
value compute( TreeNode *root )
{
/* child[0]保存结果值age，child[1]是那个+表达式 */
return op_exp( root->child[1] );
}
value op_exp( TreeNode *node )
{
switch( node->op )
{
case '+':
{
/* + 表达式必然有左右操作数 */
value left = factor( node->child[0] );
value right = factor( node->child[1] );
return left + right;
}
}
}
value factor( TreeNode *node )
{
switch( node->type )
{
case ID:
/* 查找age的值 */
return age;
case CONST:
/* 1 是常量 */
return node->cvalue;
}
}
如你所见，当我们完成了语法分析阶段，我们就可以完成我们的解释器了。后面我会单
独讲解下整个解释过程，包括每个模块是如何协作的。我不知道其他解释器是怎么做的，但
是我这样做，起码结果是对的。
如何整理出语法树？
这里不得不提到所谓的BNF文法，很明显你还是无法从我这里获取编译原理里某个概念
的讲解。我这里提这个概念完全是方便我提到这个东西。
每一种语言都有其自己的BNF文法，因为万恶的先知告诉我们，每一门语言都需要建立
其语法树。- -!
就像词法分析一样，因为大部分语言的结构都差不多，所以我觉得词法分析和语法分析
基本上都没有任何特别之处。也就是说，别的语言的BNF你可以直接拿来改改用。
抄个BNF如下：
exp -> exp adop term | term
addop -> + | -
term -> term mulop factor | factor
mulop -> *
factor -> (exp) | number
这个BNF用来描述一般的算数表达式(+-*/)。简单来说，一门语言的BNF就是用于描述该
语言所有语句的东西，包括if、while、函数定义之类。建议你google一下C语言的BNF，并
改造之用于你自己的语言。
那么有了BNF之后，该如何整理出语法树呢？
通常，我们的代码里都会直接有对应exp、term、addop之类的函数。按照我这句话的意
思，上面抄的BNF被翻译为程序代码后，就可能为：
exp()
{
if( ... ) left = exp()
right = term();
left addop right;
}
term()
{
if( ... ) left = term()
right = factor();
left mulop right;
}
factor()
{
if( ... ) return exp();
else return number;
}
(可能还会涉及到EBNF，用于处理重复和选择的一些情况---不用管这句话)
每一个函数基本上都会返回一个树节点，当然，该节点下可能会有很多子节点。
总结
语法分析基本上就是以上信息。它将词法分析输出的token集合整理成一颗语法树。为
了整理出这棵语法树，你需要找一份用于描述你语言的BNF，然后根据BNF翻译成处理代码。
代码导读
kl中的整个语法分析代码位于klparser.c/klparser.h中，其BNF基本上取自<编译原理与
实践>附录中的C_语言。