语法制导翻译

分析树

在语法知道翻译之前，先来了解程序代码在内存中的表示方法。大部分程序员对于树形结构肯定是并不陌生，而树形结构也正好适合程序结构的表达。

比如if语句的树形表示如下：

root 
+
---- condtion
---- if_statement
---- else_statement

分析树表示方法有多种，而这里选择使用异形树来表示，因为它更加直观。下面就是异形树表示if的例子：

public static class IfStatement extends T {
	public Exp.T condition;
	public Stm.T ifStatements;
	public boolean hasElse;
	public Stm.T elseStatements;

	public IfStatement(Exp.T condition, Stm.T ifStatement, Stm.T elseStatement) {
		this.condition = condition;
		this.ifStatements = ifStatement;
		this.hasElse = elseStatement != null;
		this.elseStatements = elseStatement;
	}

	public IfStatement(Exp.T condition, Stm.T ifStatement) {
		this(condition, ifStatement, null);
	}
	
	@Override
	public void accept(Visitor v) {
		v.visit(this);
	}
}

其中的T是所有Statement的基类。异形树的代码非常直观，能够一眼就明白具体是做什么！然而，异形树充斥着大量冗余操作。你必须为每一个产生式都写出相应的生成代码以及访问代码。

其中的accept(Visitor v)方法属于 Visitor 模式的应用，Visitor 属于 interface ，这样不仅解决了向下转型的问题，还使得对于多种生成树遍历方法，不需要修改原有的代码。如果使用解释器模式，就无法实现解耦。

制导动作

在语法分析的部分，关于if分析部分的代码如下：

// "if" "(" assign_exp ")" statement ["else" statement]
//
case KEYWORD_IF: {
	advance();
	eatToken(Kind.TOKEN_LPAREN);
	parseAssignExp();
	eatToken(Kind.TOKEN_RPAREN);
	parseStatement();
	if (current.kind == Kind.TOKEN_KEYWORD &&
		current.keyword == Keyword.KEYWORD_ELSE) {
		advance();
		parseStatement();
	}
	return;
}

可以看到的是，在分析语法时，直接抛弃了源代码中的信息而不是储存下来。那么只需要在该部分添加相应的语法分析动作，来生成分析树即可。修改后代码如下：

case KEYWORD_IF: {
	advance();
	eatToken(Kind.TOKEN_LPAREN);
	Exp.T exp = parseAssignExp();
	eatToken(Kind.TOKEN_RPAREN);
	Stm.T if_ = parseStatement();
	Stm.T else_ = null;
	if (current.kind == Kind.TOKEN_KEYWORD && current.keyword == Keyword.KEYWORD_ELSE) {
		advance();
		else_ = parseStatement();
	}
	return new Stm.IfStatement(exp, if_, else_);
}

也就是我们在分析阶段，将所有的非终结符信息记录下来，并填入相应的生成树节点中。

抽象语法树

生成树极大的保留了程序源代码的结构，使得我们可以轻松的恢复其原先的代码。不过，多数时候，我们所做的工作并不关心其中的大部分数据，这就造成了大量冗余代码的产生。

举个例子，假设有调用函数：id(exp);语句，其产生分析树应该如下：

exp +
	and or exp +
		condition exp +
			add sub exp +
				mul div exp +
					...

其中有很大一部分属于冗余信息，即我们并不关心这部分数据。下面是我们希望见到的语法树：

call +
---- id
---- exp

这就是抽象语法树。相比语法树，抽象语法树在时间和空间方面都有极大的优化。关于抽象语法树的建立，只需要在 parse 部分稍稍修改，就能极大地化简分析树：

private Exp.T parseConditionExp() {
	Exp.T exp = parseAddSubExp();
	while (current.kind == Kind.TOKEN_ADD || current.kind == Kind.TOKEN_SUB) {
		Kind kind = current.kind;
		advance();
		exp = new Exp.AddSubExp(kind == Kind.TOKEN_ADD, exp, parseAddSubExp());
	}
	return exp;
}

这段代码用于分析 + - 法。可以看到如果当前节点并不关加减法什么卵事，就会跳过AddSubExp的构造。按照这个步骤，最终程序返回的就是一棵非常精简的树。