一、概论

1. 语义分析的任务

• 语义检查：主要进行一致性检查和越界检查
• 语义处理
  • 说明语句：通常将其中定义的名字及属性信息记录在符号表中
  • 执行语句：生成语义上等价的中间代码

2. 语法制导翻译

在语法分析过程中，根据每个产生式对应的语义子程序（语义动作）进行翻译（生成中间代码）。

3. 语义值

在描述语义动作时，需要赋予每个文法符号以各种不同的“值”，这些值统称为“语义值”。

例：设有文法$G=\{E\to E+E,E\to 0,E\to 1\}$，可以为它写出如下的语义子程序：

E->E1+E2 { E.VAL:=E1.VAL+E2.VAL }
E->0 { E.VAL:=0 }
E->1 { E.VAL:=1 }

4. 语义分析和语法分析的关系

语法分析只能判断一个句子是否合法，不能给出句子的含义。

句子的含义是通过语义分析体现出来的。

5. 三地址码

• x=y op z
• x=op z
• x=y
• x=y[i]; x[i]=y;
• x=&y; x=*y; *x=y;
• goto L
• if x rop y goto L; if a goto L;
• param x; call P,n;
• return

例：a:=-b*c+d对应的中间代码

t1=-b;
t2=t1*c;
t3=t2+d;
a=t3;

6. 语义函数和语义变量

• i.NAME：非终结符的名字
• E.PLACE：非终结符在符号表的位置
• newtemp()：产生一个新的临时变量，并返回在符号表的位置
• entry(i.NAME)：查符号表并返回在符号表的位置
• emit(RESULT,OPD1,oper,OPD2)或emit(RESULT,oper,OPD)：根据参数产生三地址语句，并且ip+1
• error：出错

二、说明语句的翻译

采用下列文法：

D->D;D|i:T
T->real|integer|array[num] of T1|^T1

增加开始符号S和非终结符M，用于OFFSET的初始化：

S->MD
M->ε

语义子程序：

M->ε { OFFSET=0 }
D->i:T {
	enter(i.NAME,T.TYPE,OFFSET);
	OFFSET=OFFSET+T.WIDTH;
}
T->integer {
	T.TYPE=integer;
	T.WIDTH=2;
}
T->real {
	T.TYPE=real;
	T.WIDTH=4;
}
T->array[num] of T1 {
	T.TYPE=array(num.VAL,T1.TYPE);
	T.WIDTH=num.VAL*T1.WIDTH;
}
T->^T1 {
	T.TYPE=pointer(T1.TYPE);
	T.WIDTH=4;
}
D->D;D {}
S->MD {}

三、赋值语句的翻译

只含简单变量的赋值语句文法：

A->i:=E
E->i|-E1|(E1)|E1 op E2

语义子程序：

A->i:E {
	P=entry(i.NAME);
	if(P!=0) emit(P=E.PLACE);
	else error();
}
E->i {
	P=entry(i.NAME);
	if(P!=0) E.PLACE=P;
	else error();
}
E->-E1 {
	E.PLACE=newtemp();
	emit(E.PLACE=-E1.PLACE);
}
E->(E1) {
	E.PLACE=E1.PLACE;
}
E->E1 op E2 {
	E.PLACE=newtemp();
	emit(E.PLACE=E1.PLACE op E2.PLACE);
}

例：a:=-b*(c+d)的语法分析

栈	归约	输入串	语义子程序	中间代码
		a:=-b*(c+d)
i		:=-b*(c+d)
i:=		-b*(c+d)
i:=-i		*(c+d)
i:=-E1	E1->i	*(c+d)	E1.PLACE=entry(i.NAME)=b
i:=E2	E2->-E1	*(c+d)	E2.PLACE=newtemp()=T1 emit(T1=-b)	T1=-b
i:=E2*(i		+d)
i:=E2*(E3	E3->i	+d)	E3.PLACE=entry(i.NAME)=c
i:=E2*(E3+i		)
i:=E2*(E3+E4	E4->i	)	E4.PLACE=entry(i.NAME)=d
i:=E2*(E5	E5->E3+E4	)	E5.PLACE=newtemp()=T2 emit(T2=c+d)	T2=c+d
i:=E2*(E5)
i:=E2*E6	E6->(E5)		E6.PLACE=E5.PLACE=T2
i:=E7	E7->E2*E6		E7.PLACE=newtemp()=T3 emit(T3=T1*T3)	T3=T1*T2
A	A->i:=E7		emit(a=T3)	a=T3

四、布尔表达式的翻译

用于控制语句

B->b {
	B.T=ip;
	emit(if b goto 0);
	B.F=ip;
	emit(goto 0);
}

B->i1 rop i2 {
	B.T=ip;
	emit(if i1 rop i2 goto 0);
	B.F=ip;
	emit(goto 0);
}

五、无条件转移语句的翻译

标号语句：lable->i;

goto语句：S->goto i { emit(goto L) }

1. 向前转移

L:         // 将L加入符号表，类型为“标号”，已定义，地址为ip值
   ...
   goto L; // 查符号表，取出L的地址xxx，生成三地址码语句goto L

2. 向后转移

goto L;    // 生成三地址语句goto 0，将L加入符号表，类型为标号，未定义，地址为本三地址语句的地址
...
goto L;    // 生成三地址语句goto ?，与符号表中的L的地址组成一个链表（“拉链”），更新L的地址为本三地址语句的地址
...
L:         // 回填三地址语句链表，更新符号表中L的地址，已定义

3. 语义函数和语义变量

• S.CHIAN：语义变量，记录三地址语句链的链头
• merge(t1,t2)：语义函数，合并t1和t2两个链，返回新链t3
• backpatch(chain,address)：语义函数，用address回填chain链

向后转移的例子（S1.CHAIN=r）：

(p) goto 0
...
(q) goto p
...
(r) goto q

另一条链（S2.CHAIN=w）：

(u) goto 0
...
(v) goto u
...
(w) goto v

t3=merge(S1.CHAIN,S2.CHAIN)：

(p) goto 0
(q) goto p
(r) goto q
(u) goto r
(v) goto u
(w) goto v

backpatch(t3,120)：

(p) goto 120
(q) goto 120
(r) goto 120
(u) goto 120
(v) goto 120
(w) goto 120

六、条件转移语句的翻译

1. if语句的翻译

if B then S1

M->if B then {
	backpatch(B.T,ip);
	M.CHAIN=B.F;
}
S->M S1 {
	// S1如果是顺序语句CHAIN=0
	S.CHAIN=merge(S1.CHAIN,M.CHAIN);
}

例子：if a<b then a:=a+b;

栈	语义子程序	中间代码
if a<b
if B	B.T=ip=100; emit(if a<b goto 0); B.F=ip=101; emit(goto 0);	100: if a<b goto 102 101: goto 104
if B then
M	backpatch(B.T,ip); M.CHAIN=B.F=101;
M a:=a+b
M S1	t1=newtemp(); emit(t1=a+b); emit(a=t1); S1.CHAIN=0;	102: t1=a+b 103: a=t1
S	S.CHAIN=merge(S1.CHAIN,M.CHAIN)=101;
S;
L	backpatch(S.CHAIN,ip);

2. if else语句的翻译

if B then S1 else S2

M->if B then {
	backpatch(B.T,ip);
	M.CHAIN=B.F;
}
N->M S1 else {
	q=ip;
	emit(goto 0);
	backpatch(M.CHAIN,ip);
	N.CHAIN=merge(S1.CHAIN,q);
}
S->N S2 {
	S.CHAIN=merge(N.CHAIN,S2.CHAIN);
}

例子：if a<b then a:=a+b else a:=a-b;

栈	语义子程序	中间代码
if a<b
if B	B.T=ip=100; emit(if a<b goto 0); B.F=ip=101; emit(goto 0);	100: if a<b goto 102; 101: goto 105;
if B then
M	backpatch(B.T,ip); M.CHAIN=B.F=101;
M a:=a+b
M S1	t1=newtemp(); emit(t1=a+b); emit(a=t1); S1.CHAIN=0;	102: t1=a+b; 103: a=t1;
M S1 else
N	q=ip=104; emit(goto 0); backpatch(M.CHAIN,ip); N.CHAIN=merge(S1.CHAIN,q)=104;	104: goto 107;
N a:=a-b
N S2	t2=newtemp(); emit(t2=a-b) emit(a=t2); S2.CHAIN=0	105: t2=a-b; 106: a=t2
S	S.CHAIN=merge(N.CHAIN,S2.CHAIN)=104;
S;
L	backpatch(S.CHAIN,ip);

七、循环语句的翻译

1. while语句的翻译

while B do S1

W->while {
	W.CODE=ip;
}
D->W B do {
	backpatch(B.T,ip);
	D.CHAIN=B.F;
	D.CODE=W.CODE;
}
S->D S1 {
	backpatch(S1.CHAIN,D.CODE);
	emit(goto D.CODE);
	S.CHAIN=D.CHAIN;
}

例子：while a>b do if c<d then e:=f+g;

栈	语义子程序	中间代码
while
W	W.CODE=ip=100;
W a>b
W B	B.T=ip=100; emit(if a>b goto 0); B.F=ip=101; emit(goto 0);	100: if a>b goto 102; 101: goto 107;
W B do
D	backpatch(B.T,ip); D.CHAIN=B.F=101; D.CODE=W.CODE=100;
D if c<d
D if B1	B1.T=ip=102; emit(if c<d goto 0); B1.F=ip=103; emit(goto 0);	102: if c<d goto 104; 103: goto 106;
D if B1 then
D M	backpatch(B1.T,ip); M.CHAIN=B1.F=103;
D M e:=f+g
D M S2	t1=newtemp(); emit(t1=f+g); emit(e=t1); S2.CHAIN=0;	104: t1=f+g; 105: e=t1;
D S1	S1.CHAIN=merge(M.CHAIN,S2.CHAIN)=103;
S	backpatch(S1.CHAIN,ip); emit(goto D.CODE); S.CHAIN=D.CHAIN=101;	106: goto 100;
S;
L	backpatch(S.CHAIN,ip);

2. repeat语句的翻译

repeat S1 until E;

R1-> repeat {
	R1.CODE=ip;
}
R2-> R1 S1 until {
	R2.CODE=R1.CODE;
	backpatch(S1.CHAIN,ip);
}
S->R2 E {
	backpatch(E.F,R2.CODE);
	S.CHAIN=E.T;
}

3. do while语句的翻译

do S1 while B

D->do {
	D.CODE=ip;
}
E->D S1 while {
	E.CODE=D.CODE;
	backpatch(S1.CHAIN,ip);
}
W->EB {
	backpatch(B.T,E.CODE);
	W.CHAIN=B.F;
}

4. for语句的翻译

for i:=1 to N do S1

F->for i:=1 to N do {
	F.PLACE=entry(i);
	emit(F.PLACE=1);
	F.AGAIN=ip;
	emit(if F.PLACE<=N goto F.AGAIN+2);
	F.CHAIN=ip;
	emit(goto 0)
}
S->F S1 {
	backpatch(S1.CHAIN,ip);
	emit(F.PLACE=F.PLACE+1);
	emit(goto F.AGAIN);
}

for i:=E1 step E2 until E3 do S1

F1->for i:=E1 {
	P=entry(i);
	emit(P=E1.PLACE);
	F1.PLACE=P;
	F1.CHAIN=ip;
	emit(goto 0);
	F1.AGAIN=ip;
}
F2->F1 step E2 {
	F2.AGAIN=F1.AGAIN;
	F2.PLACE=F1.PLACE;
	emit(F2.PLACE=F1.PLACE+E2.PLACE);
	backpatch(F1.CHAIN,ip);
}
F3->F2 until E3 {
	F3.AGAIN=F2.AGAIN;
	F3.CHAIN=ip;
	emit(if F2.PLACE>E3.PLACE goto 0);
}
S->F3 do S1 {
	emit(goto F3.AGAIN);
	backpatch(S1.CHAIN,F3.AGAIN);
	S.CHAIN=F3.CHAIN;
}