2.1-第二章：简单的一遍编译器ppt课件

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

2、编译器后端：后缀表达式=机器代码v堆栈v例： 用堆栈计算95+2-4第二章：简单的一遍编译器v概述v语法制导翻译技术v语法定义v语法制导翻译：语法制导定义/翻译模式v语法分析5第二章：简单的一遍编译器：语法定义v上下文无关文法：定义v产生式集合v例：产生式stmt - if (expr) stmt else stmtv终结符集合：记号集合v例：终结符/记号：if、elsev由词法分析器产生：字符串=记号流v非终结符集合：表示记号序列v例：非终结符stmt、exprv开始非终结符6第二章：简单的一遍编译器：语法定义v上下文无关文法：实例v例2.1：由数字、加号和减号组成的表达式vlist - l

3、ist + digit | list digit | digitvdigit - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 97第二章：简单的一遍编译器：语法定义v上下文无关文法：实例v例2.3：PASCAL的begin-end语句块vblock - begin opt_stmts endvopt_stmts - stmt_list | vstmt_list - stmt_list ; stmt | stmt8第二章：简单的一遍编译器：语法定义v分析树：定义v树根节点为开始非终结符v每个叶节点由一个终结符记号或标记v每个内节点由一个非终结符标记v如果A是某个内节点

4、的，X1、X2Xn是该节点的从左到右的所有子节点的标记终结符或非终结符），则A -X1X2Xn是一个产生式。9第二章：简单的一遍编译器：语法定义v分析树：实例v例2.4： 9+5-2 =分析树图2-2）v分析树生成的结果v一颗分析树从左到右的叶节点v由树根节点的开始非终结符生成或导出的串10第二章：简单的一遍编译器：语法定义v几个概念v语言文法）：文法的分析树导出的串的集合v语法分析：记号串=句法树语法树）v同自然语言的句法分析：I love this game .11第二章：简单的一遍编译器：语法定义v文法的二义性v一个记号串对应几个不同的句法树v例2.5：9-5+2 =(9-5)+2 |

5、9-(5+2) ？（图2-3） v文法vstring - string + string | string string vstring - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9v例：I saw a dog with a telescope .va dog with a telescopevsaw with a telescope12第二章：简单的一遍编译器：语法定义v上下文无关文法的应用v定义语言的语法v表达式的语法v语句的语法v指导源程序的翻译v语法制导翻译技术13第二章：简单的一遍编译器：语法定义v表达式的语法：操作符的结合性和优先级v操作符的结合规

6、则v左结合如加减乘除）：操作数与左操作符结合vLeft - Left + Digit | Left Digit | Digitv Digit - 0 | 1 | 9v例：9-5+2 =（9-5）+214第二章：简单的一遍编译器：语法定义v表达式的语法:操作符的结合性和优先级v操作符的结合规则续）v右结合： ：操作数与右操作符结合v指数运算符：423 = 4(23)v运算操作符：a=b=c = a=(b=c)vRight - Letter = Right | Letter Right | LettervLetter - a | b | zv例：图2-415第二章：简单的一遍编译器：语法定义v表达

7、式的语法：操作符的结合性和优先级v操作符的优先级v例：9+5*2 =（9+5）*2 | 9+（5*2）？v括号、乘除、加减16第二章：简单的一遍编译器：语法定义v表达式的语法：如何运用操作符两原则v先优先级高的后优先级低的v左结合vs右结合v例：左结合Page 21）v例：右结合课堂练习）17第二章：简单的一遍编译器：语法定义v语句的语法：例Page 22v Stmt - id := exprv| if expr then stmtv| if expr then stmt else stmtv| while expr do stmtv| begin opt_stmts end18第二章：简单的

8、一遍编译器v概述v语法制导翻译技术v语法定义v语法制导翻译：语法制导定义/翻译模式v语法分析19第二章：简单的一遍编译器：语法制导翻译v表达式E的后缀表示v如果E是一个变量或者常量，则E的后缀是E本身v如果E是形如E1 op E2的表达式，其中op是一个二元操作符，则E的后缀表示是E1E2op，这里E1和E2分别是E1和E2的后缀表示v如果E是形如E1的表达式，则E的后缀表示就是E1的后缀表示v实例v表达式(9-5)+2的后缀表示是95-2+v表达式9-(5+2)的后缀表示是952+-20第二章：简单的一遍编译器：语法制导翻译v程序设计语言结构的翻译v生成代码v保存相关的任意信息：属性v结构类

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

10、联：文法符号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第二章：简单的一遍编译器：语法制导翻译v语法制导定义v例2.7：使用语法制导定义机器人位置计算v机器人位置的跟踪 图2-7v机器人位置的语法制导定义 图2

11、-9vBegin West South的注释分析树 图2-824第二章：简单的一遍编译器：语法制导翻译v语法制导定义v分析树中综合属性的计算顺序v自底向上遍历：深度优先遍历v尽可能访问一个节点未访问的子节点v例图2-1125第二章：简单的一遍编译器：语法制导翻译v翻译模式v一个上下文无关文法v语义动作嵌入产生式右部v前缀变中缀产生式rest - + term print (+) rest126第二章：简单的一遍编译器：语法制导翻译v翻译模式v对比：语法指导定义v语义动作和产生式分开，语义规则的计算顺序显式给出v简单语法指导定义：可以用简单翻译模式实现v每个产生式左部的非终结符的翻译是将产生式右

12、部的非终结符的翻译按照他们在右部出现的顺序连接起来得到的v在连接过程中可能还需要附加也可能不需要一些额外的串。v产生式：expr-expr1+termv语义规则：expr.t := expr1.t | term.t | +27第二章：简单的一遍编译器：语法制导翻译v翻译模式v例2.8：使用翻译模式实现中缀=后缀v图2-13 ：中缀变后缀的翻译模式v图2-14：9-5+2 =95-2+的语义动作即9-5+2对应的句法树）v在简单翻译模式中，语义动作也是按照从左到右的顺序执行的，可以在语法分析的时候执行语义动作，完全没有必要构造分析树。28第二章：简单的一遍编译器v概述v语法制导翻译技术v语法定义

13、v语法制导翻译：语法制导定义/翻译模式v语法分析29第二章：简单的一遍编译器：语法分析v功能：记号串=分析树v决定一个记号串是否合乎一个给定文法=能否由给定文法产生=能否产生一个合乎给定文法的分析树v语法分析方法分类v自顶向下语法分析v从根节点到叶节点的顺序构造分析树v常用于手工构建语法分析器v自底向上语法分析v可以处理大量文法和翻译模式v常用于直接从文法生成语法分析器的软件工具30第二章：简单的一遍编译器：语法分析v自顶向下语法分析v如何自顶向下构造一个分析树？从标有开始非终结符的根节点开始，反复执行下面两步v从标有非终结符A的节点n，选择A的一个产生式，用该产生式右部的符号构造节点n的子节

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