861第二章：简单的一遍编译器

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