Download presentation
Presentation is loading. Please wait.
1
编译原理与技术 语法制导翻译 2019/1/17 《编译原理与技术》讲义
2
语法制导翻译 属性文法 自底向上翻译 自顶向下翻译 S-属性定义 L-属性定义 语法制导定义与翻译方案 S-属性定义自底向上计算
自底向上计算继承属性 自顶向下翻译 2019/1/17 《编译原理与技术》讲义
3
属性文法 属性文法(Attributed Grammar) 上下文无关文法+属性+属性计算规则 属性-用来描述文法符号的语义特征,如
常量的“值”、变量的类型和存储位置等。 e.g. 二义性表达式文法G,非终结符E有属性E.val(表达式的值) EE ‘+’ E | E ‘*’ E | ‘(‘ E ‘)’ | number 属性计算规则(语义规则) 与产生式相关联的反映文法符号属性之间关系的“规则” 2019/1/17 《编译原理与技术》讲义
4
语义规则仅表明属性间“抽象”关系,不涉及具体翻译实现细节,如计算次序等。
属性文法 语法制导定义(文法+属性+语义规则) 语义规则仅表明属性间“抽象”关系,不涉及具体翻译实现细节,如计算次序等。 翻译方案(文法+属性+语义动作) 语义规则-即语义动作,可体现若干实现的细节。 2019/1/17 《编译原理与技术》讲义
5
e.g.1算术表达式的计算器 产生式 语法制导定义 EE1 ‘+’ E2 E.val := E1.val + E2.val
产生式 语法制导定义 EE1 ‘+’ E E.val := E1.val + E2.val EE1 ‘*’ E E.val := E1.val * E2.val E’(‘ E1 ‘)’ E.val := E1.val Enumber E.val := number.lex_val 2019/1/17 《编译原理与技术》讲义
6
e.g.1算术表达式的计算器 产生式 翻译方案 EE1 ‘+’ E2 { E.val := E1 .val + E2.val }
产生式 翻译方案 EE1 ‘+’ E2 { E.val := E1 .val + E2.val } EE1 ‘*’ E2 { E.val := E1.val * E2.val } E’(‘ E1 ‘)’ { E.val := E1.val } Enumber { E.val := number.lex_val } 2019/1/17 《编译原理与技术》讲义
7
属性文法 属性的分类 若产生式AX1X2…Xn,与之相关的属性计算规则 b := f ( c1, c2, … )
-如果属性b是产生式左部符号A的属性则称其为A的综合属性; -如果属性b是产生式右部符号Xi的属性则称其为Xi的继承属性; -c1, c2, … 一般是产生式右部其它符号的(综合)属性或A的继承属性; - 固有属性:终结符仅有的属性。如number.lex_val。通常由词法程序提供。 2019/1/17 《编译原理与技术》讲义
8
属性依赖图 A.b A X1.c1 X2.c2 … Xn.cn X1.c1 X2.c2 Xk.b … Xn.cn 继承属性Xk.b的计算
2019/1/17 《编译原理与技术》讲义
9
e.g. 2 属性依赖图: 3+4×5 + E. val = 23 E. val = 3 E. val = 20
number. lex_val = 3 E. val = 4 × E. val = 5 number. lex_val = 4 number. lex_val = 5 2019/1/17 《编译原理与技术》讲义
10
语义规则的计算方法 分析树方法 基于规则的方法 忽略规则的方法 - 为输入串建立分析树 - 由语义规则建立属性依赖图(没有属性循环依赖的)
- 对依赖图进行拓扑排序,得到属性计算次序 - 依次计算属性,得到“翻译”结果 基于规则的方法 - 构造编译器时,事先对产生式的语义规则进行分析,得到属性计算次序 忽略规则的方法 - 属性计算次序仅由分析方法限定。如S-属性定义可以在自下而上分析时,在归约前计算。如YACC中的语义动作。 2019/1/17 《编译原理与技术》讲义
11
e.g. 3 属性计算次序: 3+4×5 + E. val = 23 E. val = 3 E. val = 20
8 E. val = 23 2 7 E. val = 3 + E. val = 20 6 1 4 number. lex_val = 3 E. val = 4 × E. val = 5 3 5 number. lex_val = 4 number. lex_val = 5 2019/1/17 《编译原理与技术》讲义
12
S-属性定义 -语义规则仅包含综合属性计算(可以有固有属性出现)。 -适合自底向上计算 e.g. 语法树 -语法树与分析树
语法树可看作分析树的浓缩。也称抽象语法树。而分析树可看成具体语法树。 2019/1/17 《编译原理与技术》讲义
13
语法树 vs. 分析树 S if B-expr then S1 else S2 语法树 分析树 S if-then-else
语法树 分析树 S if-then-else B-expr S1 S2 if B-expr then S1 else S2 2019/1/17 《编译原理与技术》讲义
14
语法树 vs. 分析树 a := b* -c + b * -c 语法树 分析树 赋值语句 assign 算符 E assign E a +
语法树 分析树 赋值语句 assign 算符 E assign E a + a E + E * * E * E E * E b @ b @ @ E @ b b E c c c c 2019/1/17 《编译原理与技术》讲义
15
语法树 vs. DAG DAG(去除了公共子表达式的无环有向图) a := b* -c + b * -c assign assign a +
@ b @ b @ c c c 语法树 DAG 2019/1/17 《编译原理与技术》讲义
16
e.g.4 构造表达式的语法树(DAG) 产生式 语义规则
产生式 语义规则 EE1 + E E.nptr := mknode(‘+’,E1.nptr, E2.nptr) EE1 - E E.nptr := mknode(‘-’,E1.nptr, E2.nptr) EE1 * E E.nptr := mknode(‘*’,E1.nptr, E2.nptr) EE1 / E E.nptr := mknode(‘/’,E1.nptr, E2.nptr) E( E1 ) E.nptr := E1.nptr E - E E.nptr := -) Enumber E.nptr := mkleaf(‘NUM’,number.lex_val) Eid E.nptr := mkleaf(‘ID’,id.entry) 2019/1/17 《编译原理与技术》讲义
17
e.g.4 构造表达式的语法树(DAG) E.nptr - E的语法树(根结点指针)
mknode(op, left, right)-建立一个表达式语法树结点,它的运算符为op,左、右运算对象是left和right所指的语法树。如果建成DAG,则需要检查是否已存在相应内部结点op,其左右运算对象分别是left和right。若没有则新建一个。 mkleaf(‘NUM’,number.lex_val)- mkleaf(‘ID’,id.entry)- 建立表达式语法树的叶结点。建DAG也需检查是否已有相应结点。 2019/1/17 《编译原理与技术》讲义
18
e.g.4 构造表达式a+b*-4的属性结构树 + * @ - ID a ID b NUM 4 E.nptr E.nptr + E.nptr
2019/1/17 《编译原理与技术》讲义
19
e.g.4 构造表达式a+b*-4的语法树(DAG)
ID a * ID b @ - NUM 4 2019/1/17 《编译原理与技术》讲义
20
L-属性定义 -如果产生式AX1X2…Xn 的语义规则只计算 1)A的综合属性,或者
2)Xi的继承属性,且该属性仅依赖于产生式右部Xi的左边符号Xj(j<i)的(综合)属性或A的继承属性; -S-属性定义均为L-属性定义 -可按深度优先次序计算 - 一种自然的属性计算次序 - 在分析期间完成翻译。属性计算与结点建立有联系;适合于自顶向下和自底向上分析方法。 2019/1/17 《编译原理与技术》讲义
21
深度优先次序 procedure dfvisit( n : node ) begin
for each child m of n, from left to right do begin evaluate inherited attributes of m; dfvisit( m ) ; end; evaluate synthesized attributes of n; end 2019/1/17 《编译原理与技术》讲义
22
e.g.5 非L-属性定义的语法制导定义 产生式 语义规则 ALM L.i := l(A.i) M.i := m(L.s)
产生式 语义规则 ALM L.i := l(A.i) M.i := m(L.s) A.s := f(M.s) AQR R.i := r(A.i) Q.i := q(R.s) A.s := f(Q.s) 2019/1/17 《编译原理与技术》讲义
23
翻译方案中的动作 -语义动作可放在产生式右端任何位置;这也就显式地给出了动作的执行时刻。(可认为是在深度优先遍历中的执行时刻)
e.g. 6将含有+和-运算的中缀表达式翻译为后缀形式: ET R R addop T { print( addop.lex_val) } R | T number { print( number.lex_val) } 2019/1/17 《编译原理与技术》讲义
24
e.g. 6 中缀翻译为后缀 :9-4+5 E T R - T print(‘-’) R 9 print(9) 4 print(4) + T
3 1 4 print(4) + T print(‘+’) R 5 2 5 print(5) 4 2019/1/17 《编译原理与技术》讲义
25
翻译方案中的动作 -设计翻译方案时,必须保证动作所引用的属性值是可用的。 -只有综合综合属性时(S-属性定义),动作放在产生式末尾;
- 若有继承属性时,动作的放置须保证: - (产生式右部)符号的继承属性必须在 此符号前计算; - 动作不要引用其右边符号的综合属性; - 左部非终结符的综合属性一般放在产生式末 尾(确保它引用的属性均已计算完且可用) 2019/1/17 《编译原理与技术》讲义
26
e.g.7 翻译方案的书写 S A1 A2 { A1.in := 1 ; A2.in := 2 }
A a { print( A.in ) } 改写为: S { A1.in := 1 } A1 { A2.in := 2 } A2 2019/1/17 《编译原理与技术》讲义
27
e.g.8 类型说明的语法制导定义(0) 产生式 语义规则 DT L L.in := T.type
产生式 语义规则 DT L L.in := T.type Tint T.type := integer Treal T.type := real LL1 , id L1.in := L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 2019/1/17 《编译原理与技术》讲义
28
e.g.8 类型说明的语法制导定义(0)- 属性传递
D T L L , k int L , j i 2019/1/17 《编译原理与技术》讲义
29
e.g.8类型说明的语法制导定义(1) 改写上述类型声明文法,使得其中的T成为L的子结点(即产生式右部),可以避免继承属性的使用。修改后文法如下: DL Tint Treal LL1 , id LT id 2019/1/17 《编译原理与技术》讲义
30
e.g.8类型说明的语法制导定义(2) 产生式 语义规则 D L Tint T.type := integer
产生式 语义规则 D L Tint T.type := integer Treal T.type := real LL1 , id L.in := L1.in addtype(id.entry, L1.in) LT id addtype(id.entry, T.type); L.in := T.type 2019/1/17 《编译原理与技术》讲义
31
D e.g.8类型说明的语法制导定义(2) 属性传递 L L , k L , j T i int 2019/1/17 《编译原理与技术》讲义
32
e.g.8 类型说明的语法制导定义(3) Pascal语言类型声明文法如下: DL : T Tint Treal LL1 , id
该声明文法的“问题”在于,L中声明的变量的类型T处于产生式中L的右边!若用继承属性L.in来传递类型信息T.type形成非L-属性定义。从而无法在完成L分析同时将有关类型信息填入符号表!可以考虑将T作为L的子结点(通过修改文法)来改变这种情况 2019/1/17 《编译原理与技术》讲义
33
e.g.8 类型说明的语法制导定义(4) 产生式 语义规则 D id L addtype(id.entry,L.in)
产生式 语义规则 D id L addtype(id.entry,L.in) Tint T.type := integer Treal T.type := real L, id L L.in := L1.in addtype(id.entry, L1.in) L : T L.in := T.type 2019/1/17 《编译原理与技术》讲义
34
e.g.9 翻译方案的计算次序 EE+T { print( “1” ) } ET { print( “2” ) }
TT*F { print( “3” ) } TF { print( “4” ) } F(E) { print( “5” ) } Fid { print( “6” ) } 输入串是id*(id+id)时,该翻译方案输出什么? 2019/1/17 《编译原理与技术》讲义
35
S-属性定义的自底向上计算 拓广分析栈,即添加属性栈,包含文法符号的综合属性。在归约实施前,右部各符号的综合属性(若有的话)已放在与符号位置对应的属性栈上,因此,可以先计算获得左部非终结符的综合属性。然后再归约,这时从分析栈中弹出句柄,(注意,此时改变栈顶top即可)最后,将左部符号连同其属性放入由top指示的分析栈及属性栈的位置中。 这种属性栈只能存放综合属性。 回想YACC中如何做的? 2019/1/17 《编译原理与技术》讲义
36
属性栈与分析栈 如果AXYZ,相关 语义规则如下: A.a := f(X.x,Y.y,Z.z) 显然, X.x在Val[top-2]
Y.y在Val[top-1] Z.z在Val[top] A.a在Val[ntop] ,ntop = top – |句柄长度|+1 Val[ ntop ] := f( val[top-2], Val[top-1], Val[top] ) Z Z.z Y Y.y X X.x … 分析栈 属性栈 Val top bottom 2019/1/17 《编译原理与技术》讲义
37
属性栈与分析栈 如果AB ,相关 语义规则如下: A.a := B.b 显然, B.b在Val[top] A.a在Val[ntop] ,
ntop = top – 1+1 = top ,即归约前后栈顶top不变, 也即Val[ ntop ] 和 Val[top]对应属性栈同一个单元, 所以,可以省略原语义规则对应的属性栈操作: Val[ntop] := Val[top] top B B.b … … bottom … … 分析栈 属性栈Val 2019/1/17 《编译原理与技术》讲义
38
e.g.10 计算表达式的(栈)代码 产生式 语义规则 代码段 Print( Val[top-1] )
LE ‘\n’ Print( E.val ) Print( Val[top-1] ) EE1+T E.val := E1.val + T.val Val[ntop]:=Val[top-2]+Val[top] ET E.val := T.val TT1*F T.val := T1.val * F.val Val[ntop]:=Val[top-2]*Val[top] TF T.val := F.val F(E) F.val := E.val Val[ntop]:=Val[top-1] Fdigit F.val := digit.lex_val 2019/1/17 《编译原理与技术》讲义
39
自底向上计算继承属性 如何在自底向上分析中计算继承属性? - 属性栈上仅能存放综合属性 - 能否将继承属性的引用转换成综合属性?
分析栈中符号的继承属性 - 属性copy规则 如果,AXY,有语义规则Y.i := X.s, 翻译方案可写为: A X { Y.i := X.s } Y 2019/1/17 《编译原理与技术》讲义
40
自底向上计算继承属性 - 由属性copy规则可知,Y的继承属性Y.i和X.s在属性栈上同一位置。这样对属性Y.i的引用可以转化为对X.s的引用。若计算Y的综合属性Y.s时需要引用 Y.i,则此时Y.i(即X.s)就紧邻在句柄下面; 如果Y的句柄形成前, 它的某个右部符号 需使用Y.i,这时, 也可以直接使用Y.i。 (How to use?) bottom … X X.s(Y.i) 分析栈 属性栈 Val top 句柄 (归约为Y) top-句柄长 2019/1/17 《编译原理与技术》讲义
41
e.g.11 C声明的翻译方案 DT { L.in := T.type } L Tint { T.type := integer }
Treal { T.type := real } L { L1.in := L.in } L1 , id {addtype(id.entry, L.in) } Lid { addtype(id.entry, L.in) } 对于输入串:int p,q,r 分析过程如下: 2019/1/17 《编译原理与技术》讲义
42
输入串 分析栈 产生式 int p,q,r p,q,r int p,q,r T Tint ,q,r Tp ,q,r TL Lid
输入串 分析栈 产生式 int p,q,r p,q,r int p,q,r T Tint ,q,r Tp ,q,r TL Lid q,r TL, ,r TL,q ,r TL LL , id r TL, TL,r TL LL , id D DTL 注意:每次归约成L时,T与L的位置关系--T就在句柄的下面! 2019/1/17 《编译原理与技术》讲义
43
e.g.11 C声明的“代码段” 产生式 代码段(只含综合属性) DT L Tint val[ntop]:=integer
产生式 代码段(只含综合属性) DT L Tint val[ntop]:=integer Treal val[ntop]:=real L L1 , id addtype(val[top],val[top-3]) Lid addtype(val[top],val[top-1]) L的继承属性L.in 2019/1/17 《编译原理与技术》讲义
44
模拟继承属性的计算 问题1:继承属性的位置在构造编译器时不可预知(或不固定),如e.g.12 产生式 语义规则
产生式 语义规则 S a A C C.i := A.s S b A B C C.i := A.s C c C.s := g(C.i) … 用C c归约时,C.i的值可能在val[top-1]或者在val[top-2]的位置上。解决办法是考虑将其统一。 引入标记非终结符 M和产生式M 。 top c c A B a A b … … bottom 分析栈1 分析栈2 2019/1/17 《编译原理与技术》讲义
45
e.g.12 引入标记非终结符 产生式 语义规则 S a A C C.i := A.s S b A B M C C.i := M.s
产生式 语义规则 S a A C C.i := A.s S b A B M C C.i := M.s M.i := A.s C c C.s := g(C.i) M M.s := M.i … 引入M后,C.i 可从句柄c的下面(val[top-1])取得!属性传递: A.s M.i M.s C.i C.s top c c A M a B … A … b … … bottom 分析栈1 分析栈2 2019/1/17 《编译原理与技术》讲义
46
C c val[ntop]:= g(val[top-1]) M val[ntop] := val[top-1] …
产生式 代码段 S a A C S b A B M C C c val[ntop]:= g(val[top-1]) M val[ntop] := val[top-1] … 可否将M放在S a A C产生式中? M.i 2019/1/17 《编译原理与技术》讲义
47
模拟继承属性的计算 问题2:语义规则不是简单的属性复写拷贝。 e.g.13 : 将例12中的S a A C语义规则换为:
产生式 语义规则 S a A C C.i := f( A.s ) 虽然在例12中引入了M使得“A.s”可在val[top-1] 处找到,但在S的两个产生式中C.i的取值方式 不同,导致C.s的计算嘛… 这次可以考虑引入标记非终结符N和N 2019/1/17 《编译原理与技术》讲义
48
e.g.13 引入标记非终结符N 产生式 语义规则 S a A N C C.i := N.s N.i := A.s
产生式 语义规则 S a A N C C.i := N.s N.i := A.s N N.s := f(N.i) (其他产生式和语义规则不变) (代码段略) 2019/1/17 《编译原理与技术》讲义
49
e.g.14 文字排版的语法制导定义 产生式 语义规则 SB B.ps := 10 S.ht := B.ht
产生式 语义规则 SB B.ps := 10 S.ht := B.ht BB1B2 B1.ps := B.ps B2.ps := B.ps B.ht := max(B1.ht,B2.ht) BB1 sub B B1.ps := B.ps B2.ps := shrink(B.ps) B.ht := disp(B1.ht,B2.ht) B text B.ht := text.h × B.ps 2019/1/17 《编译原理与技术》讲义
50
文字排版中的符号属性 S : S.ht,综合属性;待排公式的整体高度 B : B.ps,继承属性; 公式(文本)中字体“点”的大小
B.ht,综合属性;公式排版高度 text :text.h,文本高度 max :求两个排版公式的最大高度 shrink(B) :将点大小缩小为B的30% disp(B1.ht,B2.ht):向下调整B2的位置 E Val 1 2019/1/17 《编译原理与技术》讲义
51
文字排版的翻译方案(0) S { B.ps := 10 } B { S.ht := B.ht } B { B1.ps := B.ps }
B2 { B.ht := max(B1.ht,B2.ht) } B1 sub { B2.ps := shrink(B.ps) } B2 { B.ht := disp(B1.ht,B2.ht) } B text { B.ht := text.h × B.ps } 2019/1/17 《编译原理与技术》讲义
52
文字排版中引入标记符号 为了自底向上计算: B text { B.ht := text.h × B.ps }
入标记非终结符L、M和N及其属性,包括相应的空产 生式和有关属性规则。这样B.ps即可在紧靠“句柄”text 下方的位置上找到。(L的综合属性置为B.ps的初值) SL B BB1M B2 BB1 sub N B2 top text text.h L L.s=10 bottom 分析栈 属性栈 2019/1/17 《编译原理与技术》讲义
53
文字排版的翻译方案(1) S L { B.ps := L.s } L { L.s := 10 } B { S.ht := B.ht }
B { B1.ps := B.ps } M { M.s := M.i } B1 { M.i := B.ps } M { B2.ps := M.s } B2 { B.ht := max(B1.ht,B2.ht) } B { B1.ps := B.ps } B1 sub { N.i := B.ps } N { N.s :=shrink(N.i) } N { B2.ps := N.s } B2 { B.ht := disp(B1.ht,B2.ht) } B text { B.ht := text.h × B.ps } 2019/1/17 《编译原理与技术》讲义
54
S L B val[ntop] := val[top]
产生式 代码段 S L B val[ntop] := val[top] BB1 M B val[ntop] := max(val[top-2],val[top]) BB1 sub N B val[ntop] := disp(val[top-3],val[top]) B text val[ntop] := val[top]×val[top-1] L val[ntop] := 10 M val[ntop] := val[top-1] N val[ntop] := shrink( val[top-2] ) 2019/1/17 《编译原理与技术》讲义
55
(L-属性定义)自顶向下翻译 删除翻译方案中的左递归 A A1Y { A.a := g(A1.a, Y.y) }
A X { A.a := f( X.x) } 消除左递归: A X { R.i := f( X.x) }//传递“左”运算量 R { A.a := R.s } R Y { R1.i := g(R.i, Y.y) } R1 { R.s := R1.s } R { R.s := R.i }//返回结果 2019/1/17 《编译原理与技术》讲义
56
输入串XY1Y2的翻译 A.a X R.i := f(X.x) R.s y2 Y1 R.i := g(f(X.x),Y1.y) R.s y1
A.a := g(g(f( X.x), y1.y), y2.y) y2 Y1 A.a := g(f( X.x), y1.y) R.i := g(f(X.x),Y1.y) R.s y1 A.a := f( X.x) Y2 R.i := g(g(f(X.x),Y1.y), Y2.y) X R.s 2019/1/17 《编译原理与技术》讲义
57
e.g.15 删除翻译方案中左递归 EE1 + T { E.nptr := mknode(‘+’,E1.nptr, T.nptr)}
ET { E.nptr := T.nptr } T( E ) { T.nptr := E.nptr } Tnum { T.nptr := mkleaf(‘NUM’,num.val) } Tid { T.nptr := mkleaf(‘ID’,id.entry) } 2019/1/17 《编译原理与技术》讲义
58
T { R1.i := mknode(‘+’, R.i, T.nptr) } //”建树“ R1 { R.s := R1.s } R -
E T { R.i := T.nptr } R { E.nptr := R.s } R + T { R1.i := mknode(‘+’, R.i, T.nptr) } //”建树“ R1 { R.s := R1.s } R - T { R1.i := mknode(‘-’, R.i, T.nptr) } R { R.s := R.i } //返回最终语法树 (其余略) 2019/1/17 《编译原理与技术》讲义
59
(递归下降)预测翻译器的设计 为每个非终结符A构造用于分析和属性计算的函数(注意,在递归下降的语法分析中构造的仅是过程),这样的函数构成如下: - 参数:符号A的继承属性 - 返回值:符号A的综合属性(记录) - 局部变量:A的产生式中每个符号的属性均有对应的局部量(A的继承属性除外) - 函数体形式为:(类似递归分析过程) -根据输入符号决定产生式的选择; - 对每个可能选择的产生式从左自右分析并计算属性(执行语义动作) 2019/1/17 《编译原理与技术》讲义
60
- 对每个可能选择的产生式从左自右分析并计算属性(执行语义动作):
(1)终结符X,将X.x保存在相应的局部量中(如果有的话),调用match(X); (2)非终结符B,产生赋值 c := B(b1,b2,…bn),c和bi分别是B的综合属性和继承属性对应的局部变量; (3)语义动作,将代码直接拷贝到函数体中,而其中属性出现改为局部量的引用; (4)函数结尾:return A的综合属性。 2019/1/17 《编译原理与技术》讲义
61
e.g.16 递归翻译函数 R + T { R1.i := mknode(‘+’, R.i, T.nptr) }
R1 { R.s := R1.s } R - T { R1.i := mknode(‘-’, R.i, T.nptr) } R { R.s := R.i } 2019/1/17 《编译原理与技术》讲义
62
node_ptr R ( node_ptr i ) { node_ptr nptr, i1, s1, s ; //符号属性对应的局部量
if (lookhead == ‘+’) { // R + T R match(‘+’); nptr = T(); i1 = mknode( ‘+’, i, nptr ); //语义动作 s1 = R ( i1 ); s = s1 ; // 语义动作 } else if … // R - T R else s = i ; // R 语义动作 return s; 非终结符R的递归翻译函数 2019/1/17 《编译原理与技术》讲义
Similar presentations