第 7 章 语义分析与语法制导的翻译
7.1. 语义分析的主要任务
分析源程序的含义并做出相应的语义处理。语义处理通常包含静态语义检查和语义的翻译。
静态语义检查包括
- 类型检查(赋值运算两边类型是否相容等)
- 控制流检查(goto 语句、continue 语句位置是否合法)
- 唯一性检查(switch 中 case 的标号是否重定义等)
- 其他相关的语言检查
此外,还要进行语义翻译,通常是生成中间代码。它有以下特点
- 独立于机器
- 复杂性介于源语言和目标语言之间
生成与硬件机器相对独立的中间语言形式的中间代码,有以下好处
- 使编译程序的结构在逻辑上更为简单明确
- 便于进行与机器无关的代码优化工作
- 易于移植「当要将编译程序移植到新的目标机器时,前端(词法分析、语法分析、语义分析及中间代码生成)几乎不变,只要修改后端即可。后端是针对具体目标机器的代码生成与优化。」
7.2. 中间语言
7.2.1. 图表示
- 抽象语法树 AST
- 有向无环图 DAG
有向无环图
- 对表达式的每个子表达式,DAG 中都有一个节点
- 一个内部节点代表一个操作符,它的孩子代表操作数
- 在一个 DAG 中代表公共子表达式的节点具有多个父节点
7.2.3. 三地址代码
形式 ,式子 的三地址代码
都是编译器产生的临时变量
- 双目运算
- 单目运算
- 复写语句,直接赋值
- 无条件跳转到标号处
- ,其中 relop 是关系运算符,条件跳转
- 实参进栈
- 调用过程或函数 ,共有 个参数
- 函数返回并带回值
- 索引赋值
- 地址和指针赋值
7.2.4. 四元式
一个带有四个域的记录结构,这四个域分别为 op, arg1, arg2, result,注意参数位置不能颠倒
- 等价于
- 等价于
7.2.5. 三元式
用三个域表示: (op, arg1, arg2)
序号 | op | arg1 | arg2 | 含义 |
---|---|---|---|---|
uminus | None | |||
7.3. 声明语句的翻译
7.3.1. 变量声明语句
常量定义
const <类型> id1 = <值1或其他常量名>, ..., idn = <值n或其他常量名>;
L.in = T.type // L.in 继承属性保存从左边 T.type 传递过来的常量类型信息
T.type = INT
T.type = float
L1.in = L.inE.in = L.in // 将 L.in 中保存的常量类型信息继续向右或向下传递
E.in = L.in // 将 L.in 中保存的常量类型信息继续向右或向下传递
id.pos = lookUp(num.lexval)id.type = E.inid.kind = CONSTANTaddType(id.entry, id.type, id.kind, id.pos)
id.pos = id1.posid.type = id1.typeid.kind = id1.kindaddType(id.entry, id.type, id.kind, id.pos)
变量定义
P → { offset = 0 } D; S
一系列的变量定义语句
id.kind = VARenter(id.name, T.type, id.kind, offset)offset = offset + T.width
id.kind = VARenter(id.name, array(num.lexval, T.type), id.kind, offset)offset = offset + num.lexval * T.width
T.type = INTT.width = 2
T.type = FLOATT.width = 4
T.type = pointer(T1.type)T.width = 4
7.3.2. 函数定义
函数定义的翻译涉及到变量的作用域的问题,即局部变量的作用域。
翻译处理的基本工作有:定义一个全局符号表,存放全局变量与函数名称等标识符信息的符号表。每个函数都有一张自己独立的符号表,在该表中登记本函数内部出现的变量等标识符信息。所有这些符号表构成一个符号表栈。每个符号表内都有自己的 offset ,用于记录本函数内部局部变量的相对地址。
需要数据结构:符号表栈 tblptr 栈,偏移量栈 offset 栈
7.4. 赋值语句
id := E
功能:对表达式 E 求值并置于变量 T 中,id.place := T
赋值语句生成三地址代码的 S-属性文法
- 非终结符 S 有综合属性 code,它代表赋值语句 S 的三地址代码
- 非终结符号 E 有两个属性
- E.place 表示存放 E 值的单元的名字(地址)
- E.code 表示对 E 求值的三地址语句序列
- 函数 newTemp 功能是,每次调用它时,将返回一个不同的临时变量名字,如 等
产生式 | 语义规则 |
---|---|
S.code:=E.code; gen(id.place ’:=’ E.place) | |
E.place:=newTemp; E.code:=E1.code; E2.code; gen(E.place ’:=’ E1.place ’+’ E2.place) | |
E.place:=newTemp; E.code:=E1.code; E2.code; gen(E.place ’:=’ E1.place ’*’ E2.place) | |
E.place:=newTemp; E.code:=E1.code; gen(E.place ’:=’ ‘uminus’ E1.place) | |
E.place:=E1.place; E.code:=E1.code | |
E.place:=id.place |
产生赋值语句三地址代码的翻译模式
过程 emit 将三地址代码送到输出文件中
-
p := lookUp(id.name)if p != nil:emit(p ':=' E.place)elsethrow Error
-
E.place := newTempemit(E.place ':=' E1.place '+' E2.place)
-
E.place := newTempemit(E.place ':=' 'uminus' E1.place)
-
E.place := E1.place
-
p := loopUp(id.name)if p != nil:E.place := pelsethrow Error
7.5. 数组定义
- 设 为 维数组,按行存放,每个元素宽度为
- 为第 维下界
- 为第 维上界
- 为第 维可取值的个数
- 为 的第一个元素相对地址
- 元素 相对地址公式
- 红色为可变部分,蓝色为不变部分,记蓝色部分为
数组地址计算
id 出现的地方也允许下面产生式的 L 出现
为了便于处理,改写为
引入下列语义变量或语义过程
- Elist.dim :下标个数计数器
- Elist.place :保存临时变量的名字,这些临时变量存放已经形成的 Elist 中的下标表达式计算出来的值
- Elist.array :保存数组名
- limit(array, j) :函数过程,它给出数组 array 的第 维的长度
代表变量的非终结符 L 有两项语义值
- L.place
- 若 L 为简单变量 ,指变量 的符号表入口
- 若 L 为下标变量,指存放不变部分的临时变量的名字
- L.offset
- 若 L 为简单变量,null
- 若 L 为下标变量,指存放可变部分的临时变量的名字
带数组元素引用的赋值语句
if (L.offset == null) { // L 是简单变量 emit(`${L.place} := ${E.place}`)} else { emit(`${L.place}[ ${L.offset} ] := ${E.place}`)}
E.place = newTempemit(`${E.place} := ${E1.place} + ${E2.place}`)
E.place = E1.place
if (L.offset == null) { // 简单变量 E.place = L.place} else { E.place = newTemp emit(`${E.place} := ${L.place} [ ${L.offset} ]`)}
处理到第一维
Elist.place = E.placeElist.ndim = 1Elist.array = id.place
t = newTempm = Elist.ndim + 1emit(`${t} := ${Elist1.place} * ${limit(Elist1.array, m)}`)emit(`${t} := ${t} + ${E.place}`)Elist.place = tElist.ndim = mElist.array = Elist1.array
L.place = newTempemit(`${L.place} := ${Elist.array} - ${C}`)L.offset = newTempemit(`${L.offset} := ${w} * ${Elist.place}*)
- Elist.array 相当于数组的首地址
L.place = id.placeL.offset = null
类型转换
double x, y; int i, j;// ...x = y + i * j;
产生的三地址代码为
用 E.type 表示非终结符 E 的类型属性,产生式 的语义动作中关于 E.type 的语义规则可定义为:
if (E1.type == INT && E2.type == INT) { E.type = INT} else { E.type = DOUBLE}
产生式 的语义动作
E.place = newTempif (E1.type == INT && E2.type == INT) { emit(`${E.place} := ${E1.place} int+ ${E2.place}`) E.type = INT} else if (E1.type == DOUBLE && E2.type == DOUBLE) { emit(`${E.place} := ${E1.place} double+ ${E2.place}`) E.type = DOUBLE} else if (E1.type == INT && E2.type == DOUBLE) { let u = newTemp emit(`${u} := intToDouble ${E1.place}`) emit(`${E.place} := ${E1.place} double+ ${E2.place}`) E.type = DOUBLE} else if (E1.type == DOUBLE && E2.type == INT) { let u = newTemp emit(`${u} := intToDouble ${E2.place}`) emit(`${E.place} := ${E1.place} double+ ${E2.place}`) E.type = DOUBLE} else { E.type = TYPE_ERROR}
7.6. 布尔表达式
- 用于逻辑演算,计算逻辑值
- 用于控制语句的条件式
计算方法
- 数值表示法:如同计算算术表达式一样一步一步酸
A || (B && C > D)
翻译(>, C, D, T1) // T1 := C > D(and, B, T1, T2) // T2 := B and T1(or, A, T2, T3) // T3 := A or T2
- 带优化的翻译法
- A or B := if A then true else B
- A and B := if A then B else false
- not A := if A then false else true
数值计算法
E.place = newTempemit(`${E.place} := ${E1.place} or ${E2.place}`)
E.place = newTempemit(`${E.place} := ${E1.place} and ${E2.place}`)
E.place = newTempemit(`${E.place} := not ${E1.place}`)
E.place = E1.place
100: if a < b goto 103101: T := 0102: goto 104103: T := 1104:
E.place = newTempemit(`if ${id2.place} ${relop.op} ${id2.place} goto ${nextStat + 3}`)emit(`${E.place} := 0`)emit(`goto ${nextStat + 2}`)emit(`${E.place} := 1`)
E.place = id.place
条件控制
if (E) { // S1} else { // S2}
if (a > c || b < d) { // S1} else { // s2}
if (a > c) goto L2 goto L1L1: if (b < d) goto L2 goto L3L2: // S1 goto LnextL3: // S2Lnext:
产生布尔表达式三地址代码的属性文法
- 语义函数 newLabel 返回一个新的符号标号
- 对于一个布尔表达式 E ,设置两个继承属性
- E.true 是为真时控制流转向的标号
- E.false 是为假时控制流转向的标号
- E.code 记录 E 生成的三地址代码序列
E1.true = E.trueE1.false = newLabelE2.true = E.trueE2.false = E.falseE.code = E1.code + gen(`${E1.false}:`) + E2.code
E1.true = newLabelE1.false = E.falseE2.true = E.trueE2.false = E.falseE.code = E1.code + gen(`${E1.true}:`) + E2.code
E1.true = E.falseE1.false = E.trueE.code = E1.code
E1.true = E.trueE1.false = E.falseE.code = E1.code
E.code = gen(`if ${id1.place} ${relop.op} ${id2.place} goto ${E.true}`) + gen(`goto ${E.false}`)
E.code = gen(`goto ${E.true}`)
E.code = gen(`goto ${E.false}`)
多遍翻译
根据属性文法翻译表达式
a < b || (c < d && e < f)
假定整个表达式的真假出口已分别设置为 Ltrue
和 Lfalse
,首先画出自上而下的继承属性的计算(需要按照上面的布尔运算来生成)
接下来自下而上计算综合属性
- 最左侧 E.code
if (a < b) goto Ltrue;goto L1;
- 蓝色 E.code
L1: if (c < d) goto L2;goto Lfalse;
- 绿色 E.code
L2: if (e < f) goto Ltrue;goto Lfalse;
蓝色和绿色合并为紫色 E.code 部分,所有代码构成整个 E.code 部分
一遍扫描
- 以四元式为中间语言
- 四元式存入一个数组,数组下标代表其标号
- 约定
(jnz, a, null, p)
表示if (a) goto p
(jrop, x, y, p)
表示if (x rop y) goto p
(j, null, null, p)
表示goto p
- 过程
emit
将四元式代码输送到输出数组 - 产生跳转四元式时,它的转移地址无法直接知道,需要以后扫描到特定位置时才能回头过来确定,把这些未完成的四元式地址作为 E 的语义值保存,待机“回填”
地址 | 四元式 |
---|---|
100 | (j<, a, b, 104) |
101 | (j, null, null, 102) |
102 | (j<, c, d, 104) |
103 | (j, null, null, 104) |
104 | … |
… | … |
110 | … |
- 为非终结符 E 赋予两个综合属性 E.trueList, E.falseList ,分别记录布尔表达式 E 所对应的四元式中需要回填“真”、“假”出口的四元式的标号所构成的链表
- 例如,假定 E 的四元式中要回填“真”出口的 p, q, r 三个四元式,则 E.tureList 为
- 引入语义变量和过程
- 变量
nextQuad
指向下一条将要产生但尚未形成的四元式的地址(标号)nextQuad
的初值为 1 ,每当执行一次emit
之后,nextQuad
将自动增 1 - 函数
makeList(i)
将创建一个仅含i
的新链表,其中i
是四元式数组的一个下标;函数返回指向这个链的指针 - 函数
merge(p1, p2)
把以 和 为链首的两条链合并为一,作为函数值,回送合并后的链首 - 过程
backPatch(p, t)
其功能是完成“回填”,把 所链接的每个四元式的第四区段都填为
- 变量
为了使得翻译模式能够和自下而上的语法分析结合起来,我们希望所有的语义动作都放在产生式的最右端,使得语义动作的执行时机能够统一到用这个产生式进行归约的时候。为此需要对文法进行一定的改造
M.quad = nextQuad
// 将 M.quad 记录的 E2 开头四元式的地址,去回填 E1.falseList 中的每一个四元式backPatch(E1.falseList, M.quad)// 整个表达式为真的地方E.trueList = merge(E1.trueList, E2.trueList)// 整个为假时,其实已经进行到 E2.falseList ,保留到 E.falseListE.falseList = E2.falseList
// 将 M.quad 记录的 E2 开头四元式的地址,去回填 E1.falseList 中的每一个四元式backPatch(E1.trueList, M.quad)// 整个表达式为真的地方,保留到 E.trueListE.trueList = E2.trueList// E1 或 E2 为假时需要去的地方E.falseList = merge(E1.falseList, E2.falseList)
E.trueList = E1.falseListE.falseList = E1.trueList
E.trueList = makeList(nextQuad)E.falseList = makeList(nextQuad + 1)emit(`j ${relop.op}, ${id1.place}, ${id2.place}, 0`)emit(`j, -, -, 0`) // 0 表示链尾
E.trueList = makeList(nextQuad)E.falseList = makeList(nextQuad + 1)emit(`jnz, ${id.place}, -, 0`)emit(`j, -, -, 0`) // 0 表示链尾
例:对表达式 a < b || (c < d && e < f)
分析
7.7. if 语句的翻译
E.true = newLabel // 生成一个标号,将来放在 S1 开始的位置,标识 true 的位置E.false = S.next // 整个 if-then 的后继S1.next = S.nextS.code = E.code + gen(`${E.true}: `) + S1.code
E.true = newLabelE.false = newLabelS1.next = S.nextS2.next = S.nextS.code = E.code + gen(`${E.true}: `) + S1.code + gen(`goto ${S.next}`) + gen(`${E.false}: `) + S2.code + gen(`${S.next}: `)
7.8. while 语句
S.begin = newLabelE.true = newLabelE.false = S.nextS1.next = S.beginS.code = gen(`${S.begin}:`) + E.code + gen(`${E.true}: `) + S1.code + gen(`goto ${S.begin}`) + gen(`${S.next}:`)
7.9. switch 语句
switch (E) { case C1: // S1 case C2: // S2 ... case Cn: // Sn default: // Sn+1}
直接设计方案
goto testL1: ; S1 的代码L2: ; S2 的代码...Ln: ; Sn 的代码Ln1: ; Sn+1 的代码 goto nexttest: if (T == C1) goto L1 if (T == C2) goto L2 ... if (T == Cn) goto Ln goto Ln1next:
较小的范围使用表格标注指令地址
将常量 直接作为表格的下标,设表格为 table ,则常量 对应的 语句的地址就是 。表格中其余空白处填写 default 后面所对应的 的地址。
最后代码结构
E 的代码(假设 E 的最终值存放在变量 T 中) goto table[T]
7.10. break 语句
出现情况:switch 和 while
翻译方案是,直接将 break 语句翻译成一条 goto S.loopNext
即可,S.loopNext
是包围该 break 语句的最内层 while 语句的 S.next
if (!S.loopNext) { throw new Error()} else { gen(`goto ${S.loopNext}`)}
7.11. continue 语句
翻译方案为,直接将 continue 翻译成一条 goto S.loopBegin
即可,S.loopBegin
是包围该 continue 语句的最内层 while 语句的 S.begin
if (!S.loopBegin) { throw new Error()} else { gen(`goto ${S.loopBegin}`)}
7.12. goto 语句
goto Label;
7.13. 函数调用语句
将实参一一入栈(可能还有其他编译程序认为需要入栈的参数),然后跳转到函数体开始执行。在执行函数体代码时,会在栈中为局部变量开辟空间,建立当前函数的活动记录。
当函数执行完毕返回调用者时,自动撤销当前函数的活动记录,因此所有局部变量自动销毁。
C 语言程序 func(p1, p2, ..., pn)
被调用时的代码结构
; 计算 pn 的代码param pn ; 将实参 pn入栈; 计算 p_{n-1} 的代码param pn_1...; 计算 p1 的代码param p1call func, n ; 转入到函数 func 中执行,共有 n 个参数
翻译方案(Elist 为参数列表)
S.code = Elist.code + gen(`call ${id.place}, ${Elist.count}`)
Elist.count = Elist1.count + 1Elist.code = E.code + gen(`param ${E.place}`) + Elist1.code
Elist.count = 1Elist.code = E.code + gen(`param ${E.place}`)