编 译 原 理 ——— 清华大学出版社 新 疆 大 学 信 息 科 学 与 工 程 学 院

编译原理 课件说明 课程简介 教学内容 新疆大学信息科学与工程学院

课件说明 课件说明 开发环境及版本 课件特色 配套教材及参考资料 作者简介 新疆大学信息科学与工程学院

开发环境及版本 开发环境 版 本 本课件使用PowerPoint 2010开发，制作共十章339张幻灯片。 版 本 本课件经过试用，目前是经过改进的第二版。 新疆大学信息科学与工程学院

课件特色 教学内容科学规范 思 考 与 练 习 总 结 丰 富 实 例 思 考 与 练 习 温馨“小贴士” 教学内容科学规范 预 备 知 识 补 充 内 容 新疆大学信息科学与工程学院

课件特色 教学设计实用高效 新疆大学信息科学与工程学院

课件特色 界面设计美观清晰 新疆大学信息科学与工程学院

课件特色 使用动画直观易懂 文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 思考： 分析符号串abbcde是否是G[S]的句子    S S aABe A aAde B A aAbcde a b b c d e abbcde 新疆大学信息科学与工程学院

课件特色 课件使用简便 导航链接明晰 运行可靠稳定 新疆大学信息科学与工程学院

清华大学出版社 《编译原理》 张素琴、吕映芝等编著 配套教材 清华大学出版社 《编译原理》 张素琴、吕映芝等编著 新疆大学信息科学与工程学院

参考文献 编译原理（第2版）张素琴等 清华大学出版社 2005.2 程序设计语言编译原理（第3版）陈火旺 国防工业出版社 2000.1 编译原理（第2版）张素琴等 清华大学出版社 2005.2 程序设计语言编译原理（第3版）陈火旺 国防工业出版社 2000.1 计算机编译原理 张幸儿 科学出版社 1999.4 编译原理 蒋立源 西北工业大学出版社 1997 编译技术 王力红 重庆大学出版社 2001.9 程序设计语言与编译-语言的设计和实现（第2版） 龚天富 电子工业出版社 2003.8 新疆大学信息科学与工程学院

参考课件 北京航空航天大学《编译技术》课件 丁文魁《编译原理》课件 清华大学《编译原理》课件 个别内容参考百度文库相关课件 新疆大学信息科学与工程学院

相关链接 武汉大学编译原理精品课程http://course.jingpinke.com/details?uuid=8a833996-18ac928d-0118-ac928f58-0220&objectId=oid:8a833996-18ac928d-0118-ac928f58-0221&courseID=A050024 华东师范大学编译原理精品课程http://www.cs.ecnu.edu.cn/compiler/4teachingplan.htm 河北科技大学编译原理精品课程http://stream.hebust.edu.cn/jpk/xxbjyl/2.htm 西安电子科技大学编译原理精品课程http://course.jingpinke.com/details?uuid=8a833999-1db3d94a-011d-b3d94c91-0163&courseID=S0400052 北京航空航天大学编译技术精品课程http://course.jingpinke.com/details?uuid=8a833999-1e4881f5-011e-4881f600-001f&courseID=S0400075 西北工业大学编译原理精品课程http://course.jingpinke.com/details?uuid=8a833999-1db3d94a-011d-b3d94c81-0157&objectId=oid:8a833999-1db3d94a-011d-b3d94c81-0156&courseID=S0400043 北京工业大学编译原理精品课程http://course.jingpinke.com/details?uuid=8a83399b-1999b5d6-0119-99b5d76e-001f&courseID=A070054 新疆大学信息科学与工程学院

相关链接 国防科学技术大学编译原理精品课程http://course.jingpinke.com/details?uuid=8a83399b-19cc280d-0119-cc280de2-0069&courseID=A070038 中国科学技术大学编译原理精品课程http://course.jingpinke.com/details?uuid=b194d06c-122c-1000-98aa-144ee02f1e73&objectId=oid:b194d06c-122c-1000-98a9-144ee02f1e73&courseID=X0900120 武汉理工大学编译原理精品课程http://course.jingpinke.com/details?uuid=ba985c7b-122e-1000-83c6-144ee02f1e73&objectId=oid:ba985c7b-122e-1000-83c5-144ee02f1e73&courseID=X0500307 中南大学编译原理精品课程http://course.jingpinke.com/details?uuid=dd11fed1-1237-1000-b127-144ee02f1e73&objectId=oid:dd11fed1-1237-1000-b126-144ee02f1e73&courseID=K090063 北京师范大学编译原理精品课程http://course.jingpinke.com/details?uuid=dc04a970-1277-1000-82fb-b7b5f3b2d8d7&objectId=oid:dc04a970-1277-1000-82fa-b7b5f3b2d8d7&courseID=X0700681 新疆大学信息科学与工程学院

作者简介 廖媛媛 吴晓红 讲师，硕士，自2001年起任教，主讲《编译原理》课程。 联系方式：liaoyuan@xju.edu.cn 副教授，硕士，自1986年起任教，主讲《编译原理》课程。 联系方式：wuxiaohong@xju.edu.cn 新疆大学信息科学与工程学院

课程简介 课程教学目的 课程主要内容 课时安排 新疆大学信息科学与工程学院

课程简介 课程教学目的 《编译原理》课程是计算机专业的一门专业基础课。通过该课程的教学，使学生能理解人类思维与计算机沟通方法，从而从抽象角度认识计算机的功能，并对编译系统的结构、工作流程及编译程序各组成部分的设计原理和实现技术有一系统的认识，使学生掌握编译程序构造的基本原理、设计方法和实现技术，具有设计、实现、分析和维护编译程序的方面的基本技能，为今后从事应用软件和系统软件的开发打下一定的理论和实践基础。 新疆大学信息科学与工程学院

课程简介 课程主要内容 《编译原理》主要研究设计和构造编译程序的原理和方法，其研究对象是程序设计语言的编译程序。 课程内容共十章，包括语言及文法的基本知识、词法分析、语法分析、语义分析及中间代码生成、符号表组织、运行时的存储组织与分配、代码优化及目标代码生成等。 新疆大学信息科学与工程学院

课程简介 课 时 分 配 我校开设《编译原理》课程共计32学时。 教学内容 课时 第一章 引论 2 第二章 文法和语言 4 第三章 词法分析 6 第四章 自顶向下语法分析方法 第五章 自底向上优先分析 第六章 LR分析 第七章 语法制导翻译和中间代码生成 第八章 符号表 第九章 目标程序运行时的存储组织 第十章 代码优化和代码生成 新疆大学信息科学与工程学院

目录 1 引论 2 文法和语言 3 词法分析 4 自顶向下语法分析方法 5 自底向上优先分析 6 LR分析 7 语法制导翻译和中间代码生成 8 符号表 9 目标程序运行时的存储组织 10 代码优化和代码生成 新疆大学信息科学与工程学院

1、引论 翻译程序 编译过程和编译程序的结构 新疆大学信息科学与工程学院

1、引论 教 学 目 的 了解三种翻译程序 弄清编译过程 建立编译程序整体概念 新疆大学信息科学与工程学院

1、引论 重点与难点 重点是理解编译程序的结构。 难点是解释程序和编译程序的区别。 新疆大学信息科学与工程学院

1.1 翻译程序 翻译程序 将源程序转换为目标程序的程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序，编译程序以及各种变换程序的总称。 目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。 源程序 用汇编语言或高级语言编写的程序称为源程序 目标程序 用目标语言所表示的程序 新疆大学信息科学与工程学院

即源程序是翻译程序的输入，目标程序是翻译程序的输出 1.1 翻译程序 源程序 翻译程序 目标程序 SOURCE PROGRAM TRANSLATER OBJECT PROGRAM 即源程序是翻译程序的输入，目标程序是翻译程序的输出 新疆大学信息科学与工程学院

1.1 翻译程序 翻译程序 汇编程序 编译程序 解释程序 1.1 翻译程序 若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过程称为“汇编”(Assemble） 若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称“编译”（Compile） 对源程序进行解释执行的程序（Interpreter） 汇编程序 翻译程序 编译程序 解释程序 新疆大学信息科学与工程学院

1.1 翻译程序 编译程序 汇编程序 编译程序 解释程序 编译程序和汇编程序主要区别：加工对象不同，由于汇编语言格式简单，常与机器语言之间有一一对应的关系，所以汇编程序所作的翻译工作比编译程序简单的多。 解释程序与编译程序的主要区别:在解释程序的执行过程中不产生目标代码。翻译程序执行的工作效率很低，但结构比编译程序简单、占用内存少，适用一些规模较小的语言。编译程序是现在计算机系统最重要的系统程序之一。 新疆大学信息科学与工程学院

1.1 翻译程序 编译或汇编阶段 运行阶段 编译汇编工作过程 源程序 编译程序 目标程序 或汇编程序 目标程序 + 输入数据 输出数据 1.1 翻译程序 编译或汇编阶段 运行阶段 编译汇编工作过程 源程序 目标程序 编译程序 或汇编程序 输出数据 目标程序 + 运行子程序 输入数据 新疆大学信息科学与工程学院

1.1 翻译程序 解释程序工作过程 解释程序工作过程 输出数据 解释程序 输入数据 源程序 新疆大学信息科学与工程学院

1.1 翻译程序 源程序 编译程序 源程序的中间形式 输出数据 解释程序 输入数据 “编译-解释执行”系统 新疆大学信息科学与工程学院

1.1 翻译程序 软件：计算机系统中的程序及其文档。 1.1 翻译程序 软件：计算机系统中的程序及其文档。 系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。它和具体的应用领域无关，如编译系统和操作系统等。 操作系统 编译系统 裸机 新疆大学信息科学与工程学院

1.1 翻译程序 高级语言程序的处理过程 需预处理的源程序 预处理程序 源程序 编译程序 目标汇编程序 汇编程序 可再装配目标文件 1.1 翻译程序 需预处理的源程序 预处理程序 源程序 编译程序 目标汇编程序 汇编程序 可再装配目标文件 可再装配的机器代码 装配/连接-编辑程序 绝对机器代码 高级语言程序的处理过程 新疆大学信息科学与工程学院

1.2 编译过程和编译程序的结构 编译过程 是指将高级语言程序翻译为等价的目标程序的过程。习惯上是将编译过程划分为6个基本阶段： 词法分析 1.2 编译过程和编译程序的结构 编译过程 是指将高级语言程序翻译为等价的目标程序的过程。习惯上是将编译过程划分为6个基本阶段： 词法分析 语法分析 语义分析 中间代码生成 代码优化 新疆大学信息科学与工程学院

词法分析 1.2 编译过程和编译程序的结构 任 务 单 词 例 题 分析和识别单词 1.2 编译过程和编译程序的结构 任 务 分析和识别单词 源程序是由字符序列构成的，词法分析扫描源程序(字符串),根据语言的词法规则分析并识别单词，并以某种编码形式输出。 单 词 是语言的基本语法单位，一般语言有五大类单词 <1>语言定义的关键字或保留字（如BEGIN、END、IF） <2>标识符 <3>常数 <4>运算符（如+、-、*、/） <5>界符（如；，（）） 例 题 对如下的程序片段进行词法分析 begin var sum, first, count: real; sum:=first+count*10 end. 词法分析 新疆大学信息科学与工程学院

语法分析 1.2 编译过程和编译程序的结构 任 务 例 题 分析和识别单词串 1.2 编译过程和编译程序的结构 任 务 分析和识别单词串 根据语法规则（即语言的文法），分析并识别出各种语法成分，如表达式、各种说明、各种语句、过程、函数程序等，并进行语法正确性检查。 例 题 对于前面提到的例子sum:=first+count*10 我们可以根据语言赋值语句的文法来分析和识别该语句（单词串）。 <赋值语句>→<变量><赋值操作符><表达式> <变量>→<标识符> <赋值操作符>→:= <表达式>→<表达式> +<表达式>|<表达式>*<表达式>|…… 语法分析根据文法，将<变量>、<赋值操作符>、<表达式>识别出来，进而将赋值语句识别出来，在识别过程中进行语法检查，若有错误，则应输出出错信息。 语法分析 新疆大学信息科学与工程学院

语义分析 1.2 编译过程和编译程序的结构 任 务 例 题 10.0 语义审查(静态语义) 上下文相关性 类型匹配 类型转换 begin 1.2 编译过程和编译程序的结构 任 务 语义审查(静态语义) 上下文相关性 类型匹配 类型转换 例 题 begin var sum, first, count: real; sum:=first+count*10 end. … 语义分析 real int 10.0 新疆大学信息科学与工程学院

中间代码生成 1.2 编译过程和编译程序的结构 中间代码 例 题 1.2 编译过程和编译程序的结构 中间代码 sum:=first+count*10 生成中间代码的目的： <1> 便于做优化处理； <2> 便于编译程序的移植（中间代码不依赖与目标计算机） 中间代码的形式：编译程序设计者可以自己设计，常用的有 四元式、三元式、逆波兰表示等。 例 题 由语法分析识别出为赋值语句，语义分析首先要分析语义上的正确性，例如要检查表达式中和赋值号两边的类型是否一致。根据赋值语句的语义，生成中间代码。即用一种语言形式来代替另一种语言形式，这是翻译的关键步骤。（翻译的实质：语义的等价性） 一种介于源语言和目标语言之间的中间语言形式。 中间代码生成 新疆大学信息科学与工程学院

中间代码生成 1.2 编译过程和编译程序的结构 四元式 例 题 三地址指令 1.2 编译过程和编译程序的结构 四元式 三地址指令 例 题 运算符 运算对象 1 运算对象2 结果 (1) intoreal 10 -- T1 (2) * count T1 T2 (3) + first T2 T3 (4) := T3 sum 其中T1和T2为编译程序生成的临时名字，用于存放运算的中间结果 这样所生成的四元式与原来的赋值语句在语言的形式上不同，但语义上等价。 中间代码生成 sum:=first+count*10 新疆大学信息科学与工程学院

代码优化 1.2 编译过程和编译程序的结构 任 务 例 题 目的是为了得到高质量(省时，省空间)的目标程序。 1.2 编译过程和编译程序的结构 任 务 目的是为了得到高质量(省时，省空间)的目标程序。 运算符 运算对象 1 运算对象2 结果 (1) * count 10.0 T1 (2) + first T1 sum 例 题 代码优化 例：x=1；y=2；z=x*y 优化后： z=2； 例：for k:=1 to 100 do 优化后：m:=I; n:=J; begin for k:=1 to 100 do m:=I+10*k; begin n :=J+10*k; m:= m+10; n:=n+10; end; end; 做300次“+”，200次“*” 做300次“+”，不做“*” 新疆大学信息科学与工程学院

目标代码生成 1.2 编译过程和编译程序的结构 任 务 由中间代码很容易生成目标程序（地址指令序列）。 1.2 编译过程和编译程序的结构 任 务 由中间代码很容易生成目标程序（地址指令序列）。 目标代码生成 绝对指令代码：直接将程序装入内存中确定的位置 可重定位的指令代码： 每个程序开始都是0，需要时装入内存 汇编指令代码 这部分工作与机器关系密切 ，所以要根据机器进行。 在做这部分工作时，也可以进行代码优化的处理。 新疆大学信息科学与工程学院

1.2 编译过程和编译程序的结构 S.P O.P 语义分析 生成目标程序 代码优化 语法分析程序 词法分析程序 出 错 处 理 表 格 管 1.2 编译过程和编译程序的结构 S.P O.P 语义分析 生成目标程序 代码优化 语法分析程序 词法分析程序 出 错 处 理 表 格 管 中间代码生成 新疆大学信息科学与工程学院

1.2 编译过程和编译程序的结构 表格 出错 编译程序 管理 处理 表格管理（符号表组织） 1.2 编译过程和编译程序的结构 编译程序 出错 处理 表格 管理 表格管理（符号表组织） 在整个编译过程中始终都要贯穿着建表（填表）和查表的工作。即要及时的把源程序中的信息和编译过程中所产生的信息登记在表格中，而在随后的编译过程中同时又要不断的查找这些表格中的信息。 出错处理 规模较大的源程序难免有多种错误，编译程序必须要有出错处理的功能。即能诊察出错误，并能报告用户错误性质和位置，以便用户修改源程序。 出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。 新疆大学信息科学与工程学院

1.2 编译过程和编译程序的结构 遍（pass）：对源程序（包括源程序中间形式）从头到尾扫描一次，并做有关的加工处理 ，生成新的源程序中间形式或目标程序，通常称之为一遍。 第一遍 第二遍 …… S.P 中间形式1 中间形式2 C2 C1 O.P 小贴士1:上一遍的结果是下一遍的输入，最后一遍生成目标程序。 小贴士2:要注意遍与基本阶段的区别 五个基本阶段：是将源程序翻译为目标程序在逻辑上要完成的 工作。 遍：是指完成上述5个基本阶段的工作，要经过几次扫描处理。 新疆大学信息科学与工程学院

1.2 编译过程和编译程序的结构 根据编译程序各部分功能，将编译程序分成前端和后端。 新疆大学信息科学与工程学院 前端 1.2 编译过程和编译程序的结构 根据编译程序各部分功能，将编译程序分成前端和后端。 前端 与源程序有关的编译部分称为前端。 词法分析、语法分析、语义分析、中间代码生成、代码优化 ——分析部分 特点：与源语言有关 后端 与目标机有关的部分称为后端。 目标程序生成（与目标机有关的优化） ——综合部分 特点：与目标机有关 新疆大学信息科学与工程学院

尝试对右面源程序进行编译过程各阶段的分析 练习 练习： 尝试对右面源程序进行编译过程各阶段的分析 PROGRAM m; VAR a,b,c:real; BEGIN read(b,c); a:=b+c*100; write(a) END. 新疆大学信息科学与工程学院

2、文法和语言 预备知识 符号和符号串 文法和语言的形式定义 文法和语言的分类 上下文无关文法及其语法树 句型的分析 有关文法实用中的一些说明 新疆大学信息科学与工程学院

教 学 目 的 2、文法和语言 了解几个概念： 递归，短语，简单短语，句柄，语法树，文法的二义性，文法的实用限制等 掌握符号串，符号串集合的运算，文法和语言的定义及其语法树、句型的分析 熟悉上下文无关文法及其语法树、句型的分析 新疆大学信息科学与工程学院

重点与难点 2、文法和语言 重点是文法和语言的形式定义、句子、句型、语言推导的基本概念。 难点是短语、简单短语、句柄的求解。 新疆大学信息科学与工程学院

2.1 预备知识 -----语言概述 语言是由句子组成的集合，是 由一组记号所构成的集合。 汉语--所有符合汉语语法的句子 的全体 2.1 预备知识 -----语言概述 汉语 英语 程序设计语言 语言 语言是由句子组成的集合，是 由一组记号所构成的集合。 汉语--所有符合汉语语法的句子 的全体 英语--所有符合英语语法的句子 的全体 程序设计语言--所有该语言的程 序的全体 新疆大学信息科学与工程学院

2.1 预备知识 -----语言概述 语言 表示在各个记号所出现的行为中，它们的来源、使用和影响。 2.1 预备知识 -----语言概述 语言 语法 语义 语用 表示构成语言句子的各个记号之间的组合规律 表示按照各种表示方法所表示的各个记号的特定含义。 表示在各个记号所出现的行为中，它们的来源、使用和影响。 新疆大学信息科学与工程学院

2.1 预备知识 -----语言概述 研究 语言 研究程序设计语言 每个句子构成的规律 每个句子的含义 每个句子和使用者的关系 2.1 预备知识 -----语言概述 研究 语言 研究程序设计语言 语法 语义 语用 每个句子构成的规律 每个句子的含义 每个句子和使用者的关系 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 新疆大学信息科学与工程学院

2.1 预备知识 -----形式语言 形式语言 语法 语义 语用 如果不考虑语义和语用， 即只从语法这一侧面来看 语言，这种意义下的语言 称作形式语言。形式语言 抽象地定义为一个数学系 统。 “形式”是指这样的事实： 语言的所有规则只以什么 符号串能出现的方式来陈 述。 形式语言理论是对符号串 集合的表示法、结构及其 特性的研究。是程序设计 语言语法分析研究的基础。 新疆大学信息科学与工程学院

2.2 符号和符号串 字母表 符号串集合 符号串 符号 符号的非空有限集 例：={a，b，c} 2.2 符号和符号串 字母表 符号的非空有限集 例：={a，b，c} 符号 字母表中的元素，不能分解的最小单位，例： a，b，c 空符号串(ε) ： 不包含任何符号的符号串 符号串 字母表中的符号组成的任何有穷序列，例：a, aa, ac, abc，.. 符号串集合 字母表 ∑ 上的符号串组成的集合 新疆大学信息科学与工程学院

2.2 符号和符号串 真前缀，真后缀，真子串 前缀 后缀 2.2 符号和符号串 前缀 移走符号串尾部的零个或多于零个符号得到的符号串. 如： ε, a, ab, abc是符号串abc的前缀. 对于每个符号串s， s和ε两者都是符号串s的前缀，后缀和子串。 后缀 删去符号串头部的零个或多于零个符号得到的符号串。如:ε, c, bc, abc是符号串abc的后缀 子串 从s中删去一个前缀和一个后缀得到的符号串。 如:bc是符号串abc的一个子串 真前缀，真后缀，真子串 任何非空符号串 x,相应地，是s的前缀，后缀或子串，并且 s  x 新疆大学信息科学与工程学院

2.2 符号和符号串 符号串的运算 符号串集合的运算 长度 符号串中符号的个数 符号串s的长度记为|s|。 ε的长度为0 连接 2.2 符号和符号串 符号串的运算 符号串集合的运算 长度 符号串中符号的个数 符号串s的长度记为|s|。 ε的长度为0 连接 符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=12 则 xy=ab12 注意：一般xy≠yx，而εx＝xε 方幂 符号串自身连接n次得到的符号串 an 定义为 aa…aa n个a a1=a, a2=aa 特殊的，a0=ε 乘积 AB =xy|xA且yB 若 集合A=a, b B = 0,1 则 AB =a0,a1, b0, b1 因为εx＝xε＝x，所以{ε}A={ε}A=A 方幂 有符号串集合A，定义 A0={ε},A1=A,A2=AA,A3=AAA,…… …… An=An-1A=AAn-1 ，n>0 例：A=｛a，b｝，A0=｛ε｝，A1=｛a，b｝，A2=｛aa,ab,ba,bb｝,…… 即符号串A的n次方乘积 闭包 A＋＝ A1 ∪ A2 ∪ A3 ∪……∪ An ∪……称为集合A的正闭包。 A*＝ A0 ∪A1 ∪ A2 ∪ A3 ∪……∪ An ∪……称为集合A的闭包。 A＋=A*A=AA* A*=A0 ∪A＋ 新疆大学信息科学与工程学院

2.2 符号和符号串 练 习 例如：L={A~Z,a~z} D={0~9} 1．L∪D={A~Z,a~z ,0~9} 2.2 符号和符号串 练 习 例如：L={A~Z,a~z} D={0~9} 1．L∪D={A~Z,a~z ,0~9} 2．LD是由所有用一个字母后跟一个数字 组成的符号串所构成的集合。 3．L4是由所有的四个字母的符号串构 的集合。 4．L（L∪D)* 是由所有的字母打头的字母 和数字组成的符号串所构成的集合. 5．D+是由所有的长度大于等于1的数字串 所构成的集合. 新疆大学信息科学与工程学院

2.2 符号和符号串 思考： 若A为某语言的基本字符集 A＝{a,b,……z,0,1,……,9, +,－,×,_/, ( , ), =……} 2.2 符号和符号串 思考： 为什么对符号、符号串、符号串集合以及它们的运算感兴趣？ 若A为某语言的基本字符集 A＝{a,b,……z,0,1,……,9, +,－,×,_/, ( , ), =……} B为单词集 B ={begin, end, if, then,else,for,……,<标识符>,<常量>,……} 则B  A* 。 语言的句子是定义在B上的符号串。 若令C为句子集合，则C  B * , 程序 C 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 2.3.1文法的定义 定义1. 文法G=（Vn，Vt，P，S） Vn：非终结符号集 Vt：终结符号集 2.3 文法和语言的形式定义 2.3.1文法的定义 V＝Vn ∪Vt 称为文法的字汇表 定义1. 文法G=（Vn，Vt，P，S） Vn：非终结符号集 Vt：终结符号集 P：产生式或规则的集合 S：开始符号（识别符号） S∈Vn 规则：U :: x U ∈Vn, x∈V* 补充: 规则的定义 我们通过建立一组规则，来描述句子的语法结构。 规则是一个有序对(U, x), 通常写为: U :: x 或U  x | U| = 1 |x|  0 “::=”表示“由……组成” 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 产生式的习惯约定： 第一条产生式的左部是开始符号 2.3 文法和语言的形式定义 产生式的习惯约定： 第一条产生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，其它字母表示终结符 G可写成G[S]，S是开始符号 例：文法G=（Vn，Vt，P，S），其中，Vn={S}, Vt={0，1}, P={S  0S1，S01} 另例：E  T|E+T|E-T T  F|T*F|T/F F  (E)|i 问Vn=? Vt=? 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 例：无符号整数的文法： G[<无符号整数>]=（Vn，Vt，P，S） 2.3 文法和语言的形式定义 例：无符号整数的文法： G[<无符号整数>]=（Vn，Vt，P，S） Vn＝{<无符号整数>,<数字串>, <数字>} Vt = {0,1,2,3,……9} P = {<无符号整数> → <数字串> ； <数字串> → <数字串> <数字> ； <数字串> → <数字> ； <数字> →0； <数字> →1； ………… <数字> →9； } S = <无符号整数>； 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 小贴士1：产生式左边符号构成集合Vn，且 S ∈Vn 小贴士2：有些产生式具有相同的左部，可以和在一起 2.3 文法和语言的形式定义 小贴士1：产生式左边符号构成集合Vn，且 S ∈Vn 文法的BNF表示 元符号“|”表示“或” 小贴士2：有些产生式具有相同的左部，可以和在一起 例: <无符号整数> → <数字串> ； <数字串> → <数字串> <数字> | <数字> ； <数字> →0 | 1 | 2 | 3 | …… | 9 小贴士3：给定一个 文法，实际只需给出产生式集合，并指定识别符号 例: G[<无符号整数>] <无符号整数> → <数字串> ； <数字串> → <数字串> <数字> | <数字> ； <数字> →0 | 1 | 2 | 3 | …… | 9 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 定义2：文法G：v＝x Uy，w＝xuy, 其中x、y ∈V* ， U∈Vn, u ∈V*, 2.3 文法和语言的形式定义 2.3.2 推导的定义 定义2：文法G：v＝x Uy，w＝xuy, 其中x、y ∈V* ， U∈Vn, u ∈V*, 若U :: u∈P，则v w。 若x＝y＝ε，有U :: u，则U  u 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 例如：G[<无符号整数>] (1) <无符号整数> → <数字串> ； 2.3 文法和语言的形式定义 例如：G[<无符号整数>] (1) <无符号整数> → <数字串> ； (2) <数字串> → <数字串> <数字> (3) <数字串> → <数字> (4) <数字> →0; (5) <数字> →1; ………… (13) <数字> →9; 例：<无符号整数> <数字串> <数字串> <数字> <数字><数字> 1 <数字> 1 0 ==> 小贴士：当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 定义3：文法G，U0,U1,U2,……，Un ∈V+ if v= U0 U1 U2 …… Un＝w 则v w 2.3 文法和语言的形式定义 定义3：文法G，U0,U1,U2,……，Un ∈V+ if v= U0 U1 U2 …… Un＝w 则v w ＋ ==> G ==> G ==> G ==> G ==> G 例：<无符号整数>==> <数字串> ==> <数字串> <数字> ==> <数字><数字> ==>1 <数字> ==>1 0 即 <无符号整数> 10 ＋ ==> G 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 定义4：文法G，v，w ∈V+ if v w ,或v=w，则v w * ＋ ==> 2.3 文法和语言的形式定义 定义4：文法G，v，w ∈V+ if v w ,或v=w，则v w * ==> G ＋ 定义5：规范推导：有xUy ==> xuy, if y ∈Vt* ,则此推导为规范的， 记为xUy ==> xuy 小贴士1：直观意义：规范推导＝最右推导 最右推导：若符号串中有两个以上的非终结符时，先推右边的。 最左推导：若符号串中有两个以上的非终结符时，先推左边的。 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 2.3.3 语言的定义 定义6：文法G[S] 文法G[Z]所产生的 所有句子的集合 2.3 文法和语言的形式定义 2.3.3 语言的定义 定义6：文法G[S] （1）句型：x是句型  S  x,且x∈V*； （2）句子：x是句子  S  x, 且x∈Vt*； （3）语言：L（G[S]）={x| x∈Vt*, S  x }； 文法G[Z]所产生的 所有句子的集合 * + * + 小贴士1：形式语言理论可以证明以下两点： （1）G →L（G）； （2）L(G)→G1，G2，……，Gn； 已知文法，求语言，通过推导； 已知语言，构造文法，无形式化方法，更多是凭经验。 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 例1、G[E]: E →A0|B1 A →1|0 B →0|1 求L(G[E])=? 2.3 文法和语言的形式定义 例1、G[E]: E →A0|B1 A →1|0 B →0|1 求L(G[E])=? E=> A0=> 10 E=> A0=> 00 E=> B1=>01 E=> B1=>00 L(G[E])={10，00，01，00} 例2、G[S]: S →0S1|01 求L(G[S])=? S =>0S1 =>0011 =>00S11 =>000111 … … L(G[S])={0n1n, n>=1} 例3、L(G[S])={anbbn , n>=1}, 写出该语言的一种文法。 G[S]：S →aAb A →aAb|b 新疆大学信息科学与工程学院

2.3 文法和语言的形式定义 练 习 1、 G[S]: S →b|bB B →bS 求L(G[S])=? 2.3 文法和语言的形式定义 练 习 1、 G[S]: S →b|bB B →bS 求L(G[S])=? 2、若语言由0、1组成，串中0和1个数相同，构造其文法。 定义7： G和G’是两个不同的文法， 若 L(G) = L(G’) , 则G和G’为等价文法。 新疆大学信息科学与工程学院

2.4 文法和语言的分类 0型文法和语言 1型文法和语言 2型文法和语言 3型文法和语言 新疆大学信息科学与工程学院 2.4 文法和语言的分类 0型文法和语言 P： u::=v,其中u∈V＋，v∈V* 0型文法称为短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。 1型文法和语言 P： xUy::= xuy,其中 U∈Vn，x、y、u∈V* 称为上下文敏感或上下文有关。也即只有在x、y这样的 上下文中才能把U改写为u 2型文法和语言 P： U::= u,其中 U∈Vn，u∈V* 称为上下文无关文法。也即把U改写为u时，不必考虑上下文。 注意：2型文法与BNF表示相等价。 3型文法和语言 （左线性） P： U::=T或 U::=wT其中 U、w∈Vn，T∈Vt （右线性） P： U::=T或 U::=Tw其中 U、w∈Vn，T∈Vt 3型文法称为正则文法。 新疆大学信息科学与工程学院

2.4 文法和语言的分类 根据上述定义，L0 L1 L2 L3 例：0型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。 ∪ ∪ ∪ L3 L2 L1 L0 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 （1）语法树：句子结构的图示表示法，它是一种有向图，由 结点和有向边组成。 结点：符号 根结点：开始符 2.5 上下文无关文法及其语法树 （1）语法树：句子结构的图示表示法，它是一种有向图，由 结点和有向边组成。 结点：符号 根结点：开始符 中间结点：非终结符 叶结点：终结符或非终结符 Z U V a b c d 有向边：表示结点间的派生关系。 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 ( 2 ) 句型的推导及语法树的生成（自顶向下） 给定G[S]，句型w： 可建立推导序列，S==>w 2.5 上下文无关文法及其语法树 ( 2 ) 句型的推导及语法树的生成（自顶向下） 给定G[S]，句型w： 可建立推导序列，S==>w 可建立语法树，以S为根结点，每步推导生成语法树的一枝，最终可生成句型的语法树。 * <无符号整数> <数字串> <数字> 1 (1) (2) (3) (5) (4) 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 ( 3 ) 子树与短语 子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。 2.5 上下文无关文法及其语法树 ( 3 ) 子树与短语 子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。 短语：某子树的所有叶子自左向右排列，得到的符号串为该句型的相对于该子树根的短语。 简单短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列形成的符号串。 句柄：最左简单短语。 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 ( 4 ) 树与推导 新疆大学信息科学与工程学院 自左向右建立推导序列 从开始符号开始 自上而下建立语法树 2.5 上下文无关文法及其语法树 ( 4 ) 树与推导 自左向右建立推导序列 从开始符号开始 自上而下建立语法树 由根结点开始 句型推导过程 句型语法树的生长过程 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 例：G[<无符号整数>] 句型10 规范推导 [<无符号整数>] 2.5 上下文无关文法及其语法树 例：G[<无符号整数>] 句型10 规范推导 [<无符号整数>] <数字串> ==> <无符号整数> <数字串> <数字> <数字串> <数字> ==> <数字串> 0 ==> <数字> <数字> 0 ==> 1 10 ==> 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 例1、G[S]: S →AB A →Aa|Bb B →a|Sb 求句型baSb的短语 S=>AB =>ASb =>bBSb =>baSb 短语：baSb(S) ,ba (A), a(B), Sb(B) 简单短语：a(B), Sb(B) 句柄：a(B) 例2、baabaab是否是上例文法的句子，如果是，找出其短语、简单短语和句柄。 短语：baabaab(S) ,ba1a (A), ba1(A), a1(B) ba2a3(S), ba2a3b(B), ba2 (A), a2(B), a3(B) S A B b a 句柄 S A B b a1 a a2 a3 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 小贴士：规约与推导互为逆过程 由语法树构造推导 规范规约：对句型中最左简 单短语（句柄）进行的规约。 2.5 上下文无关文法及其语法树 由语法树构造推导 自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。 从句型开始，自右向左地逐步进行规约，建立规约序列。 规范规约：对句型中最左简 单短语（句柄）进行的规约。 小贴士：规约与推导互为逆过程 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 小贴士：无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。 2.5 上下文无关文法及其语法树 （5）文法的二义性：若对于一个文法的某一句子存在两棵 不同的语法树，则该文法是二义性文法，否则是无二义性 文法。 小贴士：无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 对于句子S＝i＋i * i ∈ L（G[E] ），存在不同的规范推导： 2.5 上下文无关文法及其语法树 二义性文法的例子： G[E]: E:= E+E | E*E | (E) | i Vn={E} Vt={ +, * , ( , ) , i } 对于句子S＝i＋i * i ∈ L（G[E] ），存在不同的规范推导： (1) E==>E+E==>E+E*E ==>E+E*i ==>E+i*i ==> i＋i * i (2) E==> E*E ==> E*i ==> E+E*i ==> E+i*i ==> i＋i * i 这两种不同的推导对 应了两种不同的语法树 E + * i E * + i 新疆大学信息科学与工程学院

2.5 上下文无关文法及其语法树 E + * i E * + i 句柄：i 句柄：E＋E 2.5 上下文无关文法及其语法树 对于同一个句型E+E* i，它有两个不同的句柄（对应上述两棵不同的语法树）：i 和 E＋E。因此语法的二义性意味着句型的句柄不唯一。 E + * i E * + i 句柄：i 句柄：E＋E 新疆大学信息科学与工程学院

2.6 句型的分析 新疆大学信息科学与工程学院 句型分析：是识别一个符号串是否为某文法的句型，是某个推导的构造过程 2.6 句型的分析 句型分析：是识别一个符号串是否为某文法的句型，是某个推导的构造过程 自上而下分析算法：从文法的开始符出发，反复使用各种产生式，寻找与输入符相匹配的推导 自下而上分析算法：从符号串出发，反复使用各种产生式，寻找与符号串相匹配的规约 新疆大学信息科学与工程学院

2.7 有关文法的实用限制 U a 若文法中有如U::=U的规则，则这就是有害规则，它会引 起二义性。 例如存在U::=U， U::= a | b，则有两棵语法树： U a 新疆大学信息科学与工程学院

2.7 有关文法的实用限制 小贴士：若保证某一非终结符A在句子的推导中出现，必须满足两个 多余规则：（1）文法中某些非终结符不在任何规则的右部出现，所以 任何句子的推导中不可能用 它。 ---------不可到达的 （2）文法中有那样的非终结符，不能够从它推出终结符号 串来。 ----------不可中止的 多余规则 例：G[S]: S →Be B →Ce B →Af A →Ae A →e C →Cf D →f 小贴士：若保证某一非终结符A在句子的推导中出现，必须满足两个 条件： （1）A必须在某句型中出现。 （2）必须能够从A推出终结符号串t来。 新疆大学信息科学与工程学院

补充 1、扩充的BNF表示 BNF的元符号： <, >, ::=, | 2、语法图 字母 数字 标识符 无符号整数 新疆大学信息科学与工程学院

3、词法分析 词法分析程序的设计 单词的描述工具 有穷自动机 正规式和有穷自动机的等价性 正规文法和有穷自动机的等价性 新疆大学信息科学与工程学院

教 学 目 的 3、词法分析 了解单词的描述工具 掌握有穷自动机及其NFA的确定化和DFA的最小化 熟悉有穷自动机和正规文法、正规式的等价转换 设计并实现词法分析程序 新疆大学信息科学与工程学院

重点与难点 3、词法分析 重点是正规文法、正规式、有穷自动机的基本概念。 难点是NFA转换为等价的DFA、确定有穷自动机的化简。 新疆大学信息科学与工程学院

3.1 词法分析程序的设计 主要任务： 读源程序，产生单词符号 其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 语法分析程序 Token get token …. 主要任务： 读源程序，产生单词符号 其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，…… 词法分析独立的原因： 简化设计 改进编译效率 增加编译系统的可移植性 S.P.(字符串) 词法分析 S.P.(符号串) 语法分析 第一遍 第二遍 单词序列 新疆大学信息科学与工程学院

3.1 词法分析程序的设计 词法分析程序的输出 单词类别 单词值 单词的种类 1. 保留字：begin、end、for、do 2. 标识符： 单词类别 单词值 单词的种类 1. 保留字：begin、end、for、do 2. 标识符： 3. 常数：无符号数、布尔常数、字符串常数等 4. 运算符：+、-、* 5. 界符：，；（） 新疆大学信息科学与工程学院

3.1 词法分析程序的设计 例1、const i=25, yes=1; 单词的二元式表示： （标识符，指向i的表项的指针） 例2、if i=5 then x:=y; 关键字if (3, ‘ if’) 标识符i (1, 指向i的符号表入口) 等号= (4, ‘=’) 常数5 (2, ‘5’) 关键字then (3, ‘ then’) 标识符x (1, 指向x的符号表入口) 赋值号：= (4, ‘：=’) 标识符y (1, 指向y的符号表入口) 分号； (5, ‘；’) 新疆大学信息科学与工程学院

3.2 单词的描述工具 　 　 正规式也称正规表达式，是描述单词符号的方便工具，也是定义 正规集的工具。 定义（正规式和它所表示的正规集）： 设字母标为，辅助字母表`={，，，，，，}。 和都是上的正规式，它们所表示的正规集分别为{}和{ }； 任何a ，a是上的一个正规式，它所表示的正规集为{a}； 假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1))。 仅由有限词使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。 小贴士：其中的“”读为“或”（也有使用“+”代替 “” 的）；“ ”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”、“ ”、“” 。连接符“ ”一般可省略不写。“”、“ ”和“” 都是左结合的。 新疆大学信息科学与工程学院

3.2 单词的描述工具 例、令={a，b}， 上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} ab {a,b} 3.2 单词的描述工具 例、令={a，b}， 上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} ab {a,b} ab {ab} (ab)(ab) {aa,ab,ba,bb} a  { ,a,a, ……任意个a的串} (ab) { ,a,b,aa,ab ……所有由a 和b组成的串} (ab)(aabb)(ab) {上所有含有两个相继的a或两个相继 的b组成的串} 新疆大学信息科学与工程学院

3.2 单词的描述工具 设r,s,t为正规式，正规式服从的代数规律有： rs=sr “或”满足交换律 3.2 单词的描述工具 设r,s,t为正规式，正规式服从的代数规律有： rs=sr “或”满足交换律 r(st)=(rs)t “或”的可结合律 (rs)t=r(st) “连接”的可结合律 r(st)=rsrt (st)r=srtr 分配律 r=r, r=r 是“连接”的恒等元素 rr=r “或”的抽取律 此外: r* = (r|)* （ r*）* =r* (r|s)* = (r*s*)* 新疆大学信息科学与工程学院

3.2 单词的描述工具 正规文法与正规表达式的等价性 例如：正规文法=>正规式 3.2 单词的描述工具 正规文法与正规表达式的等价性 例如：正规文法=>正规式 规则 （1）A-->xB B-->y A=xy （2）A-->xA|y A=x*y A-->Ax|y A=yx* （3）A-->x A-->y A=x|y 例1、G[S]: S-->aA A-->abA A-->a 后两式：A-->abA|a, 根据规则2：A=(ab)*a , 代入S, S=a(ab)*a 例2、G[S]: S-->aS S-->aB B-->bB B-->bC C -->cC C -->c 后两式：C-->cC |c C=c*c=c+ 代入B中： B-->bB |bc+ B=b*bc+=b+c+ 代入S中：S->As|aB S=a*ab+c+=a+b+c+ 新疆大学信息科学与工程学院

3.2 单词的描述工具 正规文法与正规表达式的等价性 例如：正规式=>正规文法 3.2 单词的描述工具 正规文法与正规表达式的等价性 例如：正规式=>正规文法 规则 （1）A=xy A-->xB B-->y （2）A=x*y A-->xA|y A=yx* A-->Ax|y （3）A=x|y A-->x A-->y 例1、S=a(a|d)* G[S]: S-->aA A-->(a|d)A| ε 例2、S=ab(a|b)*(aa|bb) 形如A=x*y G[S]: S-->abA A-->(a|b)A|(aa|bb) 即，A-->aA|bA|aa|bb 新疆大学信息科学与工程学院

3.3 有穷自动机 T S A 输入带 1 0 4 3 9 7 有穷控制器 读头 1-9 1,3,5,7,9 0-9 1,3,5,7,9 3.3 有穷自动机 输入带 1 0 4 3 9 7 有穷控制器 读头 1-9 1,3,5,7,9 0-9 T S A 1,3,5,7,9 新疆大学信息科学与工程学院

3.3 有穷自动机 有穷自动机( Finite-state Automata),简称FSA或FA。 有穷自动机分为两类： 3.3 有穷自动机 有穷自动机( Finite-state Automata),简称FSA或FA。 有穷自动机分为两类： 确定的有穷自动机（DFA） 不确定的有穷自动机（NFA） 新疆大学信息科学与工程学院

3.3.1 确定的有穷自动机 定义： 一个确定有穷自动机DFA是一个五元组 M=(K, , f, S0, Z) 其中， 3.3.1 确定的有穷自动机 定义： 一个确定有穷自动机DFA是一个五元组 M=(K, , f, S0, Z) 其中， K：是非空有穷状态集,其中的每个元素称为一个状态； ：是有穷输入字母表，它的每一个元素称为一个输入 符号； f ：是一个单值映射KK，也称状态转换函数，即t(q,x)=q； S0K称之为开始状态； ZK称为终止状态集，至少由一个终止状态组成。 新疆大学信息科学与工程学院

3.3.1 确定的有穷自动机 例1、MD =( {0,1,2,3}, {a,b}, f, 0, {3} ) f: f(0,a)=1, f(0,b)=2, f(1,a)=3，f(1,b)=2 f(2,a)=1, f(2,b)=3， f(3,a)=3，f(3,b)=3 状态转换矩阵： 状态转换图： 1 状态 符号 a b 2 3 a b 1 3 2 a，b a，b 新疆大学信息科学与工程学院

3.3.1 确定的有穷自动机 对于∑*中的任何符号串t, 若存在一条从初态结点到某一 终态结点的道路，且这条路上所有弧的标记符连接成的符号 串等于t, 则称t可为DFA M所接受。 特别的，若M的初态结点同时又是终态结点，则ε字可为M 所识别（接受）。 若t∈ ∑*,f(S,t)=P, 其中S为DFA M的开始 状态，P∈Z, Z为终态集。 a b 1 3 2 a，b 新疆大学信息科学与工程学院

3.3.1 确定的有穷自动机 实验： 例2、 求解以下DFA所能识别的语言。 L(MD)={ε,a,aa,aaa,....} a 1 a 3.3.1 确定的有穷自动机 实验： 用C语言编写一个有穷自动机用来识别标识符。 例2、 求解以下DFA所能识别的语言。 1 a L(MD)={ε,a,aa,aaa,....} a b 1 L(MD)={a开头的a,b组成的任意符号串} 新疆大学信息科学与工程学院

3.3.2 不确定的有穷自动机 定义： 一个不确定有穷自动机NFA是一个五元组 M=(K，，f，S，Z) 其中， 3.3.2 不确定的有穷自动机 定义： 一个不确定有穷自动机NFA是一个五元组 M=(K，，f，S，Z) 其中， K：是非空有穷状态集,其中的每个元素称为一个状态； ：是有穷输入字母表，它的每一个元素称为一个输入 符号； f ：为K * 到K的子集（2 K）的一种映射，也称状态转换函数； S  K称之为初始状态集； ZK称为终止状态集，至少由一个终止状态组成。 新疆大学信息科学与工程学院

3.3.2 不确定的有穷自动机 例：S={0,1,2,3} ∑={a,b} S0={0} Z={3} 3.3.2 不确定的有穷自动机 例：S={0,1,2,3} ∑={a,b} S0={0} Z={3} f: f(0,a)={1,3} f(0,b)={2,3} f(1,a)= φ f(1,b)={1,3} f(2,a)={2,3} f{2,b}= φ f(3,a)= φ f(3,b)= φ 状态转换矩阵： 状态转换图： b {1,3} {2,3} φ 状态 2 3 1 符号 a 1 3 2 a b a，b 新疆大学信息科学与工程学院

3.3.3 NFA转换成等价的DFA DFA是NFA的特例，对每个（NFA）M一定存在一个（DFA）M’, 使得L(M)=L(M’) 对于任意两个有穷自动机M和M’，如果L(M)=L(M’)，则称M和M’是等价的。 假设NFA N=（K, ∑ ,f,K0 , Kt ）按如下办法构造一个DFA M=(S, ∑,D,S0,St )使得L(M)=L(N)： 新疆大学信息科学与工程学院

3.3.3 NFA转换成等价的DFA 对状态集合I的几个有关运算： 状态集合I的ε—-闭包,表示为closure（I），定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能达到的状态的集合。 状态集合I的a 弧转换，表示为move（I,a）定义为状态集合J,其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。 新疆大学信息科学与工程学院

3.3.3 NFA转换成等价的DFA 例： 1 状态 符号 a b 2 3 DFA状态转换矩阵 b {1,3} {2,3} φ 状态 2 3 2 3 DFA状态转换矩阵 b {1,3} {2,3} φ 状态 2 3 1 符号 a NFA状态转换矩阵 新疆大学信息科学与工程学院

3.3.3 NFA转换成等价的DFA 构造NFA N的状态K的子集的算法，假定所构造的子集族为C,即C=( T1 , T2,…Ti ),其中 T1 , T2,…Ti状态K的子集。 子集构造算法为: 开始，令 ε—closure(K0)为C中唯一成员，并且 它是未被标记的。 ② While（C中存在尚未被标记的子集T）do {标记T; for 每个输入字母a do {U:= ε—closure(Move(T,a))； if U不在C中 then 将U作为未被标记的子集加在C中 } 新疆大学信息科学与工程学院

3.3.3 NFA转换成等价的DFA 例1 状态转换矩阵 状态转换矩阵 NFA S B Z 1 [B,Z] [S] [B] ②[B] 1 [B,Z] [S] [B] ②[B] [S] φ [B,Z] 状态子集 输入符号 状态转换矩阵 1 状态 输入符号 状态转换矩阵 1 2 3 新疆大学信息科学与工程学院

3.3.3 NFA转换成等价的DFA 例2 小贴士:包含原初始状态S的状态子集为DFA M的初态; B Z 1 NFA 例2 1 2 3 DFA 小贴士:包含原初始状态S的状态子集为DFA M的初态; 包含原终止状态Z的状态子集为DFA M的终态。 新疆大学信息科学与工程学院

3.3.3 NFA转换成等价的DFA 例3 状态转换矩阵： DFA的状态转换图： NFA 0，1 A B C 1 1 [A] ②[A,B] 状态子集 输入符号 1 [A] ②[A,B] [A,B,C] ④[A,C] DFA 1 2 3 4 新疆大学信息科学与工程学院

3.3.4 确定有穷自动机的化简 一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。 3.3.4 确定有穷自动机的化简 一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。 在有穷自动机中，两个状态s和t等价的条件是： 一致性条件——状态s和t必须同时为可接受状态或不可接受状态。 蔓延性条件——对于所有输入的符号，状态s和状态t必须转换到等价的状态里。 新疆大学信息科学与工程学院

3.3.4 确定有穷自动机的化简 例1 简化后：  DFA ② S1 ={3,4,5,6} S2={0,1,2} 3.3.4 确定有穷自动机的化简 例1  DFA ② S1 ={3,4,5,6} S2={0,1,2}  S1中的四个状态经过a,b到达状态仍在S1中，∴不再划分 ④ S2中三个状态经过a,不在一个集合，∴S2划分为S21=｛1｝，S22=｛0，2｝ ⑤ S22再经过a,b,不在一个集合∴S22划分为 S221={0},S222={2} ⑥ 把S1中四个等价状态合并 a b 1 6 4 2 5 3 简化后： 1 3 2 a b a,b 新疆大学信息科学与工程学院

3.3.4 确定有穷自动机的化简 例2 S1={1,2} S2={3} 经过a,b都到同一集合∴合并 简化后： 简化后： a b b a 1 3.3.4 确定有穷自动机的化简 例2 S1={1,2} S2={3} 经过a,b都到同一集合∴合并 简化后： 1 2 3 a b 简化后： 1 3 a b 新疆大学信息科学与工程学院

3.3.4 确定有穷自动机的化简 例3 简化后： S1={C,D,E,G} S2={A,B,F} 3.3.4 确定有穷自动机的化简 例3 S1={C,D,E,G} S2={A,B,F} S1经过a,C,D,G到Ф，E a G ∴S11={C,D,G} S12={E} S11中经过b,S111={D,G},S112={C} ∴合并D,G S2经过a,S21={A,B},S22={F} S21经过b,S211={A},S212={B} b A B C D F E G a 简化后： A B D F C E a b 新疆大学信息科学与工程学院

3.3.4 确定有穷自动机的化简 例4 确定化  NFA(两个初态，Q经过1到达Q，Z) ②  3.3.4 确定有穷自动机的化简 例4  NFA(两个初态，Q经过1到达Q，Z) ② 0,1 Q P Z 1 确定化 A B C D E 1 0,1  ④ S1={A,B} S2={C,D,E} S21={C,E} S22={D} S11={A} S12={B } 1 A[Q,P] B[P] C[Q,Z] D[Z] E[Q,Z,P] Ф 符号 状态 新疆大学信息科学与工程学院

3.3.4 确定有穷自动机的化简 思考： ⑤ 简化后： 如何判断确定的有穷自动机化简前后等价？ A 1 B C 0,1 D 3.3.4 确定有穷自动机的化简 ⑤ 简化后： 思考： 如何判断确定的有穷自动机化简前后等价？ A B C D 1 0,1 新疆大学信息科学与工程学院

3.4 正规式和有穷自动机的等价性 有穷自动机和正规表达式的等价性： 3.4 正规式和有穷自动机的等价性 有穷自动机和正规表达式的等价性： 对于∑上的一个NFA M，可以构造一个∑上的正规式R,使得L(R)=L(M)。 对于∑上的一个正规式R，可以构造一个∑上的NFA M，似的L(M)=L(R)。 新疆大学信息科学与工程学院

3.4 正规式和有穷自动机的等价性 例1 (a|b)*(aa|bb)(a|b)* 例2 (a|b)*a(a|b) ε 3 1 4 2 b a 3.4 正规式和有穷自动机的等价性 例1 (a|b)*(aa|bb)(a|b)* 例2 (a|b)*a(a|b) 3 1 4 2 b a a,b a,b 4 1 2 3 a b ε 新疆大学信息科学与工程学院

3.5 正规文法和有穷自动机的等价性 有穷自动机和正规文法的等价性： 对于一个NFA M，都存在 一个正规文法G，使得L(G)=L(M). 3.5 正规文法和有穷自动机的等价性 有穷自动机和正规文法的等价性： 对于一个NFA M，都存在 一个正规文法G，使得L(G)=L(M). 对于一个正规文法G,都存在一个NFA M， 使得L(M)=L(G). 新疆大学信息科学与工程学院

3.5 正规文法和有穷自动机的等价性 例1 G[S]: S0B B 0B B 1S B 0 例2 G[Z]: Z aZ| bB| 3.5 正规文法和有穷自动机的等价性 例1 G[S]: S0B B 0B B 1S B 0 例2 G[Z]: Z aZ| bB| B aZ Z S B 1 Z B b a ε 新疆大学信息科学与工程学院

总结 正则文法 NFA 正则表达式 1 2 3 4 5 6 DFA 最小化 7 8 新疆大学信息科学与工程学院

某些非LL（1）文法到LL（1）文法的等价变换 4、自顶向下语法分析方法 语法分析概要 LL（1）文法及其分析程序 某些非LL（1）文法到LL（1）文法的等价变换 确定的自顶向下分析方法 新疆大学信息科学与工程学院

教 学 目 的 4、自顶向下语法分析方法 了解确定的自顶向下分析方法 熟练运算FIRST集、FOLLOW集、SELECT集的运算 掌握LL（1）文法的判别，某些非LL（1）文法到LL（1）文法的等价转换 新疆大学信息科学与工程学院

重点与难点 4、自顶向下语法分析方法 重点是LL(1)文法的判别、预测分析方法法。 难点是某些非LL(1)文法到LL(1)文法的等价变换。 新疆大学信息科学与工程学院

4.1 语法分析概要 语法分析 语法分析是编译程序的核心部分。 词 法 分析器 语 法 源程序 单词符号 取下一个单词符号 句子 4.1 语法分析概要 语法分析 语法分析是编译程序的核心部分。 语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序）。 语法分析方法 自顶向下分析法 递归子程序法 预测分析法 自底向上分析法 算符优先分析法 LR(K)分析法 词 法 分析器 语 法 源程序 单词符号 取下一个单词符号 句子 新疆大学信息科学与工程学院

4.1 语法分析概要 构造推导的关键问题 在构造最左推导的过程中,面对当前读入的单词符号和当前被替换的非终结符两者,应该选择这个非终结符的哪条候选式去替换它(推导);主要找出选择一个非终结符号的候选式的方法; 在构造最右推导的过程中,面对当前读入的单词符号,已分析过的符号串中是否已构成一个产生式的右部（可归约），即句柄。如果已构成句柄,即用相应的产生式左部(非终结符号)去替换它(归约)，寻找句柄的方法。 新疆大学信息科学与工程学院

4.1 语法分析概要 例：构造最左推导（aabbaa) (自顶向下） SaASa A SbA SS ba S S aAS a A aabAS aabbaS aabbaa aAS S A S a b 新疆大学信息科学与工程学院

4.1 语法分析概要 例：构造最右推导 (自底向上） SaAS  a A SbA  SS ba A S a b aAa ( a) 例：构造最右推导 (自底向上） SaAS  a A SbA  SS ba A S a b aAa ( a) aSbAa (SbA) aSbbaa (ba) aabbaa (a) aAS (aAS) S 新疆大学信息科学与工程学院

4.2 LL (1) 文法及其分析程序 新疆大学信息科学与工程学院 FIRST集合 FIRST集合定义 FIRST集合计算 FOLLOW集合 SELECT集合 SELECT集合定义 SELECT集合计算 判定LL(1)文法 产生式中相同左部的SELECT集合相交为空 新疆大学信息科学与工程学院

4.2 LL (1) 文法及其分析程序 FIRST集合定义 设G=(VT,VN,S,P)是上下文无关文法 FIRST（）={a| a,a∈VT, , ∈V*} 若 ε则规定ε∈FRIST（）。 FIRST集合计算 若XV,则FIRST(X)={X2} 若XVN,且有产生式Xa…，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中. 若XY…是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X  Y1Y2…YK 是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j ≤i-1,FIRST(Yj)都含有 (即Y1..Y(i-1)  ),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,…,K)均含有,则把加到FRIST(X)中. 新疆大学信息科学与工程学院

4.2 LL (1) 文法及其分析程序 例1. G[S]: S→abB, B→AbA, A→SC|ε, C→B|C FIRST(S)={a} FIRST(B)=(FIRST(A)-ε)∪{b}={a,b} FIRST(A)=FIRST(S)∪FIRST(ε)={a,ε} FIRST(C)=FIRST(B)∪{c}={a,b,c} 例2. S→eT|RT|ε, T→DR|ε, R→dR|ε, D→a|bd FIRST(S)={e}∪(FIRST(R)-ε)∪(FIRST(T)-ε)∪{ε}={e,ε,d,a,b} FIRST(T)=FIRST(D)∪{ε}={a,b,ε} FIRST(R)={d,ε} FIRST(D)={a,b} 新疆大学信息科学与工程学院

4.2 LL (1) 文法及其分析程序 练 习： S→aAbDe|d, A→BSD|e, B→SAc|cD|ε D→Se|ε 解答： FIRST(S)={a,d} FIRST(A)=(FIRST(B)-ε)∪FIRST(S)∪{e}={a,d,c,e} FIRST(B)=FIRST(S)∪{c}∪{ε}={a,d,c,ε} FIRST(D)=FIRST(S)∪{ε}={a,d,ε} 新疆大学信息科学与工程学院

4.2 LL (1) 文法及其分析程序 FOLLOW集合定义 FOLLOW（A）={aS  A 且a ∈ FRIST（）， ∈V*， ∈V+ } 若S u A  ,且 ε，则#∈FOLLOW(A)。 也可定义为：FOLLOW（A）={aS …Aa…,a ∈VT} 若S …A,则规定# ∈FOLLOW(A) FOLLOW集合计算 对于文法的开始符号S,置#于FOLLOW(S) 中; 若Ａα B β是一个产生式,则把 FIRST(β)\{}加至FOLLOW(B)中; 若Ａα B是一个产生式,或ＡαBβ是 一个产生式而β  (即FIRST(β)）， 则把FOLLOW（A），加至FOLLOW（B）中． 新疆大学信息科学与工程学院

4.2 LL (1) 文法及其分析程序 例1. S→abB A→SC*|ε, B→AbA, C→B|c FOLLOW(S)={#}∪FIRST(C)={#,a,b,c} FOLLOW(A)=FOLLOW(B)∪{b}={#,a,b,c} FOLLOW(B)=FOLLOW(S)∪FOLLOW(C)={#,a,b,c} FOLLOW(C)=FOLLOW(A)={#a,b,c} (遇到互相迭代 F(A)=F(B)=F(C) F(C)=F(A)则其FOLLOW集都相等) 例2. S→eT|RT, R→dR|ε, D→a|bd FOLLOW(S)={#} FOLLOW(R)=(FIRST(T)-ε)∪FOLLOW(S)∪FOLLOW(T)={#,a,b} FOLLOW(T)=FOLLOW(S)={#} FOLLOW(D)=(FIRST(R)-ε)∪FOLLOW(T)={d}∪{#}={d,#} 新疆大学信息科学与工程学院

4.2 LL (1) 文法及其分析程序 练 习： S→aAbDe|d, A→BSD|c, B→SAc|cD|ε, D→Se|ε 解答： FOLLOW(S)={#}∪FIRST(D)|ε∪FOLLOW(A)∪FIRST(A)∪c∪e ={#,a,d,b,c,e} FOLLOW(A)={b,c} FOLLOW(B)=FIRST(S)={a,d} FOLLOW(D)={e}∪FOLLOW(A)∪FOLLOW(B)={e,b,c,a,d} 新疆大学信息科学与工程学院

4.2 LL (1) 文法及其分析程序 SELECT集合定义 给定上下文无关文法的产生式A α , A ∈ VN, α ∈ V*, 若α==> , 则SELECT（ A α ）=(FIRST(α)-{})∪FOLLOW(A)。 一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A α ，A β，满足 SELECT（ A α ）∩SELECT（ A β ）=○ 其中α 、 β 不同时能==>  。 * * 新疆大学信息科学与工程学院

4.2 LL (1) 文法及其分析程序 例: G[Z]: Z→aAcB|Bd , A→AaB|c, B→bBcA|b SELECT(Z→aAcB)=FIRST(aAcB)={a} SELECT(A→c)={c} SELECT(Z→Bd)=FIRST(Bd)={b} SELECT(B→bBcA)={b} SELECT(A→AaB)=FIRST(AaB)={c} SELECT(B→b)={b} ∵相同左部为A、B的SELECT交集不为ε ∴不能确定是否是LL(1)文法。 （直接左递归A→AaB；有左公共因子b） 新疆大学信息科学与工程学院

4.3 非LL(1)文法到LL(1)文法的等价转换 … 消除左递归 提取左公因子 消除左递归 LL(1)文法 提取左公共因子 新疆大学信息科学与工程学院

4.3.1 消除左递归 1 .左递归的定义 一个文法G，若存在推导A A ,其中, A∈VN，∈(VT∪VN)*，则称G是左递归的。 + 4.3.1 消除左递归 1 .左递归的定义 一个文法G，若存在推导A A ,其中, A∈VN，∈(VT∪VN)*，则称G是左递归的。 存在上述推导的原因是文法G中存在左递归规则。例如，描述表达式常用的语法G[E]，其产生式如下: E→E+TT T→T*F  F F→(E) id  + 2.左递归文法不适于用来构造自顶向下分析。这种规则更简单的代表是S→Sa|b （1）FIRST（Sa）∩FIRST（b）≠Φ。 （2）由S产生的句子是{ban|n≥0}。例如，对于输入baaa，从左到右扫描输入串，开始，向前看符号是b，此时，选用S的 哪条候选式？若选用S→b，则肯定构造不出S baaa；若选用S→Sa,则面对向前看符号b，下次仍选用S→Sa，不知何时选用S→b。构造分析树的过程下图所示。  + 新疆大学信息科学与工程学院

4.3.1 消除左递归 含直接左递归文法的分析树结构 S a 小贴士：用这样的规则构造递归预测分析的过程，那么，一进入这种过程不匹配任何输入符号，直接执行递归调用，形成自己调用自己的死循环。 新疆大学信息科学与工程学院

4.3.1 消除左递归 3.消除直接左递归 直接左递归的一般形式 AA ,(VTVN)* 4.3.1 消除左递归 3.消除直接左递归 AA ,(VTVN)* A A’ A’ A’   A * 例 文法 文法 EE+TT E TE’ T T*F F E’ +TE’   F (E) id T FT’ T’ *FT’   F (E) id 直接左递归的一般形式 A A1  A2...  An  1  2...  m A  1 A’ 2A’ ...  mA’ A’  1A’  2A’ ...  n A’   + 新疆大学信息科学与工程学院

4.3.２ 提取左公共因子 文法G的产生式 A, 若 1， 1， 1和 1从左端开始有相同的子串，这个子串称为和的公共左因子。显然，含有公共左因子的规则A不能用来构造预测分析。 　 　 为此，用提取左因子来改写这样的规则。 　 　若A 1 2 改写成: AA’ A’ 12 例 G[S]: S aSdAc A aS b 把A的产生式代入S中： S aSdaScbc 提取左因子： S aSS’bc S’ dc A的产生式是多余的。 G[S]: SApBq A aAp d B aBq c 小贴士：不是所有的 G[S]在有限步骤内都能改写成无公共左因子的文法。 新疆大学信息科学与工程学院

4.4 确定的自顶向下分析方法 递归子程序法 预测分析法 语法分析方法 自顶向下分析法 递归子程序法 预测分析法 自底向上分析法 优先分析法 4.4 确定的自顶向下分析方法 递归子程序法 预测分析法 语法分析方法 自顶向下分析法 递归子程序法 预测分析法 自底向上分析法 优先分析法 简单优先分析法 算符优先分析法 LR（K）分析法 新疆大学信息科学与工程学院

4.4.1 递归子程序法 根据文法写出语法分析程序： (1)对每一个非终结符U，编写一个相应子程序P（U） 4.4.1 递归子程序法 根据文法写出语法分析程序： (1)对每一个非终结符U，编写一个相应子程序P（U） (2)对于规则U→x1|x2|...|Xn,可以构造P（U）； IF ch IN FIRST(X1) THEN P( X1) ELSE IF ch IN FIRST(X2) THEN P(X2) ELSE IF .... .... ELSE ERROR (其中ch为当前输入字符，是全程变量) (3)对于符号串x=y1,y2....ym,其相应子程序P（X）为： Yi∈Vn,程序就调用Yi相对应子程序：P（y1）;P (y2);.... Yi∈Vt,IF ch=Yi THEN READ NEXT ch ELSE ERROR (当读的字符与符号匹配时，则读下一个。否则报错。) 特例：U→x1|x2|...|Xn|ε IF ch IN FOLLOW(U) THEN RETURN 从A程序中出来到上一级 如前（3）：ELSE IF ch=yi THEN... ELSE ch∈Vn THEN . . . . . . . 新疆大学信息科学与工程学院

4.4.1 递归子程序法 例：G[S]:S→aBC,B→bC|dB|ε,C→c|a ① SELECT(S→aBC)={a} 4.4.1 递归子程序法 例：G[S]:S→aBC,B→bC|dB|ε,C→c|a ① SELECT(S→aBC)={a} SELECT(B→bC)={b} SELECT(B→dB)={d} SELECT(B→ε)=FOLLOW(B)=FIRST(C)={c,a} SELECT(C→c)={c} SELECT(C→a)={a} ②相同左P的SELECT集两两相交，都为空 ∴G[S]是LL（1）文法 新疆大学信息科学与工程学院

4.4.1 递归子程序法 ③ P[S]:SCIN’子程序入口函数入栈 ↓ P(B) Ch=a? Y N ch IN FOLLOW(B) 4.4.1 递归子程序法 ③ P[S]:SCIN’子程序入口函数入栈 ↓ P(B) Ch=a? Y N ch IN FOLLOW(B) N Y READ ch=#? Y N ERROR ch=b? RETURN P(B) N Y P(C) ch=d? READ N Y SCOUT ‘ 子程序出口函数，弹出栈 ch=#? P(B） READ P(C) N Y ERROR SCOUT 新疆大学信息科学与工程学院

4.4.1 递归子程序法 P(C):SCIN 判断输入串是否是文法的句子： Ch=c? ①从开始符的子程序进入P（S）的SCIN 4.4.1 递归子程序法 P(C):SCIN 　　　 判断输入串是否是文法的句子： Ch=c? ①从开始符的子程序进入P（S）的SCIN Y N ②调用 READ ch=a? ③从开始符的SCOUT则句子正确 Y N ch=#? 例如： READ Y N　　　　　 ａｂｃ＃　　√ ERROR ａｃａ＃　　× SCOUT ａｂ　　　 × 新疆大学信息科学与工程学院

4.4.2 预测分析方法 Input # 总控程序 预测分析表 stack 新疆大学信息科学与工程学院

4.4.2 预测分析方法 例：G[ E]: (1) E  TE’ (2) E’  +TE’ (3) E’   (4) T  FT’ 4.4.2 预测分析方法 例：G[ E]: (1) E  TE’ (2) E’  +TE’ (3) E’   (4) T  FT’ (5) T’  *FT’ (6) T’   (7) F  (E) (8) F  i 新疆大学信息科学与工程学院

4.4.2 预测分析方法 1.对文法G的每个产生式Ａ 执行第二步和第三步； 4.4.2 预测分析方法 1.对文法G的每个产生式Ａ 执行第二步和第三步； 2.对每个终结符aFIRST()，把Ａ 加至[A,a]中， 3.若 FIRST()，则对任何bFOLLOW(A)把Ａ 加至[A,b]中， 4.把所有无定义的[A,a]标上“出错标志”。 新疆大学信息科学与工程学院

4.4.2 预测分析方法 例 G[E]:E→E+T|T,T→T*F|F,F→(E)|i 4.4.2 预测分析方法 例 G[E]:E→E+T|T,T→T*F|F,F→(E)|i ①消除直接左递归：G`[F]:E→TE‘ E'→+TE'|ε, T→FT‘ T'→*FT'|ε F→(E)|i ② FIRST(E)=FIRST(T)=FIRST(F)={(,i} FIRST(E')={+, ε}. FIRST(T)={(,　i}. FIRST(T')={*, ε}. FIRST(F)={（,　i}. FOLLOW(E)={#}∪｛）｝=｛#,　)} FOLLOW(E')=FOLLOW(E)=｛#,　)} FOLLOW(T)=FIRST(E')＼ ε∪FOLLOW（E）∪FOLLOW（E'）={+,　#,　)} FOLLOW(T')=FOLLOW(T)={+,　#,　)　} FOLLOW(F)=FIRST(T')＼ ε∪FOLLOW(T)∪FOLLOW(T’)=｛*，+，#，）｝ 新疆大学信息科学与工程学院

4.4.2 预测分析方法 例 G[E]:E→E+T|T,T→T*F|F,F→(E)|i ①消除直接左递归 4.4.2 预测分析方法 例 G[E]:E→E+T|T,T→T*F|F,F→(E)|i ①消除直接左递归 ②SELECT(E→TE')=FIRST(T')=FIRST(T)={（,　i　} SELECT(E'→+TE')={+} SELECT(E'→ε)=FOLLOW(E')={#,　)　} SELECT(T→FT')=FIRST(F)={(,　i} SELECT(T'→*FT')={*} SELECT(T'→ε）=FOLLOW(T')={+,　#,　)　} SELECT(F→(E))={(｝ SELECT(F→i）={i} ③看相同左部的SELECT集相交都是空集 所以该文法是LL（１）文法。 新疆大学信息科学与工程学院

4.4.2 预测分析方法 ④画出分析表 ＬＬ（１）分析表： ＋ ＊ ( ) i # E →TＥ＇ E’ +TE’ →ε T T’ →＊ＦＴ＇ 4.4.2 预测分析方法 ④画出分析表 ＬＬ（１）分析表： ＋ ＊ ( ) i # E →TＥ＇ E’ +TE’ →ε T T’ →＊ＦＴ＇ F →（Ｅ） →ｉ 新疆大学信息科学与工程学院

4.4.2 预测分析方法 ⑤看表中是否有重叠，此题无 ⑥总控工作过程：总控程序是根据分析栈的栈顶符号X，当前输入符号a,决定下一个动作 4.4.2 预测分析方法 ⑤看表中是否有重叠，此题无 ⑥总控工作过程：总控程序是根据分析栈的栈顶符号X，当前输入符号a,决定下一个动作 算法： （1）分析栈顶放一个“#”，再放文法开始符，反复执行步骤（2） （2）设定分析的某一步，对于任何（x,a),总控程序执行下述三种可能之一： a.如果x=a=“#”,则宣布分析成功，停止分析过程 b.如果x=a≠"#”，则将x出栈，让a指向下一个输入符号 c.如果x∈Vn，查看分析表M，若M[x,a]中存放关于x的一个产生式，首先将x出栈，再将产生式的右P符号串按逆序一一推进栈，（若右部符号为 ，则不进栈），若M[x,a]中存放着“出错标志”，则报错 新疆大学信息科学与工程学院

4.4.2 预测分析方法 BEGIN 首先把’#‘然后把文法开始符号推入栈；把第一个输入符号读进a; FLAG：=TRUE； 4.4.2 预测分析方法 BEGIN 首先把’#‘然后把文法开始符号推入栈；把第一个输入符号读进a; FLAG：=TRUE； WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在Ｘ中； IF X  Vt THEN IF X=a THEN 把下一个输入符号读进a 　 ELSE ERROR ELSE IF X=‘#’ THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF [X,a]={XX1X2..XK} THEN 把XK，X K-1,..,X1一一推进栈 ELSE　ERROR END OF WHILE; STOP/*分析成功，过程完毕*／ END 新疆大学信息科学与工程学院

4.4.2 预测分析方法 i+i*i# 是该文法的正确句子 步骤 分析栈 输入串 1 #E i+i*i# 2 #E'T i+i*i# 4.4.2 预测分析方法 步骤 分析栈 输入串 1 #E i+i*i# 2 #E'T i+i*i# 3 #E'T'F i+i*i# 4 #E'T'i i+i*i# 5 #E'T' +i*i# 6 #E' +i*i# 7 #E'T+ +i*i# 8 #E'T i*i# 9 #E'T'F i*i# 10 #E'T'i i*i# 11 #E'T' *i# 12 #E'T'F* *i# 13 #E'T'F i# 14 #E'T'i i# 15 #E'T' # 16 #E' # 17 # # i+i*i# 是该文法的正确句子 新疆大学信息科学与工程学院

5、自底向上优先分析 自底向上语法分析概述 简单优先分析 算符优先分析 新疆大学信息科学与工程学院

教 学 目 的 5、自底向上语法分析 了解自底向上优先分析方法 熟练运算FIRSTVT集和LASTVT集 掌握算符优先分析方法 新疆大学信息科学与工程学院

5、自底向上语法分析 重点与难点 重点是算法优先关系表的构造、算法优先分析算法。 难点是算法优先文法的判定。 新疆大学信息科学与工程学院

5.1 自底向上语法分析概述 自下而上语法分析比自上而下语法分析更有效率，对语法的限制更少 5.1 自底向上语法分析概述 <程序> VAR A; BEGIN READ(A) END. <分程序> <语句> <复合语句> 自下而上语法分析比自上而下语法分析更有效率，对语法的限制更少 <语句> <变量说明部分> <读语句> 如名字如示，自下而上语法分析试图将一个字符串反向归约至开始符号。 <标识符> <标识符> VAR A ； BEGIN READ （ A ） END . 新疆大学信息科学与工程学院

5.1 自底向上语法分析概述 文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 5.1 自底向上语法分析概述 文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 思考： 分析符号串abbcde是否是G[S]的句子    S S aABe A aAde B A aAbcde a b b c d e abbcde 新疆大学信息科学与工程学院

5.1 自底向上语法分析概述 S S aABe A aAde aAbcde B A abbcde a b b c d e 5.1 自底向上语法分析概述    S S aABe A aAde aAbcde B A abbcde a b b c d e 新疆大学信息科学与工程学院

5.1 自底向上语法分析概述 A A S B a b b c d e S  aAcBe aAcde aAbcde abbcde 步骤 5.1 自底向上语法分析概述 步骤 符号栈 输入符号串 动作 1） # abbcde# 移进 2） #a bbcde# 移进 A 3） #ab bcde# 归约(A→b) 4） #aA bcde# 移进 A 5） #aAb cde# 归约(A→Ab) S 10） #aAcBe # 归约(S→aAcBe) 6） #aA cde# 移进 7） #aAc de# 移进 B 8） # aAcd e# 归约(B→d) 9） #aAcB e# 移进 11） #S # 接受 a b b c d e 对输入串abbcde#的移进-规约分析过程 S  aAcBe aAcde aAbcde abbcde 新疆大学信息科学与工程学院

5.1 自底向上语法分析概述 移进 就是将一个终结符推进栈 规约 自下而上语法分析的策略：移进-规约分析 5.1 自底向上语法分析概述 自下而上语法分析的策略：移进-规约分析 移进 就是将一个终结符推进栈 规约 就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈 移进-归约 是自顶向下最右推导的逆过程（规范归约）过程 新疆大学信息科学与工程学院

5.1 自底向上语法分析概述 优先分析法 LR分析 简单优先分析法 算符优先分析法 新疆大学信息科学与工程学院 优先分析 算符优先分析 5.1 自底向上语法分析概述 优先分析法 简单优先分析法 算符优先分析法 LR分析 优先分析 算符优先分析 简单优先分析 LR分析 LR(1) SLR(1) LALR(1) LR(0) 新疆大学信息科学与工程学院

5.2 简单优先分析 按照文法符号（包括终结符和非终结符）的优先关系确定句柄。 步骤 符号栈 输入符号串 动作 5.2 简单优先分析 按照文法符号（包括终结符和非终结符）的优先关系确定句柄。 文法G[S]： (1) S → bAb (2) A → (B|a (3) B → Aa) 步骤 符号栈 输入符号串 动作 1） # b(aa)b# #<b,移进 2） #b (aa)b# b<(,移进 3） #b( aa)b# (<a,移进 4） #b(a a)b# a>a,归约A→a 5） #b(A a)b# A=a,移进 6） #b(Aa )b# a=),移进 7） #b(Aa) b# )>b,归约B→Aa) 8） #b(B b# B>b,归约A→(B 9） #bA b# A=b,移进 10） #bAb # b>#,归约S→bAb 11） #S # 接受 简单优先关系矩阵 对输入串b(aa)#的简单优先分析过程 新疆大学信息科学与工程学院

5.3 算符优先分析 某些文法具有“算符”特性 只考虑算符之间的优先关系来确定句柄 表达式运算符（优先级、结合性） 5.3 算符优先分析 某些文法具有“算符”特性 表达式运算符（优先级、结合性） 人为地规定其算符的优先顺序，即给出优先级 别和同一级别的结合性 只考虑算符之间的优先关系来确定句柄 新疆大学信息科学与工程学院

5.3 .1 算符文法 定义 如果不含空产生式的上下文无关文法 G 中 没有形如 V…VW…的产生式，其中V,W∈VN则称G 为算符文法（OG）。 性质1：在算符文法中任何句型都不包含两个相邻的 非终结符.(数学归纳法) 性质2：如 Vx 或 xV 出现在算符文法的 句型  中，其中V∈VN,x∈VT, 则  中任何 含 x 的短语 必含有V.（反证法） 新疆大学信息科学与工程学院

5.3 .2 算符优先文法 在 OG文法 G 中，若任意两个终结符间至多有一种算符优先关系存在，则称G 为算符优先文法(OPG)。 5.3 .2 算符优先文法 在 OG文法 G 中，若任意两个终结符间至多有一种算符优先关系存在，则称G 为算符优先文法(OPG)。 结论 算符优先文法是无二义的。 小贴士1： 允许b> c, c>b;不允许b>c , b<c , b=c 新疆大学信息科学与工程学院

5.3 .3 算符优先关系表的构造 首先引入两个概念 FIRSTVT(B)={b|B b…或B Cb...} 5.3 .3 算符优先关系表的构造 首先引入两个概念 FIRSTVT(B)={b|B b…或B Cb...} 对于非终结符B，其往下推导所可能出现的 首个算符 LASTVT(B)={a|B a…或B aC...} 对于非终结符B，其往下推导所可能出现的 最后一个算符 新疆大学信息科学与工程学院

5.3 .3 算符优先关系表的构造 寻找算符优先关系关系 ‘=’关系 ‘<’关系 ‘>’关系 5.3 .3 算符优先关系表的构造 寻找算符优先关系关系 ‘=’关系 直接看产生式的右部，若出现了 A →…ab…或A →…aBb, 则a=b ‘<’关系 求出每个非终结符B的FIRSTVT(B) 若A→…aB…, 则b∈FIRSTVT(B), a<b ‘>’关系 求出每个非终结符B的LASTVT(B) 若A→…Bb…, 则a∈LASTVT(B), a>b 新疆大学信息科学与工程学院

5.3 .3 算符优先关系表的构造 1)‘=’关系 由产生式(0)和(6),得 #=#，（=） 2）‘<’关系 找形如：A→…aB…的产生式 #E：则#<FIRSTVT(E) +T: 则+<FIRSTVT(T) *F: 则*<FIRSTVT(F) F:则 <FIRSTVT(F) (E: 则 (<FIRSTVT(E) 例：文法G[E]： (0) E’→#E# (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→PF|P (6) P→(E) (7) P→i 3)‘>’关系 找形如：A→…Bb…的产生式 E# ,则 LASTVT(E)># E+ ,则 LASTVT(E)>+ T* ,则 LASTVT(T)>* P ,则 LASTVT(P)> E) ,则 LASTVT(E)>) 新疆大学信息科学与工程学院

5.3 .3 算符优先关系表的构造 FIRSTVT(E’)={#} FIRSTVT(E)={+,*,,(, i} FIRSTVT(T)={*,,(,i} FIRSTVT(F)={,(,i} FIRSTVT(P)={(,i} LASTVT(E’)={#} LASTVT(E)={+,*,,),i } LASTVT(T)={*,,),i} LASTVT(F)={,),i} LASTVT(P)={),i} 新疆大学信息科学与工程学院

5.3 .4 算符优先分析算法 设G[S]=(Vn,Vt,P,S)为算符优先文法 （1）由文法G（S）构造优先关系矩阵。 5.3 .4 算符优先分析算法 设G[S]=(Vn,Vt,P,S)为算符优先文法 （1）由文法G（S）构造优先关系矩阵。 （2）设置一个符号栈S。存放已规约的或待形成最左素短语的符号串，另设一个工作单元R，存放当前的待输入符号。 （3）用移进—规约的方法，当符号栈S的栈顶形成不规约串—最左素短语时，进行规约，具体方法如下： ①分析开始时，S中只有一个符号“＃”，R中存放输入串（源程序）的第一个终结符。 ②查优先关系矩阵，比较符号栈中最靠栈顶的终结符（假设为a）与R中的终结符（假设为b）的优先关系： 1）若a，b之间无优先关系，则出错并退出分析程序。 2）若a<·b或a=·b，则将b进栈，指针后移，R中存放下一个待输入终结符，重复②。 3）若a·>b，则表明此时栈顶已形成最左素短语（且其右界已空）转③ 新疆大学信息科学与工程学院

5.3 .4 算符优先分析算法 ③从S中普栈顶的终结符Xn开始，依次向前（向栈底方向）与最远的终结符比较，若Xn-1=Xn，则继续比较Xn-2和Xn-1，如比较反复，直至Xi-1<Xi，（i=1，2，…，n设X0=#）为止。 于是最左来短语的左界已确定，此时最古来短语为从Ni开始（Ni为在Xi之前临Xi的非终结符，若为Ni=ε，则从Xi开始）一直到找顶的符号串：Ni、Xi、Ni+1、Xi+1、…Nn、Xn、Nn+1。 ④文法G［S］的产生式集中，选择其右P具有NiXiNi+1Xi+1…NnXnNn+1形式的规则进行归约（注意：此时非终结符号不必完全相同）：弹击符号栈栈顶的最左来短语相应规则的左部非终结进栈，若此时分析栈中只有#和文法的一个非终结符，且待分析符号串只剩#（即R中符号为#），则表明分析成功，所分析的串是文法句子退出分析程序；否则，重复②。 新疆大学信息科学与工程学院

5.3 .4 算符优先分析算法 例2、G［S］：S→D（R）｜DR→R;P｜P P→S｜i D→i 分析i（i；i） 5.3 .4 算符优先分析算法 例2、G［S］：S→D（R）｜DR→R;P｜P P→S｜i D→i 分析i（i；i） （1） F1RSTVT（S）=﹛(﹜∪FIRSTVT（D）=﹛(，i﹜ F1RSTVT（R）=﹛;﹜∪FIRSTVT（P）=﹛;，(，i﹜ F1RSTVT（P）= FIRSTVT（S）∪﹛i﹜=﹛(，i﹜ FIRSTVT（D）=﹛i﹜ LASTVT（S）=﹛)﹜∪LASTVT（D）=﹛)， i﹜ LASTVT（R）=﹛;﹜∪LASTVT（P）=﹛;， i，)﹜ LASTVT（R）=﹛i﹜∪LASTVT（S）=﹛i，)﹜ LASTVT（D）=﹛i﹜ （2）加一条S＇→# S # （=） (<• F1RSTVT（R） LASTVT（D）·>( # = # <· ;<• F1RSTVT（P） ·> LASTVT（R）·>） #<• F1RSTVT（S） LASTVT（R）·>; LASTVT（R）·># 新疆大学信息科学与工程学院

5.3 .4 算符优先分析算法 此串是文法的句子 此文法是算符优先文法 ③ 步骤 符号栈 输入串 1 # i(i;i)# 5.3 .4 算符优先分析算法 此串是文法的句子 ③ 步骤 符号栈 输入串 1 # i(i;i)# 2 #i (i;i)# i·>( #<·i 则i归约 3 #P或#D (i;i)# # <·（ 4 #P（ i;i)# 5 #P（i ;i# i·>j ( <·I ∴i 归约 6 #P（P ;i）# (<·j 7 #P（P; i）# 8 #P（P;i ）# i·>) j <·i ∴i 归约 9 #P（P;P ）# j·>) (<·j ∴P ; P 归约 10 #P(R ）# (=) 11 #P(R) # )·>#, (=),#<·(∴(R) 归约 12 #S # 此文法是算符优先文法 新疆大学信息科学与工程学院

5.3 .5 最左素短语 归约过程中，只考虑终结符之间的优先 关系来确定句柄，而与非终结符无关。 这样去掉了单非终结符的归约，所以用 算符优先分析法的规约过程与规范归约 是不同的。 为解决在算符优先分析过程中如何寻找 句柄，引进最左素短语的概念。 新疆大学信息科学与工程学院

5.3 .5 最左素短语 算符文法的任一句型有如下形式： #N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1为句柄， 则有 ai-1<ai=ai=...= aj-1 = aj> ai+1 对于算符优先文法，如果aNb(或ab)出现在句型r中 若a<b，则在r中必含有b而不含a的短语存在 若a>b，则在r中必含有a而不含b的短语存在 若a=b，则在r中含有a的短语必含有b，反之亦然 定义 G 的句型的素短语是一个短语，它至少包含一 个终结符，且除自身外不再包含其他素短语。处于句 型最左边的素短语为最左素短语。 新疆大学信息科学与工程学院

5.3 .5 最左素短语 最左素短语和句柄的区别： 例：G[E]: EE+TT E E+E E*E (E) id 5.3 .5 最左素短语 最左素短语和句柄的区别： 例：G[E]: EE+TT E E+E E*E (E) id T T*FF F (E) id E + T * F id E + * id 新疆大学信息科学与工程学院

5.3 .5 最左素短语 小贴士：算符优先分析法的局限性 5.3 .5 最左素短语 文法G[E]： (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→PF|P (6) P→(E) (7) P→i E T + F * i 句型#T+T*F+i# 其短语有： T+T*F+i T+T*F T T*F i 最左素短语为：T*F 句型#N+N*N+i#的归约过程 N + i * 小贴士：算符优先分析法的局限性 一般语言的方法很难满足算符优先文法的条件 很难避免把错误的句子得到正确的归约 新疆大学信息科学与工程学院

6、LR分析 LR分析概述 LR(0) 分析 SLR(1) 分析 LR(1)分析 LALR(1)分析 新疆大学信息科学与工程学院

教 学 目 的 6、LR分析 了解二义性文法在LR分析中的应用 熟练LR项目集规范族的构造和LR分析器的工作过程 掌握LR（0）分析、SLR（1）分析、LR（1）分析及LALR（1）分析 新疆大学信息科学与工程学院

重点与难点 5、自底向上语法分析 重点是LR(0)分析、SLR(1)分析、LR(1)分析、LALR(1)分析。 新疆大学信息科学与工程学院

6.1 LR分析概述 LR分析法自底向上规范归约，不带回溯，准确，每步都是对当前句型找句柄。 L：从左到右扫描. R：最右推导的逆过程. K：向前看的符号数 　　LR分析方法是当前最广义的无回溯的“移进- 归约”方法。根据栈中的符号串和向右顺序查看输入串的k(k0)个符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。 大多数上下文无关文法（二型文法）都是LR类文法，对文法的限制少，但同时对它的分析也相应最复杂。 新疆大学信息科学与工程学院

6.1 LR分析概述 LR（0）：最简单，对文法的限制多，所以多数文法都不是LR（0） SLR（1）：S简单，向前看一个符号，实现容易，有使用价值。 LR（1）：多数二型文法都是LR（1），能力最强，分析表体积大，占用空间大，代价高。 LALR（1）：适用文法广，可以解决SLR（1）解决不了的问题，同时也克服LR（1）存储容易过大的缺点。 新疆大学信息科学与工程学院

6.1 LR分析概述 一个LR分析器由3个部分组成: （1）总控程序，也可以称为驱动程序。 （2）分析表或分析函数。 （3）分析栈，包括文法符号栈和相应的状态栈。 分析器的动作由栈顶状态和当前输入符号所决定（LR(0)分析器不需向前查看输入符号）。 LR分析器工作过程示意图如下图所示。 新疆大学信息科学与工程学院

6.1 LR分析概述 SP 其中SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表内容按关系GOTO[Si，X]=Sj确定。ACTION[Si，a]规定了栈顶状态为时遇到输入符号a应执行的动作。 输入串XXX…# 总控程序 ACTION表 GOTO表 Xn . X1 # Sn S1 S0 新疆大学信息科学与工程学院

6.1 LR分析概述 文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 步骤 符号栈 输入符号串 动作 状态栈 ACTION 对输入串abbcde#的 LR分析过程 GOTO 1） # abbcde# 移进 0 S2 2） #a bbcde# 移进 02 S4 3） #ab bcde# 归约(A→b) 024 r2 3 4） #aA bcde# 移进 023 S6 5） #aAb cde# 归约(A→Ab) 0236 r3 3 6） #aA cde# 移进 023 S5 7） #aAc de# 移进 0235 S8 8） # aAcd e# 归约(B→d) 02358 r4 7 9） #aAcB e# 移进 02357 S9 10） #aAcBe # 归约(S→aAcBe) 023579 r1 1 Si:移进，并将状态i进栈 ri:用第i个产生式归约，同时状态栈与符号栈退出相应个符号，根据GOTO表将相应状态入栈 11） #S # 接受 01 acc 文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 新疆大学信息科学与工程学院

6.1 LR分析概述 S’ A 是文法G中的一个规范推导，如果符号串是的前缀，则称是G的一个活前缀。 例： ab aAb aAcd aAcBe ,a,ab  ,a,aA,aAb  ,a,aA,aAc,aAcd  ,a,aA,aAc,aAcB,aAcBe LR分析需要构造识别活前缀的有穷自动机 　　我们可以文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态。 新疆大学信息科学与工程学院

6.2 LR(0)分析 小贴士：有限自动机的每一个状态由一个项目构成。 1、项目：在每个产生式的右部适当位置添加一个圆点构成项目 例如：G[S′]： S′→S S→（S）S S→ε S′→.S S→.（S）S S →. S′→S. S→（.S）S S→（S.）S S→（S）.S S→（S）S. 共8个项目 小贴士：有限自动机的每一个状态由一个项目构成。 新疆大学信息科学与工程学院

6.2 LR(0)分析 项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表示待识别的部分。 　　项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表示待识别的部分。 　　构造识别活前缀的NFA： 1、把文法的所有产生式的项目都引出，每个项目都为NFA的一个状态 2、确定初态、句柄识别态、句子识别态 3、确定状态之间的转换关系 *若项目i为 X → X1X2...Xi-1 • Xi...Xn 项目j为 X → X1X2...Xi-1 Xi • Xi+1...Xn 则从状态i到状态j连一条标记为Xi的箭弧 *若i为X → • A，k为A → • ，则从状态i画标记为  的箭弧到状态k 新疆大学信息科学与工程学院

6.2 LR(0)分析 根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种： 移进项目，形如 A → • a 　　根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种： 移进项目，形如 A → • a 待约项目，形如 A → • B 归约项目，形如 A → • 接受项目，形如 S’ →S • 新疆大学信息科学与工程学院

6.2 LR(0)分析 2、项目集规范族：构成识别一个文法活前缀的DFA项目集（状态）的全体。 　　NFA确定化为DFA的工作量较大，我们考虑直接构造出项目集作为DFA的状态，就可直接构造DFA。 　　通过闭包函数(CLOSURE)来求DFA一个状态的项目集。 新疆大学信息科学与工程学院

6.2 LR(0)分析 　　如果I是文法G’的一个项目集，定义和构造I的闭包CLOSURE(I)如下： a)I的项目都在CLOSURE(I)中 b)若A→ • B属于CLOSURE(I)，则每一形如B→• 的项目也属于CLOSURE(I) c)重复b)直到CLOSURE(I)不再扩大 　　定义转换函数如下： GOTO（I，X）= CLOSURE（J） 其中：I为包含某一项目集的状态，X为一文法符号 J={任何形如A→X • 的项目| A→ • X 属于I} 新疆大学信息科学与工程学院

6.2 LR(0)分析 　　圆点不在产生式右部最左边的项目称为核，唯一的例外是S’ → • S。因此用GOTO（I，X）转换函数得到的J为转向后状态所含项目集的核。 　　使用闭包函数（CLOSURE）和转向函数(GOTO(I,X))构造文法G’的LR(0)的项目集规范族，步骤如下： a)置项目S’→ • S为初态集的核，然后对核求闭包CLOSURE（{S’→ • S}）得到初态的项目集 b)对初态集或其它所构造的项目集应用转换函数GOTO(I，X)= CLOSURE(J)求出新状态J的项目集 c)重复b)直到不出现新的项目集为止 新疆大学信息科学与工程学院

6.2 LR(0)分析 一个项目集可能包含多种项目 a) 移进和归约项目同时存在。移进-归约冲突 　　一个项目集可能包含多种项目 a) 移进和归约项目同时存在。移进-归约冲突 b) 归约和归约项目同时存在。归约-归约冲突 　　LR(0)文法：若其LR(0)项目集规范族不存在移进-归约，或归约-归约冲突，称为LR(0)文法。 新疆大学信息科学与工程学院

6.2 LR(0)分析 3、分析表的构造： 令包含S‘→ • S 的项目集Ik的下标k为分析器的初态 LR(0)分析表的ACTION和GOTO表的构造步骤如下： a) 若项目A→ • a属于Ik，且转换函数GO(Ik,a)= Ij ，当a为终结符时，则置ACTION[k,a]为Sj b) 若项目A→ •属于Ik ，则对a为任何终结符或‘#’，置ACTION[k,a] = rj ，j为产生式在文法G‘中的编号 c) 若GO(Ik,A)= Ij ，则置GOTO[k,A]=j，其中A为非终结符，j为某一状态号 d) 若项目S‘→S •属于Ik ，则置ACTION[k,#] = acc e) 其它填上“报错标志” 新疆大学信息科学与工程学院

6.2 LR(0)分析 a c d b 例:G[S]： S→aAcBe A→b A→Ab S B→d 先加拓广 e S＇→S B A I0 S＇→.S S→.aAcBe I2 S→a.AcBe A→.b A→.Ab A→b. I1 S＇→S. I3 S→aA.cBe A→A.b I5 S→aAc.Be B→.d I9 S→aAcBe. a b S A I8 S→aAcB.e c B e I6 A→Ab. I7 B→d. d 新疆大学信息科学与工程学院

6.2 LR(0)分析 ( ) a 例：（0） A‘→A （1）A→（A） （2）A→a I0 A＇→.A A→.(A) A→.a I A＇→A. I2 A→(.A) ( I4 A→(A.) I5 A→(A). A ) I3 A→a. a 新疆大学信息科学与工程学院

6.2 LR(0)分析 状态 ACTION GOTO （ ） a # A S2 S3 1 acc 2 4 3 r2 S5 5 r1 空白处为error. ∵没有移—归或归—归冲突 ∴此文法是LR（0）文法 状态 ACTION GOTO （ ） a # A S2 S3 1 acc 2 4 3 r2 S5 5 r1 新疆大学信息科学与工程学院

6.2 LR(0)分析 此串为文法的句子. 步骤 状态栈 符号栈 输入串 1 0 # （（a））# 2 02 #( （a））# 步骤 状态栈 符号栈 输入串 1 0 # （（a））# 2 02 #( （a））# 3 022 #(( a））# 4 0223 #((a ））# 5 0224 #((A ））# 6 02245 #((A) ）# 7 024 #(A ）# 8 0245 #(A) # 9 01 #A # acc 新疆大学信息科学与工程学院

6.2 LR(0)分析 存在移进-规约冲突 状态 a d b # A 1 2 r 3/s2 r 3 r 3 r 3 …… ..acc …… 1 2 r 3/s2 r 3 r 3 r 3 …… ..acc …… 3 3 S4 S5 4 r 1 5 r 2 新疆大学信息科学与工程学院

6.3 SLR(1)分析 思考： 大多数适用的程序设计语言的文法不能满足LR(0)文法的条件，即其规范族中会有含有冲突的项目集（状态） 如何解决这种冲突？ 大多数适用的程序设计语言的文法不能满足LR(0)文法的条件，即其规范族中会有含有冲突的项目集（状态） 提示：对于有冲突的状态，向前查看一个符号，以确定采用的动作 新疆大学信息科学与工程学院

6.3 SLR(1)分析  例：文法G‘： (0) S’  S (1) S  rD (2) D D,i (3) D  i , I0: S‘ → • S S‘ → •rD I2: S → r•D D → •D,i D → • i I3: S → rD • D →D •,i I4: D → i • I5: D → D,•i I1: S‘ → S • I6: D →D,i • S r i D ,  LR(0)分析表 新疆大学信息科学与工程学院

6.3 SLR(1)分析 I3: S → rD • D →D •,i SLR(1)分析表 s-r冲突 向前查看一个符号，看其是否是S的后跟符号（FOLLOW(S)）,若否则移进，是则归约。 SLR(1)分析表 新疆大学信息科学与工程学院

6.3 SLR(1)分析 　　一个LR(0)规范族中含有如下的项目集（状态）I I = {X → • b , A → • , B → • } 若有：FOLLOW(A) ∩FOLLOW(B) = Ø FOLLOW(A) ∩{b} = Ø FOLLOW(B) ∩{b} = Ø 　　状态I面临某输入符号a 1) 若a=b，则移进 2) 若aFOLLOW(A), 则用产生式 A → 进行归约 3) 若aFOLLOW(B), 则用产生式 B → 进行归约 4) 此外，报错 　　若一个文法的LR(0)分析表中所含有的动作冲突都能用上述方法解决，则称这个文法是SLR(1)文法 新疆大学信息科学与工程学院

6.3 SLR(1)分析 “改进的”SLR(1)分析： 　　对所有非终结符都求出其FOLLOW集合，这样只有归约项目仅对面临输入符号包含在该归约项目左部非终结符的FOLLOW集合中，才采取用该产生式归约的动作。 　　改进的SLR(1)分析表的ACTION表和GOTO表的构造步骤： a) 若项目A→ • a属于Ik，且转换函数GO(Ik,a)= Ij ，当a为终结符时，则置ACTION[k,a]为Sj b) 若项目A→ •属于Ik ，则对a为任何终结符或‘#’，且满足aFOLLOW(A)时，置ACTION[k,a] = rj ，j为产生式在文法G‘中的编号 c) 若GO(Ik,A)= Ij ，则置GOTO[k,A]=j，其中A为非终结符，j为某一状态号 d) 若项目S‘→S •属于Ik ，则置ACTION[k,#] = acc e) 其它填上“报错标志” 新疆大学信息科学与工程学院

6.3 SLR(1)分析 T→Sc. S→Uta. S＇→.S S→.UTa S→.Tb U→.US T U→.e T→.S T→.Sc 例: (0) S＇→S (1) S→UTa (2)S→Tb (3)U→US (4)U→e (5)T→S (6)T→Sc (7)T→d 是否为LR（0），若是画分析表，是否是SLR（1）。 I0 S＇→.S S→.UTa S→.Tb U→.US U→.e T→.S T→.Sc T→.d I1 S＇→S. T→S. T→S.c I2 S→U.Ta T→.d S→.UTa U→U.S U→.US S→.Tb T→.S U→.e S U I5 T→d. I4 U→e. d e I7 S→UT.a S→T.b I8 U→US. I6 T→Sc. I9 S→Uta. T c I3 I10 S→Tb. b 新疆大学信息科学与工程学院

6.3 SLR(1)分析 小贴士： 仍有许多文法构造的LR(0)项目集规范族存在的动作冲突不能用SLR(1)方法解决 FOLLOW(S)={#}∪FOLLOW (U)∪FOLLOW (T)∪{c}={#,e,d,a,b,c} FOLLOW(U)=FIRST(T)∪FIRST(S)={d,e} FollOW(T)={a,b} a b c d e # U T S S5 S4 2 3 1 r5 S6 acc 7 8 S10 4 r4 5 r7 6 r6 S9 r3 9 r1 10 r2 小贴士： 仍有许多文法构造的LR(0)项目集规范族存在的动作冲突不能用SLR(1)方法解决 新疆大学信息科学与工程学院

6.4 LR(1)分析 若项目集[A→•B]属于I时，则[B→•]也属于I 把FIRST()作为用产生式归约的搜索符（称为向前搜索符），作为用产生式B→归约时查看的符号集合（用以代替SLR(1)分析中的FOLLOW集），并把此搜索符号的集合也放在相应项目的后面，这种处理方法即为LR(1)方法 新疆大学信息科学与工程学院

6.4 LR(1)分析 LR(1)项目集族的构造：针对初始项目S’→•S,#求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族。 　　1）构造LR（1）项目集的闭包函数 a)I的项目都在CLOSURE(I)中 b)若A→ • B，a属于CLOSURE(I)， B→ 是文法的产生式，V*，bFIRST(a),则B→• ,b也属于CLOSURE(I) c)重复b)直到CLOSURE(I)不再扩大 　　2)　转换函数的构造 GOTO（I，X）= CLOSURE（J） 其中：I为LR(1)的项目集，X为一文法符号 J={任何形如A→X • ,a的项目| A→ • X ,a属于I} 新疆大学信息科学与工程学院

思考：查看I3 ，I7中的冲突，体会LR(1)如何解决？ S’ ® • S, # S  • aAd, # S  • bAc, # S  • aec, # S  • bed, # 文法G‘： (0) S’  S (1) S  aAd (2) S  bAc (3) S  aec (4) S  bed (5) A  e I1: S’ ® S •, # I2: S  a •Ad, # S  a • ec, # A  • e, d I3: S  b • Ac, # S  b • ed, # A  • e, c I4: S  aA • d, # I5: S  ae • c, # A  e •, d I6: S  bA • c, # I7: S  be • d, # A  e •, c I8: S  aAd •, # I9: S  ae c •, # I10: S  bAc •, # I11: S  bed •, # 　　　思考：查看I3 ，I7中的冲突，体会LR(1)如何解决？ 新疆大学信息科学与工程学院

6.4 LR(1)分析 　　LR(1)分析表的构造 1) 若项目[A→ • a,b]属于Ik，且转换函数GO(Ik,a)= Ij ，当a为终结符时，则置ACTION[k,a]为Sj 2) 若项目[A→ • ,a]属于Ik ，则对a为任何终结符或 ‘#’，置ACTION[k,a] = rj ，j为产生式在文法 G‘中的编号 3) 若GO(Ik,A)= Ij ，则置GOTO[k,A]=j，其中A为非终 结符，j为某一状态号 4) 若项目[S‘→S • ,#]属于Ik ，则置ACTION[k,#] = acc 5) 其它填上“报错标志” 新疆大学信息科学与工程学院

6.4 LR(1)分析 例1.（0）L＇→L （1）E；L （2）L→E (3）E→a (4）E→b 是否为LR(1)文法 L＇→.L,# I0 L＇→.L,# L→.E;L,# L→.E,# E→.a,; E→.b,; E→.a,# E→.b,# I1 L＇→L.,# I2 L→E.;L,# L→E.,# I3 E→a.,; E→a.,# I4 E→b.,; E→b.,# I5 L→E;.L,# I6 L→E;L.,# L E a b ; 识别LR（1）活前缀的DFA LR（1）的项目集规范族 在I2中，上式碰到“；”移进 下式归约 ∴不产生冲突。 新疆大学信息科学与工程学院

6.4 LR(1)分析 状态 ACTION GOTO a b ; # L E S3 S4 1 2 acc S5 r2 3 r3 4 r4 5 S3 S4 1 2 acc S5 r2 3 r3 4 r4 5 6 r1 新疆大学信息科学与工程学院

6.4 LR(1)分析 分析 #a;b;a#是否为句子 判定该串是正确的句子 步骤 状态栈 符号栈 输入串 1 0 # a;b;a# 步骤 状态栈 符号栈 输入串 1 0 # a;b;a# 2 03 #a ;b;a# 3 02 #E ;b;a# 4 025 #E; b;a# 5 0245 #E;b ;a# 6 0252 #E;E ;a# 7 02525 #E;E; a# 8 025253 #E;E;a # 9 025252 #E;E;E # 10 025256 #E;E;L # 11 0256 #E;L # 12 01 #L # 判定该串是正确的句子 新疆大学信息科学与工程学院

6.4 LR(1)分析 小贴士： LR(1)项目集和转换函数 文法G‘： (0) S’  S (1) B  aB (2) S  BB (3) B  b I0: S’ ® • S, # S  • BB, # B  • aB, a/b B  • b, a/b I1: S’ ® S •, # I2: S  B • B, # B  • a B, # B  • b, # I5: S  B B •, # I6: S  a • B, # B  • aB, # I9: B  a B •, # I4: B  b •, a/b I3: B  a • B, a/b I8: B  a B •, a/b I7: B  b •, # S B b a 小贴士： LR(1)项目集的构造对某些同心集的分裂可能使状态数目剧烈的增长 LR(1)项目集和转换函数 新疆大学信息科学与工程学院

6.4 LR(1)分析 分析可发现I3和I6 ， I4和I7 ， I8和I9分别为同心集 I3: B  a • B, a/b B  • b, a/b I6: S  a • B, # B  • aB, # B  • b, # I3,6: S  a • B, a/b/# B  • aB, a/b/# B  • b, a/b/# 合并为 I4: B  b •, a/b I7: B  b •, # 合并为 I4,7: B  b •, a/b/# I9: B  a B •, # I8,9: B  a B •, a/b/# I8: B  a B •, a/b 合并为 新疆大学信息科学与工程学院

6.5 LALR(1)分析 对LR(1)项目集规范族合并同心集，若合并同心集后不产生新的冲突，则为LALR(1)项目集。 　　合并同心集的几点说明： 同心集合并后心仍相同，只是向前搜索符集合为各同心集超前搜索符的和集 合并同心集后转换函数自动合并 LR(1)文法合并同心集后也只可能出现归约-归约冲突，而没有移进-归约冲突 合并同心集后可能会推迟发现错误的时间，但错误出现的位置仍是准确的 新疆大学信息科学与工程学院

6.5 LALR(1)分析 合并同心集后 新疆大学信息科学与工程学院

总结 LR(0) SLR(1): 生成的LR(0)项目集如有冲突，则 根据非终结符的FOLLOW集决定 LR(1)、LR(k): 项由 心与向前搜索符组成， 搜索符长度为1或k LALR(1): 对LR(1)项目集规范族合并同心集 新疆大学信息科学与工程学院

总结 文法类的谱系 确定的文法 不确定的文法 LL(k) LR(k) LR(1) LL(1) LALR SLR LR(0) LL(0) 新疆大学信息科学与工程学院

7、语法制导翻译和中间代码生成 属性文法 语法制导翻译概论 中间代码的生成 新疆大学信息科学与工程学院

教 学 目 的 7、语法制导翻译和中间代码生成 了解属性文法、语法制导翻译概论 熟练进行简单赋值语句、布尔表达式、控制结构和说明语句的翻译 掌握中间代码的形式：逆波兰式、三元式、四元式 新疆大学信息科学与工程学院

重点与难点 7、语法制导翻译和中间代码生成 重点是中间代码的形式、简单赋值语句的翻译、布尔表达式的翻译。 难点是控制语句中布尔表达式的翻译。 新疆大学信息科学与工程学院

7.1 属性文法 属性：语言结构的特征 属性文法: 见后 语义规则：｛｝ 语义子程序：描述了一个产生式所对应的翻译工作。 7.1 属性文法 属性：语言结构的特征 i. type 变量数据类型 i. Val 变量，值 i. Add 变量，地址 文法符号属性：X.t 属性文法: 见后 语义规则：｛｝ 语义子程序：描述了一个产生式所对应的翻译工作。 新疆大学信息科学与工程学院

7.1 属性文法 属性文法(attribute grammar)是一个三元 组:A=(G,V,F),其中 G:是一个上下文无关文法 7.1 属性文法 　　属性文法(attribute grammar)是一个三元 组:A=(G,V,F),其中 G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一个终 结符或非终结符相连 F:关于属性的属性断言或谓词集.每个断言 与一个产生式相联.而此断言只引用该产生 式左端或右端的终结符或非终结符相联的属 性 新疆大学信息科学与工程学院

7.1 属性文法 属性值根据计算的依赖关系分成不相交的两类：综 合属性(synthesized attribute)和继承属性(inherited attribute)。 在分析树中，一个结点的综合属性值是从其子结点 的属性值计算出来的；而一个结点的继承属性值是 由该结点兄第结点和父结点的属性值计算出来的。 AX1 X2 …Xn A的综合属性,计算 S(A):=f(I(X1),…,I(Xn)) Xj的继承属性,计算 T(Xj):=f(I(A),... I(Xn)) 1)开始符号没有继承属性. 2)终结符只有综合属性. 新疆大学信息科学与工程学院

7.1 属性文法 例：简单算术表达式求值的语义描述。 综合属性val 语 义 规 则 L E E E1+T E T T T1 * F T F 7.1 属性文法 例：简单算术表达式求值的语义描述。 综合属性val 语 义 规 则 L E E E1+T E T T T1 * F T F F (E) F digit Print(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val  F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval 产 生 式 新疆大学信息科学与工程学院

7.1 属性文法 惟独只使用综合属性。 3*5+4的带注释的分析树 L E.val=19 E.val=15 T.val=4 T.val=15 7.1 属性文法 惟独只使用综合属性。 L E.val=19 E.val=15 T.val=4 T.val=15 F.val=4 T.val=3 F.val=3 F.val=5 digit.lexval=4 digit.lexval=5 digit.lexval=3 + * 3*5+4的带注释的分析树 新疆大学信息科学与工程学院

7.1 属性文法 一个结点的继承属性值是由此结点的父结，点和/或兄弟结点的某些属性来决定的。 继承属性L.in 生 产 式 语 义 规 则 7.1 属性文法 　　 一个结点的继承属性值是由此结点的父结，点和/或兄弟结点的某些属性来决定的。 　　继承属性L.in 生 产 式 语 义 规 则 D TL T int T real L  L1,id L id L.in:=T.type T.type=integer T.type:=real L1.in:=L.in addtype(id.entry,L.in) 新疆大学信息科学与工程学院

7.1 属性文法 . 例：Real id1,id2,id3 D L.in= real T.type=real real id2 id1 7.1 属性文法 例：Real id1,id2,id3 D L.in= real T.type=real real id2 id1 id3 . 新疆大学信息科学与工程学院

7.2 语法制导翻译概论 翻译的任务：首先是语义分析和正确性检查，若 正确，则翻译成中间代码或目标代码。 7.2 语法制导翻译概论 翻译的任务：首先是语义分析和正确性检查，若 正确，则翻译成中间代码或目标代码。 使用的方法称作语法制导翻译。基本思想是，根 据翻译的需要设置文法符号的属性，以描述语法 结构的语义。 例如，一个变量的属性有类型，层次，存储地址 等。表达式的属性有类型，值等。 属性值的计算和产生式相联系。随着语法分析的 进行，执行属性值的计算，完成语义分析和翻译 的任务。 新疆大学信息科学与工程学院

7.2 语法制导翻译概论 语法制导翻译 自顶向下 逆归子程序 LL（1） 自底向上 算符优先 LR（K） 推导的同时执行语义分析 7.2 语法制导翻译概论 推导的同时执行语义分析 语法制导翻译 自顶向下 逆归子程序 LL（1） 自底向上 算符优先 LR（K） 归约的同时执行执行语义分析 新疆大学信息科学与工程学院

7.2 语法制导翻译概论 思考： 例： G[A]：A aB ｛print “0”；｝ A C ｛print “1”；｝ 7.2 语法制导翻译概论 例： G[A]：A aB ｛print “0”；｝ A C ｛print “1”；｝ B Ab ｛print “2”；｝ 使用LR（K）找句柄规约同时语义分析 1 A C “1” 2 B Ab “12” 3 A aB “120” 4 B Ab “1202” 5 A aB “12020” 所以打印的字符串是“12020” 思考： 当输入为aacbb时打印的字符串是什么？ 新疆大学信息科学与工程学院

思考：问(a,(a,a))的值为多少？ 7.2 语法制导翻译概论 例：G[S' ]： S S {print(S.num);} 7.2 语法制导翻译概论 例：G[S' ]： S S {print(S.num);} S (L) {S.num:=L.num+1;} S a {S.num:=0;} L L,S {L.num:=L,num+S.num;} L S {L.num:=S.num} 　　思考：问(a,(a,a))的值为多少？ 新疆大学信息科学与工程学院

7.2 语法制导翻译概论 S'=>S=>(L)=>(L,S)=>(S,S)=>(a,S)=>(a,(L))=>(a,(L,S))=>(a,(S,S))=>（a,(L,S)）=>(a,(S,S))=>(a,(a,S))=>(a,(a,a)) 1.S1 <----- a S1.num=0 2.L1 <----- S1 L1.num=S1.num=0 3.S2 <----- a S2.num=0 4.L2 <----- S2 L2.num = S1.num=0 5.S3 <----- a S3.num=0 6.L <-----L,S L.num=0+0=0 7.S <----- (L) S.num=L.num+1=0+1=1 8.L <-----L,S L.num=L.num+S.num=0+1=1 9.S <----- (L) S.num=L,num+1=1+1=2 10.S'<----- S print(S.num) print 2; 新疆大学信息科学与工程学院

7.3 中间代码的生成 中间代码：是源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示 7.3 中间代码的生成 中间代码：是源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示 “中间代码生成”程 序的任务是：把经过语法分析和语义分析而获得的源程序中间表示翻译为中间代码表示。 方法：语法制导翻译。 采用独立于机器的中间代 码的好处： 1. 便于编译系统的 建立和编译系统的移植； 2. 便于进行独立于机器的代码优化工作。 中间代码的几种形式：逆波兰、三元式、间接三元式、树形、四元式 新疆大学信息科学与工程学院

7.3 中间代码的生成 小贴士：逆波兰表示要注意：算符的优先级，高到低：（），负号，乘方，*/，+-，=<> 算法： 7.3 中间代码的生成 算法： 设一个操作符栈； 当读到操作数时，立即输出该操作数； 当扫描到操作符时，与栈顶操作符比较优先级，若栈顶操作符优先级高于栈外，则输出该栈顶操作符，反之，则栈外操作符入栈。 逆波兰表示：后缀表示法，运算对象在前，运算符在后 例：x*(y+z) xyz+* (a+b)*(c+d) ab+cd+* a+b*(c+d)*(e+f) abcd+*ef+*+ 计算值时：例：(a+b)*c-d/e ab+c*de/- =>R1 c*de/- =>R2de/- =>R2R3- =>R4 Ri:代表第i次运算结果 小贴士：逆波兰表示要注意：算符的优先级，高到低：（），负号，乘方，*/，+-，=<> 新疆大学信息科学与工程学院

7.3 中间代码的生成 用栈实现：自左向右扫描，运算对象入栈，算符K目就对栈顶KJ元来操作，结果代替入栈，最后后果保留至栈顶 7.3 中间代码的生成 用栈实现：自左向右扫描，运算对象入栈，算符K目就对栈顶KJ元来操作，结果代替入栈，最后后果保留至栈顶 例: (a+b)*c-d\e ab+c*de\- b a + R1 * c R2 \ d e R2 - R3 R2 R4 新疆大学信息科学与工程学院

7.3 中间代码的生成 逆波兰表示推广 （1）赋值语句：<左P>:=<表达式> 7.3 中间代码的生成 逆波兰表示推广 （1）赋值语句：<左P>:=<表达式> <左P><表达式的递波兰式>:= 例：x:=a+b*(c-d) xabcd-*+:= （2）转向语句：goto<标号> <标号>LJ(Jump) 例：goto 100 100 LJ(Jump) 新疆大学信息科学与工程学院

7.3 中间代码的生成 （3）条件语句: if<exp> then <s1> else<s2> 7.3 中间代码的生成 （3）条件语句: if<exp> then <s1> else<s2> <exp 逆波兰式><N1>FJ<s1的递波兰式><N2>RJ<s2的递波兰式> 或:<exp 逆波兰式><s1><s2> ￥:三目运算符 if-then-else 例：if a>b then max:=a else max:=b a b> FJ max a:= RJ max b:= 11 14 新疆大学信息科学与工程学院

7.3 中间代码的生成 （4）循环语句: for i:=a to b do s 先转换为条件语句，再逆波兰表示 i:=a; 7.3 中间代码的生成 （4）循环语句: for i:=a to b do s 先转换为条件语句，再逆波兰表示 i:=a; 10 :If i<=b then Begin s; i:=i+1; Goto 10; end; 逆波兰表示：i a:=i b<=17 FJ s' ii1+:=4 RJ 新疆大学信息科学与工程学院

7.3 中间代码的生成 （4）循环语句: 例: for i:=1 to 20 do s:=s+i i:=1 7.3 中间代码的生成 （4）循环语句: 例: for i:=1 to 20 do s:=s+i i:=1 20: if i<=20 then begin s:=s+i; i:=i+1; goto 20; end; 逆波兰表示：i 1:=i 20<= FJ ssi+:= ii1+:= RJ 21 4 新疆大学信息科学与工程学院

7.3 中间代码的生成 While exp do s <exp递> <N1> FJ <s递> 1 RJ 7.3 中间代码的生成 While exp do s <exp递> <N1> FJ <s递> 1 RJ 例: while i<=100 do s:=s+i; 逆波兰表示：i100<=18 FJ ssi+:=ii1:=+1RJ （5）复合语句 简单 begin s1,s2,....sn end; Block <s1逆波兰><s2逆波兰>.........<sn逆波兰> blockend 新疆大学信息科学与工程学院

7.3 中间代码的生成 三元式(op，ARG1，ARG2) 例1：a+b*c (*，b，c) 操作符 左操作符 右操作符 (+，a，1) 7.3 中间代码的生成 三元式(op，ARG1，ARG2) 例1：a+b*c (*，b，c) (+，a，1) 三元式的推广 （1）表达式，赋值语句 例：x:=a+b*(c-d) (- ，c，d) (*，b，1) (+，a，2) (:=，3，x) 操作符 左操作符 右操作符 新疆大学信息科学与工程学院

7.3 中间代码的生成 （2）转向语句： goto L (LJ，L，1) （3）条件语句: 7.3 中间代码的生成 （2）转向语句： goto L (LJ，L，1) （3）条件语句: if a>b then max:=a else max:=b 1. (>，a，b) 2. (FJ，5，1) 3. (:=，a，max) 4. (RJ，6，1) 5. (:=，b，max) 6. (....) 新疆大学信息科学与工程学院

7.3 中间代码的生成 (4)循环: for i:=1 to 20 do s:=s+i; 7.3 中间代码的生成 (4)循环: for i:=1 to 20 do s:=s+i; 1. (:=，1，i) 5. (:=，4，s) 9. (...) 2. (<= ，i，20) 6. (+，i，1) 3. (FJ，9，2) 7. (:=，6，i) 4. (+，s，i) 8. (RJ，2，1) While i<=100 do s:=s+i; 1. (<=，i，100) 5. (+，i，1) 2. (FJ，8，1) 6. (:=，5，i) 3. (+，s，i) 7. (RJ，1，1) 4. (:=，3，5) 8. (.....) (5)复合语句 1.(block,1,1) n.(blockend,1,1) 新疆大学信息科学与工程学院

7.3 中间代码的生成 树形表示（由三元示而来 ） 树叶-------运算对象（常量/变量） 结点-------运算符 + * - 7.3 中间代码的生成 树形表示（由三元示而来 ） 树叶-------运算对象（常量/变量） 结点-------运算符 + * - T1 T2 T1 T2 T1 新疆大学信息科学与工程学院

7.3 中间代码的生成 一个三元式对应一个二叉树 （ OP， ARG1, ARG2） 子树根 子树的两棵子树（或终结符，或下代子树的根） 7.3 中间代码的生成 一个三元式对应一个二叉树 （ OP， ARG1, ARG2） 子树根 子树的两棵子树（或终结符，或下代子树的根） 例： a*b+c*d + 1. (*，a，b) * * 2. (*，c，d) a b c d 3. (+，1，2) 新疆大学信息科学与工程学院

7.3 中间代码的生成 间接三元式： 为了便于在三元式上作优化处理 使用三元式不便于代码优化，因为优化要删除一些 7.3 中间代码的生成 间接三元式： 为了便于在三元式上作优化处理 使用三元式不便于代码优化，因为优化要删除一些 三元式，或对某些三元式的位置要进行变更，由于三 元式的结果(表示为编号)，可以是某个三元式的操作 数，随着三元式位置的变更也将作相应的修改，很费 事。 三元式的执行次序用另一张表表示,这样在优化时， 三元式可以不变，而仅仅改变其执行顺序表。 新疆大学信息科学与工程学院

7.3 中间代码的生成 例： A:=B+C*D/E F:=C*D 间接三元式表示为： 操作 三元式 1. (1) (1) *, C, D 7.3 中间代码的生成 例： A:=B+C*D/E F:=C*D 间接三元式表示为： 操作 三元式 1. (1) (1) *, C, D 2. (2) (2) / , (1), E 3. (3) (3) +, B, (2) 4. (4) (4) :=, A, (3) 5. (1) (5) :=, F, (1) 6. (5) 新疆大学信息科学与工程学院

7.3 中间代码的生成 四元式（OP，ARG1，ARG2 , RESULT） 例1：a + b (+,a , b , T) 7.3 中间代码的生成 四元式（OP，ARG1，ARG2 , RESULT） 例1：a + b (+,a , b , T) -a (- , a , T1, /)单目ARG2为空 例2：a + b*c (* , b , c , T1) (+, a , T1 , T2) T1是临时变量,联系四元式 四元式的推广： （1）表达式和赋值语句 x:=a (:= , a , 1 , x) y:=(-b)*(c+d) (- , b , / ,T1) (+, c , d ,T2) (*, T1 , T2 , T3) (:= , T3 , / , y) 操作符 操作数1 操作数2 结果 写成赋值语句更直观: T1:=-b T2:=c+d T3=T1*T2 y:=T3 新疆大学信息科学与工程学院

7.3 中间代码的生成 (2)转向语句 goto L, (LJ , L , / , L) (3)条件语句 7.3 中间代码的生成 (2)转向语句 goto L, (LJ , L , / , L) (3)条件语句 If 无条件转到序号A (RJ , A , / , /) B为假转到A (FJ , A , B , /) 例：if a>b then max:=a else max:=b 1.(/, a , b , T1) 4. (RJ , 6 , / , /) 2.(FJ , 5 , T1 , /) 5. (:=, b , / , max) 3.(:= , a, /, max) 6. (.....) 新疆大学信息科学与工程学院

7.3 中间代码的生成 (4)循环语句 for i:=1 to 20 do s:=s+i while i<=100 do s:=s+i 7.3 中间代码的生成 (4)循环语句 for i:=1 to 20 do s:=s+i while i<=100 do s:=s+i 1.(:=,1,/,i) 2(<=,i,20,T1) 1.(<=,i,100,T1) 2.(FJ,8,T1,/) 3.(FJ,9,T1,/) 4.(+,s,i,T2) 3.(+,s,i,T2) 4.(:=,T2,/,s) 5.(:=,T2,/,s) 6.(+,i,1,T3) 5.(+,i,/,T3) 6.(:=,T3,/,i) 7.(:=,T3,/,i) 8.(RJ,2,/,/) 7.(RJ,/,/,/) 8.(.......) (5)复合语句 新疆大学信息科学与工程学院

8、符号表 符号表的作用和地位 符号表的主要属性及作用 符号表的组织 新疆大学信息科学与工程学院

8、符号表 教 学 目 的 了解符号表的组织 掌握符号表的作用和地位 重点掌握符号表的主要属性和作用 新疆大学信息科学与工程学院

8、符号表 重点与难点 重点是符号表的组织、符号表的管理。 难点是符号的查找。 新疆大学信息科学与工程学院

8.1 符号表的作用和地位 源程序 单词符号 语法单位 中间代码 目标代码 词法分析器 出 错 处 理 符 号 表 管 理 语法分析器 8.1 符号表的作用和地位 词法分析器 语法分析器 语义分析 代码优化 目标代码生成器 源程序 单词符号 语法单位 中间代码 目标代码 符 号 表 管 理 出 错 处 理 语义分析 新疆大学信息科学与工程学院

8.1 符号表的作用和地位 收集符号属性：在分析语言程序中标识符部分时，编译程序根据说明信息收集有关标识符的属性，并在符号表中建立相应的属性信息。 上下文语义的合法性检查的依据：同一个标识符可能在不同地方出现，而有关该符号的属性是在不同情况下收集的，特别是在多趟编译及程序分段编译的情况下，更需要检查标识符属性在上下文中的一致性和合法性。 作为目标代码生成阶段地址分配的依据：每个符号变量在目标代码生成时要确定其所在存储分配的位置。符号变量由它被定义的存储类别或被定义的位置来确定。首先要确定其被分配的区域；其次是根据变量出现的次序。 新疆大学信息科学与工程学院

8.2 符号表的主要属性及作用 符号名 符号的类型 符号的存储类别 符号的作用域及可视性 符号变量的存储分配信息 符号的其它属性 8.2 符号表的主要属性及作用 符号名 符号的类型 符号的存储类别 符号的作用域及可视性 符号变量的存储分配信息 符号的其它属性 数组内情向量 记录结构型的成员信息 函数及过程的形参 新疆大学信息科学与工程学院

8.3 符号表的组织 符号表的总体组织 按照属性种类完全相同的那些符号组织在一起。 把所有语言中的符号都组织在一张符号表里。 8.3 符号表的组织 符号表的总体组织 按照属性种类完全相同的那些符号组织在一起。 把所有语言中的符号都组织在一张符号表里。 折中方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。 新疆大学信息科学与工程学院

8.3 符号表的组织 符号表项 符号表的每个表项为一个名字的声明建立的 每个表项可以作为一条记录实现，该记录由连续的存储字序列组成 8.3 符号表的组织 符号表项 符号表的每个表项为一个名字的声明建立的 每个表项可以作为一条记录实现，该记录由连续的存储字序列组成 信息会在不同的时间放入符号表中 关键字可以在初始时全部放入表中 新疆大学信息科学与工程学院

8.3 符号表的组织 符号表项的排列 符号表作为一个多元组，表中元组的排列组织是构造符号表的重要成分。 8.3 符号表的组织 符号表项的排列 符号表作为一个多元组，表中元组的排列组织是构造符号表的重要成分。 在编译程序的整个工作过程中，符号表被频繁地用来建立表项，查找表项，填充和引用表项的属性。因此表项的排列组织对该系统运行的效率起着十分重要的作用。 在编译程序中，符号表项的组织传统上采用三种构造方法。即线性法，二分法及散列法。 新疆大学信息科学与工程学院

8.3 符号表的组织 符号表的组织方式 固定的存储单元 易于操作，浪费空间 非固定的存储单元 符号表中存储指示器指向独立的存储空间 8.3 符号表的组织 符号表的组织方式 固定的存储单元 易于操作，浪费空间 非固定的存储单元 符号表中存储指示器指向独立的存储空间 数组信息表 多个符号表 新疆大学信息科学与工程学院

8.3 符号表的组织 符号表的整理与查找 方法 线性表 二叉树 散列表 考虑的问题 填表和查表的效率和存储空间 新疆大学信息科学与工程学院

某编译器的符号表实例 local function global 编译程序分析第13行时符号表的内容 (1)class Computer { (2) int cpu; (3) void Crash(int nTimes) { (4) int i; (5) … (6) } (7)} (8) class Mac extends Computer { (9) int mouse; (10)} (11) void main() { (12) class Mac powerbook; (13) powerbook.Crash(2); (14) … (15)} top local作用域的符号表 local powerbook variable class Mac function nil global作用域的符号表 global Computer class 作用域栈 Mac class main function 略 Mac类的描述 parent Mac类成员符号表 field mouse variable int Computer类的描述 Computer类成员符号表 parent nil cpu variable int field 略 crash function 新疆大学信息科学与工程学院

9、目标程序运行时的存储组织 概述 数据空间的三种存储分配策略 参数传递 新疆大学信息科学与工程学院

教 学 目 的 9、目标程序运行时的存储组织 了解参数传递 理解数据空间的三种存储分配方法 掌握静态分配策略和动态分配策略基本思想，栈式分配的实现 新疆大学信息科学与工程学院

9、目标程序运行时的存储组织 重点与难点 重点是参数传递。 难点是嵌套过程语言的栈式实现。 新疆大学信息科学与工程学院

9.1 概述 编译程序在完成词法、语法和语义分析后，在生成目标代码之前，需要把程序的静态正文和实现这个程序的运行时的活动联系起来弄清楚将来在代码运行时刻，源代码中的各种变量、常量等用户定义的量是如何存放的，如何去访问它们。 在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。在程序语言中，程序使用的存储单元都是由标识符来表示的。它们对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。所以对于编译程序来说存储组织与管理是一个复杂而又十分重要的问题。 新疆大学信息科学与工程学院

9.1 概述 任务：编译程序对目标程序运行时的组织（设 计运行环境和分配存储）。如 通常存储区 布局可为： 9.1 概述 任务：编译程序对目标程序运行时的组织（设 计运行环境和分配存储）。如 通常存储区 布局可为： 逻辑阶段：在目标代码生成前，作准备 实质：关联（Binding） 将源程序的文本 程序运行动作的实现 源文件中的名字N  运行时的存储S 目标区 静态数据区 Stack heap 新疆大学信息科学与工程学院

9.1 概述 数据空间的分配： 将程序中的每个名字与一个存储位 置关联起来，该存储位置用以容纳名字的值。 9.1 概述 数据空间的分配： 将程序中的每个名字与一个存储位 置关联起来，该存储位置用以容纳名字的值。 静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。 动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。 表示将一个名字映 射到一个存储位置 的函数 表示存储位置到 值的映射。 name environment storage value state 新疆大学信息科学与工程学院

9.2 数据空间的三种存储分配策略 不同的编译程序关于数据空间的存储分配策略可能不同。 9.2 数据空间的三种存储分配策略 不同的编译程序关于数据空间的存储分配策略可能不同。 静态分配策略在编译是对所有对象分配固定的存储单元。且在运行是保持不变。 栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态的分配于栈顶，一旦退出，它所占空间就予以释放。 堆式动态存储策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者分给一块，凡释放者退回给堆。 新疆大学信息科学与工程学院

9.2 数据空间的三种存储分配策略 简单的栈式分配方案 程序结构特点：过程定义不嵌套，过程可递归调用，含可变数组; 例: main 9.2 数据空间的三种存储分配策略 简单的栈式分配方案 程序结构特点：过程定义不嵌套，过程可递归调用，含可变数组; 例: main 全局变量的说明 proc R …… end R; proc Q end Q; 主程序执行语句 end main 新疆大学信息科学与工程学院

9.2 数据空间的三种存储分配策略 新疆大学信息科学与工程学院

9.2 数据空间的三种存储分配策略 新疆大学信息科学与工程学院

9.3 参数传递 带有非局部变量和形参的PASCAL过程 (1)program reference(input,output); 9.3 参数传递 带有非局部变量和形参的PASCAL过程 (1)program reference(input,output); (2)var a,b:integer; (3)procedure swap({var} x,y:integer); (4) var temp:integer; (5) begin (6) temp:=x; (7) x:=y; (8) y:=temp (9) end; (10)begin (11) a:=1; b:=2; (12) swap(a,b); (13) writeln(‘a=‘,a);writeln(‘b=‘,b) (14)end. 带有过程swap的PASCAL程序 (1)procedure exchangel(i,j:integer); (2) var x:integer; (3) begin; (4) x:=a[i]; a[i]:=a[j]; a[j]:=x (5) end; 小贴士：非局变量a[i]和a[j]的值进行交换，i,j为形参（在这里是传值） 新疆大学信息科学与工程学院

9.3 参数传递 传地址（变量参数） 传值（值调用） 例如：过程 swap(var x,y:integer); 9.3 参数传递 传地址（变量参数） 例如：过程 swap(var x,y:integer); swap(a,b）；（ a,b为调用时的实参 ） 调用结果a,b的值被改变。 传值（值调用） 特点是对形式参数的任何运算不影响实参的值。 例如：过程 swap(x,y:integer); swap(a,b）；其结果： a,b调用前的值不改变。 新疆大学信息科学与工程学院

9.3 参数传递 传值的实现 形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。 调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。 被调用过程执行时，就像使用局部变量一样使用这些形式单元。 新疆大学信息科学与工程学院

9.3 参数传递 procedure swap( x,y:integer); var temp:integer; 9.3 参数传递 procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 调用swap(a,b) 过程将不会影响a和b的值。 其结果等价于执行下列运算： x :=a； y :=b； temp :=x； x :=y； y :=temp 新疆大学信息科学与工程学院

9.3 参数传递 传地址的实现 把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参： 9.3 参数传递 传地址的实现 把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参： 实在参数是一个名字，或具有左值的表达式----传递左值 实在参数是无左值的表达式----计算值，放入一存储单元，传此存储单元地址 目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用 新疆大学信息科学与工程学院

9.3 参数传递 调用swap(i,a[i]) 其结果等价于执行下列运算： 把 i和a[i]的地址分别放到x和y相应的单元a1,a2 9.3 参数传递 procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 调用swap(i,a[i]) 其结果等价于执行下列运算： 把 i和a[i]的地址分别放到x和y相应的单元a1,a2 ( temp :=x；)temp的内容置为a1所指单元中存的内容 (x :=y;) a1所指单元的内容置为a2所指单元值 ( y :=temp) a2所指单元的内容置为temp的值 新疆大学信息科学与工程学院

9.3 参数传递 (1)swap(x,y) (2)int *x,*y; (3){ int temp; 9.3 参数传递 在一个值调用过程中使用指针的C程序 在C程序中无传地址所以用指针实现。 (1)swap(x,y) (2)int *x,*y; (3){ int temp; (4) temp=*x; *x=*y; *y=temp; (5)} (6)main( ) (7){ int a=1,b=2; (8) swap(&a,&b); (9) printf(“a is now %d,b is now %d\n”,a,b); (10)} 新疆大学信息科学与工程学院

9.3 参数传递 思考： 例:对于下面程序： Procedure p (x,y,z) ; begin y:=y+1; z:=z+x; 9.3 参数传递 思考： 若参数传递的方法分别为 （1）传名 （2）传地址 （3） 传值。 执行时所输出的a分别是什么？ 例:对于下面程序： Procedure p (x,y,z) ; begin y:=y+1; z:=z+x; end; {p} a:=2; b:=3; p (a+b , a , a) print a end. 新疆大学信息科学与工程学院

9.3 参数传递 （1）参数传递方法为：传名 当执行调用p ( a+b, a ,a)时，相当于被调用者被替换成 9.3 参数传递 （1）参数传递方法为：传名 当执行调用p ( a+b, a ,a)时，相当于被调用者被替换成 procedure p (a+b , a , a) begin a:=a+1 a:=a+a+b end; {p} 调用者的数据区为： a: 2 b: 3 执行语句“a:=a+1”后，调用者数据区为： a: 3 b: 3 执行语句：a:=a+a+b 后，调用者的数据区为： a: 9 b: 3 因此程序输出为9。 新疆大学信息科学与工程学院

9.3 参数传递 （2）设参数传递方法为：传地址 将实在参数的地址，传递给调用者 p 9.3 参数传递 （2）设参数传递方法为：传地址 将实在参数的地址，传递给调用者 p 运行时有（ 假设a的地址为add_a, b的地址为add_b ); 调用者数据区 被调用者数据区 add_a: 2 x : T add_b: 3 y : add_a 临时单元T: 5 z : add_a (a + b)的值 程序运行执行了语句“y:=y+1”后，有: 调用者数据区 被调用者数据区 add_a 3 x: T add_b 3 y: add_a 临时单元T: 5 z: add_a 执行了语句“z:=z+x”后有： add_a 8 x : T add_b 3 y : add_a 临时单元T: 5 z : add_a 所以程序输出 8。 新疆大学信息科学与工程学院

9.3 参数传递 （3）参数传递方法为： 传值 将实参的值传递给被调用者 p .程序运行时有（假设a的地址为add_a, b的地址为 add_b); 调用者数据区 被调用者数据区 add_a 2 x : 5 add_b 3 y : 2 临时单元T: 5 z : 2 程序运行执行了语句“y:=y+1”后有: add_a 2 x : 5 add_b 3 y : 3 临时单元T: 5 z : 2 程序运行执行了语句“z:=z+x”后有: 调用者数据区 被调用者数据区 add_a 2 x : 5 add_b 3 y : 3 临时单元T: 5 z : 7 所以程序输出 2。 新疆大学信息科学与工程学院

10、代码优化 代码优化概述 局部优化 控制流程分析和循环优化 新疆大学信息科学与工程学院

10、代码优化 教 学 目 的 了解常用优化技术 掌握局部优化和循环优化 熟练DAG的构造与应用 新疆大学信息科学与工程学院

10、代码优化 重点与难点 重点是局部优化、控制流分析和循环优化。 难点是DAG的应用、程序流图。 新疆大学信息科学与工程学院

10.1 代码优化概述 何谓代码优化： 　　实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。 　　一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行，如图所示： 　 新疆大学信息科学与工程学院

10.1 代码优化概述 代码优化：旨在生成较好性能的目标代码，为此，编译程序需要对代码（中间代码或目标代码）进行各种方式的变换，变换的宗旨是：等价----经优化工作变换后的代码运行结果应与原来程序运行结果一样。 按阶段分类: 与机器无关的优化---对中间代码进行 依赖于机器的优化--对目标代码进行 根据优化所涉及的程序范围分成: 局部优化:(基本块) 循环优化:对循环中的代码进行优化 全局优化:大范围的优化 新疆大学信息科学与工程学院

代码优化 10.1 代码优化概述 新疆大学信息科学与工程学院 删除多余运算 循环不变代码外提 强度削弱 变换循环控制条件 合并已知量 10.1 代码优化概述 代码优化 删除多余运算 循环不变代码外提 强度削弱 变换循环控制条件 合并已知量 复写传播 删除无用赋值 新疆大学信息科学与工程学院

10.1 代码优化概述 1、删除多余运算 如果有表达式e1和e2，且它们的值始终相同，则e2的计算部分可以省略，只要用e1的值即可。 10.1 代码优化概述 1、删除多余运算 　　如果有表达式e1和e2，且它们的值始终相同，则e2的计算部分可以省略，只要用e1的值即可。 例：A:=B*D+1; E:=B*D-1; G:=B*D+2; 其中三个B*D的子表达式始终 一致，因此，可以优化为： 　T1:=B*D; A:=T1+1; E:=T1-1; G:=T1+2; 新疆大学信息科学与工程学院

10.1 代码优化概述 例： A:=B*D; B:=B*D; C:=B*D; 可优化：T1:=B*D; 10.1 代码优化概述 例： A:=B*D; 　B:=B*D; 　C:=B*D; 三个式子中的B*D形式相同，但第三个式子中的B*D与前两个式中的B*D的值不同，因此，第三个 B*D不能省。 可优化：T1:=B*D; A:=T1; B:=T1; C:=B*D; 小贴士：只有形式相同还不行，必须值也要相同，即形式相同并不能保证值相同。 新疆大学信息科学与工程学院

10.1 代码优化概述 ２、代码外提 　　减少循环中代码总数的一个重要办法是循环不变代码外提。这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面,使之只在循环外计算一次。 　　上例中，我们可以把四元式（4）和四元式（7）提到循环外。经过删除多余运算和代码外提后，代码变换成图(二)。 例：源程序： 　　 P∶=0 　　 for I∶=1 to 20 do 　　 P∶=P+A[I]*B[I]; 　　经过编译得到的中间代码如图(一)所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。那么，对于这个中间代码段，如何进行上述优化。 新疆大学信息科学与工程学院

10.1 代码优化概述 图(一) 优化的目的在于使生成的目标代码较少而执行速度较快。 10.1 代码优化概述 　　优化的目的在于使生成的目标代码较少而执行速度较快。 　　图(一)的中间代码段四元式（3）和四元式（6）都是4*I的运算，而从四元式（3）到四元式（6）没有对I赋值，显然，两次计算出的值是相等的。 　　所以四元式（6）的运算是多余的。我们可以把四元式（6）变换成：T4∶=T1。 　　这种优化称为删除多余运算或称为删除公共子表达式。 图(一) 新疆大学信息科学与工程学院

10.1 代码优化概述 图(二) 新疆大学信息科学与工程学院

10.1 代码优化概述 图（三） ３、强度削弱 强度削弱的思想是把强度大的运算换算成强度小的运算。例如把乘法运算换成加法运算等等。 10.1 代码优化概述 ３、强度削弱 　　强度削弱的思想是把强度大的运算换算成强度小的运算。例如把乘法运算换成加法运算等等。 　　在图(二)的循环中，每循环一次，I的值增加1，T1的值与I保持线性关系，每次总是增加4。因此，我们可以把循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算，而在循环中将其变换成加法运算。变换后如图(三）所示。 图（三） 新疆大学信息科学与工程学院

10.1 代码优化概述 ４、变换循环控制条件 　　 　　图（三）的代码中，I和T1始终保持T1＝4*I的线性关系，因此可以把四元式（12）的循环控制条件I≤20变换成T1≤80，这样整个程序的运行结果不变。这种变换称为变换循环控制条件。经过这一变换后，循环中I的值在循环后不会被引用，四元式（11）成为多余运算，可以从循环中删除。变换循环控制条件可以达到代码优化的目的。 新疆大学信息科学与工程学院

10.1 代码优化概述 ５、合并已知量与复写传播 　　 　　图（三）中，四元式（3）计算4*I时，I必为1。即4*I的两个运算对象都是编码时的已知量，可在编译时计算出它的值，即四元式（3）可变为T1＝4，这种变换称为合并已知量。 　　图（三）中，四元式(6)把T1的值复写到T4中，四元式（8）要引用T4的值，而从四元式（6）到四元式（8）之间未改变T4和T1的值，则将四元式（8）改为T6∶=T5[T1]，这种变换称为复写传播.复写传播之后运算结果保持不变。图（三）经过变换循环控制条件，合并已知量和复写传播等变换后，变为图（四）。 新疆大学信息科学与工程学院

10.1 代码优化概述 图（四） 新疆大学信息科学与工程学院

10.1 代码优化概述 ６、删除无用赋值 　　 　　在图（四）中，（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，则（6），（2）和（11）对程序的运行结果无任何作用。我们称之为无用赋值，无用赋值可以从程序中删除，如图（五）所示（设（6）（2）（11）为无用赋值）。 　　比较图（一）和图（五）可看出，经过优化后的代码的执行效率提高了很多。当然，实现这些优化的一系列工作是非常复杂的，代价也是很大的。 新疆大学信息科学与工程学院

10.1 代码优化概述 图（一） 图（五） 新疆大学信息科学与工程学院

10.２ 局 部 优 化 　　局部优化：是指对代码的每一个线性部分所进行的优化，使得在这个线性部分只存在一个入口和一个出口，而这个线性部分我们称之为基本块。 　　基本块：是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是该序列的第一个语句，出口就是该序列的最后一个语句。对一个基本块来说，执行时只能从其入口进入，从其出口退出。对一个给定的程序，我们可以把它划分为一系列基本块，在各个基本块范围内进行的优化称为局部优化。 新疆大学信息科学与工程学院

10.２ 局 部 优 化 基本块的划分 划分基本块的关键问题是准确定义入口和出口语句。下面我们给出划分四元式程序为基本块的算法： 10.２ 局 部 优 化 基本块的划分 　　划分基本块的关键问题是准确定义入口和出口语句。下面我们给出划分四元式程序为基本块的算法： (1) 从四元式序列确定满足以下条件的入口语句： ① 四元式序列的第一个语句； ② 能由条件转移语句或无条件转移语句转移到的语句； ③ 紧跟在条件转移语句后面的语句。 (2) 确定满足以下条件的出口语句： ① 下一个入口语句的前导语句； ② 转移语句(包括转移语句自身)； ③ 停语句(包括停语句自身)。 新疆大学信息科学与工程学院

10.２ 局 部 优 化 例如，考察下面求最大公因子的三地址代码程序： (1) read X (2) read Y (3) R=X % Y 10.２ 局 部 优 化 例如，考察下面求最大公因子的三地址代码程序： (1)  read X (2)  read Y (3)  R=X % Y (4)  if R=0 goto (8) (5)  X=Y (6)  Y=R (7)  goto (3) (8)  write Y (9)  halt 入口语句 新疆大学信息科学与工程学院

10.２ 局 部 优 化 小贴士： (1) read (C) (2) A:= 0 (3) B:= 1 (4) L1: A:=A + B 10.２ 局 部 优 化 (1) read (C) (2) A:= 0 (3) B:= 1 (4) L1: A:=A + B (5) if B>= C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9) halt 小贴士： 基本块内实行的优化：合并已知量、删除多余运算、删除无用赋值 新疆大学信息科学与工程学院

10.２ 局 部 优 化 练 习 (1) 1.read c 2.A:=0; 3.B:=1 4.A:=A+B 10.２ 局 部 优 化 1.read c 2.A:=0; 3.B:=1 4.A:=A+B 5.If B>=C goto 10 6.B:=B+1 7.Goto 4 8.A:=B+C 多余无用语句 9.B:=A+2 (死代码) 10.Write A 11.Halt 练 习 (1) 新疆大学信息科学与工程学院

10.２ 局 部 优 化 练 习 (2) a:=20 a:=20;(合并已知量) b:=a*(a+10) => b:=600; 10.２ 局 部 优 化 练 习 (2) a:=20 a:=20;(合并已知量) b:=a*(a+10) => b:=600; c:=a*b => c:=12000; 新疆大学信息科学与工程学院

(a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c) 10.２ 局 部 优 化 (a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c) 1.(*,a,b,T1) 2.(+,T1,c,T2) 3.(*,a,b,T3) 4.(-,T1,c,T4 5.(/,T2,T4,T5) 6.(*,c,b,T6) 7.(+,T6,a,T7) 8.(-,T7,d,T8) 9.(*,a,b,T9) 10.(+,T1,c,T2) 11.(/,T8,T10,T11) 12.(+,T5,T11,T12) 练 习 (3) 新疆大学信息科学与工程学院

10.２ 局 部 优 化 基本块的DAG表示 DAG(Directed Acyclic Graph)是一种有向图，常常用来对基本块进行优化。一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG： (1) 图的叶结点(无后继的结点)以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来表示一变量A的地址，则用addr(A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。 (2) 图的内部结点(有后继的结点)以一运算符作为标记，表示该结点代表应用该运算符对其直接后继结点所代表的值进行运算的结果。 (3) 图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。 新疆大学信息科学与工程学院

10.２ 局 部 优 化 一个基本块由一个四元式序列组成，且每一个四元式都可以用相应的DAG结点表示。 10.２ 局 部 优 化 一个基本块由一个四元式序列组成，且每一个四元式都可以用相应的DAG结点表示。 　　下图给出了不同四元式和与其对应的DAG结点形式。 　　图中，各结点圆圈中的ni是构造DAG过程中各结点的编号，而各结点下面的符号(运算符、标识符或常数)是各结点的标记，各结点右边的标识符是结点上的附加标识符。 　　除了对应转移语句的结点右边可附加一语句位置来指示转移目标外，其余各类结点的右边只允许附加标识符。除对应于数组元素赋值的结点(标记为[ ]=)有三个后继外，其余结点最多只有两个后继。 新疆大学信息科学与工程学院

10.２ 局 部 优 化 四元式与DAG结点 新疆大学信息科学与工程学院

10.２ 局 部 优 化 利用DAG进行基本块优化的基本思想是：首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG，然后按构造结点的次序将DAG还原成四元式序列。由于在构造DAG的同时已作了局部优化，所以最后所得到的是优化过的四元式序列。 　　我们规定：用大写字母(如A、B等)表示四元式中的变量名(或常数)；用函数Node(A)表示A在DAG中的相应结点，其值可为n或者无定义，并用n表示DAG中的一个结点值。这样，每个基本块仅含0、1、2型四元式的DAG构造算法如下(对基本块的每一个四元式依次执行该算法)： 新疆大学信息科学与工程学院

10.２ 局 部 优 化 (1) 若Node(B)无定义，则构造一标记为B的叶结点并定义Node(B)为这个结点，然后根据下列情况做不同处理： ① 若当前四元式是0型，则记Node(B)的值为n，转(4)。 ② 若当前四元式是1型，则转(2)①。 ③ 若当前四元式是2型，则： i. 如果Node(C)无定义，则构造一标记为C的叶结点，并定义Node(C)为这个结点；ii. 转(2)②。 　　 (2) ① 若Node(B)是以常数标记的叶结点，则转(2)③，否则转(3)①。 ② 若Node(B)和Node(C)都是以常数标记的叶结点，则转(2)④，否则转(3)②。 ③ 执行op B(即合并已知量)，令得到的新常数为P。若Node(B)是处理当前四元式时新建立的结点，则删除它；若Node(P)无定义，则构造一用P做标记的叶结点n并置Node(P)= n；转(4)。 新疆大学信息科学与工程学院

10.２ 局 部 优 化 ④ 执行B op C(即合并已知量)，令得到的新常数为P。若Node(B)或Node(C)是处理当前四元式时新建立的结点，则删除它；若Node(P)无定义，则构造一用P做标记的叶结点n并置Node(P)= n；转(4)。 (3) ① 检查DAG中是否有标记为op且以Node(B)为惟一后继的结点(即查找公共子表达式)。若有，则把已有的结点作为它的结点并设该结点为n；若没有，则构造一个新结点；转(4)。 ② 检查DAG中是否有标记为op且其左后继为Node(B)、右后继为Node(C)的结点(即查找公共子表达式)。若有，则把已有的结点作为它的结点并设该结点为n；若没有，则构造一个新结点；转(4)。   (4) 若Node(A)无定义，则把A附加在结点n上并令Node(A)= n；否则，先从Node(A)的附加标识符集中将A删去(注意，若Node(A)是叶结点，则不能将A删去)，然后再把A附加到新结点n上，并令Node(A)=n。 新疆大学信息科学与工程学院

10.２ 局 部 优 化 为了DAG构造算法的需要，我们将上图中的四元式按照其对应结点的后继结点个数分为四类： 10.２ 局 部 优 化 为了DAG构造算法的需要，我们将上图中的四元式按照其对应结点的后继结点个数分为四类： (1) 0型四元式：后继结点个数为0，如图5–1(1)所示； (2) 1型四元式：有一个后继结点，如图5–1(2)所示； (3) 2型四元式：有两个后继结点，如图5–1(3)、(4)、(5)所示； (4) 3型四元式：有三个后继结点，如图5–1(6)所示。 新疆大学信息科学与工程学院

10.２ 局 部 优 化 四元式序列 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r 10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r 10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r 10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r 新疆大学信息科学与工程学院

10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r 10.２ 局 部 优 化 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6 新疆大学信息科学与工程学院

10.２ 局 部 优 化 G’: 新疆大学信息科学与工程学院

10.２ 局 部 优 化 把G′和原基本块G相比，可以看出： 10.２ 局 部 优 化 　　把G′和原基本块G相比，可以看出： 　　1． G中的代码（2）和（6）的已知量都已合并。 　　2． G中（5）的无用赋值已被删除。 　　3． G中（3）和（7）的公共子表达式R+r只被计算一次，删除了多余运算。 　　 　　所以G′是G的优化结果。 新疆大学信息科学与工程学院

10.3 控制流分析和循环优化 在一个程序流程中，循环是必不可少的一种控制结构。 10.3 控制流分析和循环优化 　　在一个程序流程中，循环是必不可少的一种控制结构。 　　所谓循环，粗略地说，就是程序中那些可能反复执行的代码序列。因为循环中的代码要反复执行，因而为了提高目标代码的效率必须着重考虑循环的代码优化。 要进行循环优化。 　　首先必须找出程序中的循环，为找出程序中的循环，就需要对程序的控制流程进行分析。 新疆大学信息科学与工程学院

10.3 控制流分析和循环优化 　　在程序流图中，我们称具有下列性质的结点序列为一个循环： 　　① 它们是强连通的。也即，其中任意两个结点之间，必有一条通路，而且该通路上各结点都属于该结点序列。如果序列只包含一个结点，则必有一有向边从该结点引到其自身。 　　② 它们中间有且只有一个是入口结点。所谓入口结点，是指序列中具有下述性质的结点： 　　从序列外某结点，有一有向边引到它，或者它就是程序流图的首结点。 　　因此，我们定义的循环就是程序流图中具有唯一入口结点的强连通子图，从循环外要进入循环，必须首先经过循环的入口结点。 新疆大学信息科学与工程学院

10.3 控制流分析和循环优化 循环优化的三种重要技术： 代码外提；删除归纳变量和强度削弱。 将循环不变运算移到循环外 10.3 控制流分析和循环优化 循环优化的三种重要技术： 代码外提；删除归纳变量和强度削弱。 将循环不变运算移到循环外 例 11-2：程序优化 i = 0; while( i < 20 ) { x = 4 * i; i++; y = z * 6 + x; } (3) x := 4 * i (4) i := i + 1 (5) t1 := z *6 (6) y := t1 + x (7) goto (2) (4) x := 4 * i (5) i := i + 1 (7) goto (3) (1) i := 0 (2) t1 := z * 6 (2) if i >= 20 goto (8) (3) if i >= 20 goto (8) 新疆大学信息科学与工程学院

10.3 控制流分析和循环优化 练 习 控制流分析和循环优化 i:=1; B1 j:=10; Read k; 1: x:=k*i; 10.3 控制流分析和循环优化 控制流分析和循环优化 i:=1; B1 j:=10; Read k; 1: x:=k*i; y:=j*i; z:=x*y; B2 write j; i:=i+1; If i<100 goto 1; B3-------> halt; 练 习 新疆大学信息科学与工程学院

10.3 控制流分析和循环优化 练习：对图中的流图： 　　(1) 求出流图中各结点n的必经结点集D(n)； 　　(2) 求出流图中的回边； 　　(3) 求出流图中的循环。 　　 　　                          解答： （1） 　D(1)={1} 　D(2)={1,2} 　D(3)={1,2,3} 　D(4)={1,2,3,4} 　D(5)={1,2,3,5} 　D(6)={1,2,3,6} 　D(7)={1,2,7} 　D(8)={1,2,7,8} (2)回边 7 2 (3)循环 {2，3，4，5，6，7} 新疆大学信息科学与工程学院

谢谢大家 欢迎提问! 新疆大学信息科学与工程学院