编译原理与技术 语法制导翻译.ppt

2020 3 1 编译原理与技术 讲义 1 编译原理与技术 语法制导翻译 2020 3 1 编译原理与技术 讲义 2 语法制导翻译 属性文法s 属性定义l 属性定义语法制导定义与翻译方案自底向上翻译s 属性定义自底向上计算自底向上计算继承属性自顶向下翻译 2020 3 1 编译原理与技术 讲义 3 属性文法 属性文法 attributedgrammar 上下文无关文法 属性 属性计算规则属性 用来描述文法符号的语义特征 如常量的 值 变量的类型和存储位置等 e g 二义性表达式文法g 非终结符e有属性e val 表达式的值 e e e e e e number属性计算规则 语义规则 与产生式相关联的反映文法符号属性之间关系的 规则 2020 3 1 编译原理与技术 讲义 4 属性文法语法制导定义 文法 属性 语义规则 语义规则仅表明属性间 抽象 关系 不涉及具体翻译实现细节 如计算次序等 翻译方案 文法 属性 语义动作 语义规则 即语义动作 可体现若干实现的细节 2020 3 1 编译原理与技术 讲义 5 e g 1算术表达式的计算器 产生式语法制导定义e e1 e2e val e1 val e2 vale e1 e2e val e1 val e2 vale e1 e val e1 vale numbere val number lex val 2020 3 1 编译原理与技术 讲义 6 e g 1算术表达式的计算器 产生式翻译方案e e1 e2 e val e1 val e2 val e e1 e2 e val e1 val e2 val e e1 e val e1 val e number e val number lex val 2020 3 1 编译原理与技术 讲义 7 属性文法 属性的分类若产生式a x1x2 xn 与之相关的属性计算规则b f c1 c2 如果属性b是产生式左部符号a的属性则称其为a的综合属性 如果属性b是产生式右部符号xi的属性则称其为xi的继承属性 c1 c2 一般是产生式右部其它符号的 综合 属性或a的继承属性 固有属性 终结符仅有的属性 如number lex val 通常由词法程序提供 2020 3 1 编译原理与技术 讲义 8 a b x1 c1 x2 c2 x 综合属性a b的计算 a的继承属性 a x1 c1 x2 c2 继承属性xk b的计算 a的继承属性 xk b x 属性依赖图 2020 3 1 编译原理与技术 讲义 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 2020 3 1 编译原理与技术 讲义 10 语义规则的计算方法 分析树方法 为输入串建立分析树 由语义规则建立属性依赖图 没有属性循环依赖的 对依赖图进行拓扑排序 得到属性计算次序 依次计算属性 得到 翻译 结果基于规则的方法 构造编译器时 事先对产生式的语义规则进行分析 得到属性计算次序忽略规则的方法 属性计算次序仅由分析方法限定 如s 属性定义可以在自下而上分析时 在归约前计算 如yacc中的语义动作 2020 3 1 编译原理与技术 讲义 11 e g 3属性计算次序 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 1 2 3 4 5 6 7 8 2020 3 1 编译原理与技术 讲义 12 s 属性定义 语义规则仅包含综合属性计算 可以有固有属性出现 适合自底向上计算e g 语法树 语法树与分析树语法树可看作分析树的浓缩 也称抽象语法树 而分析树可看成具体语法树 2020 3 1 编译原理与技术 讲义 13 s ifb exprthens1elses2语法树分析树 语法树vs 分析树 if then else b expr s1 s2 s if b expr then s1 else s2 2020 3 1 编译原理与技术 讲义 14 a b c b c语法树分析树 语法树vs 分析树 assign a b c b c assign e e e e e b e e a 赋值语句 c e e b e c 算符 2020 3 1 编译原理与技术 讲义 15 dag 去除了公共子表达式的无环有向图 a b c b c 语法树vs dag assign a b c b c assign a b c 语法树 dag 2020 3 1 编译原理与技术 讲义 16 e g 4构造表达式的语法树 dag 产生式语义规则e e1 e2e nptr mknode e1 nptr e2 nptr e e1 e2e nptr mknode e1 nptr e2 nptr e e1 e2e nptr mknode e1 nptr e2 nptr e e1 e2e nptr mknode e1 nptr e2 nptr e e1 e nptr e1 nptre e1e nptr mknode e1 nptr e numbere nptr mkleaf num number lex val e ide nptr mkleaf id id entry 2020 3 1 编译原理与技术 讲义 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也需检查是否已有相应结点 2020 3 1 编译原理与技术 讲义 18 e g 4构造表达式a b 4的属性结构树 e nptr e nptr e nptr e nptr e nptr a b e nptr 4 2020 3 1 编译原理与技术 讲义 19 e g 4构造表达式a b 4的语法树 dag 2020 3 1 编译原理与技术 讲义 20 l 属性定义 如果产生式a x1x2 xn的语义规则只计算1 a的综合属性 或者2 xi的继承属性 且该属性仅依赖于产生式右部xi的左边符号xj j i 的 综合 属性或a的继承属性 s 属性定义均为l 属性定义 可按深度优先次序计算 一种自然的属性计算次序 在分析期间完成翻译 属性计算与结点建立有联系 适合于自顶向下和自底向上分析方法 2020 3 1 编译原理与技术 讲义 21 深度优先次序 proceduredfvisit n node beginforeachchildmofn fromlefttorightdobeginevaluateinheritedattributesofm dfvisit m end evaluatesynthesizedattributesofn end 2020 3 1 编译原理与技术 讲义 22 e g 5非l 属性定义的语法制导定义 产生式语义规则a lml i l a i m i m l s a s f m s a qrr i r a i q i q r s a s f q s 2020 3 1 编译原理与技术 讲义 23 翻译方案中的动作 语义动作可放在产生式右端任何位置 这也就显式地给出了动作的执行时刻 可认为是在深度优先遍历中的执行时刻 e g 6将含有 和 运算的中缀表达式翻译为后缀形式 e trr addopt print addop lex val r t number print number lex val 2020 3 1 编译原理与技术 讲义 24 e g 6中缀翻译为后缀 9 4 5 e t r 9 print 9 t print r 4 print 4 t print 5 print 5 r 1 2 3 4 5 2020 3 1 编译原理与技术 讲义 25 翻译方案中的动作 设计翻译方案时 必须保证动作所引用的属性值是可用的 只有综合综合属性时 s 属性定义 动作放在产生式末尾 若有继承属性时 动作的放置须保证 产生式右部 符号的继承属性必须在此符号前计算 动作不要引用其右边符号的综合属性 左部非终结符的综合属性一般放在产生式末尾 确保它引用的属性均已计算完且可用 2020 3 1 编译原理与技术 讲义 26 e g 7翻译方案的书写 s a1a2 a1 in 1 a2 in 2 a a print a in 改写为 s a1 in 1 a1 a2 in 2 a2a a print a in 2020 3 1 编译原理与技术 讲义 27 e g 8类型说明的语法制导定义 0 产生式语义规则d tll in t typet intt type integert realt type reall l1 idl1 in l inaddtype id entry l in l idaddtype id entry l in 2020 3 1 编译原理与技术 讲义 28 e g 8类型说明的语法制导定义 0 属性传递 d t l l k l j i int 2020 3 1 编译原理与技术 讲义 29 e g 8类型说明的语法制导定义 1 改写上述类型声明文法 使得其中的t成为l的子结点 即产生式右部 可以避免继承属性的使用 修改后文法如下 d lt intt reall l1 idl tid 2020 3 1 编译原理与技术 讲义 30 e g 8类型说明的语法制导定义 2 产生式语义规则d lt intt type integert realt type reall l1 idl in l1 inaddtype id entry l1 in l tidaddtype id entry t type l in t type 2020 3 1 编译原理与技术 讲义 31 e g 8类型说明的语法制导定义 2 属性传递 d t l l k l j i int 2020 3 1 编译原理与技术 讲义 32 e g 8类型说明的语法制导定义 3 pascal语言类型声明文法如下 d l tt intt reall l1 idl id 该声明文法的 问题 在于 l中声明的变量的类型t处于产生式中l的右边 若用继承属性l in来传递类型信息t type形成非l 属性定义 从而无法在完成l分析同时将有关类型信息填入符号表 可以考虑将t作为l的子结点 通过修改文法 来改变这种情况 2020 3 1 编译原理与技术 讲义 33 e g 8类型说明的语法制导定义 4 产生式语义规则d idladdtype id entry l in t intt type integert realt type reall idl1l in l1 inaddtype id entry l1 in l tl in t type 2020 3 1 编译原理与技术 讲义 34 e g 9翻译方案的计算次序 e e t print 1 e t print 2 t t f print 3 t f print 4 f e print 5 f id print 6 输入串是id id id 时 该翻译方案输出什么 2020 3 1 编译原理与技术 讲义 35 s 属性定义的自底向上计算 拓广分析栈 即添加属性栈 包含文法符号的综合属性 在归约实施前 右部各符号的综合属性 若有的话 已放在与符号位置对应的属性栈上 因此 可以先计算获得左部非终结符的综合属性 然后再归约 这时从分析栈中弹出句柄 注意 此时改变栈顶top即可 最后 将左部符号连同其属性放入由top指示的分析栈及属性栈的位置中 这种属性栈只能存放综合属性 回想yacc中如何做的 2020 3 1 编译原理与技术 讲义 36 如果a xyz 相关语义规则如下 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 句柄长度 1val ntop f val top 2 val top 1 val top 属性栈与分析栈 2020 3 1 编译原理与技术 讲义 37 如果a b 相关语义规则如下 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 属性栈与分析栈 b b b 分析栈 属性栈val top bottom 2020 3 1 编译原理与技术 讲义 38 e g 10计算表达式的 栈 代码 2020 3 1 编译原理与技术 讲义 39 如何在自底向上分析中计算继承属性 属性栈上仅能存放综合属性 能否将继承属性的引用转换成综合属性 分析栈中符号的继承属性 属性copy规则如果 a xy 有语义规则y i x s 翻译方案可写为 a x y i x s y 自底向上计算继承属性 2020 3 1 编译原理与技术 讲义 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 howtouse top 句柄长 2020 3 1 编译原理与技术 讲义 41 e g 11c声明的翻译方案 d t l in t type lt int t type integer t real t type real l l1 in l in l1 id addtype id entry l in l id addtype id entry l in 对于输入串 intp q r分析过程如下 2020 3 1 编译原理与技术 讲义 42 输入串分析栈产生式intp q rp q rintp q rtt int q rtp q rtll idq rtl rtl q rtll l idrtl tl rtll l iddd tl 注意 每次归约成l时 t与l的位置关系 t就在句柄的下面 2020 3 1 编译原理与技术 讲义 43 e g 11c声明的 代码段 产生式代码段 只含综合属性 d tlt intval ntop integert realval ntop reall l1 idaddtype val top val top 3 l idaddtype val top val top 1 l的继承属性l in 2020 3 1 编译原理与技术 讲义 44 问题1 继承属性的位置在构造编译器时不可预知 或不固定 如e g 12产生式语义规则s aacc i a ss babcc i a sc cc s g c i 用c c归约时 c i的值可能在val top 1 或者在val top 2 的位置上 解决办法是考虑将其统一 引入标记非终结符m和产生式m 模拟继承属性的计算 bottom c c a b a a b 分析栈1 分析栈2 top 2020 3 1 编译原理与技术 讲义 45 产生式语义规则s aacc i a ss babmcc i m sm i a sc cc 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 e g 12引入标记非终结符 bottom a m a b a b 分析栈1 分析栈2 top c c 2020 3 1 编译原理与技术 讲义 46 产生式代码段s aacs babmcc cval ntop g val top 1 m val ntop val top 1 可否将m放在s aac产生式中 m i 2020 3 1 编译原理与技术 讲义 47 模拟继承属性的计算 问题2 语义规则不是简单的属性复写拷贝 e g 13 将例12中的s aac语义规则换为 产生式语义规则s aacc i f a s 虽然在例12中引入了m使得 a s 可在val top 1 处找到 但在s的两个产生式中c i的取值方式不同 导致c s的计算嘛 这次可以考虑引入标记非终结符n和n 2020 3 1 编译原理与技术 讲义 48 e g 13引入标记非终结符n 产生式语义规则s aancc i n sn i a sn n s f n i 其他产生式和语义规则不变 代码段略 2020 3 1 编译原理与技术 讲义 49 产生式语义规则s bb ps 10s ht b htb b1b2b1 ps b psb2 ps b psb ht max b1 ht b2 ht b b1subb2b1 ps b psb2 ps shrink b ps b ht disp b1 ht b2 ht b textb ht text h b ps e g 14文字排版的语法制导定义 2020 3 1 编译原理与技术 讲义 50 s s ht 综合属性 待排公式的整体高度b b ps 继承属性 公式 文本 中字体 点 的大小b ht 综合属性 公式排版高度text text h 文本高度max 求两个排版公式的最大高度shrink b 将点大小缩小为b的30 disp b1 ht b2 ht 向下调整b2的位置 文字排版中的符号属性 e 1 val 2020 3 1 编译原理与技术 讲义 51 文字排版的翻译方案 0 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 b1sub b2 ps shrink b ps b2 b ht disp b1 ht b2 ht b text b ht text h b ps 2020 3 1 编译原理与技术 讲义 52 文字排版中引入标记符号 为了自底向上计算 b text b ht text h b ps 必须确定继承属性b ps的 属性栈 位置 为此引入标记非终结符l m和n及其属性 包括相应的空产生式和有关属性规则 这样b ps即可在紧靠 句柄 text下方的位置上找到 l的综合属性置为b ps的初值 s lbb b1mb2b b1subnb2 text text h l l s 10 分析栈 属性栈 top bottom 2020 3 1 编译原理与技术 讲义 53 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 b1sub 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 文字排版的翻译方案 1 2020 3 1 编译原理与技术 讲义 54 产生式代码段s lbval ntop val top b b1mb2val ntop max val top 2 val top b b1subnb2val ntop disp val top 3 val top b textval ntop val top val top 1 l val ntop 10m val ntop val top 1 n val ntop shrink val top 2 2020 3 1 编译原理与技术 讲义 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 返回结果 2020 3 1 编译原理与技术 讲义 56 输入串xy1y2的翻译 x a a f x x a a g f x x y1 y y1 a a g g f x x y1 y y2 y y2 a a x r i f x x y1 r i g f x x y1 y y2 r i g g f x x y1 y y2 y r s r s r s 2020 3 1 编译原理与技术 讲义 57 e g 15删除翻译方案中左递归 e e1 t e nptr mknode e1 nptr t nptr e e1 t e nptr mknode e1 nptr t nptr e t e nptr