Microsoft PowerPoint - syntaxdirect

Size: px

Start display at page:

Download "Microsoft PowerPoint - syntaxdirect"

竹街赵
5 years ago
Views:

1 本章内容语法制导的翻译编译原理和技术张昱中国科学技术大学计算机科学与技术学院语义描述的一种形式方法语法制导的定义 (syntax-directed definition) + E.code = E.code.code + 可读性好, 更适于描述规范翻译方案 (translation scheme) + { pr + 陈述了实现细节 ( 如语义规则的计算时机 ) 语法制导翻译的实现方法自上而下自下而上张昱 : 编译原理和技术语法制导的翻译 2 语法制导定义 4. 语法制导的定义定义综合属性继承属性属性依赖图与属性的计算次序定义基础的上下文无关文法每个文法符号有一组属性每个文法产生式 A 有一组形式为 b = f (c, c 2,, c k ) 的语义规则, 其中 : f 是函数 b 和 c, c 2,, c k 是该产生式文法符号的属性, 综合属性 (synthesized attribute): 如果 b 是 A 的属性,c, c 2,, c k 是产生式右部文法符号的属性或 A 的其它属性继承属性 (inherited attribute): 如果 b 是右部某文法符号 X 的属性张昱 : 编译原理和技术语法制导的翻译 4 简单计算器的语法制导定义产生式语义规则 E n pr (E.val) + E.val = E.val +.val E E.val =.val F.val=.val F.val F.val= F.val F (E) F.val = E.val F digit F.val = digit.lexval 的匿名属性对 E 加下标以区分不同的属性值各文法符号的属性均是综合属性的语法制导定义 S 属性定义参见 :bison-examples.tar.gz 中的 config/expr.y, expr.lex 张昱 : 编译原理和技术语法制导的翻译 5 注释分析树 (annotated parse tree) 结点的属性值都标注出来的分析树 8+5*2 n (n 为换行符 ) 的注释分析树 E.val =8.val =8 F.val =8 digit.lexval =8 E.val =8 +.val =5 F.val =5 digit.lexval =5 n.val =0 结点的综合属性值可由子结点的属性值计算得到 F.val =2 digit.lexval =2 张昱 : 编译原理和技术语法制导的翻译 6

2 继承属性举例 id, id, id 产生式语义规则.in =.type. type = eger real. type = real,id.in =.in; addype(id.entry,.in) id addype(id.entry,.in) type 的综合属性, in 的继承属性, 把声明的类型传递给标识符列表 addype 把类型信息加到符号表中的标识符条目里张昱 : 编译原理和技术语法制导的翻译 7 含继承属性的注释分析树 id, id 2, id 3 不能像综合属性那样自下而上标注继承属性.type = eger.in = eger.in = eger, id 3.in = eger, id 2 id 张昱 : 编译原理和技术语法制导的翻译 8 属性依赖图 (dependence graph) 属性依赖图 (dependence graph) id, id 2, id 3 分析树 ( 虚线 ) 的依赖图 ( 实线 ).in =.type id, id 2, id 3 分析树 ( 虚线 ) 的依赖图 ( 实线 ), id.in =.in; addype (id.entry,.in) 4 type in type in 5 6 in 7 8, id 3 3 entry in 7 8, id 3 3 entry in 9 0, id 2 2 entry in 9 0, id 2 2 entry id entry 张昱 : 编译原理和技术语法制导的翻译 9 id entry 张昱 : 编译原理和技术语法制导的翻译 0 属性依赖图 (dependence graph) id, id 2, id 3 分析树 ( 虚线 ) 的依赖图 ( 实线 ) id addype (id.entry,.in) 属性计算次序拓扑排序 (ological sort): 是 AG 的结点的一种排序 m,,m k, 若有 m i 到 m j 的边, 则在排序中 m i 先于 m j 例,2,3,4,5,6,7,8,9,0 4 type in type in 5 6 in 7 8, id 3 3 entry in 7 8, id 3 3 entry in 9 0, id 2 2 entry in 9 0, id 2 2 entry id entry 张昱 : 编译原理和技术语法制导的翻译 id entry 张昱 : 编译原理和技术语法制导的翻译 2 2

3 属性计算次序属性计算次序 ) 构造输入的分析树,2) 构造属性依赖图,3) 对结点进行拓扑排序,4) 按拓扑排序的次序计算属性 4 type in 5 6 in 7 8, id 3 3 entry in 9 0, id 2 2 entry id entry 张昱 : 编译原理和技术语法制导的翻译 3 语义规则的计算方法分析树方法刚才介绍的方法, 动态确定计算次序, 效率低概念上的一般方法基于规则的方法 ( 编译器实现者 ) 静态确定 ( 编译器设计者提供的 ) 语义规则的计算次序适用于手工构造的方法忽略规则的方法 ( 编译器实现者 ) 事先确定属性的计算策略 ( 如边分析边计算 ),( 编译器设计者提供的 ) 语义规则必须符合所选分析方法的限制适用于自动生成的方法张昱 : 编译原理和技术语法制导的翻译 4 语法树 (syntax tree) 4.2 语法树及其构造语法树语法树的构造 ( 文法对构造的影响 ) 语法制导定义翻译方案语法树是分析树的浓缩表示每个结点表示一个语法构造, 算符和关键字是语法树中的内部结点举例 : if then S else S if-then-else S S 2 语法制导翻译可以基于分析树, 也可以基于语法树张昱 : 编译原理和技术语法制导的翻译 6 * 2 构造语法树的语法制导定义语法树的构造产生式语义规则 + E.nptr = mknode( +, E.nptr,.nptr) E E.nptr =.nptr F.nptr = mknode(,.nptr, F.nptr) F.nptr = F.nptr F (E) F.nptr = E.nptr F id F.nptr = mkeaf (id, id.entry) F num F.nptr = mkeaf (num, num.val) 参见 :bison-examples.tar.gz 中的 config/asgn2ast.y, asgn.lex 张昱 : 编译原理和技术语法制导的翻译 7 a+5b 的语法树的构造 E.nptr E.nptr +.nptr.nptr.nptr F.nptr + F.nptr F.nptr id id num id num 5 id 指向符号表中 a 的入口指向符号表中 b 的入口张昱 : 编译原理和技术语法制导的翻译 8 3

4 翻译方案构造语法树的翻译方案 ( 左递归文法 ) + {E.nptr = mknode( +, E.nptr,.nptr) E {E.nptr =.nptr F {.nptr = mknode(,.nptr, F.nptr) F {.nptr = F.nptr F (E) {F.nptr = E.nptr F id {F.nptr = mkeaf (id, id.entry) F num {F.nptr = mkeaf (num, num.val) 综合属性的计算置于产生式右部的右边, 表示识别出右部后计算张昱 : 编译原理和技术语法制导的翻译 9 左递归的消除引起继承属性表达式语言的文法产生式语义规则 E R R.i =.nptr ; E.nptr = R.s R + R R.i = mknode ( +, R.i,.nptr); R.s = R.s R R.s = R.i FW W.i = F.nptr ;.nptr = W.s W * FW W.i = mknode ( +, W.i, F.nptr); W.s = W.s W W.s = W.i 张昱 : 编译原理和技术语法制导的翻译 20 F.nptr id id 语法树的构造 ( 文法 ) 指向符号表中 a 的入口 i W F.nptr num num 5 略去了 E R 部分 F W id W id *FW id * numw id * num *FW id * num * id W i W F.nptr id id i W s 指向符号表中 b 的入口张昱 : 编译原理和技术语法制导的翻译 2 a * 5 * b 的语法树翻译方案 E {R.i =.nptr R {E.nptr = R.s R + {R.i = mknode ( +, R.i,.nptr) R {R.s = R.s 继承属性的计算嵌在产 R {R.s = R.i 生式右部的某文法符号 F {W.i = F.nptr 之前, 表示在分析该文 W {.nptr = W.s 法符号之前计算 W F W {W.i = mknode (, W.i, F.nptr) {W.s = W.s W {W.s = W.i F 的产生式部分不再给出张昱 : 编译原理和技术语法制导的翻译 22 例题下面是产生字母表 = {0,, 2 上数字串的一个文法 : S S 2 0 写一个语法制导定义, 判断它接受的句子是否为回文数 SS pr(s.val) S S 2 S.val =(.val == 2.val)andS.val S 2 S.val = true 0.val =0.val = 张昱 : 编译原理和技术语法制导的翻译 23 例题 2 为下面文法写一个语法制导的定义, 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值例如, 输入 0.0 时,S.val = 5.625( 可以修改文法 ) 若按来计算, 该文法对小数点左边部分的计算不利, 因为需要继承属性来确定每个离开小数点的距离 S. S. 0 张昱 : 编译原理和技术语法制导的翻译 24 4

5 例题 2 为下面文法写一个语法制导的定义, 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值例如, 输入 0.0 时,S.val = 5.625( 可以修改文法 ) 若小数点左边按 ( 2+0)2+ 计算该办法不能直接用于小数点右边, 需改成 (( 2+0)2+)/2 3, 这时需要综合属性来统计的个数 S. S. 0 张昱 : 编译原理和技术语法制导的翻译 25 例题 2 为下面文法写一个语法制导的定义, 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值例如, 输入 0.0 时,S.val = 5.625( 可以修改文法 ) 更清楚的办法是将文法改成下面的形式 S.R R R 0 S. 张昱 : 编译原理和技术语法制导的翻译 26 R R R 例题 3 给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义例如, 因为和是左结合, ((a (b + c )) (d )) 可以重写成 a (b + c ) d 两种方法 : 先把括号都去掉, 然后在必要的地方再加括号去掉表达式中的冗余括号, 保留必要的括号例题 3 先把括号都去掉, 然后在必要的地方再加括号 SE pr( E. code ) + if. op == plus then E.code =E.code + (.code ) else E. code = E. code +. code; E. op = plus E E. code =. code; E. op =. op 张昱 : 编译原理和技术语法制导的翻译 27 张昱 : 编译原理和技术语法制导的翻译 28 例题 3 先把括号都去掉, 然后在必要的地方再加括号 F if (F. op == plus)or(f. op == times)then if. op == plus then. code = (. code ) ( F. code ) else. code =. code ( F. code ) else if. op = plus then. code = (. code ) F. code else. code =. code F. code;. op = times 例题 3 先把括号都去掉, 然后在必要的地方再加括号 F. code = F. code;. op = F. op F id F. code = id. lexeme; F. op = id F ( E ) F. code = E. code; F. op = E. op 张昱 : 编译原理和技术语法制导的翻译 29 张昱 : 编译原理和技术语法制导的翻译 30 5

6 例题 3 去掉表达式中的冗余括号, 保留必要的括号给 E, 和 F 两个继承属性 left_op 和 right_op 分别表示左右两侧算符的优先级给它们一个综合属性 self_op 表示自身主算符的优先级再给一个综合属性 code 表示没有冗余括号的代码分别用和 2 表示加和乘的优先级, 用 3 表示 id 和 (E) 的优先级, 用 0 表示左侧或右侧没有运算对象的情况例题 3 SE E. left_op =0;E. right_op =0;pr ( E. code ) + E. left_op = E. left_op; E. right_op =;. left_op =;. right_op = E. right_op; E.code =E.code +. code ; E. self_op =; E. left_op = E. left_op;. right_op = E. right_op; E. code =. code; E. self_op =. self_op 张昱 : 编译原理和技术语法制导的翻译 3 张昱 : 编译原理和技术语法制导的翻译 32 例题 3 F... F... F id F. code = id. lexeme; F. self_op =3 例题 3 F ( E ) E. left_op =0;E. right_op =0; F. self_op = if (F. left_op < E. self_op)and (E. self_op >= F. right_op) then E. self_op else 3 F. code = if (F. left_op < E. self_op)and (E. self_op >= F. right_op) then E. code else ( E. code ) 张昱 : 编译原理和技术语法制导的翻译 33 张昱 : 编译原理和技术语法制导的翻译 34 S 属性定义和属性定义 4.3 自上而下计算 S 属性定义属性定义翻译方案预测翻译器的设计用综合属性代替继承属性 S 属性定义仅使用综合属性的语法制导定义属性定义 ( 属性信息自左向右流动 ) 如果每个产生式 AX X j- X j X n 的每条语义规则计算的属性是 A 的综合属性, 或者是 X j 的继承属性, 但它仅依赖 : 该产生式中 X j 左边符号 X, X 2,,X j- 的属性 ; A 的继承属性可以按边分析边翻译的方式计算继承属性 S 属性定义是属性定义张昱 : 编译原理和技术语法制导的翻译 36 6

7 属性定义举例变量类型声明的语法制导定义产生式语义规则.in =.type. type = eger real. type = real,id.in =.in; addype(id.entry,.in) id addype(id.entry,.in) 张昱 : 编译原理和技术语法制导的翻译 37 翻译方案内嵌不传播的动作例把有加和减的中缀表达式翻译成后缀表达式如果输入是 8+5 2, 则输出是 E R R addop {pr(addop.lexeme) R num {pr(num.val) E R num {pr (8) R num {pr(8)addop {pr (+)R num {pr(8)addop num{pr(5){pr (+)R {pr(8){pr(5){pr(+)addop {pr()r {pr(8){pr(5){pr(+){pr(2){pr() 张昱 : 编译原理和技术语法制导的翻译 38 属性定义的自上而下计算数学排版语言 EQN 例数学排版语言 EQN E.val S text E.val 语法制导定义 E.val E ps-po size ( 属性 ); ht-height(s 属性 ) 产生式 S text 语义规则.ps = 0; S.ht =.ht.ps =.ps;.ps =.ps;.ht = max(.ps =.ps;.ps = shrink(.ps);.ht = disp (.ht = text.h.ps.val 张昱 : 编译原理和技术语法制导的翻译 39 张昱 : 编译原理和技术语法制导的翻译 40 数学排版语言 EQN S {.ps = 0 {S.ht =.ht 数学排版语言 EQN S {.ps = 0 {S.ht =.ht 的继承属性 ps 的计算位于的左边 S 的综合属性 ht 的计算放在 S 的产生式右部的末端张昱 : 编译原理和技术语法制导的翻译 4 张昱 : 编译原理和技术语法制导的翻译 42 7

8 数学排版语言 EQN S {.ps = 0 {S.ht =.ht {.ps =.ps {.ps =.ps {.ht = max( {.ps =.ps {.ps = shrink(.ps) {.ht = disp ( text {.ht = text.h.ps 张昱 : 编译原理和技术语法制导的翻译 43 预测翻译器的设计方法 : 将预测分析器的构造方法推广到翻译方案的实现 ( 文法 ) 产生式 R +R 的分析过程 void R( ) { if (lookahead == '+' ) { match ( '+' ); ( ); R( ); else if (lookahead == ')' lookahead == '$' ) ; else error( ); 张昱 : 编译原理和技术语法制导的翻译 44 预测翻译器的设计 syntaxreenode R (syntaxreenode i){ // 继承属性作为参数, 综合属性为返回值 syntaxreenode nptr, i, s, s; char addoplexeme; if (lookahead == '+' ) { addoplexeme = lexval; match('+' ); nptr = ( ); i = mknode(addoplexeme, i, nptr); s = R (i); s = s; else if (lookahead == ')' lookahead == '$') s = i; else error( ); return s; R : i, s : nptr + : addoplexeme 张昱 : 编译原理和技术语法制导的翻译 45 非属性定义例 Pascal 的声明, 如 m, n : eger :.in =.type eger char.type =, id id.in =.in, 该语法制导定义非属性定义信息从右向左流, 归约从左向右, 两者不一致张昱 : 编译原理和技术语法制导的翻译 46 非属性定义 : 改写文法例 Pascal 的声明, 如 m, n : eger :.in =.type ( 非属性定义 ) eger char.type =, id id.in =.in, 等所需信息获得后再归约, 改成从右向左归约 id (S 属性定义 ), id : id eger char, id 张昱 : 编译原理和技术语法制导的翻译 47 : eger 用综合属性代替继承属性 id { addtype (id. entry,. type), id {. type =. ype; addtype (id. entry,. type) : {. type =. type eger {. type = eger real {. type = real id, id 张昱 : 编译原理和技术语法制导的翻译 48 : eger 8

ab-3: Parseree =>AS AS 的定义 syntax_tree_node ab-3: Parseree =>AS AS 的定义 syntax_tree_node 访问者

4 自下而上计算综合属性的计算删除翻译方案中嵌入的动作继承属性的计算张昱 : 编译原理和技术语法制导的翻译 52 S 属性的自下而上计算边分析边计算 R 分析器的栈增加一个域来保存综合属性值栈 X X.

a 张昱 : 编译原理和技术语法制导的翻译 53 自下而上的翻译例简单计算器的语法制导定义改成栈操作代码产生式语义规则 E n pr (E.val) + E.val =E.val +.val E E.

9 ab-3: Parseree =>AS AS 的定义 syntax_tree_node ab-3: Parseree =>AS AS 的定义 syntax_tree_node 访问者 syntax_tree_visitor 访问者 syntax_tree_visitor 张昱 : 编译原理和技术语法制导的翻译 49 张昱 : 编译原理和技术语法制导的翻译 50 S 属性定义举例 4.4 自下而上计算综合属性的计算删除翻译方案中嵌入的动作继承属性的计算张昱 : 编译原理和技术语法制导的翻译 52 S 属性的自下而上计算边分析边计算 R 分析器的栈增加一个域来保存综合属性值栈 X X.x state val 若产生式 A XYZ 的语义规则是 A.a = f (X.x, Y.y, Z.z), 那么归约后 : A A.a 张昱 : 编译原理和技术语法制导的翻译 53 自下而上的翻译例简单计算器的语法制导定义改成栈操作代码产生式语义规则 E n pr (E.val) + E.val =E.val +.val E E.val =.val F.val =.val F.val X X.x F.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval 参见 :bison-examples.tar.gz 中的 config/expr.y, expr.lex 张昱 : 编译原理和技术语法制导的翻译 54 9

10 自下而上的翻译自下而上的翻译例栈简单计算器的语法制导定义改成栈操作代码产生式代码段 E n pr (E.val) + E.val =E.val +.val E E.val =.val F.val =.val F.val X X.x F.val = F.val F (E) F.val = E.val state val F digit F.val = digit.lexval 张昱 : 编译原理和技术语法制导的翻译 55 例简单计算器的语法制导定义改成栈操作代码产生式代码段 E n pr (val[] ) + E.val =E.val +.val E E.val =.val F.val =.val F.val X X.x F.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval 注 : 栈顶位置指示器的修改由原来的分析程序在语义动作执行后去做张昱 : 编译原理和技术语法制导的翻译 56 自下而上的翻译例简单计算器的语法制导定义改成栈操作代码产生式代码段 E n pr (val[] ); + val[2] = val [2] +val[]; E E.val =.val F.val =.val F.val X X.x F.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval 注 : 栈顶位置指示器的修改由原来的分析程序在语义动作执行后去做张昱 : 编译原理和技术语法制导的翻译 57 自下而上的翻译例简单计算器的语法制导定义改成栈操作代码产生式代码段 E n pr (val[] ); + val[2] = val [2] +val[]; E F.val =.val F.val X X.x F.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval 注 : 栈顶位置指示器的修改由原来的分析程序在语义动作执行后去做张昱 : 编译原理和技术语法制导的翻译 58 自下而上的翻译例简单计算器的语法制导定义改成栈操作代码产生式代码段 E n pr (val[] ); + val[2] = val [2] +val[]; E F val[2] = val [2] val[]; X X.x F.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval 注 : 栈顶位置指示器的修改由原来的分析程序在语义动作执行后去做张昱 : 编译原理和技术语法制导的翻译 59 自下而上的翻译例简单计算器的语法制导定义改成栈操作代码产生式代码段 E n pr (val[] ); + val[2] = val [2] +val[]; E F val[2] = val [2] val[]; X X.x F F (E) F.val = E.val F digit F.val = digit.lexval 注 : 栈顶位置指示器的修改由原来的分析程序在语义动作执行后去做张昱 : 编译原理和技术语法制导的翻译 60 0

11 自下而上的翻译例简单计算器的语法制导定义改成栈操作代码产生式代码段 E n pr (val[] ); + val[2] = val [2] +val[]; E F val[2] = val [2] val[]; X X.x F F (E) val[2] = val [] ; F digit F.val = digit.lexval 注 : 栈顶位置指示器的修改由原来的分析程序在语义动作执行后去做张昱 : 编译原理和技术语法制导的翻译 6 自下而上的翻译例简单计算器的语法制导定义改成栈操作代码产生式代码段 E n pr (val[] ); + val[2] = val [2] +val[]; E F val[2] = val [2] val[]; X X.x F F (E) val[2] = val [] ; F digit 注 : 栈顶位置指示器的修改由原来的分析程序在语义动作执行后去做张昱 : 编译原理和技术语法制导的翻译 62 ison 举例 bison-examples: config/expr.y 属性的自下而上计算 %{ #include <stdio.h> #include <math.h> % %union { float val; %token NUMER %token PUS MINUS MU IV EXPON %left MINUS PUS %left MU IV %right EXPON %type <val> exp NUMER %% input : input line ; exp : NUMER { $$ = $; exp PUS exp { $$ = $ + $3; exp MINUS exp { $$ = $ - $3; exp MU exp { $$ = $ * $3; exp IV exp { $$ = $ / $3; MINUS exp %prec MINUS { $$ = -$2; exp EXPON exp { $$ = pow($,$3); exp R { $$ = $2; ; %% yyerror(char *message) { prf("%s\n",message); main( argc, char *argv[]) { yyparse(); return(0); 张昱 : 编译原理和技术语法制导的翻译 63 在自下而上分析的框架中实现属性定义的方法它能实现任何基于 () 文法的属性定义也能实现许多 ( 但不是所有的 ) 基于 R() 的属性定义张昱 : 编译原理和技术语法制导的翻译 64 删除翻译方案中嵌入的动作中缀表达式翻译成后缀表达式 E R R + {pr ( + )R {pr ( )R num {pr(num.val) 在文法中加入产生的标记非终结符, 让每个嵌入动由不同的标记非终结符 M 代表, 并把该动作放在产生式 M 的右端 ( 继承属性 => 综合属性 ) E R R + M R N R num {pr (num.val) M {pr ( + ) {pr ( ) YACC 会按这种方法来处理输入的文法, 即为嵌入的语义动作引入产生式张昱 : 编译原理和技术语法制导的翻译 65 属性的自下而上计算 bison-examples: config/expr.y input : input{ lineno ++; prf("ine %d:\t", lineno); line { prf("*"); ; $$ 表示 HS 符号的语义值,$, $2 依次为 RHS 中符号的语义值, 本例中 line 的语义值通过 $3 来引用 src/expr.tab.c case 4: /* ine 806 of yacc.c */ #line 36 "config/expr.y" { prf("*"); break; yyreduce: /* yyn is the number of a rule to reduce with. */ YY_REUCE_PRIN (yyn); switch (yyn) { case 3: /* ine 806 of yacc.c */ #line 32 "config/expr.y" { lineno ++; prf("ine %d:\t", lineno); break; 张昱 : 编译原理和技术语法制导的翻译 66

12 继承属性在分析栈中情况属性位置可预测 4.4 自下而上计算综合属性的计算删除翻译方案中嵌入的动作继承属性的计算例 p, q, r {.in =.type {. type = eger real {. type = real {.in =.in,id{addtype (id.entry,.in ) id {addtype (id.entry,.in ) type in in, q p in 继承属性值已在分析栈中, r 张昱 : 编译原理和技术语法制导的翻译 68 继承属性在分析栈中情况属性位置可预测例 p, q, r type {.in =.type {. type = eger real {. type = real {.in =.in,id{addtype (id.entry,.in ) id {addtype (id.entry,.in ) 张昱 : 编译原理和技术语法制导的翻译 69 in in, r in, q p 略去继承属性的计算引用继承属性的地方改成引用其他符号的综合属性继承属性在分析栈中情况属性位置可预测产生式代码段 type in in, r val[] = eger in, q real val[] = real, id addype(val[], p val[3]) ; id addype(val[], val[]) ; 略去继承属性的计算引用继承属性的地方改成引用其他符号的综合属性张昱 : 编译原理和技术语法制导的翻译 70 YACC 中的继承属性定义在内嵌动作代码中设置该文法符号的语义值 bison-examples: config/expr.y line : NUMER { $<val>lineno = $; // val 是 %union 中声明的语义值类型 // $<val>$ = $; // 该语义动作代码未指定名字时 [lineno] exp EO { prf("ine %d: %g\n", () $<val>lineno, $3); 张昱 : 编译原理和技术语法制导的翻译 7 YACC 中的继承属性定义在内嵌代码中使用存储在栈中任意固定相对位置的语义值 bison-examples: config/midrule.y exp: a_ a_2 { $<val>$ = 3; { $<val>$ = $<val>3 + ; a_5 sum_of_the_five_previous_values { USE (($, $2, $<foo>3, $<foo>4, $5)); prf ("%d\n", $6); sum_of_the_five_previous_values: { $$ = $<val>0 + $<val>- + $<val>-2 + $<val>-3 + $<val>-4; $<val>0 $<val>- $<val>-2 $<val>-3 $<val>-4 分别表示栈中 a_5 { $<val>$ = $<val>3 + ; { $<val>$ = 3; a_2 a_ 文法符号的语义值张昱 : 编译原理和技术语法制导的翻译 72 2

13 继承属性在分析栈中情况 2 属性位置不可预测 S aac C.i = A.s S bac C.i = A.s C c C.s = g(c.i) 继承属性值已在分析栈中可能在, 也可能不在 A 和 C 之间,C.i 的值有 2 种可能增加标记非终结符, 使得位置可以预测 S aac C.i = A.s S bamc M.i = A.s; C.i = M.s C c C.s = g(c.i) M M.s = M.i 张昱 : 编译原理和技术语法制导的翻译 73 模拟继承属性的计算继承属性是综合属性的函数 S aac C.i = f (A.s) C c C.s = g(c.i) 继承属性不直接等于某个综合属性增加标记非终结符, 把 f(a.s) 的计算移到对标记非终结符归约时进行 S aanc N.i = A.s; C.i = N.s N.s = f (N.i) C c C.s = g(c.i) 张昱 : 编译原理和技术语法制导的翻译 74 数学排版语言 EQN S {.ps = 0 {S.ht =.ht {.ps =.ps {.ps =.ps {.ht = max( {.ps =.ps {.ps = shrink(.ps) {.ht = disp ( text {.ht = text.h.ps 张昱 : 编译原理和技术语法制导的翻译 75 S.ps =.s; S.ht =.ht.s = 0 将.ps 存入栈中, 便于引用 M.ps =.ps; M.i =.ps;.ps = M.s;.ht = max( M M.s = M.i N.ps =.ps; N.i =.ps;.ps = N.s;.ht = disp ( N.s = shrink(n.i) text.ht = text.h.ps 张昱 : 编译原理和技术语法制导的翻译 76 S.ps =.s; S.ht =.ht.s = 0 将.ps 存入栈中, 便于引用 M.ps =.ps; M.i =.ps;.ps = M.s;.ht = max( S.ps =.s; S.ht =.ht.s = 0 将.ps 存入栈中, 便于引用 M.ps =.ps; M.i =.ps;.ps = M.s;.ht = max( M M.s = M.i 单纯为了属性位置可预测 M M.s = M.i 单纯为了属性位置可预测 N.ps =.ps; N.i =.ps;.ps = N.s;.ht = disp ( N.ps =.ps; N.i =.ps;.ps = N.s;.ht = disp ( N.s = shrink(n.i) N.s = shrink(n.i) 兼有计算功能 text.ht = text.h.ps text.ht = text.h.ps 张昱 : 编译原理和技术语法制导的翻译 77 张昱 : 编译原理和技术语法制导的翻译 78 3

14 s S M s 在 text 归约成时, 的 ps 属性都在次栈顶位置 text N s text text 张昱 : 编译原理和技术语法制导的翻译 79 S.ps =.s; S.ht =.ht.s = 0 M.ps =.ps; M.i =.ps;.ps = M.s;.ht = max( M M.s = M.i N text.ps =.ps; N.i =.ps;.ps = N.s;.ht = disp ( N.s = shrink(n.i).ht = text.h.ps 继承属性的值等于栈中某个综合属性的值, 因此栈中只保存综合属性的值张昱 : 编译原理和技术语法制导的翻译 80 S val[] = val[].s = 0 M.ps =.ps; M.i =.ps;.ps = M.s;.ht = max( M M.s = M.i N text.ps =.ps; N.i =.ps;.ps = N.s;.ht = disp ( N.s = shrink(n.i).ht = text.h.ps.ps =.s; S.ht =.ht 张昱 : 编译原理和技术语法制导的翻译 8 S val[] = val[] val[+] = 0 M.ps =.ps; M.i =.ps;.ps = M.s;.ht = max( M M.s = M.i N text.ps =.ps; N.i =.ps;.ps = N.s;.ht = disp ( N.s = shrink(n.i).ht = text.h.ps.s = 0 张昱 : 编译原理和技术语法制导的翻译 82 S val[] = val[] val[+] = 0 M val[-2]= max(val[-2], val[] ) S val[] = val[] val[+] = 0 M val[-2]= max(val[-2], val[] ) M M.s = M.i M val[+] = val[-] N.ps =.ps; N.i =.ps;.ps = N.s;.ht = disp ( N.ps =.ps; N.i =.ps;.ps = N.s;.ht = disp ( N.s = shrink(n.i) N.s = shrink(n.i) text.ht = text.h.ps text.ht = text.h.ps.ps =.ps; M.i =.ps;.ps = M.s;.ht = max( 张昱 : 编译原理和技术语法制导的翻译 83 M.i =.ps; M.s = M.i 张昱 : 编译原理和技术语法制导的翻译 84 4

15 S val[] = val[] val[+] = 0 M val[-2]= max(val[-2], val[] ) S val[] = val[] val[+] = 0 M val[-2]= max(val[-2], val[] ) M val[+] = val[-] val[-3]= disp (val[-3], val[] ) N M val[+] = val[-] val[-3]= disp (val[-3], val[] ) N N.s = shrink(n.i) val[+] = shrink(val[-2]) text.ht = text.h.ps text.ht = text.h.ps.ps =.ps; N.i =.ps;.ps = N.s;.ht = disp ( 张昱 : 编译原理和技术语法制导的翻译 85.ht = text.h.ps 张昱 : 编译原理和技术语法制导的翻译 86 S val[] = val[] val[+] = 0 M val[-2]= max(val[-2], val[] ) M val[+] = val[-] val[-3]= disp (val[-3], val[] ) N text val[+] = shrink(val[-2]).ht = text.h val[-] N.i =.ps; N.s = shrink(n.i) 张昱 : 编译原理和技术语法制导的翻译 87 5

Microsoft PowerPoint - ch4.ppt [兼容模式]

Microsoft PowerPoint - ch4.ppt [兼容模式] 第四章语法制导的翻译本章内容 1 介绍语义描述的一种形式方法 : 语法制导的翻译 (sytax-directed traslatio), 它包括两种具体形式语法制导的定义 (sytax-directed defiitio) E.code = E 1.code.code 可读性好, 更适于描述规范翻译方案 (traslatio scheme) { prit } 陈述了实现细节 ( 如语义规则的计算时机