教学课件第二章简单的一遍编译器

1、1/35v概述v语法制导翻译技术 语法定义 语法制导翻译：语法制导定义/翻译模式 语法分析v实例：一个简单表达式的翻译器（下次）2/35v如何描述程序语言？词法+语法+语义+语用 程序模式：语法v比较容易描述v上下文无关文法或bnf 程序含义：语义v比较难以描述v非形式化方法、启发性实例3/35v任务：表达式计算 编译器前端：中缀表达式=后缀表达式v例：9+5-2 =95+2-v编译器前端结构 图2-1 词法分析器：字符流=符号流 语法制导翻译器：记号流=中间表示v语法分析器+中间代码生成器v语法制导翻译技术：面向语法的翻译技术 编译器后端：后缀表达式=机器代码v堆栈v例： 用堆栈计算95+2

2、-4/35v概述v语法制导翻译技术 语法定义语法定义 语法制导翻译：语法制导定义/翻译模式 语法分析5/35v上下文无关文法：定义 产生式集合v例：产生式stmt - if (expr) stmt else stmt 终结符集合：记号集合v例：终结符/记号：if、else 由词法分析器产生：字符串=记号流 非终结符集合：表示记号序列v例：非终结符stmt、expr 开始非终结符6/35v上下文无关文法：实例 例2.1：由数字、加号和减号组成的表达式vlist - list + digit | list digit | digitvdigit - 0 | 1 | 2 | 3 | 4 | 5 |

3、6 | 7 | 8 | 97/35v上下文无关文法：实例 例2.3：pascal的begin-end语句块vblock - begin opt_stmts endvopt_stmts - stmt_list | vstmt_list - stmt_list ; stmt | stmt8/35v分析树：定义 树根节点为开始非终结符 每个叶节点由一个终结符（记号）或标记 每个内节点由一个非终结符标记 如果a是某个内节点的，x1、x2xn是该节点的从左到右的所有子节点的标记（终结符或非终结符），则a -x1x2xn是一个产生式。9/35v分析树：实例 例2.4： 9+5-2 =分析树（图2-2） 分

4、析树生成的结果v一颗分析树从左到右的叶节点v由树根节点的开始非终结符生成或导出的串10/35v几个概念 语言（文法）：文法的分析树导出的串的集合 语法分析：记号串=句法树（语法树）v同自然语言的句法分析：i love this game .11/35v文法的二义性 一个记号串对应几个不同的句法树 例2.5：9-5+2 =(9-5)+2 | 9-(5+2) ？（图2-3） v文法 string - string + string | string string string - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 例：i saw a dog with a

5、telescope .va dog with a telescopevsaw with a telescope12/35v上下文无关文法的应用 定义语言的语法v表达式的语法v语句的语法 指导源程序的翻译v语法制导翻译技术13/35v表达式的语法：操作符的结合性和优先级 操作符的结合规则v左结合（如加减乘除）：操作数与左操作符结合 left - left + digit | left digit | digit digit - 0 | 1 | 9 例：9-5+2 =（9-5）+214/35v表达式的语法:操作符的结合性和优先级 操作符的结合规则（续）v右结合： ：操作数与右操作符结合 指数运算符

6、：423 = 4(23) 运算操作符：a=b=c = a=(b=c) right - letter = right | letter right | letter letter - a | b | zv例：图2-415/35v表达式的语法：操作符的结合性和优先级 操作符的优先级v例：9+5*2 =（9+5）*2 | 9+（5*2）？v括号、乘除、加减16/35v表达式的语法：如何运用操作符两原则 先优先级高的后优先级低的 左结合vs右结合 例：左结合（page 21） 例：右结合（课堂练习）17/35v语句的语法：例page 22 stmt - id := expr| if expr then

7、 stmt| if expr then stmt else stmt| while expr do stmt| begin opt_stmts end18/35v概述v语法制导翻译技术 语法定义 语法制导翻译：语法制导定义/翻译模式 语法分析19/35v表达式e的后缀表示 如果e是一个变量或者常量，则e的后缀是e本身 如果e是形如e1 op e2的表达式，其中op是一个二元操作符，则e的后缀表示是e1e2op，这里e1和e2分别是e1和e2的后缀表示 如果e是形如（e1）的表达式，则e的后缀表示就是e1的后缀表示v实例 表达式(9-5)+2的后缀表示是95-2+ 表达式9-(5+2)的后缀表示

8、是952+-20/35v程序设计语言结构的翻译 生成代码 保存相关的任意信息：属性v结构类型v目标代码中第一指令的位置v生成的指令个数v属性：对应于分析树的某个节点 综合属性（本章）v由其子节点的属性值确定v一刻分析树的所有综合属性值的计算只需要分析树的一次自底向上遍历 继承属性（第五章）21/35v两种翻译技术 语法制导定义v一种形式化方法：各种结构的翻译v根据与其语义部分相关联的属性说明一个结构的翻译 翻译模式v一种过程化方法22/35v语法制导定义 例2.6：使用语法制导定义实现中缀=后缀v中缀=后缀的语法制导定义 图2-5v分析树各节点的属性值 图2-6 上下文无关文法规则+语义规则v

9、每个文法符号和一个属性集合相关联：文法符号expr与属性t相关联（t是文法符号expr 产生的表达式的后缀表示）v每一个产生式和一个语义规则集合相关联：产生式expr - expr1 + term 与语义规则expr.t := expr1.t | term.t | +相关联v语义规则用来计算与产生式中出现的文法符号相关联的属性的值：如：语义规则expr.t := expr1.t | term.t | +通过连接expr1.t 、term.t 和 +产生expr.t 的值23/35v语法制导定义 例2.7：使用语法制导定义机器人位置计算v机器人位置的跟踪 图2-7v机器人位置的语法制导定义 图2

10、-9vbegin west south的注释分析树 图2-824/35v语法制导定义 分析树中综合属性的计算顺序 自底向上遍历：深度优先遍历v尽可能访问一个节点未访问的子节点v例图2-1125/35v翻译模式 一个上下文无关文法v语义动作嵌入产生式右部 前缀变中缀产生式rest - + term print (+) rest126/35v翻译模式 对比：语法指导定义v语义动作和产生式分开，语义规则的计算顺序显式给出v简单语法指导定义：可以用（简单）翻译模式实现 每个产生式左部的非终结符的翻译是将产生式右部的非终结符的翻译按照他们在右部出现的顺序连接起来得到的 在连接过程中可能还需要附加（也可能

11、不需要）一些额外的串。v产生式：expr-expr1+termv语义规则：expr.t := expr1.t | term.t | +27/35v翻译模式 例2.8：使用翻译模式实现中缀=后缀v图2-13 ：中缀变后缀的翻译模式v图2-14：9-5+2 =95-2+的语义动作（即9-5+2对应的句法树）v在简单翻译模式中，语义动作也是按照从左到右的顺序执行的，可以在语法分析的时候执行语义动作，完全没有必要构造分析树。28/35v概述v语法制导翻译技术 语法定义 语法制导翻译：语法制导定义/翻译模式 语法分析语法分析29/35v功能：记号串=分析树 决定一个记号串是否合乎一个给定文法=能否由给定

12、文法产生=能否产生一个合乎给定文法的分析树v语法分析方法分类 自顶向下语法分析自顶向下语法分析v从根节点到叶节点的顺序构造分析树v常用于手工构建语法分析器 自底向上语法分析v可以处理大量文法和翻译模式v常用于直接从文法生成语法分析器的软件工具30/35v自顶向下语法分析 如何自顶向下构造一个分析树？从标有开始非终结符的根节点开始，反复执行下面两步v从标有非终结符a的节点n，选择a的一个产生式，用该产生式右部的符号构造节点n的子节点v寻找下一个要构造子树的节点 图2-15：使用自顶向下方法构造分析树 图2-16：从左到右扫描输入串时的自顶向下语法分析 问题：回溯（产生式选择不合适）31/35v预

13、测分析法 递归下降分析法：自顶向下v执行一组递归过程来处理输入串，每一个过程都唯一地与文法的一个过程相关联 预测分析法：一种特殊的递归下降分析法v超前扫描符号无二义v依赖于产生式右部产生的第一个符号是什么v若a-a, a-b, 则first(a) 和first(b)不相交 图2-17：预测语法分析器的伪代码32/35v预测语法分析器 由多个过程组成，每个过程对应一个非终结符v检查超前扫描符号，决定使用哪个产生式：产生式右部不存在冲突v过程通过模仿其右部来使用一个产生式 非终结符：对应过程被调用 记号：若与超前扫描符号匹配，读入下一个输入记号，否则报告出错33/35v语法分析器+语义动作=语法指导翻译器 文法+语义动作(分开)=语法制导定义 文法+语义动作(合并)=翻译模式v扩展预测语法分析器构建语法制导翻译器：类似于扩展文法形成翻译模式 构造一个预测语法分析器，忽略产生式中的语义动作。 把翻译模式中的语义动作拷贝到语法分析器，插入相应位置。34/35v左递归问题 递归下降语法分析器（如预测语