编译原理课件语法制导翻译__翻译方案_SDD

表达式的解释执行
产 生 式 LEn E E1 + T ET T T1 * F TF F (E) F digit
digit+digit*digit n
L E E T F digit +
18+5*2n
n T
T * F F digit digit
语法制导定义 SDD Syntax-Directed Definition
F.val := digit.lexval
E .val = 8
T.val = 8 F.val = 8
+
T .val = 10 T .val = 5 *
F.val = 5 F .val = 2 digit .lexval = 2
digit .lexval = 8
digit .lexval = 5
SDD与属性文法
• 副作用 • 引用透明
LEn
print (E.val)
E E1 + T E.val := E1 .val + T.val
ET
T T1 * F TF
E.val := T.val
T.val := T1.val * F.val T.val := F.val
F (E)
F digit
F.val := E.val
TF
F(E) Fdigit
翻译输入 3*5+4n 所作的动作
L E n { print (statck[top-1].val ); top = top -1; } EE1 + T { statck[top-2].val = statck[top-2].val + statck[top].val; top = top -2; } TT1 * F { statck[top-2].val = statck[top-2].val * statck[top].val; top = top -2; } { statck[top-2].val = F(E) statck[top-1].val top = top -2; }

一个属性文法称为L-属性文法，如果对于每个产生式
int T_val, R_i, R_s; int E_val;
AX1X2Xn，其中每条语义规则中的每个属性或者
是综合属性，或者是X （1jn）的一个继承属性且这 (3) E→(E(1))
val[ntop]= val[top–1]
使用标记非终结符M和N改写为
2. 函数过程A的代码（指用符号形式表示的数据和程序）
要根据当前的输入符号来决定使用哪一个产生式。
3. 与每一个产生式有关的代码，从左到右根椐产生式右部是
终结符(单词符号)、非终结符号还是语义动作，分别处 理：
保存下来，以便以后语义子程序引用这些信息。
原LR分析器的分析栈也加以扩充，存放三类信息：分析
状态、文法符号及文法符号对应的语义值。
top
sk
Xk
Xk.val
... ... ...
s1
X1
X1.val
s0
#
_
状态 文法符号 语义值
扩充后的LR分析栈
例6-3 考虑下面的语法制导定义
产生式
语义规则
9–5+2的带语义动作的分析树
设计翻译模式（根据语法制导定义）
语法制导定义是L-属性文法 保证语义动作不会引用还没有计算的属性值。
只需要综合属性的情况
为每一个语义规则建立一个包含赋值的动作，并把这个 动作放在相应的产生式右边的末尾。
例如：T T(1)*F T.val:=T(1).val*F.val
产生式 语义规则 A LM L.i:=l(A.i)
M.i:=m(L.s) A.s:=f(M.s) A QR R.i:=r(A.i) Q.i:=q(R.s) A.s:=f(Q.s)

10
S { B.ps:=10 }
B {S.ht:=B.ht}
B { B1.ps:=B.ps} B1 {B2.ps:=B.ps} B2 { B.ht:=max(B1.ht,B2.ht) }
B {B1.ps:=B.ps } B1 sub {B2.ps:=shrink(B.ps)} B2 {B.ht:=disp(B1.ht,B2.ht)}
E
T
R
8 print(‘8') + T print(‘+')
R
5 print('5')
- T print(‘-')
R
经过一次深度优先遍历 得到输出：85+2-
2 print('2')
6
设计翻译方案时，必须遵守某些限制以保证当 某个动作引用一个属性时它是可用的，L属性 定义所规定的这些限制确保一个动作不会引用 一个还没有计算出来的属性
非终结符A对应的函数过程中，根据当前的输 入符号决定使用哪个产生式候选
每个产生式对应的程序代码中，按照从左到右 的次序，对于单词符号、非终结符和语义动作 分别作以下工作：
16
对于带有综合属性x的终结符X，把x的值存入为X.x 设置的变量中，然后产生一个匹配X的调用，并继 续读入一个输入符号
对于每个非终结符B，产生一个右边带有函数调用 的赋值语句c=B(b1,b2,...,bk)，其中b1,b2,...,bk是为B 的继承属性设置的变量，c是为B的综合属性设置的 变量
1
例：非L-属性文法
产生式
语义规则
ALM
L.i:=l(A.i)
M.i:=m(l.s)
AQR
R.i:=r(A.i)

属性和文法符号相关联 规则和产生式相关联

根据需要，将文法符号和某些属性相关联， 并通过语义规则来描述如何计算属性的值


E→E1+T E.code=E1.code || T.code || ‘+’ code表示了我们关心的表达式的逆波兰表示，规则说明 加法表达式的逆波兰表示由两个分量的逆波兰表示并置， 然后加上‘+’得到。
digitlexval=3
18
适用于自顶向下分析的SDD


前面的表达式文法存在直接左递归，因 此无法直接用自顶向下方法处理。 消除左递归之后，无法直接使用属性val 进行处理：


比如规则：T→FT’ T’→*FT’ T对应的项中，第一个因子对应于F， 而运算符在T’中。
19
相同表达式的不同文法的比较
38
例5.15 分析栈实现的例子

假设语法分析栈存放在一个被称为stack 的记录数组中，下标top指向栈顶；


stack[top]指向这个栈的栈顶；stack[top-1] 指向栈顶下一个位置； 如果不同的文法符号有不同的属性集合，我 们可以使用union来保存这些属性值。（归 约时，我们知道栈顶向下的各个符号分别是 什么）
语义翻译的流程
输 入 符 号 串 分 析 树 依 赖 图
语
义
规
则
的 计
实际上，编译中语义翻译的实现并不是 按图中的流程处理的；而是随语法分析 的进展，识别出一个语法结构，就对它 的语义进行分析和翻译。
算
9
5.1 语法制导定义

4.什么是语法制导定义（SDD） 上下文无关文法和属性/规则的结合；