《861-第二章：简单的一遍编译器.ppt》由会员分享，可在线阅读，更多相关《861-第二章：简单的一遍编译器.ppt（35页珍藏版）》请在三一文库上搜索。
1、1/35,第二章：简单的一遍编译器,概述 语法制导翻译技术 语法定义 语法制导翻译：语法制导定义/翻译模式 语法分析 实例：一个简单表达式的翻译器（下次）,2/35,第二章：简单的一遍编译器：概述,如何描述程序语言？词法+语法+语义+语用 程序模式：语法 比较容易描述 上下文无关文法或BNF 程序含义：语义 比较难以描述 非形式化方法、启发性实例,3/35,第二章：简单的一遍编译器：概述,任务：表达式计算 编译器前端：中缀表达式=后缀表达式 例：9+5-2 =95+2- 编译器前端结构 图2-1 词法分析器：字符流=符号流 语法制导翻译器：记号流=中间表示 语法分析器+中间代码生成器 语法制导
2、翻译技术：面向语法的翻译技术 编译器后端：后缀表达式=机器代码 堆栈 例： 用堆栈计算95+2-,4/35,第二章：简单的一遍编译器,概述 语法制导翻译技术 语法定义 语法制导翻译：语法制导定义/翻译模式 语法分析,5/35,第二章：简单的一遍编译器：语法定义,上下文无关文法：定义 产生式集合 例：产生式stmt - if (expr) stmt else stmt 终结符集合：记号集合 例：终结符/记号：if、else 由词法分析器产生：字符串=记号流 非终结符集合：表示记号序列 例：非终结符stmt、expr 开始非终结符,6/35,第二章：简单的一遍编译器：语法定义,上下文无关文法：实例
3、 例2.1：由数字、加号和减号组成的表达式 list - list + digit | list digit | digit digit - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,7/35,第二章：简单的一遍编译器：语法定义,上下文无关文法：实例 例2.3：PASCAL的begin-end语句块 block - begin opt_stmts end opt_stmts - stmt_list | stmt_list - stmt_list ; stmt | stmt,8/35,第二章：简单的一遍编译器：语法定义,分析树：定义 树根节点为开始非终结符 每个
4、叶节点由一个终结符（记号）或标记 每个内节点由一个非终结符标记 如果A是某个内节点的，X1、X2Xn是该节点的从左到右的所有子节点的标记（终结符或非终结符），则A -X1X2Xn是一个产生式。,9/35,第二章：简单的一遍编译器：语法定义,分析树：实例 例2.4： 9+5-2 =分析树（图2-2） 分析树生成的结果 一颗分析树从左到右的叶节点 由树根节点的开始非终结符生成或导出的串,10/35,第二章：简单的一遍编译器：语法定义,几个概念 语言（文法）：文法的分析树导出的串的集合 语法分析：记号串=句法树（语法树） 同自然语言的句法分析：I love this game .,11/35,第二章
5、：简单的一遍编译器：语法定义,文法的二义性 一个记号串对应几个不同的句法树 例2.5：9-5+2 =(9-5)+2 | 9-(5+2) ？（图2-3） 文法 string - string + string | string string string - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 例：I saw a dog with a telescope . a dog with a telescope saw with a telescope,12/35,第二章：简单的一遍编译器：语法定义,上下文无关文法的应用 定义语言的语法 表达式的语法 语句的语法
6、指导源程序的翻译 语法制导翻译技术,13/35,第二章：简单的一遍编译器：语法定义,表达式的语法：操作符的结合性和优先级 操作符的结合规则 左结合（如加减乘除）：操作数与左操作符结合 Left - Left + Digit | Left Digit | Digit Digit - 0 | 1 | 9 例：9-5+2 =（9-5）+2,14/35,第二章：简单的一遍编译器：语法定义,表达式的语法:操作符的结合性和优先级 操作符的结合规则（续） 右结合： ：操作数与右操作符结合 指数运算符：423 = 4(23) 运算操作符：a=b=c = a=(b=c) Right - Letter = Rig
7、ht | Letter Right | Letter Letter - a | b | z 例：图2-4,15/35,第二章：简单的一遍编译器：语法定义,表达式的语法：操作符的结合性和优先级 操作符的优先级 例：9+5*2 =（9+5）*2 | 9+（5*2）？ 括号、乘除、加减,16/35,第二章：简单的一遍编译器：语法定义,表达式的语法：如何运用操作符两原则 先优先级高的后优先级低的 左结合vs右结合 例：左结合（Page 21） 例：右结合（课堂练习）,17/35,第二章：简单的一遍编译器：语法定义,语句的语法：例Page 22 Stmt - id := expr | if expr t
8、hen stmt | if expr then stmt else stmt | while expr do stmt | begin opt_stmts end,18/35,第二章：简单的一遍编译器,概述 语法制导翻译技术 语法定义 语法制导翻译：语法制导定义/翻译模式 语法分析,19/35,第二章：简单的一遍编译器：语法制导翻译,表达式E的后缀表示 如果E是一个变量或者常量，则E的后缀是E本身 如果E是形如E1 op E2的表达式，其中op是一个二元操作符，则E的后缀表示是E1E2op，这里E1和E2分别是E1和E2的后缀表示 如果E是形如（E1）的表达式，则E的后缀表示就是E1的后缀表示
9、 实例 表达式(9-5)+2的后缀表示是95-2+ 表达式9-(5+2)的后缀表示是952+-,20/35,第二章：简单的一遍编译器：语法制导翻译,程序设计语言结构的翻译 生成代码 保存相关的任意信息：属性 结构类型 目标代码中第一指令的位置 生成的指令个数 属性：对应于分析树的某个节点 综合属性（本章） 由其子节点的属性值确定 一刻分析树的所有综合属性值的计算只需要分析树的一次自底向上遍历 继承属性（第五章）,21/35,第二章：简单的一遍编译器：语法制导翻译,两种翻译技术 语法制导定义 一种形式化方法：各种结构的翻译 根据与其语义部分相关联的属性说明一个结构的翻译 翻译模式 一种过程化方法
10、,22/35,第二章：简单的一遍编译器：语法制导翻译,语法制导定义 例2.6：使用语法制导定义实现中缀=后缀 中缀=后缀的语法制导定义 图2-5 分析树各节点的属性值 图2-6 上下文无关文法规则+语义规则 每个文法符号和一个属性集合相关联：文法符号expr与属性t相关联（t是文法符号expr 产生的表达式的后缀表示） 每一个产生式和一个语义规则集合相关联：产生式expr - expr1 + term 与语义规则expr.t := expr1.t | term.t | +相关联 语义规则用来计算与产生式中出现的文法符号相关联的属性的值：如：语义规则expr.t := expr1.t | ter
11、m.t | +通过连接expr1.t 、term.t 和 +产生expr.t 的值,23/35,第二章：简单的一遍编译器：语法制导翻译,语法制导定义 例2.7：使用语法制导定义机器人位置计算 机器人位置的跟踪 图2-7 机器人位置的语法制导定义 图2-9 Begin West South的注释分析树 图2-8,24/35,第二章：简单的一遍编译器：语法制导翻译,语法制导定义 分析树中综合属性的计算顺序 自底向上遍历：深度优先遍历 尽可能访问一个节点未访问的子节点 例图2-11,25/35,第二章：简单的一遍编译器：语法制导翻译,翻译模式 一个上下文无关文法 语义动作嵌入产生式右部 前缀变中缀产
12、生式rest - + term print (+) rest1,26/35,第二章：简单的一遍编译器：语法制导翻译,翻译模式 对比：语法指导定义 语义动作和产生式分开，语义规则的计算顺序显式给出 简单语法指导定义：可以用（简单）翻译模式实现 每个产生式左部的非终结符的翻译是将产生式右部的非终结符的翻译按照他们在右部出现的顺序连接起来得到的 在连接过程中可能还需要附加（也可能不需要）一些额外的串。 产生式：expr-expr1+term 语义规则：expr.t := expr1.t | term.t | +,27/35,第二章：简单的一遍编译器：语法制导翻译,翻译模式 例2.8：使用翻译模式实现
13、中缀=后缀 图2-13 ：中缀变后缀的翻译模式 图2-14：9-5+2 =95-2+的语义动作（即9-5+2对应的句法树） 在简单翻译模式中，语义动作也是按照从左到右的顺序执行的，可以在语法分析的时候执行语义动作，完全没有必要构造分析树。,28/35,第二章：简单的一遍编译器,概述 语法制导翻译技术 语法定义 语法制导翻译：语法制导定义/翻译模式 语法分析,29/35,第二章：简单的一遍编译器：语法分析,功能：记号串=分析树 决定一个记号串是否合乎一个给定文法=能否由给定文法产生=能否产生一个合乎给定文法的分析树 语法分析方法分类 自顶向下语法分析 从根节点到叶节点的顺序构造分析树 常用于手工
14、构建语法分析器 自底向上语法分析 可以处理大量文法和翻译模式 常用于直接从文法生成语法分析器的软件工具,30/35,第二章：简单的一遍编译器：语法分析,自顶向下语法分析 如何自顶向下构造一个分析树？从标有开始非终结符的根节点开始，反复执行下面两步 从标有非终结符A的节点n，选择A的一个产生式，用该产生式右部的符号构造节点n的子节点 寻找下一个要构造子树的节点 图2-15：使用自顶向下方法构造分析树 图2-16：从左到右扫描输入串时的自顶向下语法分析 问题：回溯（产生式选择不合适）,31/35,第二章：简单的一遍编译器：语法分析,预测分析法 递归下降分析法：自顶向下 执行一组递归过程来处理输入串
15、，每一个过程都唯一地与文法的一个过程相关联 预测分析法：一种特殊的递归下降分析法 超前扫描符号无二义 依赖于产生式右部产生的第一个符号是什么 若A-a, A-b, 则First(a) 和First(b)不相交 图2-17：预测语法分析器的伪代码,32/35,第二章：简单的一遍编译器：语法分析,预测语法分析器 由多个过程组成，每个过程对应一个非终结符 检查超前扫描符号，决定使用哪个产生式：产生式右部不存在冲突 过程通过模仿其右部来使用一个产生式 非终结符：对应过程被调用 记号：若与超前扫描符号匹配，读入下一个输入记号，否则报告出错,33/35,第二章：简单的一遍编译器：语法分析,语法分析器+语义
16、动作=语法指导翻译器 文法+语义动作(分开)=语法制导定义 文法+语义动作(合并)=翻译模式 扩展预测语法分析器构建语法制导翻译器：类似于扩展文法形成翻译模式 构造一个预测语法分析器，忽略产生式中的语义动作。 把翻译模式中的语义动作拷贝到语法分析器，插入相应位置。,34/35,第二章：简单的一遍编译器：语法分析,左递归问题 递归下降语法分析器（如预测语法分析器）分析一个左递归产生式时，会产生无限循环 expr - expr + term | term,35/35,第二章：简单的一遍编译器：语法分析,左递归问题 需要消除：转换成右递归？ expr - term + R R - + term R | ：默认产生式 没有其他产生式可用的时候用 stmt - begin opt_stmts end opt_stmt - stmt_list | 第四章将讨论更一般的左递归形式，并讨论如何从一个文法中消除所有左递归。,