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,第二章:简单的一遍编译器:语法定义,上下文无关文法:实例
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的后缀表示
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 861 第二 简单 编译器
链接地址:https://www.31doc.com/p-3024932.html