第6章自底向上分析思想

《编译原理与技术》课程教学大纲一、课程编号：1311020二、课程名称：编译原理与技术（64学时）Compiler Principle and Technology三、课程教学目的通过本课程的学习，使学生了解并掌握程序设计语言的编译程序的设计原理与实现技术，了解编译程序的构造方法；加深学生对高级程序设计语言的理解，做到触类旁通；使学生体会到其他专业基础知识如算法与数据结构、程序设计、操作系统、形式语言与自动机、计算机组成原理、汇编语言、软件工程等综合应用，对计算机的软硬件工作原理建立比较深刻的理解，提高学生的专业素养，使学生能够利用所学的理论知识解决实际问题，培养学生分析问题、解决问题的能力。

四、课程教学基本要求1．了解编译的基本概念和步骤，编译程序的基本组成、结构、编译环境等基本概念。

2．掌握词法分析的原理、词法分析程序的设计和实现方法。

3．掌握语法分析的原理和实现技术、简单的语法分析程序的设计和实现。

4．掌握语法制导翻译技术。

5．理解利用语法制导翻译技术进行语义分析、中间代码生成的实现。

6．理解程序运行环境、代码生成相关的基本概念和实现方法。

7．了解代码优化技术的基本概念和方法。

五、教学内容及学时分配（含实验）第一章编译概述2学时1．翻译和解释2．编译的阶段3．编译程序的前后处理器（预处理器、汇编程序、连接装配程序）第二章词法分析4学时1．词法分析器的作用2．词法分析器的输入与输出3．记号的描述与识别4．词法分析程序的设计与实现5*．软件工具LEX（规格说明、工作原理）1．语法分析器的作用2．自顶向下分析（预测分析器、非递归的预测分析器）3．自底向上分析（规范归约、移进-归约方法实现）4．LR分析器（模型及工作过程、SLR(1)分析器、LR(1)分析器、LALR(1)分析器）5．LR分析方法对二义文法的应用6*．软件工具YACC （规格说明、二义性处理）第四章语法制导翻译技术8学时1．语法制导定义与翻译方案2．S属性定义的自底向上翻译3．L属性的自顶向下翻译4．L属性的自底向上翻译第五章语义分析4学时1．语义分析的概念2．符号表的组织与管理3．类型检查（类型表达式、类型等价）4．简单类型检查器的说明（语言说明、确定标识符的类型、表达式及语句的类型检查）5*．类型检查有关的其他主题（函数和运算符的重载、类型转换、多态函数）第六章运行环境6学时1．程序运行时的存储组织2．存储分配策略（静态存储分配、栈式存储分配、堆式存储分配）3．访问非局部名字4．参数传递方式第七章中间代码生成6学时1．中间代码形式2．赋值语句的翻译3．布尔表达式的翻译4．控制语句的翻译5．过程调用语句的翻译1．代码生成概述2．基本块与流图3．一个简单的代码生成程序第九章代码优化2学时1．优化概述2．基本块的优化3．循环优化教学实践：实验1．设计并实现一个C语言程序的词法分析程序4学时实验2．设计并实现一个简单赋值语句的语法分析程序12学时六、教学重点、难点重点：语法分析、语法制导翻译技术、运行环境、中间代码生成难点：语法分析、语法制导翻译技术七、先修课程：计算机导论与程序设计、算法与数据结构、形式语言与自动机、计算机组成原理八、适用专业：计算机科学与技术、网络工程九、使用教材及参考书目《编译原理与技术》李文生编著清华大学出版社 2009.1执笔人: 李文生。

《编译原理》课程教学大纲课程编号：（先不填）英文名称：Compiler Construction Principles课程类型：专业基础课学时/学分：40+16/3.5授课对象：本科生先修课程：高等数学，数据结构，C程序设计课程简介：本课程是计算机专业学生的一门重要专业基础课,本课程属于计算机科学与技术专业的一门重要的专业必修课。

通过本课程学习，使学生掌握编译程序的一般构造原理，包括语言基础知识、词法分析程序设计原理和构造方法。

各种语法分析技术和中间代码生成符号表的构造、代码优化、并行编译技术常识及运行时存储空间的组织等基本方法和主要实现技术。

它有一定的理论性,又有一定的实践性, 尤其是本课程的知识与计算机应用中很多领域有紧密联系与广泛应用。

了解与掌握本课程的基本内容将有利于学生提高专业素质和适应社会多方面需要的能力。

教学目的和要求：教学目的：培养学生掌握构造编译程序的基本原理与设计方法，为培养计算机语言与大型应用程序的开发人才打下良好的基础。

本课程坚持理论与实践教学并重的原则，理论上主要叙述语言和文法的形式定义、自动机理论、词法分析、语法和语义分析、优化和代码生成等环节的基本理论和方法，与此同时，通过上机实习构造简单语言的编译程序等编辑器使学生掌握开发应用程序的基本方法。

教学要求：通过本课程的学习, 学生应掌握形式语言理论与编译实现相关的基础概念, 了解与掌握编译程序构造的基本原理与技术, 从形式语言理论的角度, 进一步认识与理解程序设计语言及其与编译程序的联系。

做习题是理解课程中基本概念、培养思考能力和解题能力的重要方面, 要求学生认真做好习题, 并注意解题规范化。

学生也应重视配合教学, 做好上机实习。

教学内容：第1章编译程序概述（2学时）1、教学内容：1)什么是编译程序2)编译过程概述3)编译程序的结构4)编译阶段的组合5)编译技术和软件工具2、教学重点：编译程序的结构3、教学难点：编译程序的结构，以及每一阶段任务第3章文法与语言（6学时）1)文法的直观概念2)符号和符号串3)文法与语言的形式定义4)文法的分类5)上下文无关文法及其语法树6)句型的分析7)有关文法实用中的一些说明2、教学重点：与编译技术密切相关的一些术语和概念。

第六章自底向上优先分析方法•教学要求：了解简单优先分折法，掌握算符优先分析法的关系表的构造以及分析过程。

•教学重点：算符优先表构造及算符优先分析法。

1自底向上分析法的基本思想•从输入串开始，朝着文法的开始符号进行最左归约，直到到达文法的开始符号为止。

•工作方式：“移进－归约”方式。

2分析程序模型1）初态时栈内仅有栈底符“＃”，读头指针在最左单词符号上。

2）语法分析程序执行的动作：a）移进读入一个单词并压入栈内，读头后移；b）归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；c）识别成功移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；d）识别失败语法分析程序语法表a+b……#输出带#3例如：有文法如下（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d问：语句abbcde是不是该文法的合法语句？4•例：设文法G(S)：(1) S aAcBe(2) A b(3) A Ab(4) B d 试对abbcde进行“移进－归约”分析。

bbcde bbcde b cde de deabbcde eB cA a SB A a 5成功11接受2,3,4,1＃＃S 10归约＃＃aAcBe 9移进2,3,4e ＃＃aAcB 8归约e ＃＃aAc d 7移进de ＃＃aAc 6移进2,3cde ＃＃aA 5归约cde ＃＃a Ab 4移进2bcde ＃＃aA 3归约bcde ＃＃a b 2移进bbcde ＃＃a 1移进abbcde ＃＃0动作输出带输入串栈步骤移进归约的分析过程G[S]:（1）S →aAcBe（2）A →b（3）A →Ab（4）B →d 6遇到的问题：（1）如何找出进行直接归约的简单短语？（2）找出的简单短语应直接归约到哪一个非终结符？关键：确定句柄.常用的分析方法:（1）优先分析法（2）LR分析法7b db ac eSA B A d b a c e S A B A d a c eSA B a c e A B S 没有语法树如何确定句柄？86.1 自底向上优先分析法概述•基本思想：利用文法符号中相邻符号之间的优先关系（谁先规约的优先关系）找出句柄。

第6 章自底向上优先分析第1 题已知文法G[S]为：S→a|∧|(T)T→T,S|S(1) 计算G[S]的FIRSTVT 和LASTVT。

(2) 构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。

(3) 计算G[S]的优先函数。

(4) 给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。

答案：文法展开为：S→aS→∧S→(T)T→T,ST→S(1) FIRSTVT - LASTVT 表：表中无多重人口所以是算符优先（OPG）文法。

友情提示：记得增加拓广文法S`→#S#，所以# FIRSTVT(S)，LASTVT(S) #。

(3)对应的算符优先函数为：Success!对输入串（a,(a,a)）# 的算符优先分析过程为：Success!第2 题已知文法G[S]为：S→a|∧|(T)T→T,S|S(1) 给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。

(2) 将(1)和题1 中的(4)进行比较给出算符优先归约和规范归约的区别。

答案：(2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而和非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名字是什么，因此去掉了单非终结符的归约。

规范归约的可归约串是句柄，并且必须准确写出可归约串归约为哪个非终结符。

第３题：有文法G[S]：S VV T|ViTT F|T+FF )V*|((1) 给出(+(i(的规范推导。

(2) 指出句型F+Fi(的短语，句柄，素短语。

(3) G[S]是否为OPG？若是，给出(1)中句子的分析过程。

因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。

(+(i(的分析过程第４题文法G［S］为：S→S;G｜GG→G(T)｜HH→a｜(S)T→T+S｜S（１）构造G［S］的算符优先关系表，并判断G［S］是否为算符优先文法。

（２）给出句型a(T+S);H;(S)的短语、句柄、素短语和最左素短语。

供应链管理第一章1.纵向一体化：企业对于制造资源的占有要求和对生产过程直接控制的需要，传统上采用的策略是自身投资建厂，或参股到供应商企业，一个产品上所需要的各种零部件基本上都是在自己企业内由各个工厂加工出来的，直接控制着各个零部件的生产过程，这就是“纵向一体化”2.纵向一体化的缺陷：（1）增加企业投资负担：新建工厂和控股都需要筹集资金，用于项目的基本建设时间越长，企业背负的利息负担就越重。

（2）承担丧失市场时机的风险：新建项目由于有一定的建设周期，容易在这过程中丧失市场机会。

（3）迫使企业从事不擅长的业务活动：管理人员要花费过多的时间、精力和资源去从事辅助性的管理工作。

由于精力分散，他们无法做好关键性业务活动的管理工作。

（4）在每个业务领域都直接面临众多竞争对手：选择“纵向一体化”管理模式的企业必须在不同业务领域直接与不同的竞争对手进行竞争。

（5）增大企业的行业风险：不仅会在最终用户市场遭受损失，而且还会在各个纵向发展的市场上遭受损失。

3. 供应链：是指围绕核心企业，通过对物流、信息流和资金流的控制，从采购原材料开始，制成中间产品以及最终产品，最后通过销售网络把产品送到消费者手中的，将供应商、制造商、分销商、零售商直到最终用户连成一个整体的功能网链结构。

4.供应链的特征：（一）复杂性供应链会产生不同的形态结构、行为主体和控制方式。

（二）动态性供应链节点企业的信息流需要动态地更新，这就使得供应链具有明显的动态性。

（三）响应性响应性即供应链以满足用户需求为目的。

（四）交叉性节点企业可以是这个供应链的成员，同时又是另一个供应链的成员。

5.供应链管理：供应链管理就是使供应链运作达到最优化，以最少的成本，令供应链从采购开始，到满足最终顾客的所有过程，包括工作流、物流、资金流和信息流等高效率的操作，把合适的产品、以合理的价格，及时准确地送到消费者手上。

6.推动式和拉动式的供应链推动式供应链：以制造商为核心，产品生产出来以后逐级推向下游企业，分销商和零售商则处于被动接受的地位。

编译原理教案说明：一、参考书：1、陈意云、张昱：《编译原理》，高等教育出版社，2003年。

2、陈意云、张昱：《编译原理习题精选》，中国科技大学出版社，2003年。

3、吕映芝、张素琴、蒋维杜：《编译原理》，清华大学出版社，1998年第二版。

4、王生原、吕映芝、张素琴：《编译原理课程辅导》，清华大学出版社，2007年。

5、伍春香：《编译原理习题与解析》，清华大学出版社，2001年。

6、Andrew W.Appel：《现代编译原理—C语言描述》，人民邮电出版社，2005年。

7、Noam Nison等：《计算机系统要素》，电子工业出版社，2007年。

8、Randall Hyde：《编程卓越之道（第二卷）》，电子工业出版社，2007年。

二、教学目的：通过学习形式语言与自动机理论、词法分析、语法分析、语义分析、代码优化和生成等内容使学生掌握构造编译程序的基本原理和基本方法，并通过上机实习使学生进一步掌握开发应用程序的基本方法，为深入理解计算机系统、程序设计语言与开发大型应用程序打下良好的基础。

三、教学时数：课堂教学51学时，上机实验30学时。

四、授课内容：第一章编译程序概述第二章 PL/0编译程序的实现第三章文法和语言第四章词法分析第五章自顶向下语法分析方法第六章自底向上优先分析方法第七章 LR分析方法第八章语法制导翻译和中间代码生成第九章符号表第一○章目标程序运行时的存储组织第一一章代码优化第一二章代码生成第一章概述一、说明：1、教学目的与要求：了解编译程序的概念、结构以及工作流程。

2、主要内容：什么是编译程序、编译过程概述、编译程序的结构、编译阶段的组合、编译技术和软件工具以及实例分析。

3、教学重点：编译程序的结构以及每一阶段的任务。

4、教学难点：理解编译程序各模块的判错功能、编译方式和解释方式执行速度上的不同。

二、教学内容第一节编译程序1、机器语言：直接用计算机能够识别的二进制代码指令来编写程序的语言。

第6章⾃底向上优先分析法⾃底向上分析⽅法，也称移进－归约分析法，粗略地说它的实现思想是对输⼊符号串⾃左向右进⾏扫描，并将输⼊符逐个移⼊⼀个后进先出栈中，边移⼊边分析，⼀旦栈顶符号串形成某个句型的句柄时，（该句柄对应某产⽣式的右部），就⽤该产⽣式的左部⾮终结符代替相应右部的⽂法符号串，这称为归约。

重复这⼀过程直到归约到栈顶中只剩⽂法的开始符号时则为分析成功，也就确认输⼊串是⽂法的句⼦。

本章将在介绍⾃底向上分析思想基础上，着重介绍算符优先分析法。

例6.1，设⽂法G[S]为：（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d对输⼊串abbcde#进⾏分析，检查该符号串是否是G[S]的句⼦。

由于⾃底向上分析的移进－归约过程是⾃顶向下最右推导的逆过程，⽽最右推导为规范推导，⾃左向右的归约过程也称为规范归约。

容易看出对输⼊串abbcde的最右推导为：S aAcBe aAcde aAbcde abbcde由此我们可以构造它的逆过程即归约过程。

先设⼀个后进先出的符号栈，并把句⼦左括号”#”号放⼊栈底。

对上述分析过程也可看成⾃底向上构造语法树的过程，每步归约都是构造⼀棵⼦树，最后当输⼊串结束时刚好构造出整个语法树。

在上述移进－归约或⾃底向上构造语法树的过程中，考虑⼏个问题：u 何时移进？u 何时归约？u 将哪个字符串归约？当⼀个⽂法⽆⼆义性时，那么它对⼀个句⼦的规范推导是唯⼀的，规范规约也必然是唯⼀的。

因⽽每次归约时要找当前句型的句柄，也就是说，任何时候栈中的符号串和剩余的输⼊串组成⼀个句型，当句柄出现在栈顶符号串中时，则可⽤句柄归约，这样⼀直归约到输⼊串只剩结束符，⽂法符号栈中只剩开始符号。

由此可见，⾃底向上分析的关键问题是在分析过程中如何确定句柄，即如何知道何时在栈顶符号串中已形成某句型的句柄。

然⽽⾃底向上的分析算法很多，我们仅在本章和第7章介绍⽬前常⽤的算符优先分析和LR类分析法。

6.1 ⾃底向上优先分析法概述优先分析法⼜可分简单优先法和算符优先分析法。

第6章LR分析法LR（Left to Right Rightmost)分析法，是一种自底向上的分析方法，用于构建给定文法的句子的语法树。

它是由Donald Knuth于1965年首次提出，并成为编译原理课程的重要内容之一LR分析法的核心思想是将输入的符号串从左到右进行分析，并以右边界为参考点来进行规约动作。

其中，"L"表示从左到右扫描符号串，"R"表示使用逆推的方式构建语法树，"rightmost"表示将规约动作应用于右边界才开始构建语法树。

LR分析法分为两个关键步骤：构建LR分析表和执行分析过程。

首先是构建LR分析表。

我们需要构建两个表格，即项目集规范族和LR分析表。

项目集规范族是由多个项目集构成，每个项目集是一组项目的集合。

项目是文法规则的一种特殊形式，它包含文法规则的产生式以及一个“·”，表示正在扫描的位置。

LR分析表是一个二维表，行代表项目集，列代表终结符和非终结符。

表格中的每个条目包含动作和状态信息。

接下来是执行分析过程。

分析过程中需要构建一个分析栈和一个输入缓冲区。

分析栈用来保存已经处理的符号串，输入缓冲区用来保存待处理的符号串。

在分析过程中，根据当前的状态和输入符号，查找LR分析表中的相应条目来确定下一步的动作。

根据动作的类型（移进、规约或接受），对分析栈和输入缓冲区进行相应的操作。

LR分析法的优点是可以处理任意的LR文法，而不仅仅局限于SLR或LALR文法。

它能够进行自动错误恢复，并且适用于那些上下文无关文法的语法结构分析。

然而，LR分析法也存在一些缺点。

首先，构建LR分析表需要消耗大量的时间和空间。

其次，对于一些复杂的文法，可能会出现冲突（reduce-reduce或shift-reduce冲突），需要通过手动修改文法来解决冲突。

总而言之，LR分析法是一种强大的自底向上的分析方法，能够处理广泛的文法，并提供自动错误恢复的功能。