自己动手用java写编译器 课时3 语法解析改进及代码生成

缘起

《自己动手用java写编译器》 课时3

分析

本节首先对上一节的代码做了基于递归的优化. 因为如果表达式很大的话，可能递归的层数能达到非常深（有爆栈的风险）. 所以我们的语法解析器必须要做”尾递归”优化. 所谓尾递归优化，基于以下事实

1
2
3
4
5
6
7
8
9
void doSth()
{
	if(condition)
	{
		return; // 递归出口
	}
	...
	doSth(); // 递归调用
}

则上面的代码完全可以优化为（事实上，很多现代编译器就这么做了——即尾递归优化是很多现代编译器拥有的优化能力）

1
2
3
4
5
6
7
void doSth()
{
    while(!condition)
    {
        doSth();
    }
}

这就是尾递归优化. 而上一节的代码（参考DEMO【1】）其实就充斥了大量的递归. 而都可以使用尾递归优化. 举个例子

上一节的statements代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
	 * 规则1: statements -> expression ; | expression ; statements
	 */
	public void statements() {

		expression();

		if (lexer.match(Lexer.SEMI)) {
			/*
			 * look ahead 读取下一个字符，如果下一个字符不是 EOI 那就采用右边解析规则
			 */
			lexer.advance();
		} else {
			/*
			 *  如果算术表达式不以分号结束，那就是语法错误
			 */
			isLegalStatement = false;
			System.out.println("line: " + lexer.lineno + " Missing semicolon");
			return;
		}

		if (lexer.match(Lexer.EOF) != true) {
			/*
			 * 分号后还有字符，继续解析
			 */
			statements(); // 递归之处
		}

		if (isLegalStatement) {
			System.out.println("The statement is legal");
		}
	}

则完全可以”尾递归（虽然递归不在尾部）”优化为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
	 * 规则1: statements -> expression ; | expression ; statements
	 */
	public void statements() {
        
        while(lexer.match(Lexer.EOF) != true) {
            expression();

            if (lexer.match(Lexer.SEMI)) {
                /*
                 * look ahead 读取下一个字符，如果下一个字符不是 EOI 那就采用右边解析规则
                 */
                lexer.advance();
            } else {
                /*
                 *  如果算术表达式不以分号结束，那就是语法错误
                 */
                isLegalStatement = false;
                System.out.println("line: " + lexer.lineno + " Missing semicolon");
                return;
            }
        }

		if (isLegalStatement) {
			System.out.println("The statement is legal");
		}
	}

其他地方的优化完全是机械的（这也是为什么编译器可以做到尾递归优化的原因）. 这个知识点就讲完了. 尾递归优化并不是本集的终点. 本集的重点是下面要讲的代码生成的问题.

我们前面学习了词法解析、语法解析. 我们复习一下

1
2
词法解析就是把statements中有意义的文本抽取出来打上标签（token）.
语法解析就是校验statements是否符合预设的一组规则.

但是我们立马就发现这样还不够. 这仅仅是完成了识别层面上的事情——仅仅识别合法的文本还是不够的——必须要在识别的基础上，增加代码生成的功能，例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1+2*3+4, 经过编译后转换成：

t0 = 1

t1 = 2

t2 = 3

t1 *= t2

t0 += t1

t1 = 4

t0 += t1

t0, t1 是对寄存器的模拟，上述语句基本上就类似计算机能执行的汇编语句了。

当然，（汇编）代码生成之后，一般还会有优化器——将（汇编）代码中不必要的赋值或者多余的语句去除——提高汇编代码的效率. 但是我们现在还不研究优化上，而是把精力集中在如何生成代码上，那么代码是如何生成的呢? 代码额生成依赖上一节讲到的语法解析树. 对于 1+2*3+4， 给大家看一个图可能更加清晰

代码生成，就类似于二叉树的遍历，先从叶子节点开始（叶子节点进行的是赋值语句），任何非叶子节点对应的都是运算符. 例如

t1=2 和 t2=3 的父节点是一个 , 所以生成语句 2\3.

但是感觉讲师的代码风格比较乱，看的不是很舒服. 理解了算法的思想之后，决定自己写一个c++版的只包含 加号、乘号、括号、数字的算术表达式的编译器作为前三个课时的总结.

ps： 我没办法往下继续看视频教程了. 因为这里不能不搞清楚.

DEMO

【1】https://github.com/yfsyfs/backend/tree/master/compiler%20%E8%AF%AD%E6%B3%95%E8%A7%A3%E6%9E%90/src