计算机编译原理.ppt

《计算机编译原理.ppt》由会员分享，可在线阅读，更多相关《计算机编译原理.ppt（53页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、计算机编译原理,王海文 2005,本书结构,第一章 语言程序概述第二章 文法与语言第三章 词法分析第四章 语法分析第五章 编译程序的数据结构和符号表第六章 语法制导翻译第七章 编译程序,课程要求,基础理论：熟悉基于形式语言理论的编译程序构造原理和高级语言的实现原理。基础知识：全面掌握词法分析、语法分析和语法制导翻译方法等计算机处理技术，了解高级语言中各种语言成分的实现方法。基本技能：掌握计算机语言处理系统中各种通用的分析和翻译技术，以及自动生成系统的运用。,本课程的目的,构造编译器基本知识编译的阶段和相关的活动相关数据结构和算法计算机科学中相关的基础理论形式语言与自动机进一步加深对软件开发的

2、认识,第一章 概述,【课前思考】 什么是编译程序？ 编译过程和编译程序的结构？【学习目标】介绍语言翻译的基本概念程序和语言翻译和解释介绍翻译的步骤和相关的活动介绍编译器的开发方法,知 识 结 构,课前说明,基于形式语言理论中的有关概念来讨论编译实现问题。即 编译原理=形式语言理论+编译技术本书主要内容涉及：高级程序设计语言形式语言理论的基本概念构造编译程序的基本概念、原理和技术,基本观念程序、语言,计算机、程序、语言计算机接受指令，然后执行指令指令组成的序列，称为程序符合一定规则（文法）的程序的集合，称为语言语法（形式）语义（意义） /形式与意义之间的对应关系？讨论：C语言与C语言程序之间的关

3、系,基本观念语言与程序,语言的作用设计程序(选出特定的程序构造程序)程序的作用由计算机执行在人之间的交流想法，由于程序没有歧义如何定义语言本课程要学习的内容以有限的规则，定义无限多的程序 。,基本观念语言的多样性,语言的多样性方便在特定领域的应用交流障碍解决方案统一语言，一个梦想没有个性的语言语言的不断发展翻译,基本观念语言之间的翻译,对翻译的要求保持程序的意义，即功能不变。翻译的可能性Church猜想与通用计算机（语言的等价性）+、-、JNZ翻译的策略软件开发过程的策略编译（整体翻译）解释（逐句的翻译、执行）,程序的执行方式,高级语言程序通常采用两种方式执行：解释方式和翻译方式解释方式：逐个

4、语句地分析和执行，如Basic，Prolog优点：易于查错缺点：效率低，运行速度慢翻译方式：对整个程序进行分析，翻译成等价机器语言程序后执行，如Pascal，Fortran，C优点：只需分析和翻译一次，缺点：在运行中发现的错误必须在源程序中查找,什么是编译程序？,定义：是一种语言转换系统,C+编译器,C+,C,Java,Bytecode,Java编译器,编译程序,运行系统,目标程序,输入数据,计算结果,源程序,需预处理的源程序,预处理程序,源程序,编译程序,汇编程序,装配/连接编辑程序,目标汇编程序,可再装配的机器代码,绝对机器代码,可再装配目标文件,高级语言程序的处理过程,编译程序的功能,从

5、功能上看，一个编译程序就是一个语言翻译程序。源语言通常是一个高级语言，如FORTRAN，C 或Pascal。目标语言通常是一个低级语言,如汇编或机器语言。,编译程序,源语言程序,目标语言程序,出错和警告信息,T形图,常用T形图来表示编译程序涉及的三个语言：,其中：S:源语言(程序)，Source language(program)O:目标语言(程序), target/object language(program)I:实现语言, implementation language,编译程序在计算机系统中的作用,编译系统是一种软件，一种系统软件。软件：计算机系统中的程序及其文档。系统软件：居于计算机

6、系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。和具体的应用领域无关，如编译系统和操作系统等。语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序，如编译系统。,裸机,操作系统,语言处理系统,应用软件层,编译程序的组成结构,semantics,parser,scanner,optimizer,code generator,program,前端front end与源语言有关,middle end,后端back end与目标机相关,编译程序的结构,翻译外文资料与编译源程序进行类比,翻译之前的准备,必须了解的源语言（翻译谁输入）目标语言（翻译成谁输出）翻译方法（如何实现翻译

7、）如何定义源语言和目标语言程序的基本组成是字符，程序是一个字符串由字符组成程序的方法,先定义接口，然后再实现,(1) 词法分析(Lexical analysis),词法分析程序又称扫描程序。是编译过程的第一个阶段，其任务是：读源程序的字符流、识别单词（如标识符、整数、界限符等），并转换成内部形式。输入字符串（即源程序）输出单词符号（最基本的语法单位） 。,词法分析举例,一个C源程序片段：int a;a=a+2;词法分析后返回(如右图)：,单词类型 单词值保留字 int标识符 a界符 ;标识符 a算符(赋值) =标识符 a算符(加) +整数 2界符 ；,(2) 语法分析（Syntax analy

8、sis）,语法分析语法定义如何由单词符号组成更大的语法单位输入单词符号输出语法单位及其之间的关系，通常是语法树表达语法规则的主要工具为上下文无关文法,id1:=id2+id3*10 的语法树,id1:=id2+id3*10的语法树的另一种形式,(3) 语义分析(Semantic analysis)和中间代码生成,语义分析和中间代码生成分析（检查和计算）程序中各个语法单位的语义，翻译为中间代码形式。输入语法单位及其之间的关系（语法树）输出中间代码表达语义规则的主要工具是属性文法表达中间代码的主要工具是四元式主要使用语法制导的翻译方法,语义分析举例,错在哪里？例1： int arr2, c; c

9、= arr1 * 10;,插入语义处理结点的语法树,例子1,C语言的源程序a = b*c + b*d 的四元式序列（赋值语句形式的四元式）： (1) t1 = b*c (2) t2 = b*d (3) t3 = t1 + t2 (4) a = t3,例子2,源程序： if (ab If t1 goto l t2=a-c a=t2 l: t3=b*c c=t3,翻译成,(4) 代码优化,优化（在理论上不是必须的）输入中间代码输出优化后的中间代码对中间代码进行处理，期望得到高效的代码删除无用代码减少冗余目前不要对优化寄予过高的期望现在不能优化算法将来也许能在一定范围内自动选择算法或重构,(5) 目

10、标代码生成,目标代码生成输入中间代码输出目标代码涉及的知识包括目标机器指令的选取、寄存器的分配、运行时存储空间组织等可以根据目标机的模型，对目标代码进一步进行优化,符号表管理,记录源程序中使用的名字(标识符)收集每个名字的各种属性信息类型、作用域、分配存储信息,出错处理,检查错误、报告出错信息、排错、恢复编译工作词法错误和语法错误可由编译程序在编译时刻查出。语义错误常采用下列方式查出：静态模拟检查：动态调试检查：,编译程序的结构,词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错管理程序,编译程序的结构框图,编译的各个阶段,概念：趟（遍）,一个编

11、译程序的工作分成若干个阶段来完成。每个阶段读入整个输入并进行处理的过程称为趟（或遍，pass）。一个编译系统可以看成是一个变换系统进行一系列的变换，即 (SL,L1),(L1,L2),.(Lk,TL) 其中SL为源语言，TL为目标语言几趟编译程序：,编译原理课程的学习内容,程序设计语言之间的翻译方法翻译的必要性和可能性定义语言的方法翻译的活动、步骤及相关数据结构、算法和理论词法分析（重点）语法分析（重点）语义分析和中间代码生成（重点）优化和目标代码生成,编译技术的发展,第一个编译程序出现在20世纪50年代早期，多是将算术公式翻译成机器代码20世纪50年代末，提出并研制编译程序的编译程序，20世

12、纪60年代起，出现自展技术（用被编译的语言来书写该语言自身的编译程序）。,编译实现方式的发展,手工机器语言汇编语言系统程序设计语言自动构造工具lex yacc,编译技术的应用,语言的结构化编辑器语言程序的调试工具预处理程序高级语言之间的转换工具,研究领域,并行编译技术：交叉编译技术：如嵌入式应用硬件描述语言及其编译技术：如芯片设计,交叉编译,交叉编译程序产生不同于宿主机的机器代码的编译器可变目标编译器前端与目标机无关的编译器A(L)=A 求生成B(L)=B的方法构造C = L(L)=B对C = L(L)=B, 用A(L)=A，得到C = A(L)=B, 对C = L(L)=B, 用A(L)=B

13、，得到C = B(L)=B,本章小结,高级程序设计语言通常有解释和翻译两种执行方式。从功能上说,编译程序是一个翻译程序,将高级语言的程序翻译成低级语言的程序。一个编译过程可划分成词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成六个阶段。编译技术会应用在很多领域。,相关概念,源语言目标语言源程序目标程序运行子程序趟,参考书（1）,Tomas Pittmn, The art of Compiler Design theory and Practice, Prentice-Hall 1992Charles N. Fischer, Richard J. Leblanc, Crafti

14、ng A Compiler, The Benjamin/Cummings Publishing Company 1988ALFRED V. AHO, RAVISETHI, JEFFREY D. ULLMAN, Compilers Principles, Techniques and Tools ADDISSON-WESLEY 1986,参考书（2）,Terrence W.Pratt,Marvin V.Zelkowitz Programming Languages Design and Implementation, Prentice-Hall 1996Bennett, J.P.,Introdu

15、ction to Compiling techniques: a first course using ANSI C,LEX and YACC.-2nd ed- , The McGRAW-HILL Publishing Company 1996David A. Watt, Programming Language Syntax and Semantics,Prentice Hall 1991Modern Compiler Design, 现代编译程序设计，人民邮电出版社,多级化和多元化的嵌入式系统的发展为我国自主版权的嵌入式软件开发带来机遇昂贵的国外开发软件给我国造成了巨大经济损失国外开发环境

16、产品与国产OS的无缝连接水平有限,制约了我国新一代智能化数字产品的发展嵌入式软件开发环境的市场增长迅速,嵌入式系统的研究意义及其现状,国际市场上已经出现了以VRTX、VxWorks、pSOS和Windows CE为代表的近40个嵌入式操作系统家族，支持不同处理器的200多个产品.应用开发平台虽然可支持多种处理器但不能支持我国自行研制的新型处理器，另外，这类产品中存在着各种问题，如将不需要的库函数链接到了嵌入式应用程序中，优化后的代码调试时调试器往往出现各种错误.目前国外研究方向主要有以下几个方面：提高嵌入式系统的实时性；编译优化；支持面向对象的网络语言的编译和调试工具。, 国内有多家企业和学校研究嵌入式操作系统. 在嵌入式软件开发环境研究方面有清华计算机系为台湾金远见公司开发的WBASIC交叉编译系统。 国内使用的嵌入式软件开发环境，几乎全是国外引进，自主开发成果极少。 可扩展的嵌入式软件开发环境所涉及的关键技术是多目标交叉编译和交叉调试，国内目前在这些方面没有什么突破。,电子答疑,E-mail: Tel: 82022966（灵）如有什么建议和问题，课后可E-mail或电话联系。,Thanks!,