语法制导翻译和中间代码生成.ppt

第七讲语法制导翻译和中间代码 7 1属性文法7 2语法制导翻译概论7 3中间代码7 4一些语句的翻译 属性文法 属性文法 attributegrammar 是一个三元组 A G V F F 关于属性的属性断言或谓词集 每个断言与一个产生式相联 而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性 V 有穷的属性集 每个属性与文法的一个终结符或非终结符相连 G 是一个上下文无关文法 表达式文法E T T TorTT n true false E T1 T2 T1 type intANDT2 type T1 typeE type int E T1orT2 T1 type boolANDT2 type T1 typeE type bool T n T type int T true T type bool T false T type bool 类型检查的属性文法 综合属性val 综合属性 在分析树中 如果一个结点的某一个属性由其子结点的属性确定 则称这种属性为该结点的综合属性 产生副作用的语义规则 如打印一个值 向符号表中插入信息或更新一个全程变量等 语义规则函数都不具有副作用的语法制导定义称为属性文法 在语法制导定义中 一条语义规则完成一个计算属性值的动作 digit是终结符 只使用综合属性 且其属性值由词法分析器提供 通常不要计算属性值 如果一个语法制导定义仅仅使用综合属性 则称这种语法制导定义为S属性定义 通常采用自底向上的方法对其分析树加注释 即从树叶到树根 按照语义规则计算每个节点的属性值 继承属性 一个结点的继承属性值是由此结点的父结点和 或兄弟结点的某些属性来决定的 生产式 语义规则 D TL T int T real L L1 id L id L in T type T type integer T type real L1 in L in addtype id entry L in addtype id entry L in 继承属性L in 语句 realid1 id2 id3的分析树 采用自上而下的分析方法 语法制导翻译概论 在语法分析过程中 随着分析的步步进展 根据每个产生式所对应的语义子程序 或语义规则描述的语义动作 进行翻译的办法称作语法制导翻译 参见P 157 159对表达式2 3 5进行的分析 中间代码的形成 中间代码的常见形式 逆波兰记号三元式 树形表示 间接三元式四元式 逆波兰记号 后缀式 将运算对象写在前面 把运算符号写在后面 计算方法 自左向右扫描逆波兰式 遇到运算对象则入栈 遇到算符则将相应数目的运算对象出栈计算后结果入栈 逆波兰记号的扩充用途 复杂性 压栈的可能是地址 如变量赋值 不是值 栈中不一定产生结果 逆波兰示例 把下述产生式定义的算术表达式映射到后缀式表示 E E T E T T T F T F F E F a E ET E T T TF T F F E F a 产生式 翻译成分 确定输入a a a的输出 E E E T ET T T TT F T FT a T aT a T F aTF a F F aFF a a F aaF a a a aaa E E T E T T T F T F F E F a E ET E T T TF T F F E F a 产生式 翻译成分 将下列语句翻译成后缀式 ifx ytheny y zelsex x z 错误的翻译 ifEthenS1elseS2翻译成 ES1S2 x y y z y z x x 三元式和树形表示 格式 算符 第一运算对象 第二运算对象 如 a b c b d 1 b c 2 b d 3 1 2 4 3 a 三元式表示 树形表示 间接三元式 执行表三元式表 例如 x a b cb a by c a b 三元式 a b 1 c 2 x a b 4 b a b c 6 7 y 间接三元式 三元式表执行表 a b 1 1 c 2 2 x 3 1 b 1 2 y 4 1 2 5 四元式 格式 算符 第一运算对象 第二运算对象 结果 如 a b c b d 1 b c t1 2 b d t2 3 t1 t2 t3 4 t3 a 四元式的特点 类似于三地址指令利于优化和代码生成 四元式的直观表示 t1 b ct2 b dt3 t1 t2a t3 jump L gotoL jrop B C L ifBropCgotoL 简单赋值语句的翻译 四元式形式 t arg1oparg2语义属性 id name E place函数 lookup id name 过程 emit t arg1oparg2 newtemp 返回指向id的指针 输出四元式 生成临时变量 E place 值E的位置 产生式和语义描述 1 S id E P lookup id name ifP nilthenemit P E place elseerror 2 E E1 E2 E place newtemp emit E place E1 place E2 place 3 E E1 E2 E place newtemp emit E place E1 place E2 place 返回 4 E E1 E place newtemp emit E place uminus E1 place 5 E E1 E place E1 place 6 E id P lookup id name ifP nilthenE place Pelseerror 返回 例 将下列语句翻译成四元式形式 A B C D A B C D 查看语意义子程序1 3 查看语意义子程序4 6 栈余留输入字符语意义动作产生的四元式 idA B C D idA B C D idA B C D idA idB C D idA EB C D Sub6 idA ET1 C D Sub4 B T1 idA ET1 C D idA ET1 C D idA ET1 idC D idA ET1 EC D Sub6 idA ET1 EC D 查看语意义子程序1 3 查看语意义子程序4 6 栈余留输入字符语意义动作产生的四元式 idA ET1 EC D idA ET1 EC idD idA ET1 EC ED Sub6 idA ET1 ET2 Sub2 C D T2 idA ET1 ET2 idA ET1 ET2 Sub5 idA ET3 Sub3 T1 T2 T3 S Sub1 T3 A 语句A B C D 翻译成四元式形式为 1 B T1 2 C D T2 3 T1 T2 T3 4 T3 A 类型转换的语义处理 E E1 E2 E place newtemp ifE1 type intANDE2 type intthenBeginemit E place E1 place i E2 place E type int EndelseifE1 type realANDE2 type realthenBeginemit E place E1 place r E2 place E type real EndelseifE1 type int E2 type real thenBegint newtemp emit t irt E1 place emit E place t r E2 place E type real Endelse E1 type realANDE2 type int Begint newtemp emit t irt E2 place emit E place E1 place r t E type real End E false 控制语句中布尔表达式的翻译 控制语句 S ifEthenS 1 elseS 2 E 的代码 E true E true S 1 的代码 gotoout E false S 2 的代码 out 语义描述使用的变量和过程 E true 真 链 E false 假 链 E codebegin E 的第一个四元式 Nextstat 下一四元式地址 过程 emit 输出一条四元式 merge p1 p2 把 p1 的链头填在 p2 的链尾 例 merge p1 p2 p10 0 p1 链 p 10 0 p10 p1 p100 p20 0 p2 链 p200 p20 p2 p200 backpatch p t 把 p 所链接的每个四元式 的第四区段都填为 t 语义描述使用的变量和过程 E true 真 链 E false 假 链 E codebegin E 的第一个四元式 Nextstat 下一四元式地址 过程 emit 输出一条四元式 merge p1 p2 把 p1 的链头填在 p2 的链尾 例 merge p1 p2 p10 0 p1 链 p 10 0 p10 p1 p100 p20 p100 p2 链 p200 p20 p2 p200 backpatch p t 把 p 所链接的每个四元式 的第四区段都填为 t 自下而上分析中的一种翻译方案 1 E E 1 orE 2 backpatch E 1 false E 2 Codebegin E Codebegin E 1 codebegin E true merge E 1 true E 2 true E false E