编译器一日一练（DIY系列之语法树打印）

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

        代码地址：https://github.com/feixiaoxing/DIYCompiler/blob/master/day08/Parse1.jj 

        之前我们谈到了词法分析、语法分析、语义分析，但是没有讨论，如果自己写编译器的话，应该如何来调试。其实，对于编译器来说，它也是有自己的调试方法。

        一般来说，语法分析结束了，这个时候一个完整的语法树就被构建出来了。所以，这个时候可以通过打印语法树的方法，来判断构建的语法树是否正确。等到语义分析确认没有问题，转成中间代码的时候，这个时候又可以通过打印中间代码的方法，判断生成的中间代码是否正确。中间代码生成后，一般会进行一次代码优化，剔除冗余代码和垃圾代码，这个时候又会生成一遍优化后的中间代码，所以还是可以继续通过打印，查看优化后的中间代码是否正确。等这些都完成后，就可以将优化后的中间代码生成汇编，所以可以直接查看汇编代码是否正确。

        所以，在编写编译器的过程当中，有四处地方可以打印，这分别是语法树、中间代码、优化后的中间代码、汇编。当然，如果没有优化的话，直接就变成了三处，即语法树、中间代码和汇编。

        今天，我们就来看看语法树如何打印。这些内容基本都是二叉树数据结构的部分。首先，需要计算节点的深度，其实主要还是为了计算根节点的深度，

	public int calculate_depth() { // node depth should be calculated before print it, so just calculate root node
 
		int left_depth = 0;
		int right_depth = 0;
		int final_depth = 0;
		if(get_left_node() == null && get_right_node() == null) {
			set_depth(1);
			return 1;
		}
		
		if(null != get_left_node()) {
			left_depth = get_left_node().calculate_depth();
		}
 
		if(null != get_right_node()){
			right_depth = get_right_node().calculate_depth();
		}
		
		final_depth = (left_depth > right_depth) ? (left_depth+1) :(right_depth +1);
		set_depth(final_depth);
		return final_depth;
	}

        再根据根节点的深度，按照根、左、右的方法依次打印，

	public void print_node(int start_depth, int start_point) // add print node function
	{
		int i = 0;
		
		for(i =0; i < (start_point - start_depth*5); i++){
			System.out.print(" ");
		}
		
		if(get_node_type() != "value_node")
		{
			System.out.println("/");
		}
		else
		{
			System.out.println(((value_node)this).get_value());
		}
 
		if(get_left_node() != null) get_left_node().print_node(start_depth -1, start_point);
		if(get_right_node() != null) get_right_node().print_node(start_depth -1, start_point);
	}

        这部分代码有点拗口。start_depth代表了节点深度信息，而start_point代表单行最大缩进的信息。所以第一个for循环当中，深度越深，前面的空格就越少。接着，就是打印除号或者数据。最后继续递归打印左子树和右子树。

    public static void main(String[] args) {
        for (String arg : args) {
            try {
				div_node div = evaluate(arg);
                System.out.println();
				
				div.calculate_depth();
				div.print_node(div.get_depth(), div.get_depth()*5);
 
            } catch (ParseException ex) {
                System.err.println(ex.getMessage());
            }
        }
    }

        调用方法其实比较简单，首先利用evalute函数生成语法树。其次调用calculate_depth计算根节点的深度。最后就是调用print_node打印节点，注意深度信息和start_point的调用方法。

        下面可以看一下最后的效果，

C:\Users\feixiaoxing\Desktop\DIYCompiler\day08>java Parse 2/1
 
/
     2
     1
 
C:\Users\feixiaoxing\Desktop\DIYCompiler\day08>java Parse 3/1/2
 
/
     /
          3
          1
     2
 
C:\Users\feixiaoxing\Desktop\DIYCompiler\day08>java Parse 3/2/1/1/2/3/4/5/6
 
/
     /
          /
               /
                    /
                         /
                              /
                                   /
                                        3
                                        2
                                   1
                              1
                         2
                    3
               4
          5
     6

        上面的打印还是比较直观的。大家可以根据自己的需要灵活修改和调试。最后，给出完整的jj文件，供大家调试和参考，

options {
    STATIC = false;
}
 
PARSER_BEGIN(Parse)
import java.io.*;
 
class node
{
	public node left;
	public node right;
	public String node_type;
	public int depth;
	
	node() {this.left = this.right = null;}
	public void set_left_node(node left) { this.left = left;}
	public node get_left_node() { return this.left;}
	
	public void set_right_node(node right) { this.right = right;}
	public node get_right_node() {return this.right;}
	
	public void set_node_type(String node_type) {this.node_type = node_type;}
	public String get_node_type() {return this.node_type;}
 
	public void set_depth(int depth) {this.depth = depth;}
	public int get_depth() {return this.depth;}
	public int calculate_depth() { // node depth should be calculated before print it, so just calculate root node
 
		int left_depth = 0;
		int right_depth = 0;
		int final_depth = 0;
		if(get_left_node() == null && get_right_node() == null) {
			set_depth(1);
			return 1;
		}
		
		if(null != get_left_node()) {
			left_depth = get_left_node().calculate_depth();
		}
 
		if(null != get_right_node()){
			right_depth = get_right_node().calculate_depth();
		}
		
		final_depth = (left_depth > right_depth) ? (left_depth+1) :(right_depth +1);
		set_depth(final_depth);
		return final_depth;
	}
	
	public void print_node(int start_depth, int start_point) // add print node function
	{
		int i = 0;
		
		for(i =0; i < (start_point - start_depth*5); i++){
			System.out.print(" ");
		}
		
		if(get_node_type() != "value_node")
		{
			System.out.println("/");
		}
		else
		{
			System.out.println(((value_node)this).get_value());
		}
 
		if(get_left_node() != null) get_left_node().print_node(start_depth -1, start_point);
		if(get_right_node() != null) get_right_node().print_node(start_depth -1, start_point);
	}
}
 
class value_node extends node
{
	public int value;
	
	value_node() { set_node_type("value_node");}
	public int get_value() { return this.value;}
	public void set_value(int value) {this.value = value;}
}
 
class div_node extends node
{
	div_node() { set_node_type("/");}
	
	public int get_value() {
		int left = 0, right = 0;
		
		// get left node
		if(get_left_node().get_node_type() == "/")
		{
			left = ((div_node)get_left_node()).get_value();
		}
		else
		{
			left = ((value_node)get_left_node()).get_value();
		}
 
		// get right node
		if(get_right_node() == null)
		{
			return left;
		}
		else
		{
			right = ((value_node)get_right_node()).get_value();
			return left/right;
		}
	}
 
	// add semantic check
	public int check_value() {
	
		if(get_right_node() != null)
		{
			if( 0 == ((value_node)get_right_node()).get_value())
			{
				System.out.println("Div by Zero");
				return -1;
			}
		}
		
		if(get_left_node().get_node_type() == "/")
		{
			return ((div_node)(get_left_node())).check_value();
		}
 
		return 1;
	}
}
 
public class Parse {
 
    public static void main(String[] args) {
        for (String arg : args) {
            try {
				div_node div = evaluate(arg);
                System.out.println();
				
				div.calculate_depth();
				div.print_node(div.get_depth(), div.get_depth()*5);
 
            } catch (ParseException ex) {
                System.err.println(ex.getMessage());
            }
        }
    }
 
    public static div_node evaluate(String src) throws ParseException {
        Reader reader = new StringReader(src);
        return  new Parse(reader).expr();
    }
}
PARSER_END(Parse)
 
SKIP: { <[" ", "\t", "\r", "\n"]> }
TOKEN: {
    <INTEGER: (["0"-"9"])+>
}
 
div_node expr() throws NumberFormatException :
{
    Token a ;
    Token b ;
    div_node div;
}
{
	a = <INTEGER> 
	{ 
		value_node node_a = new value_node();
		node_a.set_value(Integer.parseInt( a.image ));
		
		div = new div_node();
		div.set_left_node(node_a);
		
	}
	
	(
	"/" b = <INTEGER>
	{
		value_node node_b = new value_node();
		node_b.set_value(Integer.parseInt( b.image ));
 
		// important code about node adding
		if(div.get_right_node() == null)
		{
			div.set_right_node(node_b);
		}
		else
		{
			div_node prev = div;
			div = new div_node();
			
			div.set_left_node(prev);
			div.set_right_node(node_b);
		}
	}
	)*
	
	<EOF>
	{ return div ; }
}