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

《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,第二章：简单的一遍编译器：语法定义,上下文无关文法：实例例2.1：由数字、加号和减号组成的表达式list-list+digit|lis

3、t digit|digitdigit-0|1|2|3|4|5|6|7|8|9,7/35,第二章：简单的一遍编译器：语法定义,上下文无关文法：实例例2.3：PASCAL的begin-end语句块block-begin opt_stmts endopt_stmts-stmt_list|stmt_list-stmt_list;stmt|stmt,8/35,第二章：简单的一遍编译器：语法定义,分析树：定义树根节点为开始非终结符每个叶节点由一个终结符（记号）或标记每个内节点由一个非终结符标记如果A是某个内节点的，X1、X2Xn是该节点的从左到右的所有子节点的标记（终结符或非终结符），则A-X1X2Xn是

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

5、tring string-0|1|2|3|4|5|6|7|8|9例：I saw a dog with a telescope.a dog with a telescopesaw with a telescope,12/35,第二章：简单的一遍编译器：语法定义,上下文无关文法的应用定义语言的语法表达式的语法语句的语法指导源程序的翻译语法制导翻译技术,13/35,第二章：简单的一遍编译器：语法定义,表达式的语法：操作符的结合性和优先级操作符的结合规则左结合（如加减乘除）：操作数与左操作符结合Left-Left+Digit|Left Digit|Digit Digit-0|1|9例：9-5+2=（9

6、-5）+2,14/35,第二章：简单的一遍编译器：语法定义,表达式的语法:操作符的结合性和优先级操作符的结合规则（续）右结合：操作数与右操作符结合指数运算符：423=4(23)运算操作符：a=b=c=a=(b=c)Right-Letter=Right|Letter Right|LetterLetter-a|b|z例：图2-4,15/35,第二章：简单的一遍编译器：语法定义,表达式的语法：操作符的结合性和优先级操作符的优先级例：9+5*2=（9+5）*2|9+（5*2）？括号、乘除、加减,16/35,第二章：简单的一遍编译器：语法定义,表达式的语法：如何运用操作符两原则先优先级高的后优先级低的左

7、结合vs右结合例：左结合（Page 21）例：右结合（课堂练习）,17/35,第二章：简单的一遍编译器：语法定义,语句的语法：例Page 22 Stmt-id:=expr|if expr then 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的表

8、达式，其中op是一个二元操作符，则E的后缀表示是E1E2op，这里E1和E2分别是E1和E2的后缀表示如果E是形如（E1）的表达式，则E的后缀表示就是E1的后缀表示实例表达式(9-5)+2的后缀表示是95-2+表达式9-(5+2)的后缀表示是952+-,20/35,第二章：简单的一遍编译器：语法制导翻译,程序设计语言结构的翻译生成代码保存相关的任意信息：属性结构类型目标代码中第一指令的位置生成的指令个数属性：对应于分析树的某个节点综合属性（本章）由其子节点的属性值确定一刻分析树的所有综合属性值的计算只需要分析树的一次自底向上遍历继承属性（第五章）,21/35,第二章：简单的一遍编译器：语法制导

9、翻译,两种翻译技术语法制导定义一种形式化方法：各种结构的翻译根据与其语义部分相关联的属性说明一个结构的翻译翻译模式一种过程化方法,22/35,第二章：简单的一遍编译器：语法制导翻译,语法制导定义例2.6：使用语法制导定义实现中缀=后缀中缀=后缀的语法制导定义 图2-5分析树各节点的属性值 图2-6上下文无关文法规则+语义规则每个文法符号和一个属性集合相关联：文法符号expr与属性t相关联（t是文法符号expr 产生的表达式的后缀表示）每一个产生式和一个语义规则集合相关联：产生式expr-expr1+term 与语义规则expr.t:=expr1.t|term.t|+相关联语义规则用来计算与产生

10、式中出现的文法符号相关联的属性的值：如：语义规则expr.t:=expr1.t|term.t|+通过连接expr1.t、term.t 和+产生expr.t 的值,23/35,第二章：简单的一遍编译器：语法制导翻译,语法制导定义例2.7：使用语法制导定义机器人位置计算机器人位置的跟踪 图2-7机器人位置的语法制导定义 图2-9Begin West South的注释分析树 图2-8,24/35,第二章：简单的一遍编译器：语法制导翻译,语法制导定义分析树中综合属性的计算顺序自底向上遍历：深度优先遍历尽可能访问一个节点未访问的子节点例图2-11,25/35,第二章：简单的一遍编译器：语法制导翻译,翻译

11、模式一个上下文无关文法语义动作嵌入产生式右部前缀变中缀产生式rest-+term print(+)rest1,26/35,第二章：简单的一遍编译器：语法制导翻译,翻译模式对比：语法指导定义语义动作和产生式分开，语义规则的计算顺序显式给出简单语法指导定义：可以用（简单）翻译模式实现每个产生式左部的非终结符的翻译是将产生式右部的非终结符的翻译按照他们在右部出现的顺序连接起来得到的在连接过程中可能还需要附加（也可能不需要）一些额外的串。产生式：expr-expr1+term语义规则：expr.t:=expr1.t|term.t|+,27/35,第二章：简单的一遍编译器：语法制导翻译,翻译模式例2.8

12、：使用翻译模式实现中缀=后缀图2-13：中缀变后缀的翻译模式图2-14：9-5+2=95-2+的语义动作（即9-5+2对应的句法树）在简单翻译模式中，语义动作也是按照从左到右的顺序执行的，可以在语法分析的时候执行语义动作，完全没有必要构造分析树。,28/35,第二章：简单的一遍编译器,概述语法制导翻译技术语法定义语法制导翻译：语法制导定义/翻译模式语法分析,29/35,第二章：简单的一遍编译器：语法分析,功能：记号串=分析树决定一个记号串是否合乎一个给定文法=能否由给定文法产生=能否产生一个合乎给定文法的分析树语法分析方法分类自顶向下语法分析从根节点到叶节点的顺序构造分析树常用于手工构建语法分

13、析器自底向上语法分析可以处理大量文法和翻译模式常用于直接从文法生成语法分析器的软件工具,30/35,第二章：简单的一遍编译器：语法分析,自顶向下语法分析如何自顶向下构造一个分析树？从标有开始非终结符的根节点开始，反复执行下面两步从标有非终结符A的节点n，选择A的一个产生式，用该产生式右部的符号构造节点n的子节点寻找下一个要构造子树的节点图2-15：使用自顶向下方法构造分析树图2-16：从左到右扫描输入串时的自顶向下语法分析问题：回溯（产生式选择不合适）,31/35,第二章：简单的一遍编译器：语法分析,预测分析法递归下降分析法：自顶向下执行一组递归过程来处理输入串，每一个过程都唯一地与文法的一个

14、过程相关联预测分析法：一种特殊的递归下降分析法超前扫描符号无二义依赖于产生式右部产生的第一个符号是什么若A-a,A-b,则First(a)和First(b)不相交图2-17：预测语法分析器的伪代码,32/35,第二章：简单的一遍编译器：语法分析,预测语法分析器由多个过程组成，每个过程对应一个非终结符检查超前扫描符号，决定使用哪个产生式：产生式右部不存在冲突过程通过模仿其右部来使用一个产生式非终结符：对应过程被调用记号：若与超前扫描符号匹配，读入下一个输入记号，否则报告出错,33/35,第二章：简单的一遍编译器：语法分析,语法分析器+语义动作=语法指导翻译器文法+语义动作(分开)=语法制导定义文

15、法+语义动作(合并)=翻译模式扩展预测语法分析器构建语法制导翻译器：类似于扩展文法形成翻译模式构造一个预测语法分析器，忽略产生式中的语义动作。把翻译模式中的语义动作拷贝到语法分析器，插入相应位置。,34/35,第二章：简单的一遍编译器：语法分析,左递归问题递归下降语法分析器（如预测语法分析器）分析一个左递归产生式时，会产生无限循环expr-expr+term|term,35/35,第二章：简单的一遍编译器：语法分析,左递归问题需要消除：转换成右递归？expr-term+RR-+term R|：默认产生式没有其他产生式可用的时候用stmt-begin opt_stmts endopt_stmt-stmt_list|第四章将讨论更一般的左递归形式，并讨论如何从一个文法中消除所有左递归。,