第6章自底向上分析思想
- 格式:ppt
- 大小:2.94 MB
- 文档页数:34
《编译原理与技术》课程教学大纲一、课程编号: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)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串,而和非终结符无关,只需知道把当前可归约串归约为某一个非终结符,不必知道该非终结符的名字是什么,因此去掉了单非终结符的归约。
规范归约的可归约串是句柄,并且必须准确写出可归约串归约为哪个非终结符。
第3题:有文法G[S]:S VV T|ViTT F|T+FF )V*|((1) 给出(+(i(的规范推导。
(2) 指出句型F+Fi(的短语,句柄,素短语。
(3) G[S]是否为OPG?若是,给出(1)中句子的分析过程。
因为该文法是OP,同时任意两个终结符的优先关系唯一,所以该文法为OPG。
(+(i(的分析过程第4题文法G[S]为:S→S;G|GG→G(T)|HH→a|(S)T→T+S|S(1)构造G[S]的算符优先关系表,并判断G[S]是否为算符优先文法。
(2)给出句型a(T+S);H;(S)的短语、句柄、素短语和最左素短语。
供应链管理第一章1.纵向一体化:企业对于制造资源的占有要求和对生产过程直接控制的需要,传统上采用的策略是自身投资建厂,或参股到供应商企业,一个产品上所需要的各种零部件基本上都是在自己企业内由各个工厂加工出来的,直接控制着各个零部件的生产过程,这就是“纵向一体化”2.纵向一体化的缺陷:(1)增加企业投资负担:新建工厂和控股都需要筹集资金,用于项目的基本建设时间越长,企业背负的利息负担就越重。
(2)承担丧失市场时机的风险:新建项目由于有一定的建设周期,容易在这过程中丧失市场机会。
(3)迫使企业从事不擅长的业务活动:管理人员要花费过多的时间、精力和资源去从事辅助性的管理工作。
由于精力分散,他们无法做好关键性业务活动的管理工作。
(4)在每个业务领域都直接面临众多竞争对手:选择“纵向一体化”管理模式的企业必须在不同业务领域直接与不同的竞争对手进行竞争。
(5)增大企业的行业风险:不仅会在最终用户市场遭受损失,而且还会在各个纵向发展的市场上遭受损失。
3. 供应链:是指围绕核心企业,通过对物流、信息流和资金流的控制,从采购原材料开始,制成中间产品以及最终产品,最后通过销售网络把产品送到消费者手中的,将供应商、制造商、分销商、零售商直到最终用户连成一个整体的功能网链结构。
4.供应链的特征:(一)复杂性供应链会产生不同的形态结构、行为主体和控制方式。
(二)动态性供应链节点企业的信息流需要动态地更新,这就使得供应链具有明显的动态性。
(三)响应性响应性即供应链以满足用户需求为目的。
(四)交叉性节点企业可以是这个供应链的成员,同时又是另一个供应链的成员。
5.供应链管理:供应链管理就是使供应链运作达到最优化,以最少的成本,令供应链从采购开始,到满足最终顾客的所有过程,包括工作流、物流、资金流和信息流等高效率的操作,把合适的产品、以合理的价格,及时准确地送到消费者手上。
6.推动式和拉动式的供应链推动式供应链:以制造商为核心,产品生产出来以后逐级推向下游企业,分销商和零售商则处于被动接受的地位。