Liping Zou bio photo

Liping Zou

An Android Developer

Email Twitter Instagram Github

Overview

说起这次的语义分析,不得不说的是我的重大的改变。上一次的语法分析是利用了预测分析法来实现的,经过多方考证,发现用预测分析法的语法分析器基础来实现语义分析的困难重重,例如在语法指导翻译的时候那个栈的变化和各种属性的传递就已经让我头晕脑胀了。无奈之下,只好重写语法分析,用了递归下降来实现语法分析进而实现我的语义分析。

使用递归下降的最大好处就是思路特别清晰,一旦开始写了,就特别明确接下来要做什么。这就是我选择递归下降的原因。

简单的说一下,递归下降语法分析的思想。一个递归下降的语法分析程序由一堆的过程组成,每个非终结符号都有一个对应的过程。程序的执行从开始符号对应的过程开始,如果这个过程的过程体扫描了整个输入串,它就停止执行,并且语法分析结束。

而要在递归下降语法分析的过程中进行翻译:在语法分析中对应于每个非终结符A都有一个函数A,在函数A的函数体中,可以进行语法分析和处理继承属性和综合属性。

  1. 决定用哪一个产生式来展开A
  2. 当需要读入一个终结符号时,在输入中检查这些符号是否出现。
  3. 在局部变量中保存所有必要的属性值。这些属性可以用来计算产生式体中的非终结符号的继承属性,或产生式左部的非终结符号的综合属性。
  4. 调用对应于被选定产生式体中的非终结符号的函数,向他们提供正确的参数。

实现语义分析很关键的一点是语义动作的书写。我的语义动作都嵌入到了每个非终结符所对应的类中的某些方法来实现的。

例如在类Expression中有如下几个方法:

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
33
34
35
36
37
38
39
40
41
	/**
	 * 返回一个可以成为某个三地址指令的右部
	 * @return 一个项
	 */
	public Expression gen() {
		return this;
	}
	
	/**
	 * 把一个表达式规约成一个地址
	 * @return 一个地址
	 */
	public Expression reduce(){
		return this;
	}
	
	/**
	 * 调用jumps()方法,生成跳转代码
	 * @param t true出口
	 * @param f false出口
	 */
	public void jumping(int t,int f){
		jumps(toString(),t,f);
	}
	
	/**
	 * 生成跳转代码
	 * @param string
	 * @param t
	 * @param f
	 */
	public void jumps(String string,int t,int f){
		if (t != 0 && f != 0){
			emit("if " + string + " goto L" + t);
			emit("goto L"+ f);
		}else if(t != 0){
			emit("if " + string + " goto L" + t);
		}else if (f != 0){
			emit("iffalse " + string + " goto L" + f);
		}
	}

在Expression的子类中通常会实现gen()方法和reduce()方法。

而在类Or中,也有jumps()方法与此相关,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
	/**
	 * 为布尔表达式B = B1 || B2生成跳转代码
	 * 如果B1为真,那么B必然为真,所以B1的true出口是B的true出口
	 * 如果B1为假,那么B1的false出口则是B2的第一条指令
	 * B2的true出口和false出口与B的相同
	 */
	public void jumping(int t,int f) {
		int label = t != 0 ? t : newLabel();
		expression1.jumping(label, 0);
		expression2.jumping(t, f);
		if (t == 0){
			label(label);
		}
	}

在类And中,也有也有jumps()方法与此相关,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
	/**
	 * 为布尔表达式B = B1 & B2生成跳转代码
	 * 如果B1为假,那么B必然为假,所以B1的false出口是B的false出口
	 * 如果B1为真,那么B1的true出口则是B2的第一条指令
	 * B2的true出口和false出口与B的相同
	 */
	public void jumping(int t,int f) {
		int label = f != 0 ? f : newLabel();
		expression1.jumping(0,label);
		expression2.jumping(t, f);
		if (f == 0){
			label(label);
		}
	}		

还有一些方法,如label()和newLabel()方法也都与语义动作相关,newLabel()方法是用来生成一个新的标号,label()方法是用给接下来的一句三地址码标号。

关于符号表的处理:

我的符号表是一个HashMap,其定义是HashMap<String, ID>。其中key是变量名,value是一个ID类的对象。在ID类中,保存了变量的名字,类型,类型的长度,偏移量,入口地址等多个属性。如果变量是一个数组,则包含更加复杂的属性,如数组元素个数,数组元素的类型等等。

在变量声明阶段,程序每读到一个新的声明语句,都会将其加入到符号表中。当在赋值语句中使用这些变量的时候,首先从符号表中寻找是否已经存在这样一个已经被声明过的变量,否则不可使用。

我的测试程序如下:

image

根据这个测试程序,生成的符号表如下:

image

简要的说一下我的语义分析可识别的错误类型:

  1. if或while的条件必须是布尔语句
  2. 变量必须要先声明后使用
  3. 相同变量名的变量不得重复声明

好像主要能识别的错误就是以上的三类了,其中还要说明的一点是,我的语义分析支持简单的类型转换,例如把float类型的值赋给int型变量是不会出错的。

总体来说,这次的语义分析实现的不大好。没有坚持用预测分析的方法来实现语义分析一直是我的一个遗憾,却转向较为简单递归下降的实现。并且在递归下降的实现中仍然有缺陷,例如不支持函数调用,符号表对于函数没有处理,指针运算的不支持,数组赋值只适用于a[i] = x这类的赋值,错误处理不完备等等。

最后,语义分析结果(仍然是针对上述测试程序)如下:

image